Re: [boost] hierarchical container

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
iterator.

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: http://www.boost.org  Unsubscribe:
> <mailto:boost-unsubscribe_at_[hidden]>
> 
> 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]