• Advertisement

Archived

This topic is now archived and is closed to further replies.

STL style n-ary trees

This topic is 4962 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello I’m writing an STL like n-ary tree container so i can use it for stuff like Scene Graphs, and other interesting things. I need your advice please, I know there is one on the net but I think its been implemented horribly in my opinion. Basically I took GCC implementation of Red-Black tree, modified it into a n-ary tree and all is fine so far I can build generic trees very efficiently, if people are interested and i''m more than happy to release it for use by anyone once its complete. At the moment the problem I’m having is figuring out how to deal with begin and end methods in amortized constant time as the standard specifies with the various methods of iteration also what would be a valid begin and end?. I have written some Iterators for pre, post order iteration (others to follow) the problem is that begin and end iterators are different for the type of traversal. In the tree type there is a header member that maintains a pointer to the root of the tree I was wondering if I should also use the other members of the header to point to the very bottom most last and first child that always gets updated when another value is inserted. Then the begin and end methods would become constant time, do you think this is a good idea?

Share this post


Link to post
Share on other sites
Advertisement
If you use different kinds of iterators for different traversals, I don''t think there''s any good method of specifying a single begin() member function. It''s probably better to specify a different member function for each kind of traversal, like how standard container classes have both begin() for forward traversal and rbegin() for reverse traversals.

For specifying the end() for a tree traversal, I can think of two basic approaches. One is to just to use a sentinal value of some sort, like a special empty node in your tree. The other is to have a special end representation for your iterator. For example, if your iterators store pointers to nodes, then have an end iterator have a null pointer.

Share this post


Link to post
Share on other sites
quote:
Original post by SiCrane
If you use different kinds of iterators for different traversals, I don't think there's any good method of specifying a single begin() member function. It's probably better to specify a different member function for each kind of traversal, like how standard container classes have both begin() for forward traversal and rbegin() for reverse traversals.

For specifying the end() for a tree traversal, I can think of two basic approaches. One is to just to use a sentinal value of some sort, like a special empty node in your tree. The other is to have a special end representation for your iterator. For example, if your iterators store pointers to nodes, then have an end iterator have a null pointer.


The way i'm handling the different types of traversal is by making it a policy so i have only two Iterators iterator & const_iterator that are parameterized by traversal schemes, and delegates the algorithm to one of the traversal schemes. There is also methods of reverse iterators, i just use a typedef std::reverse_iterators passing my iterator type to its parameter.

I make a typedef default iterators for pre-order and normal begin/end/rbegin/rend methods with that i also provide templated versions of begin/end/rbegin/rend that take a traversal schemes. The problem with that is because the tree is already a parameterized type when i try specialize the inner templated methods i get errors. Can you specialize templated methods of an already parameterized type?

With your two approaches i'm acutally doing your first one already and using the address of the header as a sentinal, i just thought it might not be the same begin/end for all the types of traversal. Like with post-order iteration the first iterator will have to refer to the bottom most first child.

[edited by - snk_kid on June 10, 2004 3:52:06 AM]

Share this post


Link to post
Share on other sites
I've always wondered why there wasnt a generalised tree in the STL. Seems like a fairly common data structure to me.
Would you mind posting your code when your done?
Cheers.

EDIT:
found a gpl n-ary tree implementation here

(fixed link)

[edited by - aboeing on June 10, 2004 9:00:12 AM]

Share this post


Link to post
Share on other sites
Yes i've seen that one already but i don't like it, it seems like it could be implementated way better and its interface is completely bloated, they also make distinction between a iterators i believe you don't need to.

There is also one in the Game Programming Gems 4 but its a completely ridiculous implementation there view is of it is rubbish.

I'd say that the advantage of mine is that its been implementated in terms of an already robust and very efficent implementation of already simillar type, gcc's version of red-black tree.

You can think of its interface is an intersection of STL's red-black tree & the STL's sets, a simple interface.

Also its extendable, just provide a new traversal policy/scheme type, chuck it into a iterator/const_iterator that comes with it and thats it.

[edited by - snk_kid on June 10, 2004 6:02:09 AM]

Share this post


Link to post
Share on other sites
cool, I've been wanting to do this for some time. more specificly, doing a quad/oct-tree that follows the flow of STL. But my idea was kinda hammered and I was to dum to believe that STL can't be predictable in terms of speed, since it would be MY tree it would be super predictable!

Please post the code when you're done. Sorry I don't have any tips, but my old thread might have some? Click here.

}-- Programmer/Gamer/Dreamer --{
I didn't choose to code, coding choose me.

(edit: forgot the bloody link )

[edited by - seriema on June 10, 2004 5:39:23 AM]

Share this post


Link to post
Share on other sites
I'm almost ready to post/submit the code; it has 4 standard iterator types, iterator & const_iterator and reverse versions. They are parameterized by traversal schemes. Depth first iteration via pre & post order which are reversible and end up being the other e.g. a reverse pre-order is identical to post-order the other way. Breadth first iteration currently no proper reverse support because I thought it didn’t make sense to have a begin method for it but you can move backwards with the forward iterators.

I believe sibling iterators are pointless so I’m thinking of having a method called children that returns a std:: pair of suitable iterators to the beginning and end of the children list.

If people are interested I would like to read any standard features that should be included before I post soon.

edit: Compiled on GCC 3.4 & VS.NET 2003

[edited by - snk_kid on June 13, 2004 5:56:30 PM]

Share this post


Link to post
Share on other sites
Do you need your own reverse iterator type?

Won''t std::reverse_iterator do the trick?

Share this post


Link to post
Share on other sites
quote:
Original post by DrPizza
Do you need your own reverse iterator type?

Won''t std::reverse_iterator do the trick?



Yep already using it, sorry if i wasn''t clear enough

Share this post


Link to post
Share on other sites
I'll try to think of some, and update (i.e. edit) this post when something pops up.

1) Do you have the standard typedefs such as value_type and others?

2) Have you tested your iterators with different std::algorithms?

Share this post


Link to post
Share on other sites
Sorry it took a while, well i'm ready to release version 0.1 but before i do, as this is originally from the GCC implementation of a red-black tree (but major modifification) should i copy and paste the GNU licensing comments to the top of the code?

Share this post


Link to post
Share on other sites
I have a custom linked list that I use which has a "GetFirst()" and "GetLast()" member function. Depending on which one you call, the "GetNext()" function will either return the previous, or the next element. The list contains pointers to both head & tail, and each node contains a previous and next pointer.

I think something like that is probably the way to go if you have multiple transversal methods.

Share this post


Link to post
Share on other sites
Quote:
Original post by Etnu
I have a custom linked list that I use which has a "GetFirst()" and "GetLast()" member function. Depending on which one you call, the "GetNext()" function will either return the previous, or the next element. The list contains pointers to both head & tail, and each node contains a previous and next pointer.

I think something like that is probably the way to go if you have multiple transversal methods.


Its okay i've already sorted the iterators out a while ago, there is two iterators constant and non constant iterator types which are parameterized by traversal scheme and you can copy/construct any iterators with any iterators with other types of traversal scheme.

I'm thinking about later on to have tree_traits type so people can add new traversal schemes and drop them into the iterators

Share this post


Link to post
Share on other sites
Hi! How's the code coming along? Really curious on your work :)

How will you post your code? Are you gonna smack it up here in source-tags or are you going to host it somewhere? I've used SourceForge for several projects and I love it. If you ented on having your code open source and letting people submitt patches and bug reports, I really recommend you set up a SF account.

Hope to hear more soon!

Share this post


Link to post
Share on other sites
I was wondering whether you are familiar with the boost.graph library.

It uses STL like generic design principles. There is a lot of rationale so you might find inspiration there

Share this post


Link to post
Share on other sites
Out of curiosity, what don't you like about the tree container in GPG4? I thought the concept of no recursion to follow a pre-order traversal was a nice touch.

Share this post


Link to post
Share on other sites
Quote:
Original post by aboeing
I've always wondered why there wasnt a generalised tree in the STL. Seems like a fairly common data structure to me.


Generally because the idea of a tree is on a different level to the other STL containers. If you just wanted a balanced tree for some sort of lookup speed, then that is what std::set and std::map is for, and the tree implementation is irrelevant. And if you absolutely require a hierarchical structure, then most of the time I would expect you'd want to create custom node types that contain links to their children, and whether you used deque, list, or vector in that implementation would depend on your needs. Personally I can't ever see a time where a STL tree class wouldn't either be too low-level or too abstract for a task.

Share this post


Link to post
Share on other sites
Quote:
Original post by DrNecessiter
Out of curiosity, what don't you like about the tree container in GPG4? I thought the concept of no recursion to follow a pre-order traversal was a nice touch.


Hello all of the traversal schemes i've written don't use recursion. The reason why i didn't like there version was the way they handled the concept of it, viewing a tree as a linear sequence of trees. The way i see it the iterators allow the algorithms to view as it as linear container.

Some of the operations in there are a little strange like what does it mean to get/push/pop the front & back of a tree?

The implementation wasn't very good & the way it handles allocators seemed a little abit hacky.

I've believe mine is much better than that one & the one thats on the net as it was based off GCC implementation of red-black tree its very robust & efficent. Yes i'm ready to release it for people to critique & improve, it compiles & runs on VS.NET 2003 & GCC 3.4.

I may add a tree_traits type later on so people can add there own traversal scheme implementations and use the same 2 iterators types provided.

As it is a modified source of GCC i wasn't sure about the rules of releasing it so i've copied the license comments at the top

here is the source:
tree.hpp

// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING. If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction. Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License. This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
*
* Copyright (c) 1996,1997
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
*/


// tree type v0.1
// author: Korcan Hussein
# ifndef _KTREE_
# define _KTREE_
# ifndef _GNUC_
# ifndef __EXCEPTIONS
// Iff -fno-exceptions, transform error handling code to work without it.
# define try if (true)
# define catch(X) if (false)
# define __throw_exception_again
# else
// Else proceed normally.
# define __throw_exception_again throw
# endif
# endif
# include <cstddef>
# include <utility>
# include <algorithm>
# include <iterator>
# include <queue>

