[boost] Re: graph structure interface (proxies and forward it erators)

From: scleary_at_[hidden]
Date: 1999-12-10 11:44:27

> From: scleary_at_[hidden] [mailto:scleary_at_[hidden]]
> > P.S. I've fooled around with this before, and made a "mayfly_iterator"
> > class, templated on a Generator and a type, which generates
> > its results on the fly when dereferenced.  It is basically a
> > generalized proxy iterator.
> > I've demoted it to "experimental" because of the problems
> > with iterator tags.  It's a simple class, exactly what you
> > would expect, but I'll post it if there's interest.
>
> Please do. I'm having difficulty following the discussion in the abstract.
A
> concrete example might help...
>

Here you go.  I'm sorry this took so long to get to you.  Also, I'm not sure
how much it will help -- this is one case where the code may complicate the
issue.

Actually, I originally wrote this class with the intention of using it to
write a generic graph library similar to GGCL.  The mayfly_iterator class is
very simple; it wraps around an iterator of any type and a generator object.
Most of the iterator abilities (increment, random access, etc.) are passed
through to the underlying iterator; when it is dereferenced, it returns an
object created by the generator called with the argument of the dereferenced
internal iterator.

The code for mayfly_iterator is "experimental" because it currently pretends
to be in the same iterator category as the iterator it wraps around.  (By
the current Standard definitions, it cannot be Forward or higher -- it can
only be Input).  I do not know of a workaround for this.

Just a word on mayfly objects in general: the design pattern of mayfly
objects is very powerful; they allow advanced and easier-to-use requirements
to be satisfied in a run-time- and memory- efficient manner.  For example,
if you look at the original GGCL specs, a "ContainerRef" is basically a
mayfly container (that doesn't own its objects); this could allow, for a
vertex "v": "v.in_edges()" to return a ContainerRef of edges going into this
vertex, "v.out_edges()" to return a ContainerRef of edges leaving this
vertex, and "v.edges()" to return a ContainerRef of edges incident on this
vertex, but each of these functions taking constant time.  Conceptually,
[v.in_edges() + v.out_edges()] == v.edges().  However, ContainerRef objects
usually consist of one or two references or pointers to the underlying
(actual) container, and only *appear* to be containers, so they are far more
efficient, as opposed to using actual containers.

Optimizing compilers in many cases can optimize away mayfly objects
completely; thus, mayfly objects are nice to allow complicated semantics
with no overhead.

Hope this helps.

        -Steve