Re: [boost] hierarchical container

From: Ken Shaw (ken_at_[hidden])
Date: 2001-10-29 18:14:27

Sean,

You seem to be much further along than I am. I would be happy to either work
with you if you need any help or if you are not going to be able to submit
because of legal issues keep working on my not too disimiliar version. Would
you let me know what your feeling is on this?

Thanks
Ken Shaw
ken_at_[hidden]
Programming Manager
Computer Innovations
Chicago IL

----- Original Message -----
From: "Sean Parent" <sparent_at_[hidden]>
To: "boost yahoogroups.com" <boost_at_[hidden]>
Sent: Monday, October 29, 2001 4:33 PM
Subject: Re: [boost] hierarchical container

> 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]
>
>
>
> 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/
>
>