namespace std {

struct tree_node_base {

typedef tree_node_base* base_ptr;
typedef const tree_node_base* const_base_ptr;

tree_node_base* _parent;
tree_node_base* _first_child;
tree_node_base* _last_child;
tree_node_base* _pred;
tree_node_base* _succ;

static
inline base_ptr most_bottom_first_child(base_ptr __x) {
while(__x->_first_child != 0) __x = __x->_first_child;
return __x;
}

static
inline const_base_ptr most_bottom_first_child(const_base_ptr __x) {
while(__x->_first_child != 0) __x = __x->_first_child;
return __x;
}

static
inline base_ptr most_bottom_last_child(base_ptr __x) {
while(__x->_last_child != 0) __x = __x->_last_child;
return __x;
}

static
inline const_base_ptr most_bottom_last_child(const_base_ptr __x) {
while(__x->_last_child != 0) __x = __x->_last_child;
return __x;
}

};

template< typename T > struct tree_node : public tree_node_base {
typedef tree_node_base* link_type;
typedef const tree_node_base* const_link_type;
typedef T value_type;
value_type _elem;
};

/*template< typename T, typename node_t = tree_node<T> >
struct tree_traits {
typedef typename node_t::value_type value_type;
typedef const typename node_t::value_type const_value_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef value_type* pointer;
typedef const pointer const_pointer;
typedef ptrdiff_t difference_type;
typedef size_t size_type;

typedef typename node_t::link_type link_type;
typedef typename node_t::const_link_type const_link_type;

typedef node_t* node_type;
typedef const node_t* const_node_type;

static node_type _M_cast_node(link_type __x) {
return static_cast<node_type>(__x);
}

static const_node_type _M_cast_node(const_link_type __x) {
return static_cast<const_node_type>(__x);
}
};*/


struct traversal_base {
typedef tree_node_base::base_ptr _base_ptr;
typedef tree_node_base::const_base_ptr _const_base_ptr;
};

struct pre_order : public traversal_base {
pre_order(): traversal_base() {}

static
inline _base_ptr tree_increment(_base_ptr __x) {
if((__x->_first_child == 0) && (__x->_succ == 0)) {
while(__x->_parent->_succ == 0) __x = __x->_parent;
return __x->_parent->_succ;
} else
return ((__x->_first_child != 0) ? __x->_first_child : __x->_succ);
}

static
inline _const_base_ptr tree_increment(_const_base_ptr __x) {
if((__x->_first_child == 0) && (__x->_succ == 0)) {
while(__x->_parent->_succ == 0) __x = __x->_parent;
return __x->_parent->_succ;
} else
return ((__x->_first_child != 0) ? __x->_first_child : __x->_succ);
}

static
inline _base_ptr tree_decrement(_base_ptr __x) {
if((__x->_pred != 0) && (__x->_pred->_last_child != 0)) {
__x = __x->_pred;
while(__x->_last_child != 0) __x = __x->_last_child;
return __x;
} else if((__x->_pred != 0)) {
return __x->_pred;
} else {
return __x->_parent;
}
}

static
inline _const_base_ptr tree_decrement(_const_base_ptr __x) {
if((__x->_pred != 0) && (__x->_pred->_last_child != 0)) {
__x = __x->_pred;
while(__x->_last_child != 0) __x = __x->_last_child;
return __x;
} else if((__x->_pred != 0)) {
return __x->_pred;
} else {
return __x->_parent;
}
}
};

struct post_order : public traversal_base {
post_order(): traversal_base() {};

static
inline _base_ptr tree_increment(_base_ptr __x) {
if((__x->_succ != 0) && (__x->_succ->_first_child != 0)) {
__x = __x->_succ;
if(__x->_parent != 0) {
while(__x->_first_child != 0) __x = __x->_first_child;
return __x;
} else
return __x;
} else if((__x->_succ != 0)) {
return __x->_succ;
} else {
return __x->_parent;
}

}

static
inline _const_base_ptr tree_increment(_const_base_ptr __x) {
if((__x->_succ != 0) && (__x->_succ->_first_child != 0)) {
__x = __x->_succ;
if(__x->_parent != 0) {
while(__x->_first_child != 0) __x = __x->_first_child;
return __x;
} else
return __x;
} else if((__x->_succ != 0)) {
return __x->_succ;
} else {
return __x->_parent;
}
}

static
inline _base_ptr tree_decrement(_base_ptr __x) {
if((__x->_last_child == 0) && (__x->_pred == 0)) {
while(__x->_parent->_pred == 0) __x = __x->_parent;
return __x->_parent->_pred;
} else
return ((__x->_last_child != 0) ? __x->_last_child : __x->_pred);
}

static
inline _const_base_ptr tree_decrement(_const_base_ptr __x) {
if((__x->_last_child == 0) && (__x->_pred == 0)) {
while(__x->_parent->_pred == 0) __x = __x->_parent;
return __x->_parent->_pred;
} else
return ((__x->_last_child != 0) ? __x->_last_child : __x->_pred);
}

};

struct breadth_first : public traversal_base {

breadth_first(): traversal_base(), _q_of_first() {}

inline _base_ptr tree_increment(_base_ptr __x) {
if(__x->_first_child != 0) {
_q_of_first.push(__x->_first_child);
}

if(__x->_succ != 0 && __x->_parent != 0)
return __x->_succ;
else if(!_q_of_first.empty()) {
_base_ptr& __y = _q_of_first.front();
_q_of_first.pop();
return __y;
} else {
return 0;
}
}

inline _const_base_ptr tree_increment(_const_base_ptr __x) {
if(__x->_first_child != 0) {
_q_of_first.push(__x->_first_child);
}

if(__x->_succ != 0 && __x->_parent != 0)
return __x->_succ;
else if(!_q_of_first.empty()) {
_base_ptr& __y = _q_of_first.front();
_q_of_first.pop();
return __y;
} else {
return 0;
}
}

inline _base_ptr tree_decrement(_base_ptr __x) {
if(__x->_pred != 0)
return __x->_pred;
else if(__x->_parent != 0 && __x->_parent->_pred != 0) {

__x = __x->_parent->_pred;

while(__x->_pred != 0 && __x->_pred->_last_child == 0) { __x = __x->_pred; }

if(__x->_pred != 0)
return __x->_pred->_last_child;
else
return __x->_parent->_last_child;
} else if(__x->_parent == 0)
return __x->_succ;
else
return __x->_parent;

}

inline _const_base_ptr tree_decrement(_const_base_ptr __x) {
if(__x->_pred != 0)
return __x->_pred;
else if(__x->_parent != 0 && __x->_parent->_pred != 0) {

__x = __x->_parent;

while(__x->_pred != 0 && __x->_pred->_last_child == 0) { __x = __x->_pred; }

if(__x->_pred->_last_child != 0)
return __x->_pred->_last_child;
else
return __x->_parent->_last_child;
} else
return __x->_succ;
}
private:
std::queue< _base_ptr > _q_of_first;
};

template< typename item_type, typename traversal_scheme = pre_order >
class tree_iterator {


typedef tree_iterator<item_type, traversal_scheme> _self;

typedef const tree_node<item_type>* _const_link_type;
typedef tree_node<item_type>* _link_type;
typedef tree_node_base::base_ptr _base_ptr;
typedef traversal_scheme _traversal_policy;

public:

typedef std::bidirectional_iterator_tag iterator_category;
typedef ::ptrdiff_t difference_type;
typedef item_type value_type;
typedef item_type& reference;
typedef item_type* pointer;

//private:
_traversal_policy _trav_policy;
_base_ptr _M_node;

public:

tree_iterator(): _trav_policy(), _M_node(0) {}

tree_iterator(_link_type __x, const _traversal_policy& __t = _traversal_policy())
: _M_node(__x), _trav_policy(__t) { }

template< typename trav_type >
tree_iterator(const tree_iterator< item_type, trav_type >& __i)
: _M_node(__i._M_node),
_trav_policy() {}

tree_iterator(const _self& __i)
: _M_node(__i._M_node),
_trav_policy(__i._trav_policy) {}

template< typename trav_type >
_self& operator=(const tree_iterator< item_type, trav_type >& __it) {
if(this != &__it) {
_M_node = __it._M_node;
_trav_policy = _traversal_policy();
}
return *this;
}

_self& operator=(const _self& __it) {
if(this != &__it) {
_M_node = __it._M_node;
_trav_policy = __it._trav_policy;
}
return *this;
}

reference operator*() const {
return static_cast<_link_type>(_M_node)->_elem;
}

pointer operator->() const {
return &static_cast<_link_type>(_M_node)->_elem;
}

_self& operator++() {
_M_node = _trav_policy.tree_increment(_M_node);
return *this;
}

_self operator++(int) {
_self __tmp = *this;
_M_node = _trav_policy.tree_increment(_M_node);
return __tmp;
}

_self& operator--() {
_M_node = _trav_policy.tree_decrement(_M_node);
return *this;
}

_self operator--(int) {
_self __tmp = *this;
_M_node = _trav_policy.tree_decrement(_M_node);
return __tmp;
}

template<typename trav_type>
bool operator==(const tree_iterator< item_type, trav_type >& __x) const {
return _M_node == __x._M_node;
}

template< typename trav_type >
bool operator!=(const tree_iterator< item_type, trav_type >& __x) const {
return _M_node != __x._M_node;
}

bool operator==(const _self& __x) const {
return _M_node == __x._M_node;
}

bool operator!=(const _self& __x) const {
return _M_node != __x._M_node;
}
};

template<typename item_type, class traversal_scheme = pre_order >
class const_tree_iterator {


typedef const_tree_iterator<item_type> _self;
typedef tree_node_base::const_base_ptr _base_ptr;
typedef const tree_node<item_type>* _link_type;
typedef traversal_scheme _traversal_policy;

public:

typedef std::bidirectional_iterator_tag iterator_category;
typedef tree_iterator<item_type> iterator;
typedef const item_type& reference;
typedef const item_type* pointer;
typedef ptrdiff_t difference_type;
typedef item_type value_type;

//private:
_traversal_policy _trav_policy;
_base_ptr _M_node;

public:

const_tree_iterator()
: _trav_policy(),
_M_node(0) {}

const_tree_iterator(_link_type __x, const _traversal_policy& __t = _traversal_policy())
: _M_node(__x),
_trav_policy(__t) {}

template< typename trav_type >
const_tree_iterator(const tree_iterator< item_type, trav_type >& __it)
: _M_node(__it._M_node),
_trav_policy() {}

const_tree_iterator(const iterator& __it)
: _M_node(__it._M_node),
_trav_policy(__it._trav_policy) {}

template< typename trav_type >
_self& operator=(const tree_iterator< item_type, trav_type>& __it) {
if(this != &__it) {
_M_node = __it._M_node;
_trav_policy = _traversal_policy();
}
return *this;
}

_self& operator=(const iterator& __it) {
if(this != &__it) {
_M_node = __it._M_node;
_trav_policy = __it._trav_policy;
}
return *this;
}

reference operator*() const {
return static_cast<_link_type>(_M_node)->_elem;
}

pointer operator->() const {
return &static_cast<_link_type>(_M_node)->_elem;
}

_self& operator++() {
_M_node = _trav_policy.tree_increment(_M_node);
return *this;
}

_self operator++(int) {
_self __tmp = *this;
_M_node = _trav_policy.tree_increment(_M_node);
return __tmp;
}

_self& operator--() {
_M_node = _trav_policy.tree_decrement(_M_node);
return *this;
}

_self operator--(int) {
_self __tmp = *this;
_M_node = _trav_policy.tree_decrement(_M_node);
return __tmp;
}

template<typename trav_type>
bool operator==(const const_tree_iterator< item_type, trav_type >& __x) const {
return _M_node == __x._M_node;
}

template<typename trav_type>
bool operator!=(const const_tree_iterator< item_type, trav_type >& __x) const {
return _M_node != __x._M_node;
}

bool operator==(const _self& __x) const {
return _M_node == __x._M_node;
}

bool operator!=(const _self& __x) const {
return _M_node != __x._M_node;
}
};

template<typename _Val, typename trav1, typename trav2>
inline bool operator==( const tree_iterator<_Val, trav1 >& __x,
const const_tree_iterator<_Val, trav2 >& __y) {
return __x._M_node == __y._M_node;
}

template<typename _Val, typename trav1, typename trav2>
inline bool operator!=( const tree_iterator< _Val, trav1 >& __x,
const const_tree_iterator< _Val, trav2 >& __y) {
return __x._M_node != __y._M_node;
}

template<typename _Val>
inline bool operator==( const tree_iterator<_Val>& __x,
const const_tree_iterator<_Val>& __y) {
return __x._M_node == __y._M_node;
}

template< typename _Val>
inline bool operator!=( const tree_iterator<_Val>& __x,
const const_tree_iterator<_Val>& __y) {
return __x._M_node != __y._M_node;
}

template< typename item_type, typename _Alloc = std::allocator< item_type > >
class tree_base {
protected:

typedef typename _Alloc::template rebind< tree_node< item_type > >::other _node_allocator;

typedef tree_node_base* _base_ptr;
typedef const tree_node_base* _const_base_ptr;
typedef tree_node< item_type > _tree_node;
typedef _tree_node* _link_type;
typedef const _tree_node* _const_link_type;

public:

typedef item_type value_type;
typedef _Alloc allocator_type;
typedef ::size_t size_type;

protected:

struct tree_impl : public _node_allocator {
tree_node_base _M_header;
size_type _M_node_count; // Keeps track of size of tree.

tree_impl(const _node_allocator& __a = _node_allocator())
: _node_allocator(__a),
_M_node_count(0),
_M_header()
{
this->_M_header._parent = 0;
this->_M_header._first_child = &this->_M_header;
this->_M_header._last_child = &this->_M_header;
this->_M_header._pred = &this->_M_header;
this->_M_header._succ = 0;
}
};

private:

tree_impl _M_impl;

protected:

//conversion utils
static _link_type _M_parent(_base_ptr __x) {
return static_cast<_link_type>(__x->_parent);
}

static _const_link_type _M_parent(_const_base_ptr __x) {
return static_cast<_const_link_type>(__x);
}

static _link_type _M_first(_base_ptr __x) {
return static_cast<_link_type>(__x->_first_child);
}

static _const_link_type _M_first(_const_base_ptr __x) {
return static_cast<_const_link_type>(__x->_first_child);
}

static _link_type _M_last(_base_ptr __x) {
return static_cast<_link_type>(__x->_last_child);
}

static _const_link_type _M_last(_const_base_ptr __x) {
return static_cast<_const_link_type>(__x->_last_child);
}

static _link_type _M_succ(_base_ptr __x){
return static_cast<_link_type>(__x->_succ);
}

static _const_link_type _M_succ(_const_base_ptr __x) {
return static_cast<_const_link_type>(__x->_succ);
}

static _link_type _M_pred(_base_ptr __x) {
return static_cast<_link_type>(__x->_pred);
}

static _const_link_type _M_pred(_const_base_ptr __x) {
return static_cast<_const_link_type>(__x->_pred);
}

static _link_type _M_cast_node(_base_ptr __x) {
return static_cast<_link_type>(__x);
}

static _const_link_type _M_cast_node(_const_base_ptr __x) {
return static_cast<_const_link_type>(__x);
}

_base_ptr& _M_bottom_first() { return _M_impl._M_header._first_child; }

_const_base_ptr _M_bottom_first() const { return _M_impl._M_header._first_child; }

_base_ptr& _M_bottom_last() { return _M_impl._M_header._last_child; }

_const_base_ptr _M_bottom_last() const { return _M_impl._M_header._last_child; }

_base_ptr& _M_root() { return this->_M_impl._M_header._pred; }

_const_base_ptr _M_root() const { return this->_M_impl._M_header._pred; }
/////////////////////////////////////////////////////////////////////////////////

_link_type _M_pre_begin() { return static_cast<_link_type>(this->_M_impl._M_header._pred); }

_const_link_type _M_pre_begin() const { return static_cast<_const_link_type>(this->_M_impl._M_header._pred); }

_link_type _M_pre_end() { return static_cast<_link_type>(&this->_M_impl._M_header); }

_const_link_type _M_pre_end() const { return static_cast<_const_link_type>(&this->_M_impl._M_header); }

////////////////////////////////////////////////////////////////////////////////
_link_type _M_post_begin() { return static_cast<_link_type>(this->_M_impl._M_header._first_child); }

_const_link_type _M_post_begin() const { return static_cast<_const_link_type>(this->_M_impl._M_header._first_child); }

_link_type _M_post_end() { return static_cast<_link_type>(&this->_M_impl._M_header); }

_const_link_type _M_post_end() const { return static_cast<_const_link_type>(&this->_M_impl._M_header); }

/////////////////////////////////////////////////////////////////////////////////
_link_type _M_begin() { return static_cast<_link_type>(this->_M_impl._M_header._pred); }

_const_link_type _M_begin() const { return static_cast<_const_link_type>(this->_M_impl._M_header._pred); }

_link_type _M_end() { return static_cast<_link_type>(&this->_M_impl._M_header); }

_const_link_type _M_end() const { return static_cast<_const_link_type>(&this->_M_impl._M_header); }

_tree_node* _M_get_node() {
return _M_impl._node_allocator::allocate(1);
}

void _M_put_node(_tree_node* __p) {
_M_impl._node_allocator::deallocate(__p, 1);
}

_link_type _M_create_node(const item_type& __x) {
_link_type __tmp = _M_get_node();

try {
std::_Construct(&__tmp->_elem, __x);
} catch(...) {
_M_put_node(__tmp);
__throw_exception_again;
}
return __tmp;
}

_link_type _M_clone_node(_const_link_type __x) {
_link_type __tmp = _M_create_node(__x->_elem);
__tmp->_parent = 0;
__tmp->_pred = 0;
__tmp->_succ = 0;
__tmp->_first_child = 0;
__tmp->_last_child = 0;
return __tmp;
}

void _M_init() {

_M_impl._M_header._parent = 0;
_M_impl._M_header._first_child = &_M_impl._M_header;
_M_impl._M_header._last_child = &_M_impl._M_header;
_M_impl._M_header._pred = &_M_impl._M_header;
_M_impl._M_header._succ = 0;
_M_impl._M_node_count = 0;
}

_link_type
_M_copy(_const_link_type __x, _link_type __p);

size_type _M_count_nodes(_const_base_ptr) const;

void _M_swap(_base_ptr __x) {
//swap headers
_base_ptr tmp_link = _M_impl._M_header._last_child;
_M_impl._M_header._last_child = __x->_last_child;
__x->_last_child = tmp_link;

tmp_link = _M_impl._M_header._first_child;
_M_impl._M_header._first_child = __x->_first_child;
__x->_first_child = tmp_link;

tmp_link = _M_impl._M_header._pred->_succ;
_M_impl._M_header._pred->_succ = __x->_pred->_succ;
__x->_pred->_succ = tmp_link;

tmp_link = _M_impl._M_header._pred;
_M_impl._M_header._pred = __x->_pred;
__x->_pred = tmp_link;
}

void _M_detach_node(_base_ptr __x) {
if( (__x == __x->_parent->_first_child) &&
(__x == __x->_parent->_last_child)) { // most special case 0 pos is only child

__x->_parent->_first_child = 0;
__x->_parent->_last_child = 0;

} else if(__x == __x->_parent->_first_child) {// special case 1 pos is at first child

__x->_parent->_first_child = __x->_succ;
__x->_succ->_pred = 0;
__x->_succ = 0;

} else if(__x == __x->_parent->_last_child) {// special case 2 pos is at last

__x->_parent->_last_child = __x->_pred;
__x->_pred->_succ = 0;
__x->_succ = 0;

} else {// general case

__x->_pred->_succ = __x->_succ;
__x->_succ->_pred = __x->_pred;
__x->_pred = 0;
__x->_succ = 0;
}
}

//destructive erase
void _M_erase(_link_type __x);

//non-destructive single erase
void _M_erase_leaf(_link_type __pos) {

if(__pos->_parent != 0) {

if( (__pos == __pos->_parent->_first_child) &&
(__pos == __pos->_parent->_last_child)) {

__pos->_parent->_first_child = 0;
__pos->_parent->_last_child = 0;

} else if(__pos == __pos->_parent->_first_child) {

__pos->_parent->_first_child = __pos->_succ;
__pos->_succ->_pred = 0;

} else if(__pos == __pos->_parent->_last_child) {

__pos->_parent->_last_child = __pos->_pred;
__pos->_pred->_succ = 0;

} else {

__pos->_succ->_pred = __pos->_pred;
__pos->_pred->_succ = __pos->_succ;

}
}
destroy_node(__pos);
}

// non-destructive erase-all
void _M_erase_all(_link_type __pos);

void destroy_node(_link_type __p) {
std::_Destroy(&__p->_elem);
_M_put_node(__p);
}

const size_type& _M_size() const {
return _M_impl._M_node_count;
}

size_type& _M_size() {
return _M_impl._M_node_count;
}

template<typename trav_type>
_link_type _M_insert(tree_iterator< item_type, trav_type >& itr, const item_type& __v) {
_link_type __z = _M_create_node(__v);

__z->_first_child = 0;
__z->_last_child = 0;
__z->_parent = 0;
__z->_succ = 0;

if(_M_root() == _M_end()) {

__z->_succ = &_M_impl._M_header;
_M_root() = __z; //root of the tree

_M_impl._M_header._first_child = __z;
_M_impl._M_header._last_child = __z;

} else if(itr._M_node == _M_root()) {

return static_cast<_link_type>(itr._M_node);

} else {

if(itr._M_node == itr._M_node->_parent->_first_child) {
//insert front
__z->_parent = itr._M_node->_parent;
__z->_succ = itr._M_node;
itr._M_node->_pred = __z;
itr._M_node->_parent->_first_child = __z;

} else {
//insert back
__z->_parent = itr._M_node->_parent;
__z->_succ = itr._M_node;
__z->_pred = itr._M_node->_pred;
itr._M_node->_pred->_succ = __z;
itr._M_node->_pred = __z;

}

_M_bottom_first() = _tree_node::most_bottom_first_child(_M_root());
_M_bottom_last() = _tree_node::most_bottom_last_child(_M_root());
}

++_M_size();
return __z;
}

template<typename trav_type>
_link_type _M_insert_child(tree_iterator< item_type, trav_type >& itr, const item_type& __v) {
_link_type __z = _M_create_node(__v);

__z->_first_child = 0;
__z->_last_child = 0;
__z->_parent = 0;
__z->_pred = 0;
__z->_succ = 0;

if(_M_root() == _M_end()) {

__z->_succ = &_M_impl._M_header;
_M_root() = __z; //root of the tree

_M_impl._M_header._first_child = __z;
_M_impl._M_header._last_child = __z;

} else {

if(itr._M_node->_first_child == 0) {
// append front
__z->_parent = itr._M_node;
itr._M_node->_first_child = __z;
itr._M_node->_last_child = __z;
} else {
//append back
__z->_parent = itr._M_node;
__z->_pred = itr._M_node->_last_child;
itr._M_node->_last_child->_succ = __z;
itr._M_node->_last_child = __z;
}

_M_bottom_first() = _tree_node::most_bottom_first_child(_M_root());
_M_bottom_last() = _tree_node::most_bottom_last_child(_M_root());
}

++_M_size();
return __z;
}


_link_type _M_insert_child(_link_type& pos, _link_type& __z) {
if(pos->_first_child == 0) {
// append front
__z->_parent = pos;
pos->_first_child = __z;
pos->_last_child = __z;
} else {
//append back
__z->_parent = pos;
__z->_pred = pos->_last_child;
pos->_last_child->_succ = __z;
pos->_last_child = __z;
}
return __z;
}

public:

// allocation/deallocation
tree_base(const allocator_type& __a)
: _M_impl(__a) {}

~tree_base() {
if(_M_begin() != _M_end())
_M_erase(_M_begin());
}

allocator_type get_allocator() const {
return *static_cast<const _node_allocator*>(&this->_M_impl);
}
};

// destructive erase, for clear and deconstructor only
template<typename item_type, typename _Alloc >
void tree_base< item_type, _Alloc >::_M_erase(typename tree_base< item_type, _Alloc >::_link_type __x) {
//recursively destroy
_base_ptr _curr = __x->_first_child;
_base_ptr _tmp = 0;

while(_curr != 0) {
_tmp = _curr->_succ;
_M_erase(_M_cast_node(_curr));
_curr = _tmp;
}
destroy_node(__x);
}

// non destructive erase
template<typename item_type, typename _Alloc >
void tree_base< item_type, _Alloc >::_M_erase_all(typename tree_base< item_type, _Alloc >::_link_type __pos) {
_base_ptr _curr = __pos->_first_child;
_base_ptr _tmp = 0;

while(_curr != 0) {
_tmp = _curr->_succ;
_M_erase_all(_M_cast_node(_curr));
_curr = _tmp;
}

_M_erase_leaf(__pos);
}

template<typename item_type, typename _Alloc >
typename tree_base< item_type, _Alloc >::_link_type
tree_base< item_type, _Alloc >::_M_copy(typename tree_base< item_type, _Alloc >::_const_link_type __x,
typename tree_base< item_type, _Alloc >::_link_type __p) {
// Structural copy
_link_type __top = _M_clone_node(__x);

if(__p == _M_end()) {
//special case making connection with the root & header
__top->_succ = __p;
__p->_pred = __top;
} else {
__top->_parent = __p;
}

try {

_const_base_ptr _curr = __x->_first_child;
while(_curr != 0) {
_link_type new_kid = _M_copy(_M_cast_node(_curr), __top);
_M_insert_child(__top, new_kid);
_curr = _curr->_succ;
}

} catch(...) {
_M_erase(__top);
__throw_exception_again;
}
return __top;
}

template<typename item_type, typename _Alloc >
typename tree_base< item_type, _Alloc >::size_type
tree_base< item_type, _Alloc >::
_M_count_nodes(typename tree_base< item_type, _Alloc >::_const_base_ptr __x) const {
size_type size = 0;
_const_base_ptr _curr = __x->_first_child;
if(_curr != _M_end()) {
while(_curr != 0) {
size += _M_count_nodes(_curr);
_curr = _curr->_succ;
}
++size;
}

return size;
}

template< typename item_type, typename _Alloc = std::allocator< item_type > >
class tree : protected tree_base< item_type, _Alloc > {

typedef tree_base< item_type, _Alloc > _base;
typedef typename _base::_link_type _link_type;
typedef typename _base::_const_link_type _const_link_type;
typedef typename _base::_base_ptr _base_ptr;
typedef typename _base::_const_base_ptr _const_base_ptr;

using _base::_M_swap;
using _base::_M_copy;
using _base::_M_insert_child;
using _base::_M_get_node;
using _base::_M_cast_node;
using _base::_M_count_nodes;
using _base::_M_put_node;
using _base::_M_root;
using _base::_M_end;
using _base::_M_begin;
using _base::_M_pre_begin;
using _base::_M_post_begin;
using _base::_M_post_end;
using _base::_M_pre_end;
using _base::_M_size;
using _base::_M_bottom_first;
using _base::_M_bottom_last;
using _base::_M_parent;
using _base::_M_init;
using _base::_M_detach_node;

public:

using _base::get_allocator;

typedef item_type value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef ::ptrdiff_t difference_type;
typedef typename _base::size_type size_type;
typedef typename _base::allocator_type allocator_type;

typedef tree_iterator<value_type> iterator;
typedef const_tree_iterator<value_type> const_iterator;

typedef tree_iterator< value_type, pre_order > pre_order_itr;
typedef const_tree_iterator<value_type, pre_order > const_pre_order_itr;

typedef tree_iterator< value_type, post_order > post_order_itr;
typedef const_tree_iterator< value_type, post_order > const_post_order_itr;

typedef tree_iterator< value_type, breadth_first > breadth_first_itr;
typedef const_tree_iterator< value_type, breadth_first > const_breadth_first_itr;

typedef std::reverse_iterator< iterator > reverse_iterator;
typedef std::reverse_iterator< const_iterator > const_reverse_iterator;

typedef std::reverse_iterator< pre_order_itr > reverse_pre_itr;
typedef std::reverse_iterator< const_pre_order_itr > const_reverse_pre_itr;

typedef std::reverse_iterator< post_order_itr > reverse_post_itr;
typedef std::reverse_iterator< const_post_order_itr > const_reverse_post_itr;

private:
//special constructor for substree operation
tree(_base_ptr __x, const allocator_type& __a = allocator_type())
: _base(__a) {
_M_root() = __x;
__x->_succ = _M_end();
_M_bottom_first() = tree_node_base::most_bottom_first_child(_M_root());
_M_bottom_last() = tree_node_base::most_bottom_last_child(_M_root());
_M_size() = _M_count_nodes(_M_begin());
}

public:

explicit tree(const allocator_type& __a = allocator_type())
: _base(__a) {}

tree(const tree< item_type, _Alloc >& t): _base(t.get_allocator()) {
if(t._M_root() != 0 && t._M_root() != t._M_end()) {
_M_root() = _M_copy(t._M_begin(), _M_end());
_M_bottom_first() = tree_node_base::most_bottom_first_child(_M_root());
_M_bottom_last() = tree_node_base::most_bottom_last_child(_M_root());
_M_size() = t._M_size();
}
}

template< typename trav_type >
tree( tree_iterator< item_type, trav_type >& __top,
const allocator_type& __a = allocator_type())
: _base(__a) {
_M_root() = _M_copy(_M_cast_node(__top._M_node), _M_end());
_M_bottom_first() = tree_node_base::most_bottom_first_child(_M_root());
_M_bottom_last() = tree_node_base::most_bottom_last_child(_M_root());
_M_size() = _M_count_nodes(_M_begin());
}

tree<item_type, _Alloc>& operator=(const tree<item_type, _Alloc>&);

iterator begin() { return _M_begin(); }
const_iterator begin() const { return _M_begin(); }

reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }

iterator end() { return _M_end(); }
const_iterator end() const { return _M_end(); }

reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

pre_order_itr pre_begin() { return _M_pre_begin(); }
const_pre_order_itr pre_begin() const { return _M_pre_begin(); }

pre_order_itr pre_end() { return _M_pre_end(); }
const_pre_order_itr pre_end() const { return _M_pre_end(); }

post_order_itr post_begin() { return _M_post_begin(); }
const_post_order_itr post_begin() const { return _M_post_begin(); }

post_order_itr post_end() { return _M_post_end(); }
const_post_order_itr post_end() const { return _M_post_end(); }

breadth_first_itr breadth_begin() { return _M_begin(); }
const_breadth_first_itr breadth_begin() const { return _M_begin(); }

breadth_first_itr breadth_end() { return 0; }//_M_end(); }
const_breadth_first_itr breadth_end() const { return 0; }//_M_end(); }

reverse_pre_itr pre_rbegin() { return reverse_pre_itr(pre_end()); }

const_reverse_pre_itr pre_rbegin() const { return const_reverse_pre_itr(pre_end()); }

reverse_pre_itr pre_rend() { return reverse_pre_itr(pre_begin()); }

const_reverse_pre_itr pre_rend() const { return const_reverse_pre_itr(pre_begin()); }

reverse_post_itr post_rbegin() { return reverse_post_itr(_M_begin()); }

const_reverse_post_itr post_rbegin() const { return const_reverse_post_itr(_M_begin()); }

reverse_post_itr post_rend() { return reverse_post_itr(post_begin()); }

const_reverse_post_itr post_rend() const { return const_reverse_post_itr(post_begin()); }

template<class trav_type>
tree_iterator< item_type, trav_type > root() { return (_M_begin()); }

template<class trav_type>
const_tree_iterator< item_type, trav_type > root() const { return(_M_begin()); }

template<class trav_type>
std::reverse_iterator< tree_iterator< item_type, trav_type > >
rroot() {
return std::reverse_iterator< tree_iterator< item_type, trav_type > >(_M_begin());
}

template< typename trav_type >
std::reverse_iterator< const_tree_iterator< item_type, trav_type > >
rroot() const {
return std::reverse_iterator< const_tree_iterator< item_type, trav_type > >(_M_begin());
}

bool empty() const { return _M_size() == 0; }

size_type size() const { return _M_size(); }

size_type max_size() const { return size_type(-1); }

//returns number of children
template< typename trav_type >
size_type child_size(const_tree_iterator< item_type, trav_type >) const;

//returns number of children
template< typename trav_type >
size_type child_size(tree_iterator< item_type, trav_type >) const;

template< typename trav_type >
size_type depth(const_tree_iterator< item_type, trav_type >) const;

template< typename trav_type >
size_type depth(tree_iterator< item_type, trav_type >) const;

//insert sibiling
template< typename trav_type1, typename trav_type2 >
tree_iterator< item_type, trav_type2 >
insert(tree_iterator< item_type, trav_type1 >, const item_type&);

template< typename trav_type >
tree_iterator< item_type, trav_type>
insert(tree_iterator< item_type, trav_type>, const item_type&);

template< typename InputIter, typename trav_type >
void insert(tree_iterator< item_type, trav_type>, InputIter, InputIter);


template< typename trav_type1, typename trav_type2 >
tree_iterator< item_type, trav_type2 >
add_child(tree_iterator< item_type, trav_type1 >, const value_type&);

template< typename trav_type >
tree_iterator< item_type, trav_type >
add_child(tree_iterator< item_type, trav_type >, const value_type&);


template< typename InputIter, typename trav_type >
void
add_child(tree_iterator< item_type, trav_type>, InputIter, InputIter);

//destructive erase, deletes any children aswell
template< typename trav_type >
void erase(tree_iterator< item_type, trav_type >);

template< typename trav_type >
void erase(tree_iterator< item_type, trav_type >, tree_iterator< item_type, trav_type >);


//non destructive erase, inflates the child into the previous location of the deleted node
template< typename trav_type >
void erase_child(tree_iterator< item_type, trav_type >);

template< typename trav_type >
void erase_child(tree_iterator< item_type, trav_type >, tree_iterator< item_type, trav_type >);

void swap(tree< item_type, _Alloc >&);

template< typename trav_type >
tree_iterator< item_type, trav_type > find(const value_type& __x);

template< typename trav_type >
const_tree_iterator< item_type, trav_type > find(const value_type& __x) const;

iterator find(const value_type& __x);

const_iterator find(const value_type& __x) const;

template< typename trav_type, typename trav_type2 >
tree_iterator< item_type, trav_type2 >
child(tree_iterator< item_type, trav_type >, size_type);

template< typename trav_type >
tree_iterator< item_type, trav_type >
child(tree_iterator< item_type, trav_type >, size_type);

template< typename trav_type, typename trav_type2 >
const_tree_iterator< item_type, trav_type2 >
child(const_tree_iterator< item_type, trav_type >, size_type) const;

template< typename trav_type >
const_tree_iterator< item_type, trav_type >
child(const_tree_iterator< item_type, trav_type >, size_type) const;


template< typename trav_type, typename trav_type2 >
std::pair< tree_iterator< item_type, trav_type2 >,
tree_iterator< item_type, trav_type2 > >
children(tree_iterator< item_type, trav_type > pos) {

return std::make_pair( _M_cast_node(pos._M_node->_parent->_first_child),
_M_cast_node(pos._M_node->_parent->_last_child));
}

template< typename trav_type, typename trav_type2 >
std::pair< const_tree_iterator< item_type, trav_type2 >,
const_tree_iterator< item_type, trav_type2 > >
children(const_tree_iterator< item_type, trav_type > pos) const {
return std::make_pair( _M_cast_node(pos._M_node->_parent->_first_child),
_M_cast_node(pos._M_node->_parent->_last_child));
}

template< typename trav_type >
std::pair< tree_iterator< item_type, trav_type >,
tree_iterator< item_type, trav_type > >
children(tree_iterator< item_type, trav_type > pos) {
return std::make_pair( _M_cast_node(pos._M_node->_parent->_first_child),
_M_cast_node(pos._M_node->_parent->_last_child));
}

template< typename trav_type >
std::pair< const_tree_iterator< item_type, trav_type >,
const_tree_iterator< item_type, trav_type > >
children(const_tree_iterator< item_type, trav_type > pos) const {
return std::make_pair( _M_cast_node(pos._M_node->_parent->_first_child),
_M_cast_node(pos._M_node->_parent->_last_child));
}

template< typename trav_type, typename trav_type2 >
tree_iterator< item_type, trav_type2 >
parent(tree_iterator< item_type, trav_type > pos) {
return _M_parent(pos._M_node);
}

template< typename trav_type, typename trav_type2 >
const_tree_iterator< item_type, trav_type2 >
parent(const_tree_iterator< item_type, trav_type > pos) const {
return _M_parent(pos._M_node);
}

template< typename trav_type >
tree_iterator< item_type, trav_type >
parent(tree_iterator< item_type, trav_type > pos) {
return _M_parent(pos._M_node);
}

template< typename trav_type >
const_tree_iterator< item_type, trav_type >
parent(const_tree_iterator< item_type, trav_type > pos) const {
return _M_parent(pos._M_node);
}

template< typename trav_type >
tree< item_type, _Alloc > subtree(tree_iterator< item_type, trav_type >);

template< typename trav_type >
bool is_root(tree_iterator< item_type, trav_type >) const;

template< typename trav_type >
bool is_root(const_tree_iterator< item_type, trav_type >) const;

template< typename trav_type >
bool is_parent(tree_iterator< item_type, trav_type >) const;

template< typename trav_type >
bool is_parent(const_tree_iterator< item_type, trav_type >) const;

template < typename trav_type >
bool is_child_of(tree_iterator< item_type, trav_type >, tree_iterator< item_type, trav_type >) const;

template< typename trav_type >
bool is_child_of(const_tree_iterator< item_type, trav_type >, const_tree_iterator< item_type, trav_type >) const;

template< typename trav_type >
bool is_leaf(tree_iterator< item_type, trav_type >) const;

template< typename trav_type >
bool is_leaf(const_tree_iterator< item_type, trav_type >) const;

void clear(){
_M_erase(_M_begin());
_M_init();
}
};

template< typename item_type, typename _Alloc >
inline bool operator==( const tree< item_type, _Alloc >& __x,
const tree< item_type, _Alloc >& __y) {
return ((__x.size() == __y.size()) && std::equal(__x.begin(), __x.end(),
__y.begin()));
}

template< typename item_type, typename _alloc >
inline bool operator!=( const tree< item_type, _alloc >& __x,
const tree< item_type, _alloc >& __y) {
return !(__x == __y);
}

template< typename item_type, typename _Alloc >
tree< item_type, _Alloc >&
tree< item_type, _Alloc >::operator=(const tree< item_type, _Alloc >& __x) {
if (this != &__x) {
if (__x._M_root() != 0 && __x._M_root() != __x._M_end()) {
clear();
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_bottom_first() = tree_node_base::most_bottom_first_child(_M_root());
_M_bottom_last() = tree_node_base::most_bottom_last_child(_M_root());
_M_size() = __x._M_size();
}
}
return *this;
}

template<typename item_type, typename _Alloc >
template< typename trav_type1, typename trav_type2 >
inline tree_iterator< item_type, trav_type2 >
tree< item_type, _Alloc >::insert( tree_iterator< item_type, trav_type1 > itr,
const item_type& __v) {
return _M_insert(itr, __v);
}

template<typename item_type, typename _Alloc >
template<typename trav_type>
inline tree_iterator< item_type, trav_type>
tree< item_type, _Alloc >::insert( tree_iterator< item_type, trav_type > itr,
const item_type& __v) {
return _M_insert(itr, __v);
}

template<typename item_type, typename _Alloc >
template<typename InputIter, typename trav_type>
inline void
tree< item_type, _Alloc >::insert( tree_iterator< item_type, trav_type > pos,
InputIter first, InputIter last) {
for(; first != last; ++first) {
_M_insert(pos, *first);
}
}

template<typename item_type, typename _Alloc >
template<typename trav_type>
inline void tree<item_type, _Alloc >::erase(tree_iterator< item_type, trav_type> pos) {
bool needs_init = false;
if(pos._M_node == _M_root()) {
needs_init = true;
}
_M_erase_all(_M_cast_node(pos._M_node));

if(needs_init) {
_M_init();
} else {
_M_bottom_first() = tree_node_base::most_bottom_first_child(_M_root());
_M_bottom_last() = tree_node_base::most_bottom_last_child(_M_root());
}
}

template<typename item_type, typename _Alloc >
template<typename trav_type>
inline void tree<item_type, _Alloc >::erase(tree_iterator< item_type, trav_type> __first,
tree_iterator< item_type, trav_type> __last) {
if( (__first._M_node != _M_root()) &&
(__first._M_node->_parent == __last._M_node->_parent)) {

_base_ptr __tmp = 0;
_base_ptr __curr = __first._M_node;
while(__curr != 0 && __curr != __last._M_node) {
__tmp = __curr->_succ;
_M_erase_all(_M_cast_node(__curr));
__curr = __tmp;
}
_M_bottom_first() = tree_node_base::most_bottom_first_child(_M_root());
_M_bottom_last() = tree_node_base::most_bottom_last_child(_M_root());
}
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline void tree< item_type, _Alloc >::erase_child(tree_iterator< item_type, trav_type> pos) {
if( pos._M_node->_parent != 0) {

if( (pos._M_node->_first_child != 0) &&
(pos._M_node->_last_child != 0)) {

//for each child in pos
_base_ptr _curr = pos._M_node->_first_child;
while(_curr != 0) {
_curr->_parent = pos._M_node->_parent;
_curr = _curr->_succ;
}

if( (pos._M_node == pos._M_node->_parent->_first_child) &&
(pos._M_node == pos._M_node->_parent->_last_child)) { // most special case 0 pos is only child

pos._M_node->_parent->_first_child = pos._M_node->_first_child;
pos._M_node->_parent->_last_child = pos._M_node->_last_child;

} else if(pos._M_node == pos._M_node->_parent->_first_child) {// special case 1 pos is at first child

pos._M_node->_last_child->_succ = pos._M_node->_succ;
pos._M_node->_succ->_pred = pos._M_node->_last_child;
pos._M_node->_parent->_first_child = pos._M_node->_first_child;

} else if(pos._M_node == pos._M_node->_parent->_last_child) {// special case 2 pos is at last

pos._M_node->_first_child->_pred = pos._M_node->_pred;
pos._M_node->_pred->_succ = pos._M_node->_first_child;
pos._M_node->_parent->_last_child = pos._M_node->_last_child;

} else {// general case

pos._M_node->_first_child->_pred = pos._M_node->_pred;
pos._M_node->_last_child->_succ = pos._M_node->_succ;
pos._M_node->_pred->_succ = pos._M_node->_first_child;
pos._M_node->_succ->_pred = pos._M_node->_last_child;

}

destroy_node(_M_cast_node(pos._M_node));

_M_bottom_first() = tree_node_base::most_bottom_first_child(_M_root());
_M_bottom_last() = tree_node_base::most_bottom_last_child(_M_root());

} else {//its a leaf
_M_erase_leaf(_M_cast_node(pos._M_node));
}
}
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline void tree<item_type, _Alloc >::erase_child( tree_iterator< item_type, trav_type > __first,
tree_iterator< item_type, trav_type > __last) {
if( (__first._M_node != _M_root()) &&
(__first._M_node->_parent == __last._M_node->_parent)) {

_base_ptr __tmp = 0;
_base_ptr __curr = __first._M_node;
while(__curr != 0 && __curr != __last._M_node) {
__tmp = __curr->_succ;
erase_child(iterator(_M_cast_node(__curr)));
__curr = __tmp;
}
_M_bottom_first() = tree_node_base::most_bottom_first_child(_M_root());
_M_bottom_last() = tree_node_base::most_bottom_last_child(_M_root());
}
}

template< typename item_type, typename _Alloc >
inline void
tree< item_type, _Alloc >::swap(tree< item_type, _Alloc >& tr) {
if(this != &tr) {
_M_swap(tr._M_end());
const size_type n = _M_size();
_M_size() = tr.size();
tr._M_size() = n;
}
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline tree_iterator< item_type, trav_type>
tree<item_type, _Alloc >::find(const item_type& __x) {
iterator curr = begin();
for(iterator _end = end();
curr != _end;
++curr){
if(__x == *curr)
break;

}
return _M_cast_node(curr._M_node);
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline const_tree_iterator< item_type, trav_type >
tree< item_type, _Alloc >::find(const item_type& __x) const {
const_iterator curr = begin();
for(const_iterator _end = end();
curr != _end;
++curr){
if(__x == *curr)
break;

}
return _M_cast_node(curr._M_node);
}

template< typename item_type, typename _Alloc >
inline typename tree< item_type, _Alloc >::iterator
tree<item_type, _Alloc >::find(const item_type& __x) {
iterator curr = begin();
for(iterator _end = end();
curr != _end;
++curr){
if(__x == *curr)
break;

}
return _M_cast_node(curr._M_node);
}

template< typename item_type, typename _Alloc >
inline typename tree< item_type, _Alloc >::const_iterator
tree< item_type, _Alloc >::find(const item_type& __x) const {
const_iterator curr = begin();
for(const_iterator _end = end();
curr != _end;
++curr){
if(__x == *curr)
break;

}
return _M_cast_node(curr._M_node);
}

template< typename item_type, typename _Alloc >
template< typename trav_type1, typename trav_type2 >
inline tree_iterator< item_type, trav_type2 >
tree< item_type, _Alloc >::add_child(tree_iterator< item_type, trav_type1 > itr,
const typename tree< item_type, _Alloc >::value_type& __v) {
return _M_insert_child(itr, __v);
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline tree_iterator< item_type, trav_type >
tree< item_type, _Alloc >::add_child(tree_iterator< item_type, trav_type > itr,
const typename tree< item_type, _Alloc >::value_type& __v) {
return _M_insert_child(itr, __v);
}

template< typename item_type, typename _Alloc >
template< typename InputIter, typename trav_type >
inline void
tree< item_type, _Alloc >::add_child(tree_iterator< item_type, trav_type > pos,
InputIter first,
InputIter last) {
for(; first != last; ++first) {
_M_insert_child(pos, *first);
}
}

template< typename item_type, typename _Alloc >
template< typename trav_type, typename trav_type2 >
inline tree_iterator< item_type, trav_type2 >
tree< item_type, _Alloc >::child(tree_iterator< item_type, trav_type > pos, size_type n) {
_base_ptr _curr = pos._M_node->_first_child;

while(_curr != 0 && n-- != 0)
_curr = _curr->_succ;

return _M_cast_node(_curr);
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline tree_iterator< item_type, trav_type >
tree< item_type, _Alloc >::child(tree_iterator< item_type, trav_type > pos, size_type n) {
_base_ptr _curr = pos._M_node->_first_child;

while(_curr != 0 && n-- != 0)
_curr = _curr->_succ;

return _M_cast_node(_curr);
}

template< typename item_type, typename _Alloc >
template< typename trav_type, typename trav_type2 >
inline const_tree_iterator< item_type, trav_type2 >
tree< item_type, _Alloc >::child(const_tree_iterator< item_type, trav_type > pos, size_type n) const {
_const_base_ptr _curr = pos._M_node->_first_child;

while(_curr != 0 && n-- != 0)
_curr = _curr->_succ;

return _M_cast_node(_curr);
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline const_tree_iterator< item_type, trav_type >
tree< item_type, _Alloc >::child(const_tree_iterator< item_type, trav_type > pos, size_type n) const {
_const_base_ptr _curr = pos._M_node->_first_child;

while(_curr != 0 && n-- != 0)
_curr = _curr->_succ;

return _M_cast_node(_curr);
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline tree< item_type, _Alloc >
tree< item_type, _Alloc >::subtree(tree_iterator< item_type, trav_type > __pos) {
if(__pos._M_node->_parent != 0) {
_M_detach_node(__pos._M_node);
__pos._M_node->_parent = 0;
}

_M_bottom_first() = tree_node_base::most_bottom_first_child(_M_root());
_M_bottom_last() = tree_node_base::most_bottom_last_child(_M_root());

return __pos._M_node;
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline bool
tree< item_type, _Alloc >::is_root(tree_iterator< item_type, trav_type > __r) const {
return (__r._M_node == _M_root());
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline bool
tree< item_type, _Alloc >::is_root(const_tree_iterator< item_type, trav_type > __r) const {
return (__r._M_node == _M_root());
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline bool
tree< item_type, _Alloc >::is_parent(tree_iterator< item_type, trav_type > ___p) const {
return !is_leaf(___p);
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline bool
tree< item_type, _Alloc >::is_parent(const_tree_iterator< item_type, trav_type > ___p) const {
return !is_leaf(___p);
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline bool
tree< item_type, _Alloc >::is_child_of( tree_iterator< item_type, trav_type > __c,
tree_iterator< item_type, trav_type > __p) const {
return (__c._M_node->_parent == __p._M_node);
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline bool
tree< item_type, _Alloc >::is_child_of( const_tree_iterator< item_type, trav_type > __c,
const_tree_iterator< item_type, trav_type > __p) const {
return (__c._M_node->_parent == __p._M_node);
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline bool
tree< item_type, _Alloc >::is_leaf(tree_iterator< item_type, trav_type > __pos) const {
return ((__pos._M_node->_first_child == 0) && (__pos._M_node->_last_child == 0));
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline bool
tree< item_type, _Alloc >::is_leaf(const_tree_iterator< item_type, trav_type > __pos) const {
return ((__pos._M_node->_first_child == 0) && (__pos._M_node->_last_child == 0));
}

//returns number of children
template< typename item_type, typename _Alloc >
template< typename trav_type >
inline typename tree< item_type, _Alloc >::size_type
tree< item_type, _Alloc >::child_size(const_tree_iterator< item_type, trav_type > ___p) const {
_const_base_ptr _curr = ___p._M_node->_first_child;
size_type _child_size = 0;
while(_curr != 0) {
++_child_size;
_curr = _curr->_succ;
}
return _child_size;
}

//returns number of children
template< typename item_type, typename _Alloc >
template< typename trav_type >
inline typename tree< item_type, _Alloc >::size_type
tree< item_type, _Alloc >::child_size(tree_iterator< item_type, trav_type > ___p) const {
_const_base_ptr _curr = ___p._M_node->_first_child;
size_type _child_size = 0;
while(_curr != 0) {
++_child_size;
_curr = _curr->_succ;
}
return _child_size;
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline typename tree< item_type, _Alloc >::size_type
tree< item_type, _Alloc >::depth(const_tree_iterator< item_type, trav_type > ___p) const {
size_type _depth_size = 0;
_const_base_ptr _curr = ___p._M_node->_parent;
while(_curr != 0) {
++_depth_size;
_curr = _curr->_parent;
}
return _depth_size;
}

template< typename item_type, typename _Alloc >
template< typename trav_type >
inline typename tree< item_type, _Alloc >::size_type
tree< item_type, _Alloc >::depth(tree_iterator< item_type, trav_type > ___p) const {
size_type _depth_size = 0;
_const_base_ptr _curr = ___p._M_node->_parent;
while(_curr != 0) {
++_depth_size;
_curr = _curr->_parent;
}
return _depth_size;
}
}
# endif


here is a little sample test:
main.cpp

#include "tree.hpp"

using std::tree;

#include <string>
#include <vector>
#include <iostream>

template< typename T >
void print_tree(const tree<T>& );

int main() {

tree<std::string> t;

tree<std::string>::pre_order_itr itr = t.pre_begin();

itr = t.add_child(itr, "university");

t.add_child(itr, "Eng");

t.add_child(itr, "Medicine");

tree<std::string>::iterator itr2 = t.add_child(itr, "Science");

t.add_child(itr2, "Chemistry");

t.add_child(itr2, "Physics");

tree<std::string>::pre_order_itr itr3 = t.add_child(itr2, "Biology");

t.add_child(itr3, "PE");

t.add_child(itr3, "RE");

t.add_child(itr2, "Mathematics");

t.add_child(itr2, "Computer Science");

t.add_child(itr, "Education");

t.add_child(itr, "Social Ed");

tree<std::string>::pre_order_itr itr4 = t.add_child(itr, "Humanties");

t.add_child(itr4, "Lanugages");

t.add_child(itr4, "History");

std::cout << "\nTree 1\n";

print_tree(t);

tree<std::string> t2 = t.subtree(itr3);

std::cout << "\nTree 2\n";

print_tree(t2);

std::cout << "\nswapping tree 1 & 2....\n";

t.swap(t2);

std::cout << "\nTree 1\n";

print_tree(t);

std::cout << "\nTree 2\n";

print_tree(t2);

std::cout << "is t1 != t2? " << std::boolalpha << (t != t2) << '\n';

std::cout << "\ncopying t2 to a vector of strings:\n";

std::vector<std::string> vstrings(t2.begin(), t2.end());

std::cout << "\nPrinting vector of strings...\n\n";

for(int i = 0, n = vstrings.size(); i < n; i++)
std::cout << vstrings[i] << '\n';
return 0;
}

template< typename T >
void print_tree(const tree< T >& t) {
for(typename tree< T >::const_iterator tree_itr = t.begin(),
end = t.end();
tree_itr != end;
++tree_itr) {
std::cout << *tree_itr << '\n';
}
}

Share this post


Link to post
Share on other sites
I thought i better mention something about it. There is only two iterators const_iterator & iterator types that are paramatized by traversal scheme preorder, postorder, breadth-first are provided, the usual STL typedefs are there aswell some extras to make it easy create an iterator with a particular type of traversal scheme, you can construct an iterator of one traversal scheme with another iterator of a different traversal scheme.

Share this post


Link to post
Share on other sites

  • Advertisement