Boost logo

Boost :

From: Larry Evans (cppljevans_at_[hidden])
Date: 2004-07-09 16:48:36

On 07/09/2004 04:24 PM, Matthias Schabel wrote:
> A couple of thoughts on such a D-dimensional array class :
> 1) it should implement as much of the STL one-dimensional container
> interface as possible so that
> algorithms which are unconcerned with the order of traversal can use an
> efficient 1D iterator interface -
> for example, if I want to replace every element of a matrix with its
> square, I should be able to do this :
> matrix_type mat;
> for (matrix_type::iterator it=mat.begin();it!=mat.end();++it) *it =
> (*it)*(*it);
> The advantage here is that the algorithm doesn't need to know if the
> matrix is sparse or dense, as that
> logic is in the iterator, and applies equally well to higher rank
> arrays. Indexed element access can just be
> viewed as a mapping of a D-dimensional index to the corresponding 1D
> offset.
> 2) it should support two common syntaxes :
> mat[i][j] - zero offset C-style access
> mat(i,j) - possibly non-zero offset access
> 3) implementations for both statically allocated and dynamically
> allocated memory should be feasible.
> 4) for genericity (in algorithms which work for various values of D)
> there should also be an index type Index<D>
> which may be passed to operator() as an index :
> mat(Index<2>(i,j)) - equivalent to mat(i,j)
> 5) should support various types of slicing : indirection, subranges,
> masking, etc...
> 6) should facilitate range checking if desired.
> If there is interest, I have written some starting code that I would be
> happy to share which addresses most of

I'm interested.

> these points to some extent and provides some other nice properties
> such as allowing transposition of arbitrary
> indices with no need to reorder the underlying storage (that is
> mat.transpose(0,1) causes all subsequent calls to mat(i,j) to provide
> the transposed element without moving the elements themselves). I have

I'd be interested in seeing how this was done, especially in comparison
with Timothy Budd's methods in _An Apl Compiler_. I had an
implementation of this; however, it was only for dense matrices since
that's all Budd had in his book.

> functioning dense, sparse, and diagonal
> implementations (with a proxy reference type) as well as indirection,
> subrange, and mask slicing. The design is uses a single policy
> template for the underlying implementation :
> Array<T,R,Imp> - T is the value type of elements, R is the rank, and
> Imp contains the functional implementation details.
> I'll see about shaping the code up this weekend and posting it on the
> Yahoo files section if there's interest....

I'd be very interested. I'm thinking about using a sparse matrix
where T is symbol_set, where symbol_set is the set of terminal
and non-terminal symbols in a grammar. This could be used by
spirit in deriving LL(k) parser as described in:

Boost list run by bdawes at, gregod at, cpdaniel at, john at