Re: matrix and vector iterators

From: Hubert HOLIN (Hubert.Holin_at_[hidden])
Date: 2001-06-15 08:30:31

Somewhere in the E.U., le 15/06/2001

--- In boost_at_y..., "David Abrahams" <david.abrahams_at_r...> wrote:
> 
> ----- Original Message -----
> From: "Hubert HOLIN" <Hubert.Holin_at_B...>
> > >

[SNIP]

> I guess "quadtree" means something different to you than it does to me. I
> thought it was a kind of spatial indexing system used often in 3-d graphics
> applications.

                We are talking about the same thing (quadtree is one form of 
structure to access image data, and has various generalizations).

> > > I would prefer to see sophisticated operations taking iterator
> parameters
> > > (possibly among others) as available, rather than building sophisticated
> > > behavior into the iterators themselves.
> >
> > One (among many) ways to see things is to remember that the
> > mathematical definition of a matrix is a function (not the
> > representation of some linear or bilinear operator, that comes as a
> > fringe benefit, but as a function from some subset of NxN (or greater)
> > to whatever set we are considering for values).
> 
> That view corresponds well with the linear algebra concepts we've been
> looking at.
> 
> > An iterator is,
> > basicaly, some form of bijection from a subset of N into the set of
> > indices we are interested in.
> 
> I'm not sure if that part rings true. Maybe you should clarify a bit.

                Well, bijection is too stringent. Injection is enough. 
Bijection is when we want to access each and every index one time, and 
one time only. Injection is when we only want to see some indices, but 
each index is accessed only once (in this case it is understood that 
this index is actually representative of a class, for instance the 
index may designate the "row", or "column" of a matrix, or a "cell" of 
a quadtree, or a "block" when we hav block matrices, or a "band" when 
we have band matrices). I believe we need at least injection (we do not 
want to see one index more then once in each traversal) in practice.

                The begining iterator is just the image of 0 by the 
injection, after the first increment we have the value of 1, etc. .

> > A 'behaviour' is then simply some
> > function from the set of indices to itself.
> 
> Maybe you should give an example of what you've got in mind.

                A behaviour could be accessing each index in the order [0,0], 
[1,0],..., [N,0], [0,1],..., [N,M], another would be accessing in the 
order [0,0], [0,1],..., [0,N], [1,0],..., [N,M], yet another (when N == 
M) would be acessing them in quadtree-key order.

                These are all bijections from {0,...,N}x{0,...,M} to itself, 
though they may perhaps appear more clearly as bijections from {0,..., 
(N+1)(M+1)} to {0,...,N}x{0,...,M} (hence it might perhaps be 
advantageous to consider injections of {0,..., (N+1)(M+1)} into itself 
rather than from {0,...,N}x{0,...,M} into itself, but this moves the 
problem from defining iterator adaptors into building the capacity into 
the iterators themselves, perhaps as a policy...).

                The idea is that they may be combined; this may be 
interesting, for instance, to automatically generate reverse iteration 
from forward iteration (and just one implementation of reverse 
iteration).

[SNIP]

> -Dave

                Hubert Holin
                Hubert.Holin_at_[hidden]