Re: A class template for an N-dimensional generic resizable array

From: Randy Roberts (rroberts_at_[hidden])
Date: 2000-12-08 17:14:25

--- In boost_at_[hidden], Ronald Garcia <rgarcia4_at_c...> wrote:
> At certain times it is necessary to work with both "C" style and
> "Fortran" style arrays, especially when interfacing with fortran
which
> (IMHO) is unfortunately necessary at times.  I think that given the
> right abstractions, code to support a fortran view of arrays can
also
> support arbitrary dimension permutations without greatly affecting
the
> complexity of the code. 
> 
> Since not everyone is going to need altered views of arrays, simple
> abstractions that provide enough hooks to implement an altered view
> as an extension of the base library would suffice and provide great
> flexibility at what should be a minimal cost in complexity. This
> mechanism could also be a way of providing a flattened view of
arrays
> if the standard iterators iterate across N-1 dimensional subarrays,
> which I think is the way to go.

I think the important thing to realize here, is that us poor sm*cks
who have to work with legacy F77 code not just need a Fortran **view**
of an array, we need access to a pointer to the contiguous,
Fortran-ordered array data.

There are two problems with a Fortran view approach to this problem...

First, if the view causes a copy of the data into a Fortran-ordered
array (it really isn't a view, is it), then we may be faced with large
copying overheads in both space and time.

Second, if we were only to have a Fortran view of the array with
iterators that gallop through the strided generalized slices of an
underlying C-ordered C-style array, then there is no way to obtain
from this iterator a pointer to a contiguous Fortran-ordered array.
One would have to use something akin to std::copy(,,) into a temporary
buffer, and we are right back to the large copying overheads in both
space and time.

I have played with N-dimensional arrays, and have delegated the
storage order to a separate class.  This class would also be
responsible for which iterators to use, e.g.

// C ordering could use a simple T* iterator
// for both array level and all sub-array's

template <typename T, int N>
struct C_ordering
{
   typedef T* iterator;
   typedef C_ordering<T,N-1> SubOrdering;

   // ...
   // Include methods to create sub-array's SubOrdering, etc.
};

// The case of the sub-array F77 ordering would need a more
// complex striding iterator.

template <typename T, int N, int Norig=N>
struct F77_ordering
{
   typedef SomethingMoreComplex<T,N,Norig> iterator;
   typedef F77_ordering<T,N-1,Norig> SubOrdering;

   // ...
   // Include methods to create sub-array's SubOrdering, etc.
};

// The case of the array level F77 ordering could use a simple
// T* iterator into the entire C-array

template <typename T, int N>
struct F77_ordering<T,N,N>
{
   typedef T* iterator;
   typedef F77_ordering<T,N-1,N> SubOrdering;

   // ...
   // Include methods to create sub-array's SubOrdering, etc.
};

template <typename T, int N, class Ordering = C_ordering<T,N> >
class array : public Ordering
{
public:

   typedef typename Ordering::iterator iterator;
   // ...

private:

   typedef sub_array<T,N-1,typename Ordering::SubOrdering>
the_sub_array;

   T *data;
};

typedef array< double, 3, F77_ordering<double,3> > f77_array3_double;

The common code would be placed in array and sub_array, and defer
order-based decisions to the Ordering Strategy/Policy.

I wasn't planning on coming up with a working demonstration of this
technique unless there was enough interest in pursuing this.

Let me know.

Randy
--
Randy M. Roberts          |    "His men would follow him anywhere,
rsqrd_at_[hidden]            |     but only out of morbid curiosity."
work: [phone]       |            -- a performance review