Re: [boost] range, multi-dimensional

From: Daniel Walker (daniel.j.walker_at_[hidden])
Date: 2007-04-16 11:51:16

On 4/16/07, Paul Giaccone <paulg_at_[hidden]> wrote:
> Daniel Walker wrote:
>
> >On 4/13/07, Marco <mrcekets_at_[hidden]> wrote:
> >
> >
> >>On Fri, 13 Apr 2007 20:26:17 +0200, Daniel Walker
> >><daniel.j.walker_at_[hidden]> wrote:
> >>
> >>
> >>>I'm not sure if span is the right name for it, and this has got to be
> >>>encroaching on UBLAS' domain. But it's doable for ranges. I just tried
> >>>the following, which I believe will work for arbitrary dimensions.
> >>>
> >>Mathematically speaking, the term "span" is inappropriate: span is usually
> >>used in linear algebra to denote the space generated by all linear
> >>combinations of a set of vectors [...].
> >>
> >>
> >
> >Thanks. I thought "span" might not be right. I wasn't sure if slice
> >only referred to 1d vectors or if it could be a subspace of any
> >dimension.
> >
>
> I think "slice" could be used for any number of (positive integer)
> dimensions. From a non-mathematical point of view, consider:
>
> * a "time slice": this is one-dimensional (the dimension is time);
> * a rock sliced through the middle so you can see its internal
> structure, which would be 2D; and
> * a slice of cake, which is definitely 3D (even though this doesn't
> reduce the original number of dimensions; if it did, the slice would
> have zero volume and so zero calories!)

I see, OK, that makes sense to me. I wouldn't mind zero calorie cake,
but it wouldn't be as good if it weren't fluffy!

On the less fattening topic of multi-dimensional ranges, after
thinking about this some more over the weekend, I really like the oven
library's use of the name at(), like std::vector::at(). Even though it
may be the same thing as a slice(), I think a generic abstraction for
multi-dimensional ranges may be better off making an analogy to C++
syntax for subscripting rather than a Linear Algebra idea like slices.

I'm not an experienced ublas user, but I always figured if I needed
Linear Algebra one day, I would use it or MTL. Even though I
complained that ublas concepts are intrusive, really so is the STL,
and it's not that bad. Besides, a lot of people like using member
functions, which in some respects is a matter of personal preference.

Still, I don't think it is necessary for multi-dimensional ranges to
reference Linear Algebra or ublas. The "span" function I posted may
actually be a Linear Algebra slice, but it's also very similar to a
C++ subscript. You could call it at() or perhaps multi_at(). The
following notation for a RandomAccessIterator into a type composed of
multiple embedded RandomAccessContainers ...

    foo = i[1][2][3];
    foo = *(boost::begin(*(boost::begin(*(i + 1)) + 2)) + 3);

... or more generically for non-random access ...

    foo = *boost::next(boost::begin(
              *boost::next(boost::begin(
                  *boost::next(i, 1))
                , 2))
            , 3);

... could also be the following for any ForwardRange ...

    range = // some pair of i and j from i's container or i's container itself
    foo = multi_at(range, 1, 2, 3);

By providing overloads of multi_at (either by hand or automatically
with Boost.Preprocessor) multi_at could handle arbitrary depths of
embedded ForwardRanges (i.e. multiple dimensions). Note that multi_at
wouldn't work with ublas because ublas' matrix doesn't model either
ForwardContainer or ForwardRange. If ublas provided an interface that
did, then it could work.

The code below is an implementation of multi_at() for three levels of
embedded ranges. It probably needs some sort of bounds checking before
you would want to deploy it, and concept-checking too for that matter.

Daniel

#include <utility>
#include <vector>

#include <boost/range.hpp>
#include <boost/utility.hpp>

using namespace boost;
using namespace std;

template<typename ForwardRange, int Depth>
struct range_multi_at_value;

template<typename ForwardRange>
struct range_multi_at_value<ForwardRange, 3> {
    typedef typename range_value<
        typename range_value<
            typename range_value<
                ForwardRange
            >::type
        >::type
    >::type type;
};

template<typename ForwardRange>
inline typename range_multi_at_value<
    ForwardRange, 3
>::type const&
multi_at(ForwardRange const& range
       , const int i0 , const int i1 , const int i2) {
    return
        *next(begin(
            *next(begin(
                *next(begin( range )
                    , i0) )
              , i1) )
          , i2) ;
}

int main() {
//  typedef int range_type[2][3][4]; // this also works for arrays.
    typedef vector<vector<vector<int> > > range_type;

    range_type r;
    typedef boost::range_const_iterator<
        range_type
    >::type iterator_type;
    iterator_type i = boost::begin(r);

    int foo;

    // the following ...
    foo = i[1][2][3];
    foo = *(boost::begin(*(boost::begin(*(i + 1)) + 2)) + 3);

    // ... is like ...
    foo = *boost::next(boost::begin(
              *boost::next(boost::begin(
                  *boost::next(i, 1))
                , 2))
            , 3);

    // ... but could be ...
    pair<iterator_type, iterator_type>
        range = make_pair(i, i + 2);
    foo = multi_at(range, 1, 2, 3);
}