I have also thought about that before when I was looking at GIL for example. It seems to me that what you need is recursive-range class, so that range_value is a lower dimensional range. BOOST_FOREACH( typename range_value<xyz>::type xy, xyz) BOOST_FOREACH( typename range_value<xy>::type x, xyz) BOOST_FOREACH( typename range_value<x>::type element, x) //this is the element in a 3D range.... Syntactically it is a "range of range of range of value", but presumably the ranges need not be stored as they can be computed. Then you just need to make a iterator whose value type is a range-proxy according to whatever method is appropriate for your collection. A 3d range_iterator needs all of the info required to make a sequence of iterators to 2D proxy-ranges, likewise a 2D range_iterator must be able to make a sequence of 1D proxy-ranges. Then you can easily construct ways to iterate through subimages, arbitrary blocks or runs of an image, or whatever. Such ranges could potentially overlap etc. John -----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Daniel Walker Sent: Friday, April 13, 2007 11:26 AM To: boost@lists.boost.org Subject: Re: [boost] range, multi-dimensional On 4/13/07, Neal Becker <ndbecker2@gmail.com> wrote:

I just posted something on ublas, but I think it may be of more general interest.

I have been using boost::range heavily, and find it useful for generic interfaces. I think it is also useful to have a multi-dimensional extension to range. In particular, a 2-d extension would help in creating algorithms that can accept a variety of 2-d structures.

For example, range has size, begin, end.

range2d would have size1, size2, begin1, begin2.

I think this is an interesting idea, and I've been looking into a little while. You could make this multi-dimensional not just 2d. How about something like .. // get the number of lines in the plane at index 0 of a 3d space plane_type& space_2d = span(space_3d, 0); range_size< plane_type >::type n_2d = size(space_2d); 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. #include <boost/preprocessor.hpp> #include <boost/range.hpp> #include <boost/utility.hpp> using namespace boost; #define RANGE_SPAN_RETURN_TYPE_OPEN(z, n, _) \ typename range_value< \ /**/ #define RANGE_SPAN_RETURN_TYPE_CLOSE(z, n, _) \

::type \ /**/

#define RANGE_SPAN_GET_OPEN(z, n, _) \ *next(begin( \ /**/ #define RANGE_SPAN_GET_CLOSE(z, n, _) \ ), BOOST_PP_CAT(i, n)) \ /**/ // RANGE_SPAN expands to something like ... // template<typename Range> // typename range_value< // typename range_value< Range >::type // >::type & // span(Range& range , const int i0 , const int i1) // { // return *next(begin( *next(begin( range ), i0) ), i1) ; // } #define RANGE_SPAN(z, n, _) \ template<typename Range> \ BOOST_PP_REPEAT(n, RANGE_SPAN_RETURN_TYPE_OPEN, _) \ Range \ BOOST_PP_REPEAT(n, RANGE_SPAN_RETURN_TYPE_CLOSE, _) \ & \ span(Range& range BOOST_PP_ENUM_TRAILING_PARAMS(n, const int i)) \ { \ return \ BOOST_PP_REPEAT(n, RANGE_SPAN_GET_OPEN, _) \ range \ BOOST_PP_REPEAT(n, RANGE_SPAN_GET_CLOSE, _) \ ; \ } \ /**/ // Overloads could be generated for larger dimensions than 3. BOOST_PP_REPEAT(3, RANGE_SPAN, _) int main() { typedef int volume_type[1][1][1]; typedef int plane_type[1][1]; typedef int line_type[1]; volume_type space_3d; plane_type& space_2d = span(space_3d, 0); range_size< plane_type >::type n_2d = size(space_2d); line_type& space_1d = span(space_3d, 0, 0); range_size< line_type >::type n_1d = size(space_1d); } Daniel _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On 4/13/07, Marco <mrcekets@gmail.com> wrote:

