Re: n-ary ordered tree template in boost ??

On Mon, 02 Sep 2002 10:47:42 +0200, Matthias Kronenberger wrote:

You could chose to emulate such an tree using a std::multimap. Which maps the father vertex id to the child vertices. you can also specify your own ordering relation. To access all children is trivial, if you want to access all grandchilds and so own, you'd have to create a nice adapter class, that connects all children of children ranges together.

I thought of this, too, but then, there is a simpler emulation using the property that an N-ary ordered tree has nodes with either no child or exactly N childeren. This menas that we can number the nodes of a complete tree by (if N=3) level 0: 0 level 1: 1 2 3 level 2: 4 5 6 7 8 9 10 11 12 and so on. Very simple calculations then give the id numbers of all children of a given parent, or the parent of a given child, and so on. If the tree is not complete, some of the groups are missing, but the same ordering can still be applied. Putting this in a pair, we can store it in a map, not a multimap, and we have automagically iterators which parse the tree in levels. The concept is quite simple, but usefull, at least if you want to parse efficiently horizontally. If you want to parse up-down, it requires an O(log n) lookup in the map, and then you probably want to implement this thing in a pointer-to-children and pointer-to parent fashion for efficiency. But this get us back to the original question: 2) An N-ary ordered tree is such a basic concept that it is funny that neither STL or Boost offers it. Would it be welcome by the Boost community if it get proposed and included into the Boost libs ??? cheers, Marc Cromme