On 07/12/2004 12:10 PM, Matthias Schabel wrote:
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.
What I do is maintain a signature of permutations (essentially the index order : for example, in a 3D C array the signature would be (0,1,2) while a FORTRAN order array would be (2,1,0). An accessor class is responsible for converting between the multidimensional index and a one dimensional offset corresponding to a dense matrix; the allocator then uses this offset to get the element out of storage - if the matrix is dense, the allocator just passes the already computed offset along, while if it is sparse, a map is used to look for the existence of the specified element.
In _An Apl Compiler_, an "expansion vector", e, is used. The size is the array's rank (what I think you term dimension). The transpose simply permutes (probably what you're doing with index order) the expansion vector (e.g. instead of e0,e1,e2, it would be e2,e1,e0). The expansion vector is just the "scan" of the "shape" in apl terms. I think that's right, or maybe it's the scan of the reverse of the shape. For example if the shape is 2,5,10, then the expansion vector would be 2, 10, 100, and the location of a[i0][i1][i2] would be a0[e0*i0+e1*i1+e2*i2], where a0 is the start if the array.