Boost logo

Boost :

From: Sean Parent (sparent_at_[hidden])
Date: 2001-10-29 17:33:59

I'm still working through the legal issues on my end of getting my libraries
posted but I have a good hierarchical container class.

I went through several iterations before I settled on this one -

The internal structure is a "pre-traversed" tree. Each node contains four
pointers joined as forward/back pairs. Each pair follows a pre/post order
depth first traversal. The base iterators (a full iterator) point to a
specific pair on the node, and also track relative depth so that depth need
not be stored in the nodes.

The final structure is a forest of trees. The dangling ends of the traversal
are looped over on top (which eliminates most special cases).

Fully bi-directional iterators provide depth first pre, post and in -order
traversals. As well as a "full order" iterator that visits every node twice
and reports leading or trailing edge. Very handy for generating XML.

There is also a forward iterator for parents, and bi-directional for
siblings. I have done breadth first iterators (or adaptors) but believe that
are doable without added complications.

Insert is a simple splice operation and erase can be done in linear time
removing all nodes for which a full traversal passes through the node twice.

As for types of trees. There are certainly choices for internal structure
(this represents my 3rd or 4th attempt at something useful) - but a quick
read of Knuth will show that a forest of tree's is equivalent to a binary
tree, and balancing operations are built out of general primitives (like
rotate). As such these operations and structures could be built as adaptors
and algorithms on a general tree structure - just as heaps and stacks are
built with the current STL.

Here is a snippit that generates formatted XML from a tree (elements only
for a short example) but it demonstrates tying the depth and edge to the

typedef tree<int>::fullorder_iterator fullorder;
for (fullorder iter (foo.begin<fullorder>());
        iter != foo.end<fullorder>(); ++iter)
        for (int i = 0; i < iter.depth(); ++i)
            cout << " ";
        cout << "<";
        if (!iter.leading()) cout << "/";
        cout << *iter << ">" << endl;

on 10/28/01 9:48 AM, Jens Maurer at Jens.Maurer_at_[hidden] wrote:

> Ken Shaw wrote:
>> While working an xml parser for a project I came to the conclusion that no
>> standard container would easily support the storage of the various elements
>> in the document while retaining the inherent structure of the document. So I
>> started writing a tree container based on the STL container interface.
> Certainly, a "tree container" will not only have begin() / end() members
> for linear iteration, but will also support tree-like iteration (down, up,
> etc.)
> Furthermore, there may be several different possible implementations for
> a tree container (B-tree, binary tree, balanced binary tree). Therefore, I'd
> like to see a "TreeContainer" concept (probably together with a
> "TreeIterator") defined, instead of just having some code.
> Jens Maurer
> Info: Unsubscribe:
> <mailto:boost-unsubscribe_at_[hidden]>
> Your use of Yahoo! Groups is subject to

Sean Parent
Sr. Computer Scientist II
Advanced Technology Group
Adobe Systems Incorporated

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