On 04/22/11 15:01, Larry Evans wrote:
On 04/11/11 15:15, Pierre-Andre Noel wrote: [snip]
The "Domain" concept defined in the IndexList library generalizes the conversion you are talking about. Passing a number in the range [0,num_elements()-1] to the "expand()" member of a Domain returns a collection of indices, and passing that collection of indices to its "reduce()" member will return the original number. Given any collection of indices, a Domain's "is_valid()" member will return true if this
collection
could have been obtained from a call to "expand(i)" using "i" in range [0,num_elements()-1], and false otherwise.
For box_domain, "reduce()" reproduce the same algorithm Boost.MultiArray uses to locate an element in memory (using shape() and index_bases()), "expand()" performs the opposite task as you earlier proposed and "is_valid()" simply compare each element of the provided collection of indices to index_bases and index_bases + shape.
This is similar to the encode and decode functions in apl. The difference is with the direction (increasing or decreasing w.r.t. value) of the strides and the fact that strides are already calculated in index_list; whereas in the encode/decode functions, they have to be calculated from scratch (from the shape vector).
Here's the equivalent to reduce and expand using functions from the std library and variadic templates:
-{{---cut here--- [snip] -}}---cut here--- This is now uploaded here:
http://svn.boost.org/svn/boost/sandbox/variadic_templates/sandbox/array_dyn/
In the above, indices_at_offset corresonds to index_list expand, and offset_at_indices corresponds to index_list reduce.
Aside from runtime dimension selection, what does 'box' add beyond the current extent_gen-based capabilities. (Compile-time) dimension-independent code can be written by templating on the MultiArray NumDims parameter (
http://agentzlerich.blogspot.com/2010/01/providing-fill-and-foreach-algorith...
is an example).
Excluding runtime dimensionality, the sole advantages I see for data organized in a "box" way are: - it facilitate coding concerning the current position using "expand()", - it lighten the treatment of "boundary conditions" using "is_valid()" (By boundary conditions, I refer to the special treatment that is sometime required, in the form of "ifs", around the edges of the MultiArray.) and - for the cases where, although it is ok to store the data using a "box" organization, the same data has to be accessed in a different way that is not trivial to implement (The access could then be made using a different domain than a box_domain.).
I didn't notice any operations for doing transforms. Methods for doing transforms, as well as all the stride calculations as well as many other operations are described in the book:
http://web.engr.oregonstate.edu/~budd/Books/aplc/
You might find it useful.
On page 82 of the above reference, there's this: the value A[a_1;...;a_n] will be found at offset in the underlying subexpression given by: offset = alpha + a_1*gamma_1 + ... + a_n*gamm_n for some values of alpha and gamma_i. ... Given this uniform representation, it is perhaps not surprising that structural functions can be composed. ... For structural functions, the medium for composition is an object called the 'stepper'. Each node in the parse tree that represents a structural function has a stepper associated with it. The stepper is characterized by three vectors, each of size 'n' where 'n' is the rank of the result. q_i The dimension of the result that the i-th dimension of the current node corresponds to. t_i The index along the i_th coordinate of the current node that contributes to the initial element in the result ravel order. d_i The direction to move along the i_the dimension in in order to arive at the next element in the result along the q_i-th coordinate. Or, put in another way: q_i is modified by transpose. For example, initially: q_i = i but after a transpose, the resulting values, q_i', are reversed: q_i' = q_(n-(i-1) as shown on p. 84 of the reference. t_i has something to do with initial offsets. IOW, alpha = t_1*stride_1+...+t_n*stride_n is the alpha mentioned earlier. Initially, all t_i's are 0, so that the initial alpha is also 0. After a drop of, say 2 on coordinate 1, then: t_1=2 as indicated on p. 85 of the reference, and the alpha becomes 2*stride_2. d_i indicates whether: A[a_1;...;a_i...;an] is stored after (d_i=+1) or before(d_i=-1) A[a_1;...a_i+1...;an] and I think this is related to either your box_domain's ordering_ or ascending_. For example, after coordinate i is reversed, then the resulting values, t_i' and d_i' are: t_i'= s_i-t_i-1 d_i'= -d_i where s_i is the initial size in the i_th coordinate (or dimension, in your terms). These d_i's and stride_i's are used to calculate the gamma_i's mentioned earlier as shown on p. 86 of the reference. The code I mentioned earlier, in array_dyn directory in box_domain.hpp, has none of q_i, t_i or d_i, but they could be provided and encapsulated in some sort of stepper object that the reference mentions if there's anyone interested. [snip] -regards, Larry