Re: [boost] [multi_array] Is there interest for an [index_list] library?

Subject: Re: [boost] [multi_array] Is there interest for an [index_list] library?
From: Larry Evans (cppljevans_at_[hidden])
Date: 2011-04-30 11:51:35

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-algorithms.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 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