Re: [boost] any interest in a 'tree' container?

From: Samuel Krempp (krempp_at_[hidden])
Date: 2002-10-10 09:41:27

Le jeu 10/10/2002 à 10:55, Kasper Peeters a écrit :
> Dear all,
> 
> I have written a templated 'tree' container class which has been
> available for some time under the GPL. Every node in the tree can have
> an arbitrary number of children, and iterators are present for
> depth-first traversal of the entire tree or for traversal of only a
> range of nodes which are siblings of each other. 

iterators are definitely what makes the difference between tree classes.

2 years ago I needed a tree class with iterators (depth-first AND
breadth-first), 
I finally had to implement my own, so I wrote it very specialised for my
needs (strange complicated stuff that allows building 'recursive trees',
via 'teleportation nodes' ..),  so I'd say there is interest for a tree
container with good iterators.

I looked at your increment_() (I would call it iterate_, but well) and I
think purists have a precise name for this iteration scheme. I was told
my iteration was not true "depth-first", because it picks father before
son, and I think your iteration is the same. I vaguely recall names like
"prefix depth-first", or suffix, or whatever.. but you'd need to know
the precise litterature name for this  for a boost submission.

BTW, I could contribute a breadth-first iteration. (implemented with a
loop, no additional iterator-state required).

Though, I think a requirement of this code is to be able to ask for the
indice of the current node among its siblings, e.g. 1 for the first son,
2 for the second, and I guess it would thus require an extra method
somewhere.

Ah, also, I found it very useful to provide 'path' functions, ie
bijections between nodes position and a sub-set of strings. 

I personally came to use a kind of tokens notation, S1 for son 1, R for
Root, ..e.g. :
iterator it;
it = tree.begin();
++it; // goes to the first son.
it.go("S3"); // relative path, takes third son of current node
string s = it.path();  // "R S1 S3" 
it.go(" R S2 S1"); // absolute path
s = it.path();         // "R S2 S1"

for full use as relative paths, it needs extra tokens, e.g. 'F' - father
just like file-system's '..'

So, yes, in my opinion a tree class is interesting, it could provide
several useful features that are completely absent from other
containers, while still being very general. 

(The most similar containers I see are binary trees, and generic graphs
- cf Boost.graph. both certainly don't overlap much with what would be
provided in a Boost.Tree class)

-- 
Samuel