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: Erik Erlandson (eerlands_at_[hidden])
Date: 2011-05-09 18:40:34

On Fri, 2011-05-06 at 14:38 -0500, Rene Rivera wrote:

> 
> > 3) I don't feel like I'm understanding the motivation for cursors versus
> > iterators.  Is there an "elevator pitch" for that?
> 
> 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.

As far as that goes, it makes sense as an abstraction and seems like a
really useful extension of the STL Concept hierarchy.

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 don't know if this is an ambiguity of the design, or just the
documentation, or my incomplete understanding.    Does anybody have
insight?