Boost logo

Boost :

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

"David B. Held" <dheld_at_[hidden]> wrote in message
>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,

Boost list run by bdawes at, gregod at, cpdaniel at, john at