Boost logo

Boost :

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

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk