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
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.
Cromwell D. Enage
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk