
Boost : 
Subject: Re: [boost] [multi_array] Is there interest for an [index_list] library?
From: Larry Evans (cppljevans_at_[hidden])
Date: 20110430 11:51:35
On 04/22/11 15:01, Larry Evans wrote:
> On 04/11/11 15:15, PierreAndre 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_genbased
>>> capabilities. (Compiletime) dimensionindependent code can be
>>> written by templating on the MultiArray NumDims parameter
>>> (
>>
> http://agentzlerich.blogspot.com/2010/01/providingfillandforeachalgorithms.html
>>> 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 ith 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_ith 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(i1)
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_it_i1
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk