Re: [boost] [tree] Reviving the tree library

Subject: Re: [boost] [tree] Reviving the tree library
From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2011-05-06 15:38:30

On 5/5/2011 6:46 PM, Erik Erlandson wrote:
> On Wed, 2011-05-04 at 17:17 -0500, Rene Rivera wrote:
>
>> It looks like Bernhard stopped development 1.5 years ago. Which sure
>> sounds like it's orphaned. Given that I've copied it over to
>> sandbox/tree location (the last trunk state for it). I'm willing to help
>> out in moving the library forward, especially since it's based on some
>> of the core concepts I suggested. Who else is willing to help out in
>> improving and finishing this lib? Note, that helping out involves
>> thinking about adjusting the TR proposal so that it can be submitted for
>> the soon to start up again TR2.
>>
>>
>
> I have a few questions regarding the TR2 tree iterators
>
> 1) I would recommend a breadth-first iterator

Right. There are many additional traversal algorithms possible. And the 
specification of the pre-defined ones is one of the week points of the 
current TR.

> 2) What is the semantic of in-order traversal for a non-binary tree?

Even though it's only implied I think it's left-to-right in-order traversal.

> 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.

Longer:

Because of the additional cardinality of trees the current std model of 
iterators doesn't allow for a compact mapping to trees. Even though it's 
possible to define a group of iterator, node, and function interfaces to 
accomplish the same task it makes it harder to conceptualize algorithms 
when one has to deal with two or three types of iterators at once. 
Essentially it's possible to write generic algorithms entirely on the 
single cursor concept without really having to think about the 
particular context. And I'm not talking only about user visible 
algorithms here. I'm also including usually internal algorithms. For 
example it's possible to write generic tree balancing algorithms using 
cursors that would be rather mind bending with just iterators (and 
usually would require direct access to the nodes).

Note, it's likely the current TR doesn't actually deliver on the 
entirety of the above though ;-)

> Also, a question regarding the definition of 'multi-way' tree:   My
> reaction to 'multi-way' is: 'synonym for n-ary', but that appears to not
> be the idea.  What makes a binary tree "multi-way" and an nary tree not
> multi-way?

Don't have an answer for that.. multi-way is a term Bernhard came up 
with. Which I never really understood either. So I'll have to get back 
to you on that.

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org (msn) - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail