Subject: Re: [boost] [tree] tree cursors and iterators (was: Reviving the tree library)
From: Cromwell Enage (sponage_at_[hidden])
Date: 2011-05-10 15:11:04
--- On Mon, 5/9/11, Erik Erlandson wrote:
> On Fri, 2011-05-06 at 14:38 -0500, Rene Rivera wrote:
> > Single sentence:
> >
> > Cursors provide an abstraction for *all* the possible
> > traversals of trees vs. the linear only traversals of
> > iterators in a single object making it possible to
> > base the expanse of tree algorithms solely on cursors.
>
> I've been trying to sort out the semantics of tree
> cursors. One thing seems fairly clear: cursors embody
> the semantics for what more traditionally are defined as
> 'nodes': A cursor has 'begin()' and 'end()' methods
> that refer to the children of that cursor. The Cursor
> concept inherits from the Container concept, since a
> cursor (like a "node") is, recursively, a container of
> cursors.
To me, a cursor is a hierarchical node iterator: an iterator that is itself a range of its children.
> Given the above, I get a bit confused about the meaning
> of methods like inorder_first(). A cursor, as defined
> above, seems to not mesh with any particular traversal
> mode. And the increment operators '++' seem to make
> sense only as 'increment to the next sibling.'
I couldn't find inorder_first() in the tree proposal. Did you mean inorder::begin(), which is a namespace-level algorithm?
And yes, it doesn't look like a cursor is meant to be a drop-in replacement for a breadth-first or depth-first iterator, but that both can be defined in terms of cursors.
> I don't know if this is an ambiguity of the design, or
> just the documentation, or my incomplete understanding.
The documentation looks sparse, which is probably why Rene Rivera called for improvements to it.
HTH,
Cromwell D. Enage