Re: [Boost-users] Help with a generic algorithm using boost::MultiArray/Multiple nested range traversal

Subject: Re: [Boost-users] Help with a generic algorithm using boost::MultiArray/Multiple nested range traversal
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-01-12 14:15:18

AMDG

Jesse Perla wrote:
>
> Thanks for the response.  I also think this is a pretty important use 
> case for this great library.  Let me justify why I think an Iterator 
> based approach is the best:
>
> * For maximum efficiency (I will be using this in numerical 
> simulations), we will want have an incrementing pointer within the 
> data structure pointing to the actual object, and not just the iterator.
>
> * Also, if we have a single forward iterator, then we should be able 
> to reuse a bunch of standard algorithms in the cases where we do not 
> need the actual index values or the order of execution doesn't matter.
>
> * In the iterator algorithm, I would love to check the ordering of the 
> data from the template parameters.  If it is fortran ordering then we 
> would do the loops in the opposite order for example, and this should 
> be based on querying the data structure in the iterator code.
>
> * As for your range based use case, I don't know enough about how 
> iterators and ranges interact to see how that would work.
>
> * As to implementation of this, thanks for the pointer to Fusion.  
> This indeed seems to be the best approach since the loops can be 
> generated at compile time, and compilers could then do some very fancy 
> optimization on them.  Sadly, I am not a template metaprogrammer, or a 
> very good C++ programmer in general, and am terrified to learn it and 
> lose sight of my non-CS research.
>
> Now for the semantics of this, it seems to me that the way the 
> iterator concepts are designed, the distance() function is intended to 
> pass back the related index information.  Now my question is whether 
> it is OK for the semantics of distance to pass back a 
> boost::array<NUMDIMS> instead?  Seems reasonable to me that it would 
> not be based on passing back a scalar value in this case because that 
> is arbitrarily dependent on the column vs. row ordering.  And we can 
> easily generate a boost::array from the distance function by looking 
> at the distance between the .begin() for all of our current positions 
> in the sub-iterators?
>

If you just want to iterate over the elements you can use data to get a 
pointer:

  multi_array<int, 3> m;
  m.data(), m.data() + m.num_elements()

Given a pointer into a multi_array, you can deduce its index:

int index_of(const multi_array<int, 3>& m, int* iter, int dimension) {
    int offset = iter - m.origin();
    return(offset / m.strides()[dimension] % m.shape()[dimension] + 
m.index_bases()[dimension]);
}

In Christ,
Steven Watanabve