5.3. Domains

A domain specifies the set of points on which an array can define values. These indices are the arguments placed within parentheses to select particular values, as described previously. A domain supported both by Arrays and by built-in C++ arrays is the interval [0,n-1] of integers containing all integers {0, 1, 2, …, n-1}. For C++, every integer in the interval must be included, and the minimum index must be zero. POOMA expands the set of permissible domains to support intervals with nonzero minimal indices, nonzero strides, and other options.

In POOMA, Domain classes implement domains. There are four different categories:

Loc

Domain with a single point.

Interval

Domain with an integral interval [a,b].

Range

Domain with an integral interval [a,b] and an integral stride s indicating the gap between indices: {a, a+s, a+2s, …, b}.

Grid

Domain with an ascending or descending sequence of integral values. The sequence elements must be individually specified.

One-dimensional and multidimensional versions of the categories are supported. A multidimensional Domain consists of the direct product of one-dimensional Domains. For example, the first dimension of a two-dimensional interval [0,3]x[2,9] is the interval [0,3], and its second dimension is the interval [2,9]. Its indices are ordered pairs such as (0,2), (0,3), (1,2), (1,9), and (3,7).

Many domains can be represented using domain triplets. That is, a domain triplet [begin:end:stride] represents the mathematical set {begin, begin + stride, begin + 2stride, …, end}, where end is in the set only if it equals begin plus some integral multiple of stride. If the stride is negative, its beginning index begin should at least be as large as end if the interval is to be nonempty. The stride can be zero only if begin and end are equal. There are lots of ways to represent an empty interval, e.g., [1:0:1] and [23,34,-1], and POOMA will accept them, but they are all equivalent. The domain triplet notation is easily extended to multiple dimensions by separating different dimension's intervals with commas. For example, [2:4:2,6:4:-2] contains (2,6), (2,4), (4,6), and (4,4).

All the Domain categories listed above except Grid can be represented using domain triplet notation. Since the triplet [7:7:1] represents {7}, or more simply 7, it can also represent the one-dimensional Loc<1>(7). Multidimensional Locs are similarly represented. For example, [0:0:1,10:10:1,2:2:1] represents Loc<3>(0,10,2), but it is frequently abbreviated as [0,10,2]. An Interval [a,b] has unit stride: [a:b:1], while a Range has specific stride s, e.g., [a:b:s].

Domains can be constructed by combining Domains with smaller dimension. For example, since a two-dimensional Interval is the direct product of two one-dimensional Intervals, it can be specified using two one-dimensional Intervals. For example, Interval<2>(Interval<1>(2,3), Interval<1>(4,5)) creates a [2:3:1,4:5:1] Domain. The resulting dimensionality equals the sum of the components' dimensions. For example, a four-dimension Loc can be specified using three- and one-dimension Locs or using four one-dimension Locs. If fewer dimensions than the created object's dimensionality, the last dimensions are unspecified and uninitialized. Locs, Intervals, Ranges, and Grids can all be composed from smaller similar components.

A Domain can be composed from smaller components with different types. A Loc object can be constructed from other Loc objects and integers. Intervals, Ranges, and Grids can be constructed using any of these types, Locs, and integers. For example, Interval<3> a(Loc<2>(1,2), Interval<1>(3,5)) uses a two-dimensional Loc and a one-dimensional Interval to create a [1:1:1,2:2:1,3:5:1] Domain. During creation of a Domain, the type of each object is changed to the Domain's type. In the example, Loc<2>(1,2) is first converted to an Interval.

Domains can participate in some arithmetic and comparison operations. For example, a Domain's triplet can be shifted two units to the right by adding two. Multiplying a Domain by two multiplies its triplet's beginnings, endings, and strides by two. POOMA users rarely need to compare Domains, but we describe operating with the less-than operator on Intervals: Interval d1 < Interval d2 if the length of d1's interval is less than d2's or, if equal, its beginning value is smaller. Domain arithmetic is frequently used with data-parallel statements and container views. These will be discussed in Chapter 7 and Chapter 8.

The current POOMA implementation supports Domains with dimensionality between one and seven, inclusive. Since most scientific computations use one, two, or three dimensions, this is usually sufficient. If more dimensions than seven are needed, they can be added to the source code.

5.3.1. Declaring Domains

Since Domains are mainly used to declare container domains, we focus on declaring Domains, deferring most discussion of their use. We subsequently describe a few Domain operations but most, including arithmetic operations with Domains, are described in Chapter 8.

All Domain declarations require a dimension template parameter D. This positive integer specifies the number of dimensions, i.e., rank, of the Domain and determines the length of the tuples for points in the Domain. For example, a three-dimensional Domain contains ordered triples, while a one-dimensional Domain contains singletons, or just integers. Multidimensional Domains are just the direct products of one-dimensional Domains so the techniques for declaring one-dimensional Domains carry over to multidimensional ones.

To declare a Domain, one must include the Pooma/Domains.h header file. However, most POOMA programs use Domains when constructing containers. The storage container header files automatically include Pooma/Domains.h so no explicit inclusion is usually necessary.

5.3.1.1. Locs

A Loc<D> is a Domain with just a single D-dimensional point. Although it is infrequently used as a container's domain, it is used to refer to a single point within another domain. Its beginning and ending points are the same, and its stride is one. One-dimensional Locs and integers are frequently interchanged.

Table 5-1. Declaring One-Dimensional Locs

constructorresult
Loc<1>()indicates zero.
Loc<1>(const Pooma::NoInit& no)creates an uninitialized Loc<1>, to be assigned a value later.
Loc<1>(const DT1& t1)creates a Loc<1> with the integer converted from t1.
Loc<1>(const DT1& t1, const DT2& t2)creates a Loc<1> with the integer converted from t1. t2 must equal t1.
Loc<1>(const DT1& t1, const DT2& t2, const DT3& t3)creates a Loc<1> with the integer converted from t1. t2 must equal t1, and t3 is ignored.
DT1, DT2, and DT3 are template parameters. 

Constructors for one-dimensional Locs appear in Table 5-1. The empty constructor yields the zero point. The constructor taking a Pooma::Init object does not initialize the resulting Loc to any particular value. Presumably, the value will be assigned later. For small Domains such as Locs, the time savings from not initializing is small, but the functionality is still available. The constructor taking one argument with type DT1 converts this argument to an integer to specify the point. The template type DT1 may be any type that can be converted to an integer, e.g., bool, char, int, or double. The constructors taking two and three arguments of templatized types facilitate converting an Interval<1> and a Range<1> into a Loc<1>. Since a Loc represents a single point, the Interval's or Range's first two arguments must be equal. The stride is ignored. Again, the templatized types may be any type that can be converted into an integer.

Table 5-2. Declaring Multidimensional Locs

constructorresult
Loc<D>()indicates zero.
Loc<D>(const Pooma::NoInit& no)creates an uninitialized Loc, to be assigned a value later.
Loc<D>(const DT1& t1)creates a Loc using the given Domain object.
Loc<D>(const DT1& t1, const DT2& t2)creates a Loc using the given Domain objects.
Loc<D>(const DT1& t1, const DT2& t2, const DT3& t3)creates a Loc using the given Domain objects.
Loc<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4)creates a Loc using the given Domain objects.
Loc<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5)creates a Loc using the given Domain objects.
Loc<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5, const DT6& t6)creates a Loc using the given Domain objects.
Loc<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5, const DT6& t6, const DT7& t7)creates a Loc using the given Domain objects.
D indicates the Loc's dimension. DT1, DT2, … are template parameters. 

Constructors for multidimensional Locs appear in Table 5-2. D indicates the Loc's dimension. The first two constructors are similar to Loc<1>'s first two constructors, returning a representation of the zero point and returning an uninitialized point. The seven other constructors create a Loc using other Domain objects. These Domain objects, having types DT1, …, DT7, can have any type that can be converted into an integer, to a Loc<1>, or to a multidimensional Domain object that itself can be converted into a Loc. The total dimensionality of all the arguments' types should be at most D. For example, Loc<5>(Range<1>(2,2,2), Loc<2>(2,3), Interval<1>(4,4)) creates a five-dimensional Loc [2,2,3,4,1] using a one-dimensional Range, a two-dimensional Loc, and a one-dimensional Interval. The final fifth dimension has an unspecified value, in this case 1. The one-dimensional Range is converted into the single integer two; its beginning and ending points must be the same. The two-dimensional Loc contributes values for the next two dimensions, while the Interval contributes its beginning point, which must be the same as its ending point. Note that the Loc<1> constructors taking two and three parameters ignore their second and third arguments, but this is not true for the multidimensional constructors.

5.3.1.2. Intervals

A one-dimensional Interval represents a set of integers within a mathematical interval. Multidimensional Intervals represent their multidimensional generalization, i.e., the direct product of one-dimensional intervals. Intervals are arguably the most commonly used POOMA Domain. A one-dimensional Interval has integral beginning and ending points and a unit stride.

Table 5-3. Declaring One-Dimensional Intervals

constructorresult
Interval<1>()creates an empty, uninitialized interval.
Interval<1>(const Pooma::NoInit& no)creates an uninitialized Interval<1>, to be assigned a value later.
Interval<1>(const DT1& t1)creates an Interval<1>. See the text for an explanation.
Interval<1>(const DT1& t1, const DT2& t2)creates an Interval<1> with the integers converted from t1 and t2.
Interval<1>(const DT1& t1, const DT2& t2, const DT3& t3)creates an Interval<1> with the integers converted from t1 and t2. t3 must equal 1.
DT1, DT2, and DT3 are template parameters. 

Interval<1> constructors are patterned on Loc<1> constructors except that Interval<1>s can have differing beginning and ending points. See Table 5-3. The default constructor creates an empty, uninitialized interval, which should not be used before assigning it values. If the one-parameter constructor's argument is a Domain object, it must be a one-dimensional Domain object which is converted into an Interval if possible; for example, it must have unit stride. If the one-parameter constructor's argument is not a Domain object, it must be convertible to an integer e and an interval [0:e-1:1] starting at zero is constructed. Note e-1, not e, is used so the Interval<1> has e indices. If two arguments are specified, they are assumed to be convertible to integers b and e, specifying the interval [b:e:1]. The three-parameter constructor is similar, with the third argument specifying a stride, which must be one.

Table 5-4. Declaring Multidimensional Intervals

constructorresult
Interval<D>()creates an empty, uninitialized Interval, to be assigned a value later.
Interval<D>(const Pooma::NoInit& no)creates an empty, uninitialized Interval, to be assigned a value later.
Interval<D>(const DT1& t1)creates an Interval using the given Domain object.
Interval<D>(const DT1& t1, const DT2& t2)creates an Interval using the given Domain objects.
Interval<D>(const DT1& t1, const DT2& t2, const DT3& t3)creates an Interval using the given Domain objects.
Interval<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4)creates an Interval using the given Domain objects.
Interval<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5)creates an Interval using the given Domain objects.
Interval<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5, const DT6& t6)creates an Interval using the given Domain objects.
Interval<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5, const DT6& t6, const DT7& t7)creates an Interval using the given Domain objects.
D indicates the Interval's dimension. DT1, DT2, … are template parameters. 

Constructors for multidimensional Intervals closely follow constructors for multidimensional Locs. See Table 5-4. D indicates the Interval's dimension. The first two constructors both return empty, uninitialized intervals. The seven other constructors create an Interval using Domain objects. These Domain objects, having types DT1, …, DT7, can have any type that can be converted into an integer, into a single-dimensional Domain object that can be converted into a single-dimensional Interval, or to a multidimensional Domain object that itself can be converted into an Interval. The total dimensionality of all the arguments' types should be at most D. One-dimensional Domain objects that can be converted into one-dimensional Intervals include Loc<1>s, Interval<1>s, and Range<1>s with unit strides. If the sum of the objects' dimensions is less than D, the intervals for the final dimensions are unspecified. See the last paragraph of Section 5.3.1.1 for an analogous example. Note that the Interval<1> constructors taking two and three parameters treat these arguments differently than the multidimensional constructors do.

5.3.1.3. Ranges

A one-dimensional Range generalizes an Interval by permitting a non-unit stride between integral members. A range is a set of integers in a mathematical interval [b,e] with a stride s between them: {a, a+s, a+2s, …, b}. Ranges are generalized to D dimensions using the direct product of one-dimensional ranges.

Table 5-5. Declaring One-Dimensional Ranges

constructorresult
Range<1>()creates an empty, uninitialized range.
Range<1>(const Pooma::NoInit& no)creates an uninitialized Range<1>, to be assigned a value later.
Range<1>(const DT1& t1)creates a Range<1>. See the text for an explanation.
Range<1>(const DT1& t1, const DT2& t2)creates a Range<1> with an interval specified by the integers converted from t1 and t2.
Range<1>(const DT1& t1, const DT2& t2, const DT3& t3)creates a Range<1> by converting the arguments to integers i1, i2, and i3 and then making a range [i1:i2:i3].
DT1, DT2, and DT3 are template parameters. 

