# Boost :

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]