[boost] Re: Boost library inclusion: generic tree containers?

From: Justin Gottschlich (jgottschlich_at_[hidden])
Date: 2005-02-27 14:18:00

"David B. Held" <dheld_at_[hidden]> wrote in message 
news:cvqlqp$fnk$1_at_sea.gmane.org...
>I see I'm a little late to the party.  However, I'd like to
> summarize what I have noticed as the important concepts that
> have been exposed, and chip in my own 2c.  I think the core
> concept that should be recognized is that a tree is not a
> container of objects, but a container of containers.

Yes, I couldn't agree more. =)

> Second, trees are complicated because there are two sets of
> iterators that need to be addressed.  First is the iterator
> over objects in the root, and second is the iterator over
> children.  However, they are two separate kinds of iterators.

Well, I think this depends on how the tree's structure is formed. I think 
it's possible to achieve the tree building with a single iterator type and 
then add additional iterators as needed. The reason I say this is that if 
you consider the initial tree object as the "root node" (owning one of the 
contained objects of the tree), you should only need a single iterator type 
since by definition a tree can only have one root node. Since you wouldn't 
need to iterator over the objects contained within the root level as by 
definition, they'd be children of the root node. At least, this is how I 
handled this problem in my tree container. Nonetheless, as you've pointed 
out Dave - this is a very important issue to tackle, regardless of the way 
you attack it. =)

> I haven't been able to look at Jeff's library because I can't
> seem to access his web site

I've sent Jeff a couple e-mails and am requesting he present his tree 
container ideas to the Boost group before Joao and I continue to work on 
building the generic base tree type, as his solution may be the solution to 
use. The last thing I want to do is overlook his design since it seems quite 
nice - although I have some questions about some of its functionality and 
reasoning behind some implementation details. I've asked Jeff if he could 
write some sample code showing how to build some basic trees and present 
that to the group. I hope he can find time to do this as I don't want anyone 
to feel "slighted" regarding any of their tree designs. Whatever happens I 
think we need to maintain our forward momentuum (which we've been doing 
wonderfully), without it this tree discussion could easily fall prey to what 
happened to Kasper Peeter's tree discussion in 2002. =( I don't think any of 
us want to see that happen.

> Finally, flat iterators would have to be built on
> top of the two iterator types presented by the tree itself.

Yes, I'm with you on that logic.

> Clearly, the tree invariants would need to be carefully preserved
> by the algorithms which operate on them.  But since different
> trees have different invariants, it makes more sense to group
> the algorithms by the set of common invariants they enforce,
> rather than by a concrete tree type.  Some algorithms will have
> very few invariant requirements, such as find_first() and find_last(),
> and will work on any ordered tree.  Others may have more stringent
> requirements, but defining the tree as a pair of tuples and a set
> of algorithms on those tuples seems like the best factorization
> of behaviors possible.

Ummm, hmmm. I need to think about this some more. =)

Thanks for the great feedback Dave,
Justin