Range<1> constructors are the same as Interval<1> constructors except they create ranges, not intervals. See Table 5-5. The default constructor creates an empty, uninitialized range, which should not be used before assigning it values. If the one-parameter constructor's argument is a Domain object, it must be a one-dimensional Domain object which is converted into a Range if possible. If the one-parameter constructor's argument is not a Domain object, it must be convertible to an integer e and a range [0:e-1:1] starting at zero is constructed. Note e-1, not e, is used so the Interval<1> has e indices. If two arguments are specified, they are assumed to be convertible to integers b and e, specifying the range [b:e:1]. The three-parameter constructor is similar, with the third argument specifying a stride.

Table 5-6. Declaring Multidimensional Ranges

constructorresult
Range<D>()creates an empty, uninitialized Range, to be assigned a value later.
Range<D>(const Pooma::NoInit& no)creates an empty, uninitialized Range, to be assigned a value later.
Range<D>(const DT1& t1)creates a Range using the given Domain object.
Range<D>(const DT1& t1, const DT2& t2)creates a Range using the given Domain objects.
Range<D>(const DT1& t1, const DT2& t2, const DT3& t3)creates a Range using the given Domain objects.
Range<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4)creates a Range using the given Domain objects.
Range<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5)creates a Range using the given Domain objects.
Range<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5, const DT6& t6)creates a Range using the given Domain objects.
Range<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5, const DT6& t6, const DT7& t7)creates a Range using the given Domain objects.
D indicates the Range's dimension. DT1, DT2, … are template parameters. 

Constructors for multidimensional Ranges are the same as multidimensional Interval constructors except they create ranges, not intervals. See Table 5-6. D indicates the Range's dimension. The first two constructors return empty, uninitialized ranges. The seven other constructors create an Range using Domain objects. These Domain objects, having types DT1, …, DT7, can have any type that can be converted into an integer, into a single-dimensional Domain object that can be converted into a single-dimensional Range, or to a multidimensional Domain object that itself can be converted into an Range. The total dimensionality of all the arguments' types should be at most D. One-dimensional Domain objects that can be converted into one-dimensional Ranges include Loc<1>s, Interval<1>s, and Range<1>s. If the sum of the objects' dimensions is less than D, the ranges for the final dimensions are unspecified. See the last paragraph of Section 5.3.1.1 for an analogous example. Note that the Range<1> constructors taking two and three parameters treat these arguments differently than the multidimensional constructors do.

5.3.1.4. Grids

Locs, Intervals, and Ranges all have regularly spaced integral values so they can be represented using domain triplets. One-dimensional Grid integral domains contain ascending or descending sequences of integers, with no fixed stride. For example, a Grid<1> may represent {-13, 1, 4, 5, 34}. Grid<1> is generalized to multidimensional Grids using the direct product of Grid<1> Domains.

Grids that can be represented using domain triplets can be constructed using techniques similar to other Domains, but irregularly spaced domains can be constructed using IndirectionList<int>s.

Table 5-7. Declaring One-Dimensional Grids

constructorresult
Grid<1>()creates an empty, uninitialized grid.
Grid<1>(const DT1& t1)creates a Grid<1>. See the text for an explanation.
Grid<1>(const DT1& t1, const DT2& t2)creates a Grid<1> from the interval specified by the integers converted from t1 and t2.
Grid<1>(const DT1& t1, const DT2& t2, const DT3& t3)creates a Grid<1> from the domain triplet specified by the integers converted from t1, t2, and t3.
DT1, DT2, and DT3 are template parameters. 

To construct a Grid<1> that can also be represented by a domain triplet, use a Grid<1> constructor similar to those for Interval<1> and Range<1>. See Table 5-7 and the text explanations following Table 5-5 or Table 5-3.

Grid<1>s with irregularly spaced points can be constructed using IndirectionList<int>s. For example,


IndirectionList<int> list(4);
list(0) = 2;
list(1) = 5;
list(2) = 6;
list(3) = 9;
Grid<1> g(list);
constructs an empty IndirectionList<int>, fills it with ascending values, and then creates a Grid<1> containing {2, 5, 6, 9}. When creating a list, its size must be specified. Subsequently, its values can be assigned. IndirectionLists can also be initialized using one-dimensional Arrays:

 Array<1,int,Brick> a1(Interval<1>(0,3));
 a1(0) = 2; a1(1) = 5; a1(2) = 6; a1(3) = 9;
 IndirectionList<int> il(a1);
 Grid<1> g1(il);
 
