FreePOOMA  2.4.1
Public Types | Public Member Functions
DomainMap< Dom, T > Class Template Reference

DomainMap<Domain,Data> is templated on the type of domains it is storing, and the Data type it stores for each Domain. More...

#include <DomainMap.h>

Inheritance diagram for DomainMap< Dom, T >:
Inheritance graph
[legend]

List of all members.

Public Types

typedef Dom Domain_t
typedef Dom key_type
typedef T Data_t
typedef T mapped_type
typedef std::pair< Domain_t,
Data_t
Value_t
typedef std::pair< Domain_t,
Data_t
value_type
typedef DomainMapIterator
< Domain_t, Data_t
iterator
typedef DomainMapConstIterator
< Domain_t, Data_t
const_iterator
typedef DomainMapTouchIterator
< Domain_t, Data_t
touch_iterator
typedef std::pair
< touch_iterator,
touch_iterator
Touch_t
typedef std::pair
< touch_iterator,
touch_iterator
touch_type
typedef long Size_t
typedef long size_type

Public Member Functions

 DomainMap ()
 DomainMap (const Domain_t &d)
void initialize (const Domain_t &d)
 ~DomainMap ()
iterator begin ()
iterator end ()
const_iterator begin () const
const_iterator end () const
Size_t size () const
Touch_t touch (const Domain_t &d) const
void insert (const Value_t &v)
void update ()
void clear ()
void zap ()
template<class Out >
void print (Out &o) const
 output a DomainMap to an output stream, by doing a touches operation on the entire global domain.
void print () const

Detailed Description

template<class Dom, class T>
class DomainMap< Dom, T >

DomainMap<Domain,Data> is templated on the type of domains it is storing, and the Data type it stores for each Domain.

The purpose of DomainMap is to store a set of N domains in a way that is very fast for 'touches' operations. This operation is done when you want to find out which subdomains in a list happen to touch a given domain. This domain is typically the extent for an expression, but it could be anything.

DomainMap maintains a binary tree of domains, where each node in the tree is of type 'DomainMapNode' and stores the following information:

  1. The domain for that node. This is a section of the total domain, which is obtained by splitting the domain of the parent node. The root node has a domain equal to the total domain. Under this are two nodes with the parent domain split in two, and so on.
  2. A list of domains which are part of that node. When a subdomain is inserted into the DomainMap, it is inserted into the root node, which checks to see if the subdomain is contained by the left or right split domains. If it is, the subdomain is inserted in the left or right. But if it spans both left and right, it is inserted in the current node's list.

A DomainMap is constructed either with a default constructor, or with a global domain which should represent the "bounding box" of the DomainMap. Subsequent insertions of subdomains into the DomainMap should be for subdomains contained within the bounding box domain. DomainMap keeps the root node for its tree of DomainMapNode's, and a count of how many domains have been inserted. If the default constructor is used, the 'initialize(domain)' method must be called before the DomainMap can be used in any other way.

For each subdomain inserted into the DomainMap, there is a data element of type 'Data', where Data is the second template parameter for DomainMap. For example, for Layout objects, Data is an int that stores the context number. The elements stored in the lists in each DomainMapNode are actually of type pair<Domain,Data>; this typedef'd to DomainMap<Domain,Data>::Value_t and it is elements of type Value_t which are inserted: DomainMap<...> dmap; dmap.insert(DomainMap<...>::Value_t(domain, context));

After a number of elements have been inserted, the user should call DomainMap.update(), which resets an internal pointer in DomainMap to point to the leftmost node. If update() is not called after an insertion, then the 'touch' method will not function properly. However, you can peform multiple insert() operations between calls to update without a problem. The typical method is to create a DomainMap, insert all the subdomains in some kind of loop, and then call update() after everything has been inserted. update() can be called any number of times. DomainMap could have done an implicit call to update() at the end of each insert(), but this is inefficient and in most cases unnecessary.

