Re: [boost] [tree] tree cursors and iterators (was: Reviving the tree library)

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