The Array stores the integral points to include in the Grid<1> and is used to create the IndirectionList<int>, which itself is used to create the Grid<1>. Since the points are integers, the Array's type is int. Either a Brick or CompressibleBrick Engine should be used.

Table 5-8. Declaring Multidimensional Grids

constructorresult
Grid<D>()creates an empty, uninitialized Grid, to be assigned a value later.
Grid<D>(const DT1& t1)creates a Grid using the given Domain object.
Grid<D>(const DT1& t1, const DT2& t2)creates a Grid using the given Domain objects.
Grid<D>(const DT1& t1, const DT2& t2, const DT3& t3)creates a Grid using the given Domain objects.
Grid<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4)creates a Grid using the given Domain objects.
Grid<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5)creates a Grid using the given Domain objects.
Grid<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5, const DT6& t6)creates a Grid using the given Domain objects.
Grid<D>(const DT1& t1, const DT2& t2, const DT3& t3, const DT4& t4, const DT5& t5, const DT6& t6, const DT7& t7)creates a Grid using the given Domain objects.
D indicates the Grid's dimension. DT1, DT2, … are template parameters. 

Constructors for multidimensional Grids are the same as multidimensional Interval constructors except they create Grids, not intervals. See Table 5-8. D indicates the Grid's dimension. The first constructor returns empty, uninitialized grids. The seven other constructors create an Grid using Domain objects. These Domain objects, having types DT1, …, DT7, can have any type that can be converted into an integer, into a single-dimensional Domain object that can be converted into a single-dimensional Grid, or to a multidimensional Domain object that itself can be converted into an Grid. The total dimensionality of all the arguments' types should be at most D. One-dimensional Domain objects that can be converted into one-dimensional Grids include Loc<1>s, Interval<1>s, Range<1>s, and Grid<1>s. If the sum of the objects' dimensions is less than D, the grids for the final dimensions are unspecified. See the last paragraph of Section 5.3.1.1 for an analogous example. Note that the Grid<1> constructors taking two and three parameters treat these arguments differently than the multidimensional constructors do.

5.3.2. Using Domains

Since an Array can be queried for its domain, we briefly describe some Domain operations. A fuller description, including arithmetic operations, occurs in Chapter 8. As we mentioned in Section 5.3.1, the Pooma/Domains.h header file declares Domains, but most storage container header files automatically include Pooma/Domains.h so no explicit inclusion is usually necessary.

Table 5-9. Some Domain Accessors

Domain member functionresult
Multidimensional Domain Accessors 
long size()returns the total number of indices.
bool empty()returns true if and only if the Domain has no indices.
D<1> operator[](int dimension)returns the one-dimensional Domain for the specified dimension. The return type is a one-dimensional version of the Domain.
One-dimensional Domain Accessors 
long length()returns the number of indices.
int first()returns the beginning of the domain.
int last()returns the ending of the domain.
int min()returns the minimum index in the domain.
int max()returns the maximum index in the domain.
D<1>::iterator begin()returns a forward iterator pointing to the beginning domain index.
D<1>::iterator end()returns a forward iterator pointing to the ending domain index.
D abbreviates a particular Domain type, e.g., Interval or Grid. Other Domain accessors are described in Chapter 8. 

Domain member functions are listed in Table 5-9. Functions applicable to both one-dimensional and multidimensional Domains are listed before functions that only applicable to one-dimensional Domains. The size member function yields the total number of indices in a given Domain. If and only if this number is zero, empty will yield true. A multidimensional domain<D> is the direct product of D one-dimensional Domains. The operator[](int dimension) operator extracts the one-dimensional Domain corresponding to its parameter. For example, the three one-dimensional Range<1> Domains can be extracted from a Range<3> object r using r[0], r[1], and r[2].

Domain accessors applicable only to one-dimensional Domains are listed in the second half of Table 5-9. The length member function, analogous to the multidimensional size function, returns the number of indices in the Domain. The first and last member functions return the domain's beginning and ending indices. The begin and end member functions return forward iterators pointing to these respective locations. They have type D<1>::iterator, where D abbreviates the Domain's type, e.g., Interval or Grid. The min and max member functions return the minimum and maximum indices in the Domain object, respectively. For Loc<1> and Interval<1>, these yield the same values as first and last, but Range<1> and Grid<1> can have their numerically largest index at the beginning of their Domains.