On Fri, 13 Apr 2007 20:26:17 +0200, Daniel Walker <daniel.j.walker@gmail.com> wrote:

...

On 4/13/07, Neal Becker <ndbecker2@gmail.com> wrote:

...

I just posted something on ublas, but I think it may be of more general interest.

I have been using boost::range heavily, and find it useful for generic interfaces. I think it is also useful to have a multi-dimensional extension to range. In particular, a 2-d extension would help in creating algorithms that can accept a variety of 2-d structures.

For example, range has size, begin, end.

range2d would have size1, size2, begin1, begin2.

I think this is an interesting idea, and I've been looking into a little while. You could make this multi-dimensional not just 2d. How about something like ..

// get the number of lines in the plane at index 0 of a 3d space plane_type& space_2d = span(space_3d, 0); range_size< plane_type >::type n_2d = size(space_2d);

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; so if you have two indipendent vectors belonging to the plane they generate the whole plane (they are a system of generators for the plane). On the contrary you do not want to expand space_3d. The right term, IMHO, could be "slice" because you want to slice space_3d in order to get one of its affine subspace.

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. std::slice produces a sequence of indices, but I guess those could be all the points in any n-dimensional space. The function I gave doesn't exactly give you points, at least not points you can immediately/directly loop over, so I'm not sure if it's quite the same as std::slice. Actually, I'm not sure that this is what Neal originally wanted since the size of the 2d "slice" is the number of lines and not the number of points. Maybe a good name for the function would be "subspace"... or better yet it could be called "slice" if it were extended to return a range of iterator adaptors (along the lines of John Femiani's earlier comments) that enumerate all the points. But this may be reinventing the wheel since there are already libraries for stuff like this. Daniel

On 4/16/07, Paul Giaccone <paulg@cinesite.co.uk> wrote:

Daniel Walker wrote:

...

On 4/13/07, Marco <mrcekets@gmail.com> wrote:

...

On Fri, 13 Apr 2007 20:26:17 +0200, Daniel Walker <daniel.j.walker@gmail.com> 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); }

Here is an example:

Neal Becker wrote:

I don't know yet if this is feasible, but here's what I am imagining:

template<typename range_2d_t> int alg (range_2d_t const& x) { typedef typename row_iterator<range_2d_t>::type ri_t; ri_t ri = first_row (x); for (; ri != end_row (x); ++ri) { typename range_const_iterator<ri_t>::type i = begin (ri); for (; i != end (ri); ++i) do_something_with (*i); } } }

I also tried to see if it is feasible, though I don't know ublas at all. Thanks to Boost.Range(and result_of), No specific iterator was required. Example: http://tinyurl.com/2f2zep Implementation(not boostified yet): http://tinyurl.com/2aecas Regards, -- Shunsuke Sogame

Marco wrote: [...]

However I think that Neal wants to start with something like a vector< vector<int> > and I didn't succeed in guessing if your library can manage it.

What I am looking for is: * A generalization of range to multi-dim (starting with, at minimum, 2d) * What makes range useful? The ability to generically traverse containers, accessing (ro/rw) the elements. The example I gave has an interface that looks like vector<vector>>, but that is a result of thinking about how I would like a generalization of range traversal to look. I didn't state it, but I imagine the 2d range would also support traversal by columns, and maybe other types of traversal. The row/col example was just an example (but a common one). Of course, not all 2d ranges would support all kinds of traversal.

Marco wrote:

I gave a glance to oven library

rng|columns(5, 7)|at(5) really a nice construct !

However I think that Neal wants to start with something like a vector< vector<int> > and I didn't succeed in guessing if your library can manage it.

Do you foresee to submit oven for a boost review sooner or later ?

I actually plan to upload it to Vault in a few months as an unofficial part of Boost.Range. But, I'm not sure it can reach a review phase :-) Anyway, we can look forward to MTL version 4.0, which must be a more generic library than Range. Regards, -- Shunsuke Sogame