Re: [boost] Re: boost::tree advice?

From: Dan Rosen (dan.rosen_at_[hidden])
Date: 2005-03-28 12:11:24

Hi João,

> In my design nodes were made an implementation detail but I also
> attempted to define some node concepts to allow advanced users to plug
> their own node types into pre-defined trees.

I'm curious what one would do with that ability ... what kind of use
cases were you picturing? I've been attempting not to expose nodes in
the interface, but maybe there's a reason why I should?

> I'd be interested in looking at the details, however draft they are
> (Feel free to mail them privately).

Actually, I shouldn't be such a tease. I'll try to get the document
semi-workable and post it here when I get back from work this evening.

> > I have a couple "selector" structs,
> > basically identical to Boost Graph Library's vecS, listS, etc, and the
> > tree<> class template takes one of these selectors as a template
> > parameter.
> 
> I'm not sure if you're referring to the standard containers here. I
> initially considered using those, after considering allocator issues and
> the (potentially) large per-node overhead I almost completely dropped
> the idea.

Well, vecS and listS do refer specifically to the standard containers,
but my idea was that you could plug any container conforming to the
standard Sequence concept into the tree. But yes, the overhead is one
of the aspects of this approach that's been plaguing me.

> Right now, I'm pondering on a node concept based on boost::range, plus
> some free functions (insert, update, erase...) that would allow greater
> flexibility and extensibility, with no overhead.

I haven't looked at boost::range at all. I'll check that out!

> Personally, I prefer a tree-iterator concept that allows traversal of
> the tree without needing to carry the tree around. Having children as a
> member function of the tree prevents this.

Oh, I think I was unclear, sorry. I wanted to provide children() as a
convenience, rather than as a necessary method for traversal and
mutation of the tree. In lieu of having a document prepared, let me
give you a little more detail on my basic idea for the concepts behind
the tree.

The basic building blocks are what I've been calling a "Multiply
Traversable Container" and a "Traversal", which go hand in hand. The
notion is that if there is no single, canonical traversal of a
container from beginning to end (unlike the present standard
containers which are all "flat"), I still want to be able to ask for a
begin() and an end() and use standard algorithms on an iterator range.
So iterators and member functions such as begin() and end() are
parametrized on a traversal policy. In the case of the Tree concept,
I've provided the obvious ones:

  X::pre_order_traversal
  X::post_order_traversal
  X::depth_first_traversal
  X::breadth_first_traversal
  X::sibling_traversal
  X::first_descendant_traversal
  X::last_descendant_traversal

The first four traverse the whole tree, whereas the second three may traverse
only a subset of the tree.

One outcome of having multiple potential traversals is that, although
it still makes sense for a Multiply Traversable Container to be
EqualityComparable, it no longer makes sense to be LessThanComparable.
So I also thought, in the event that you actually want to compare two
trees (or other multiply-traversable containers) via operator <, I
could provide a little wrapper utility (I've called this
"single_traversal") modelling the standard Container concept, which
hangs onto a traversal policy and gives you only a single iterator
type.

Anyway, I'm omitting a lot of detail here (Multiply Traversable
Container is split up into Forward, Reversable and Random Access
variants, and I also have a separate Binary Tree concept, which
provides in-order iterators, etc.), but hopefully this gives you a
better basic idea of what I'm going for.

> That's one of the reasons I decided to define a TreeIterator concept
> that overlaps with the standard Iterator concept when it comes to
> sibling traversal.
> [snip]
> On the thread Justin Gottschlich started on this issue
> (http://tinyurl.com/44e3u), I suggested pre-order and other
> linearizations of a tree could be provided externally. I think putting
> these on the tree unnecessarily complicates the design of the tree and
> the iterators.

So, hopefully my comments above illustrate my opinions on this. I
think the minimum set of iterators necessary to build all other tree
iterators on (with reasonable efficiency) is
first_descendant_iterator, last_descendant_iterator, and
sibling_iterator. If I understand you correctly, I think that jives
with what you're saying, and seems to be in rough agreement with the
general consensus in Justin's thread. But I think it's a good thing to
have the full set of traversals in the tree as well, even if for no
other reason than for consistency with those three "fundamental"
traversals.

> I solved parent/root issue by having the tree class promise only the
> most basic TreeIterator: for traversal from parent to child. [snip]
> From the initial root iterator one could get SiblingIterators for
> iteration over its children.

So, from your description, I'm picturing two things:

  - A TreeIterator is an extension of the standard iterator concept
that provides an additional method, something like children(), which
returns a SiblingIterator, to provide access to a node's children.
  - The only way to get a SiblingIterator is via a TreeIterator's
children() method.

I'm not sure if this is what you were implying or not. But in my own
design, I was thinking two things: first, my iterators do not extend
the standard Iterator concept, and second, all iterator types should
be convertible to each other. For example, if I'm doing a pre-order
traversal of a tree -- maybe as a means of searching -- and I find an
interesting element, I might want to convert my iterator to a sibling
iterator to deal with the siblings of the element I've found. That
implies that even for the root of the tree, I should be able to get a
sibling iterator to point to it (though it would have no previous or
next siblings).

> Depending on the underlying node, both iterators could actually be the
> same. This could be inspected through separate traits classes.

Hmm, this gets back to the question about providing a node concept and
interface. I'm having trouble picturing what you're describing here.

> My idea was to write the basic single and double-linked lists
> operations from scratch. We don't be need the whole std::list interface
> for the nodes anyway.

I think I tend to agree now. I'd like to be able to plug in arbitrary
sequences (including std::list) to represent a node's children, but
that seems to come encumbered with too many penalties. On the other
hand, I'm still soliciting clever approaches to this problem, and I'm
still curious whether (despite having given up on it) you think it's a
good idea conceptually.

I think at this point (lacking a decent solution for the pluggable
child sequence problem) if I were to provide a tree::children() method
to expose a child sequence, the sequence returned still should conform
to the standard Sequence concept, but needn't literally be a
std::vector, std::list, or whatever.

Thanks again for your insight,
dr