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,
> 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: http://www.boost.org Unsubscribe:
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
-- Sean Parent Sr. Computer Scientist II Advanced Technology Group Adobe Systems Incorporated sparent_at_[hidden]
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk