5.6. DynamicArrays

Arrays have fixed domains so the set of valid indices remains fixed after creation. The DynamicArray class supports one-dimensional domains that can be resized even while the array is used.

DynamicArray's interface extends the one-dimensional interface of an Array by adding member functions to change the domain's size. It is declared in Pooma/DynamicArrays.h. A DynamicArray has two, not three, template parameters, omitting the array's dimensionality which must be one. The first parameter T specifies the type of stored values. Its default value is usually double, but this may be changed when the POOMA Toolkit is configured. The second parameter specifies an Engine via an Engine tag. The engine must support a domain with dynamic resizing. For example, the Dynamic Engine is analogous to a one-dimensional Brick Engine supporting a dynamically-resizable domain. It is also usually the default value for this tag. For example, DynamicArray<> d0(1);, DynamicArray<double> d1(1);, and DynamicArray<double, Dynamic> d2(1); all declare the same DynamicArrays explicitly storing one double value. A DynamicArray automatically allocates its initial memory and deallocates its final memory, just as an Array does.

The create and destroy member functions permit changing a DynamicArray's domain. Table 5-14 lists these member functions but omits functions exclusively used in distributed computation. When making the domain larger, new indices are added to the end of the one-dimensional domain and the corresponding values are initialized with the default value for T. Existing values are copied.

Table 5-14. Changing a DynamicArray's Domain

DynamicArray member functiondescription
void create(int num)extend the current domain by the requested number of elements.
void destroy(const Dom& killList)remove the values specified by the indices in the given Domain argument. The "Backfill" method moves values from the end of the domain to replace the deleted values.
void destroy(Iter killBegin, Iter killEnd)remove the values specified by the indices in the container range [begin,end) specified by the random-access iterators. The "Backfill" method moves values from the end of the domain to replace the deleted values.
void destroy(const Dom& killList, const DeleteMethod& method)remove the values specified by the indices in the given Domain argument. Deleted values can be replaced by BackFill'ing, i.e., moving data from the domain's end to fill removed values, or by ShiftUp'ing, i.e., compacting all data but maintaining the relative ordering.
void destroy(Iter killBegin, Iter killEnd, const DeleteMethod& method)remove the values specified by the indices in the container range [begin,end) specified by the random-access iterators. Deleted values can be replaced by BackFill'ing, i.e., moving data from the domain's end to fill removed values, or by ShiftUp'ing, i.e., compacting all data but maintaining the relative ordering.
This table omits member functions designed for distributed computation. 

The destroy member function deletes the specified indices. The indices may be specified using either a Domain object (Interval<1>, Range<1>, or IndirectionList) or by random-access iterators pointing into a container. For example, every other value from a ten-value array d might be removed using Range<1>(0,9,2). Alternatively,


int killList[] = {0, 2, 4, 6, 8};
d.destroy(killList, killList+5);
performs the same deletions. As indices are removed, other indices are moved into their positions. Using the BackFill method moves the last index and its associated value into deleted index's position. Thus, the total number of indices is decreased by one, but the indices are reordered. Using the ShiftUp method ensures the order of the indices is preserved by "shifting" all values left (or up) so all "gaps" between indices disappear. For example, consider removing the first index from a domain.

original indices:0 1 2 3
destroy using BackFill:3 1 2
destroy using ShiftUp:1 2 3

The BackFill moves the rightmost index 3 into the removed index 0's position. The ShiftUp moves all the indices one position to the left. This illustrates that BackFill moves exactly as many indices as are deleted, while ShiftUp can shift all indices in a domain. Thus, BackFill is the default method. When multiple indices are deleted, they are deleted from the last (largest) to the first (smallest). When using the BackFill method, some indices may be moved repeatedly. For example, consider removing indices 0 and 2 from original indices of 0 1 2 3. Removing 2 yields 0 1 3 because 3 is moved into 2's position. Removing 0 yields 3 1 because 3 is again moved. Use an object with the desired type to indicate which fill method is desired, i.e., BackFill() or ShiftUp().

We illustrate DynamicArray resizing in Example 5-3. DynamicArrays are declared in Pooma/DynamicArrays.h, not Pooma/Arrays.h. Their declarations require two, not three, template arguments because the array must be one-dimensional. The three arrays, each having one double value, are equivalent. (The POOMA Toolkit can be configured to support different default template values.) Invoking d0's create with an argument of five increases its domain size from one to six. The additional indices are added to the end of the domain so the value at index 0 is not changed. To illustrate which indices are removed and which indices are reordered, the program first sets all values equal to their indices. This illustrates that DynamicArray values are accessed the same way as Array values. For example, d0(i) accesses the ith value. The destroy member function removes every other index from the array because the one-dimensional Range specifies the domain's entire interval with a stride of 2. The BackFill function call creates a BackFill object indicating the BackFill method should be used. We illustrate the steps of this method:

original indices:0 1 2 3 4 5
delete index 4:0 1 2 3 5
delete index 2:0 1 5 3
delete index 0:3 1 5

Since multiple indices are specified, the rightmost one is removed first, i.e., index 4. The rightmost index 5 is moved into 4's position. When removing index 2, the index originally at 5 is again moved into 2's position. Finally, index 0 is replaced by index 3. The rest of the program repeats the computation, using the random-access iterator version of destroy. Since this DynamicArray's indices are specified using ints, the killList explicitly lists the indices to remove. The destroy call uses pointers to the beginning and end of the killList array to specify which of its indices to use. Since no replacement method is specified, the default BackFill method is used. All the DynamicArrays' unallocated memory is deallocated.

Example 5-3. Example Using DynamicArrays


#include "Pooma/Pooma.h"
#include "Pooma/DynamicArrays.h"  (1)
#include <iostream>

// Demonstrate using DynamicArrays.

int main(int argc, char *argv[])
{
  Pooma::initialize(argc,argv);

  // Create a DynamicArray with one element.  (2)
  DynamicArray<> d0(1);
  DynamicArray<double> d01(1);
  DynamicArray<double, Dynamic> d02(1);

  // Add five more elements.  (3)
  d0.create(5);
  // Store values in the array.
  for (int i = d0.domain().first(); i <= d0.domain().last(); ++i)
    d0(i) = i;  (4)

  // Delete every other element.  (5)
  d0.destroy(Range<1>(d0.domain().first(),d0.domain().last(),2), BackFill());

  // Print the resulting array.
  std::cout < < d0 < < std::endl;

  // Use the iterator form of 'destroy.'
  DynamicArray<> d1(6);
  for (int i = d1.domain().first(); i <= d1.domain().last(); ++i)
    d1(i) = i;
  int killList[] = { 0, 2, 4 };  (6)
  d1.destroy(killList, killList+3);
  std::cout < < d1 < < std::endl;

  Pooma::finalize();
  return 0;
}
(1)
This header file declares DynamicArrays.
(2)
These three declarations yield equivalent DynamicArrays, storing one double value.
(3)
This create member function call adds five indices to the end of the domain.
(4)
DynamicArray values are accessed the same way as Array values.
(5)
The Range object specifies that every other index should be removed. The BackFill() object is unnecessary since it is the default replacement method.
(6)
This destroy call is equivalent to the previous one but uses iterators.