The elements of DomainMap can be iterated over, using begin() and end() methods. DomainMap has a size() method as well. The iterators are of type DomainMap::iterator and DomainMap::const_iterator. These iterators have forward-iterator semantics only; dereferencing an iterator returns an item of type DomainMap::Value_t, which is a pair<Domain,Data>. Elements will be iterated over from "left node" to "right node". The DomainMapIterator and DomainMapConstIterator classes are used to implement these iterators.

Finally, the key use of DomainMap is to perform a 'touch' operation. The touch(domain) method returns a pair of iterators, as pair<DomainMap::touch_iterator,DomainMap::touch_iterator> which is typedef'd as DomainMap::Touch_t. This pair of iterators is a begin/end pair which can be used to iterate through all subdomains which touch the domain given to the 'touch' method. touch_iterator has forward-iterator semantics, and dereferencing returns a Value_t pair.


Member Typedef Documentation

template<class Dom, class T>
typedef Dom DomainMap< Dom, T >::Domain_t
template<class Dom, class T>
typedef Dom DomainMap< Dom, T >::key_type
template<class Dom, class T>
typedef T DomainMap< Dom, T >::Data_t
template<class Dom, class T>
typedef T DomainMap< Dom, T >::mapped_type
template<class Dom, class T>
typedef std::pair<Domain_t,Data_t> DomainMap< Dom, T >::Value_t
template<class Dom, class T>
typedef std::pair<Domain_t,Data_t> DomainMap< Dom, T >::value_type
template<class Dom, class T>
typedef DomainMapIterator<Domain_t,Data_t> DomainMap< Dom, T >::iterator
template<class Dom, class T>
typedef DomainMapConstIterator<Domain_t,Data_t> DomainMap< Dom, T >::const_iterator
template<class Dom, class T>
typedef DomainMapTouchIterator<Domain_t,Data_t> DomainMap< Dom, T >::touch_iterator
template<class Dom, class T>
typedef std::pair<touch_iterator,touch_iterator> DomainMap< Dom, T >::Touch_t
template<class Dom, class T>
typedef std::pair<touch_iterator,touch_iterator> DomainMap< Dom, T >::touch_type
template<class Dom, class T>
typedef long DomainMap< Dom, T >::Size_t
template<class Dom, class T>
typedef long DomainMap< Dom, T >::size_type

Constructor & Destructor Documentation

template<class Dom, class T>
DomainMap< Dom, T >::DomainMap ( ) [inline]
template<class Dom, class T>
DomainMap< Dom, T >::DomainMap ( const Domain_t d) [inline]
template<class Dom, class T>
DomainMap< Dom, T >::~DomainMap ( ) [inline]

Member Function Documentation

template<class Dom, class T>
void DomainMap< Dom, T >::initialize ( const Domain_t d) [inline]
template<class Dom, class T>
iterator DomainMap< Dom, T >::begin ( ) [inline]
template<class Dom, class T>
iterator DomainMap< Dom, T >::end ( ) [inline]
template<class Dom, class T>
const_iterator DomainMap< Dom, T >::begin ( ) const [inline]
template<class Dom, class T>
const_iterator DomainMap< Dom, T >::end ( ) const [inline]
template<class Dom, class T>
Size_t DomainMap< Dom, T >::size ( ) const [inline]
template<class Dom, class T>
Touch_t DomainMap< Dom, T >::touch ( const Domain_t d) const [inline]
template<class Dom, class T>
void DomainMap< Dom, T >::insert ( const Value_t v) [inline]
template<class Dom, class T>
void DomainMap< Dom, T >::update ( ) [inline]
template<class Dom, class T>
void DomainMap< Dom, T >::clear ( ) [inline]
template<class Dom, class T>
void DomainMap< Dom, T >::zap ( ) [inline]
template<class Dom , class T >
template<class Out >
void DomainMap< Dom, T >::print ( Out &  o) const

output a DomainMap to an output stream, by doing a touches operation on the entire global domain.

template<class Dom , class T >
void DomainMap< Dom, T >::print ( ) const

The documentation for this class was generated from the following file: