Re: [boost] Re: any interest in a 'tree' container?

From: Victor A. Wagner, Jr. (vawjr_at_[hidden])
Date: 2002-10-12 22:09:09

At Friday 2002/10/11 01:06, you wrote:
> > I have only briefly looked over the documentation. Are you using a
> > quad-linked structure to avoid link allocations (i.e. the links are 
> embedded
> > in the nodes)?
>
>Yes, the nodes are
>
>   template<class T>
>   struct tree_node_ {
>                   tree_node_<T> *parent;
>                   tree_node_<T> *first_child, *last_child;
>                   tree_node_<T> *prev_sibling, *next_sibling;
>                   T data;
>   };

At my previous job, we inherited a data structure which could have been 
refactored into your tree_node_<>
We were asked to make an "iterator" for another group and these guys had 
never heard of the STL.  In their architecture, "containers" were defined 
by the iterators, the data was "just there".   Since in a "tree" it's 
somewhat ambiguous as to whether a "node" is just a data element, or if 
it's a container (itself and all it's children) we came up with a concept 
we were calling a containerator.  Unfortunately, a serious downturn in 
business cost us 35% of the people (including me) and I don't know what 
happened to the project.  The interface for the containerator looked like:

class Containerator : public std::iterator<std::bidirectional_iterator_tag, 
DataNode>
{
public:
         Containerator(); 
//!<default constructor
         Containerator(const Containerator& i);                  //!<copy 
constructor
         explicit Containerator(DataNode* ptr);              //!<make 
iterator from a pointer
         ~Containerator();
         Containerator& operator =(const Containerator& i);
         DataNode& operator *()const;
         DataNode* operator ->()const;
         Containerator& operator ++();
         const Containerator operator ++(int);
         Containerator& operator --();
         const Containerator operator --(int);
         Containerator begin()const;
         Containerator end()const;
         bool operator ==(const Containerator& rhs)const;
         bool operator !=(const Containerator& rhs)const;
         bool operator !() const;
protected:
         DataNode* where_we_are;
};

Note that sizeof Containerator<> is only the same size as a pointer to your 
tree_node_

I still have some of the preliminary code we were putting together if 
you're interested.
The ++ operators traversed in node, child0, child1, child2.... order
The -- operators in   childn, childn-1, childn-2...child0, node  order

>For very small-size objects 'T' this is of course a lot of overhead,
>and perhaps a singly linked list would be preferable in this case (I
>guess this is one of the reasons why Herve wants the class to be
>templated over the container class in which the children are stored,
>right?).
>
>Kasper
>_______________________________________________
>Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Victor A. Wagner Jr.      http://rudbek.com
PGP RSA fingerprint = 4D20 EBF6 0101 B069 3817 8DBF C846 E47A
PGP D-H fingerprint = 98BC 65E3 1A19 43EC 3908 65B9 F755 E6F4 63BB 9D93
The five most dangerous words in the English language:
               "There oughta be a law"