[boost] Re: multidimensional arrays (was Boost Mathematicians)

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

On 07/09/2004 04:24 PM, Matthias Schabel wrote:
[snip]
> 
> 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:

   http://facweb.cs.depaul.edu/tchristopher/llkppr.pdf