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