-////////////////////////////////////////////////////////////////////////////////
-
-// Author: Andy Rushton
-// Copyright: (c) Southampton University 1999-2004
-// (c) Andy Rushton 2004-2009
-// License: BSD License, see ../docs/license.html
-
-////////////////////////////////////////////////////////////////////////////////
-#include <vector>
-#include <algorithm>
-
-namespace stlplus
-{
-
- ////////////////////////////////////////////////////////////////////////////////
- // ntree_node
-
- template<typename T>
- class ntree_node
- {
- public:
- master_iterator<ntree<T>, ntree_node<T> > m_master;
- T m_data;
- ntree_node<T>* m_parent;
- std::vector<ntree_node<T>*> m_children;
-
- public:
- ntree_node(const ntree<T>* owner, const T& data = T()) :
- m_master(owner,this), m_data(data), m_parent(0)
- {
- }
-
- void change_owner(const ntree<T>* owner)
- {
- m_master.change_owner(owner);
- for (TYPENAME std::vector<ntree_node<T>*>::iterator i = m_children.begin(); i != m_children.end(); i++)
- (*i)->change_owner(owner);
- }
-
- ~ntree_node(void)
- {
- m_parent = 0;
- for (TYPENAME std::vector<ntree_node<T>*>::iterator i = m_children.begin(); i != m_children.end(); i++)
- delete *i;
- }
-
- };
-
- template<typename T>
- static ntree_node<T>* ntree_copy(const ntree<T>* new_owner, ntree_node<T>* root)
- {
- if (!root) return 0;
- ntree_node<T>* new_tree = new ntree_node<T>(new_owner, root->m_data);
- for (TYPENAME std::vector<ntree_node<T>*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++)
- {
- ntree_node<T>* new_child = ntree_copy(new_owner, *i);
- new_tree->m_children.push_back(new_child);
- new_child->m_parent = new_tree;
- }
- return new_tree;
- }
-
- template<typename T>
- static unsigned ntree_size(ntree_node<T>* root)
- {
- if (!root) return 0;
- unsigned result = 1;
- for (TYPENAME std::vector<ntree_node<T>*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++)
- result += ntree_size(*i);
- return result;
- }
-
- template<typename T>
- static unsigned ntree_depth(ntree_node<T>* root)
- {
- unsigned depth = 0;
- for (ntree_node<T>* i = root; i; i = i->m_parent)
- depth++;
- return depth;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // ntree_iterator
-
- // constructor to create a null iterator - you must assign a valid value to this iterator before using it
- template<typename T, typename TRef, typename TPtr>
- ntree_iterator<T,TRef,TPtr>::ntree_iterator(void)
- {
- }
-
- // used to create an alias of an iterator
- template<typename T, typename TRef, typename TPtr>
- ntree_iterator<T,TRef,TPtr>::ntree_iterator(const safe_iterator<ntree<T>, ntree_node<T> >& iterator) :
- safe_iterator<ntree<T>,ntree_node<T> >(iterator)
- {
- }
-
- // constructor used by ntree to create a non-null iterator
- template<typename T, typename TRef, typename TPtr>
- ntree_iterator<T,TRef,TPtr>::ntree_iterator(ntree_node<T>* node) :
- safe_iterator<ntree<T>,ntree_node<T> >(node->m_master)
- {
- }
-
- // constructor used by ntree to create an end iterator
- template<typename T, typename TRef, typename TPtr>
- ntree_iterator<T,TRef,TPtr>::ntree_iterator(const ntree<T>* owner) :
- safe_iterator<ntree<T>,ntree_node<T> >(owner)
- {
- }
-
- // destructor
- template<typename T, typename TRef, typename TPtr>
- ntree_iterator<T,TRef,TPtr>::~ntree_iterator(void)
- {
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_iterator<T,TRef,TPtr>::const_iterator ntree_iterator<T,TRef,TPtr>::constify(void) const
- {
- return ntree_iterator<T,const T&,const T*>(*this);
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_iterator<T,TRef,TPtr>::iterator ntree_iterator<T,TRef,TPtr>::deconstify(void) const
- {
- return ntree_iterator<T,T&,T*>(*this);
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const
- {
- return equal(r);
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const
- {
- return !operator==(r);
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const
- {
- return compare(r) < 0;
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_iterator<T,TRef,TPtr>::reference ntree_iterator<T,TRef,TPtr>::operator*(void) const
- throw(null_dereference,end_dereference)
- {
- this->assert_valid();
- return this->node()->m_data;
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_iterator<T,TRef,TPtr>::pointer ntree_iterator<T,TRef,TPtr>::operator->(void) const
- throw(null_dereference,end_dereference)
- {
- return &(operator*());
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // ntree_prefix_iterator
-
- template<typename T, typename TRef, typename TPtr>
- ntree_prefix_iterator<T,TRef,TPtr>::ntree_prefix_iterator(void)
- {
- }
-
- template<typename T, typename TRef, typename TPtr>
- ntree_prefix_iterator<T,TRef,TPtr>::~ntree_prefix_iterator(void)
- {
- }
-
- template<typename T, typename TRef, typename TPtr>
- ntree_prefix_iterator<T,TRef,TPtr>::ntree_prefix_iterator(const ntree_iterator<T,TRef,TPtr>& i) :
- m_iterator(i)
- {
- // this is initialised with the root node
- // which is also the first node in prefix traversal order
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_prefix_iterator<T,TRef,TPtr>::null(void) const
- {
- return m_iterator.null();
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_prefix_iterator<T,TRef,TPtr>::end(void) const
- {
- return m_iterator.end();
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_prefix_iterator<T,TRef,TPtr>::valid(void) const
- {
- return m_iterator.valid();
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::const_iterator ntree_prefix_iterator<T,TRef,TPtr>::constify(void) const
- {
- return ntree_prefix_iterator<T,const T&,const T*>(m_iterator);
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::iterator ntree_prefix_iterator<T,TRef,TPtr>::deconstify(void) const
- {
- return ntree_prefix_iterator<T,T&,T*>(m_iterator);
- }
-
- template<typename T, typename TRef, typename TPtr>
- ntree_iterator<T,TRef,TPtr> ntree_prefix_iterator<T,TRef,TPtr>::simplify(void) const
- {
- return m_iterator;
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_prefix_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const
- {
- return m_iterator == r.m_iterator;
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_prefix_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const
- {
- return m_iterator != r.m_iterator;
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_prefix_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const
- {
- return m_iterator < r.m_iterator;
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& ntree_prefix_iterator<T,TRef,TPtr>::operator ++ (void)
- throw(null_dereference,end_dereference)
- {
- // pre-increment operator
- // algorithm: if there are any children, visit child 0, otherwise, go to
- // parent and deduce which child the start node was of that parent - if
- // there are further children, go into the next one. Otherwise, go up the
- // tree and test again for further children. Return null if there are no
- // further nodes
- m_iterator.assert_valid();
- ntree_node<T>* old_node = m_iterator.node();
- if (!old_node->m_children.empty())
- {
- // simply take the first child of this node
- m_iterator.set(old_node->m_children[0]->m_master);
- }
- else
- {
- // this loop walks up the parent pointers
- // either it will walk off the top and exit or a new node will be found and the loop will exit
- for (;;)
- {
- // go up a level
- ntree_node<T>* parent = old_node->m_parent;
- if (!parent)
- {
- // we've walked off the top of the tree, so return end
- m_iterator.set_end();
- break;
- }
- else
- {
- // otherwise walk down the next child - if there is one
- // find which index the old node was relative to this node
- TYPENAME std::vector<ntree_node<T>*>::iterator found =
- std::find(parent->m_children.begin(), parent->m_children.end(), old_node);
- // if this was found, then see if there is another and if so return that
- found++;
- if (found != parent->m_children.end())
- {
- // visit the next child
- m_iterator.set((*found)->m_master);
- break;
- }
- else
- {
- // keep going up
- old_node = parent;
- }
- }
- }
- }
- return *this;
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator ntree_prefix_iterator<T,TRef,TPtr>::operator ++ (int)
- throw(null_dereference,end_dereference)
- {
- // post-increment is defined in terms of the pre-increment
- ntree_prefix_iterator<T,TRef,TPtr> result(*this);
- ++(*this);
- return result;
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::reference ntree_prefix_iterator<T,TRef,TPtr>::operator*(void) const
- throw(null_dereference,end_dereference)
- {
- return m_iterator.operator*();
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::pointer ntree_prefix_iterator<T,TRef,TPtr>::operator->(void) const
- throw(null_dereference,end_dereference)
- {
- return m_iterator.operator->();
- }
-
- template<typename T, typename TRef, typename TPtr>
- const ntree_iterator<T,TRef,TPtr>& ntree_prefix_iterator<T,TRef,TPtr>::get_iterator(void) const
- {
- return m_iterator;
- }
-
- template<typename T, typename TRef, typename TPtr>
- ntree_iterator<T,TRef,TPtr>& ntree_prefix_iterator<T,TRef,TPtr>::get_iterator(void)
- {
- return m_iterator;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // ntree_postfix_iterator
-
- template<typename T, typename TRef, typename TPtr>
- ntree_postfix_iterator<T,TRef,TPtr>::ntree_postfix_iterator(void)
- {
- }
-
- template<typename T, typename TRef, typename TPtr>
- ntree_postfix_iterator<T,TRef,TPtr>::~ntree_postfix_iterator(void)
- {
- }
-
- template<typename T, typename TRef, typename TPtr>
- ntree_postfix_iterator<T,TRef,TPtr>::ntree_postfix_iterator(const ntree_iterator<T,TRef,TPtr>& i) :
- m_iterator(i)
- {
- // this is initialised with the root node
- // initially traverse to the first node to be visited
- if (m_iterator.valid())
- {
- ntree_node<T>* node = m_iterator.node();
- while (!node->m_children.empty())
- node = node->m_children[0];
- m_iterator.set(node->m_master);
- }
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_postfix_iterator<T,TRef,TPtr>::null(void) const
- {
- return m_iterator.null();
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_postfix_iterator<T,TRef,TPtr>::end(void) const
- {
- return m_iterator.end();
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_postfix_iterator<T,TRef,TPtr>::valid(void) const
- {
- return m_iterator.valid();
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::const_iterator ntree_postfix_iterator<T,TRef,TPtr>::constify(void) const
- {
- return ntree_postfix_iterator<T,const T&,const T*>(m_iterator);
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::iterator ntree_postfix_iterator<T,TRef,TPtr>::deconstify(void) const
- {
- return ntree_postfix_iterator<T,T&,T*>(m_iterator);
- }
-
- template<typename T, typename TRef, typename TPtr>
- ntree_iterator<T,TRef,TPtr> ntree_postfix_iterator<T,TRef,TPtr>::simplify(void) const
- {
- return m_iterator;
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_postfix_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const
- {
- return m_iterator == r.m_iterator;
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_postfix_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const
- {
- return m_iterator != r.m_iterator;
- }
-
- template<typename T, typename TRef, typename TPtr>
- bool ntree_postfix_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const
- {
- return m_iterator < r.m_iterator;
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& ntree_postfix_iterator<T,TRef,TPtr>::operator ++ (void)
- throw(null_dereference,end_dereference)
- {
- // pre-increment operator
- // algorithm: this node has been visited, therefore all children must have
- // already been visited. So go to parent. Return null if the parent is null.
- // Otherwise deduce which child the start node was of that parent - if there
- // are further children, go into the next one and then walk down any
- // subsequent first-child pointers to the bottom. Otherwise, if there are no
- // children then the parent node is the next in the traversal.
- m_iterator.assert_valid();
- // go up a level
- ntree_node<T>* old_node = m_iterator.node();
- ntree_node<T>* parent = old_node->m_parent;
- if (!parent)
- {
- // we've walked off the top of the tree, so return end
- m_iterator.set_end();
- }
- else
- {
- // otherwise find which index the old node was relative to this node
- TYPENAME std::vector<ntree_node<T>*>::iterator found =
- std::find(parent->m_children.begin(), parent->m_children.end(), old_node);
- // if this was found, then see if there is another
- found++;
- if (found != parent->m_children.end())
- {
- // if so traverse to it and walk down the leftmost child pointers to the bottom of the new sub-tree
- ntree_node<T>* new_node = *found;
- while (!new_node->m_children.empty())
- new_node = new_node->m_children[0];
- m_iterator.set(new_node->m_master);
- }
- else
- {
- // the parent's children have all been visited - so the parent is visited
- m_iterator.set(parent->m_master);
- }
- }
- return *this;
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator ntree_postfix_iterator<T,TRef,TPtr>::operator ++ (int)
- throw(null_dereference,end_dereference)
- {
- // post-increment is defined in terms of the pre-increment
- ntree_postfix_iterator<T,TRef,TPtr> result(*this);
- ++(*this);
- return result;
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::reference ntree_postfix_iterator<T,TRef,TPtr>::operator*(void) const
- throw(null_dereference,end_dereference)
- {
- return m_iterator.operator*();
- }
-
- template<typename T, typename TRef, typename TPtr>
- TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::pointer ntree_postfix_iterator<T,TRef,TPtr>::operator->(void) const
- throw(null_dereference,end_dereference)
- {
- return m_iterator.operator->();
- }
-
- template<typename T, typename TRef, typename TPtr>
- const ntree_iterator<T,TRef,TPtr>& ntree_postfix_iterator<T,TRef,TPtr>::get_iterator(void) const
- {
- return m_iterator;
- }
-
- template<typename T, typename TRef, typename TPtr>
- ntree_iterator<T,TRef,TPtr>& ntree_postfix_iterator<T,TRef,TPtr>::get_iterator(void)
- {
- return m_iterator;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- ////////////////////////////////////////////////////////////////////////////////
- // ntree
- ////////////////////////////////////////////////////////////////////////////////
- ////////////////////////////////////////////////////////////////////////////////
-
- template<typename T>
- ntree<T>::ntree(void) : m_root(0)
- {
- }
-
- template<typename T>
- ntree<T>::~ntree(void)
- {
- if (m_root) delete m_root;
- }
-
- template<typename T>
- ntree<T>::ntree(const ntree<T>& r) : m_root(0)
- {
- *this = r;
- }
-
- template<typename T>
- ntree<T>& ntree<T>::operator=(const ntree<T>& r)
- {
- if (m_root) delete m_root;
- m_root = ntree_copy(this, r.m_root);
- return *this;
- }
-
- template<typename T>
- bool ntree<T>::empty(void) const
- {
- return m_root == 0;
- }
-
- template<typename T>
- unsigned ntree<T>::size(void) const
- {
- return ntree_size(m_root);
- }
-
- template<typename T>
- unsigned ntree<T>::size(const TYPENAME ntree<T>::const_iterator& i) const
- throw(wrong_object,null_dereference,end_dereference)
- {
- i.assert_valid(this);
- return ntree_size(i.node());
- }
-
- template<typename T>
- unsigned ntree<T>::size(const TYPENAME ntree<T>::iterator& i)
- throw(wrong_object,null_dereference,end_dereference)
- {
- i.assert_valid(this);
- return ntree_size(i.node());
- }
-
- template<typename T>
- unsigned ntree<T>::depth(const TYPENAME ntree<T>::const_iterator& i) const
- throw(wrong_object,null_dereference,end_dereference)
- {
- i.assert_valid(this);
- return ntree_depth(i.node());
- }
-
- template<typename T>
- unsigned ntree<T>::depth(const TYPENAME ntree<T>::iterator& i)
- throw(wrong_object,null_dereference,end_dereference)
- {
- i.assert_valid(this);
- return ntree_depth(i.node());
- }
-
- template<typename T>
- TYPENAME ntree<T>::const_iterator ntree<T>::root(void) const
- {
- if (!m_root) return ntree_iterator<T,const T&,const T*>(this);
- return ntree_iterator<T,const T&,const T*>(m_root);
- }
-
- template<typename T>
- TYPENAME ntree<T>::iterator ntree<T>::root(void)
- {
- if (!m_root) return ntree_iterator<T,T&,T*>(this);
- return ntree_iterator<T,T&,T*>(m_root);
- }
-
- template<typename T>
- unsigned ntree<T>::children(const TYPENAME ntree<T>::const_iterator& i) const
- throw(wrong_object,null_dereference,end_dereference)
- {
- i.assert_valid(this);
- return i.node()->m_children.size();
- }
-
- template<typename T>
- unsigned ntree<T>::children(const ntree_iterator<T,T&,T*>& i)
- throw(wrong_object,null_dereference,end_dereference)
- {
- i.assert_valid(this);
- return i.node()->m_children.size();
- }
-
- template<typename T>
- TYPENAME ntree<T>::const_iterator ntree<T>::child(const TYPENAME ntree<T>::const_iterator& i, unsigned child) const
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
- {
- i.assert_valid(this);
- if (child >= children(i)) throw std::out_of_range("stlplus::ntree");
- return ntree_iterator<T,const T&,const T*>(i.node()->m_children[child]);
- }
-
- template<typename T>
- TYPENAME ntree<T>::iterator ntree<T>::child(const TYPENAME ntree<T>::iterator& i, unsigned child)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
- {
- i.assert_valid(this);
- if (child >= children(i)) throw std::out_of_range("stlplus::ntree");
- return ntree_iterator<T,T&,T*>(i.node()->m_children[child]);
- }
-
- template<typename T>
- TYPENAME ntree<T>::const_iterator ntree<T>::parent(const TYPENAME ntree<T>::const_iterator& i) const
- throw(wrong_object,null_dereference,end_dereference)
- {
- i.assert_valid(this);
- ntree_node<T>* parent = i.node()->m_parent;
- if (!parent) return ntree_iterator<T,const T&,const T*>(this);
- return ntree_iterator<T,const T&,const T*>(parent);
- }
-
- template<typename T>
- TYPENAME ntree<T>::iterator ntree<T>::parent(const TYPENAME ntree<T>::iterator& i)
- throw(wrong_object,null_dereference,end_dereference)
- {
- i.assert_valid(this);
- ntree_node<T>* parent = i.node()->m_parent;
- if (!parent) return ntree_iterator<T,T&,T*>(this);
- return ntree_iterator<T,T&,T*>(parent);
- }
-
- template<typename T>
- TYPENAME ntree<T>::const_prefix_iterator ntree<T>::prefix_begin(void) const
- {
- return ntree_prefix_iterator<T,const T&,const T*>(root());
- }
-
- template<typename T>
- TYPENAME ntree<T>::prefix_iterator ntree<T>::prefix_begin(void)
- {
- return ntree_prefix_iterator<T,T&,T*>(root());
- }
-
- template<typename T>
- TYPENAME ntree<T>::const_prefix_iterator ntree<T>::prefix_end(void) const
- {
- return ntree_prefix_iterator<T,const T&,const T*>(ntree_iterator<T,const T&,const T*>(this));
- }
-
- template<typename T>
- TYPENAME ntree<T>::prefix_iterator ntree<T>::prefix_end(void)
- {
- return ntree_prefix_iterator<T,T&,T*>(ntree_iterator<T,T&,T*>(this));
- }
-
- template<typename T>
- TYPENAME ntree<T>::const_postfix_iterator ntree<T>::postfix_begin(void) const
- {
- return ntree_postfix_iterator<T,const T&,const T*>(root());
- }
-
- template<typename T>
- TYPENAME ntree<T>::postfix_iterator ntree<T>::postfix_begin(void)
- {
- return ntree_postfix_iterator<T,T&,T*>(root());
- }
-
- template<typename T>
- TYPENAME ntree<T>::const_postfix_iterator ntree<T>::postfix_end(void) const
- {
- return ntree_postfix_iterator<T,const T&,const T*>(ntree_iterator<T,const T&,const T*>(this));
- }
-
- template<typename T>
- TYPENAME ntree<T>::postfix_iterator ntree<T>::postfix_end(void)
- {
- return ntree_postfix_iterator<T,T&,T*>(ntree_iterator<T,T&,T*>(this));
- }
-
- template<typename T>
- TYPENAME ntree<T>::iterator ntree<T>::insert(const T& data)
- {
- // insert a new node as the root
- return insert(ntree_iterator<T,T&,T*>(this), 0, data);
- }
-
- template<typename T>
- TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const T& data)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
- {
- // if i is the end iterator, this means insert a new root
- if (i.end())
- erase();
- else
- {
- i.assert_valid(this);
- if (offset > children(i)) throw std::out_of_range("stlplus::ntree");
- }
- ntree_node<T>* new_node = new ntree_node<T>(this,data);
- if (i.end())
- {
- m_root = new_node;
- }
- else
- {
- i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);
- new_node->m_parent = i.node();
- }
- return ntree_iterator<T,T&,T*>(new_node);
- }
-
- template<typename T>
- TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const T& data)
- throw(wrong_object,null_dereference,end_dereference)
- {
- return insert(i, i.node()->m_children.size(), data);
- }
-
- template<typename T>
- TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const ntree<T>& tree)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
- {
- // insert a whole tree as a child of i
- i.assert_valid(this);
- if (offset > children(i)) throw std::out_of_range("stlplus::ntree");
- ntree_node<T>* new_node = ntree_copy(this, tree.m_root);
- i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);
- new_node->m_parent = i.node();
- return ntree_iterator<T,T&,T*>(new_node);
- }
-
- template<typename T>
- TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const ntree<T>& tree)
- throw(wrong_object,null_dereference,end_dereference)
- {
- return insert(i, children(i), tree);
- }
-
- template<typename T>
- TYPENAME ntree<T>::iterator ntree<T>::push(const TYPENAME ntree<T>::iterator& node, const T& data)
- throw(wrong_object,null_dereference,end_dereference)
- {
- // insert a new node to replace the existing node in the tree
- // making the original node the child of the new node
- // i.e. (node) becomes (new)->(node)
- // afterwards, the iterator still points to the old node, now the child
- // returns the iterator to the new node
- node.assert_valid(this);
- ntree_node<T>* new_node = new ntree_node<T>(this,data);
- if (node.node() == m_root)
- {
- // pushing the root node
- m_root = new_node;
- new_node->m_parent = 0;
- }
- else
- {
- // pushing a sub-node
- *(std::find(node.node()->m_parent->m_children.begin(), node.node()->m_parent->m_children.end(), node.node())) = new_node;
- new_node->m_parent = node.node()->m_parent;
- }
- // link up the old node as the child of the new node
- new_node->m_children.insert(new_node->m_children.begin(),node.node());
- node.node()->m_parent = new_node;
- return ntree_iterator<T,T&,T*>(new_node);
- }
-
- template<typename T>
- void ntree<T>::pop(const TYPENAME ntree<T>::iterator& parent, unsigned offset)
- throw(wrong_object,null_dereference,end_dereference)
- {
- // inverse of push
- // removes the specified child of the parent node, adding its children to the parent node at the same offset
- parent.assert_valid(this);
- ntree_node<T>* node = parent.node();
- if (offset >= node->m_children.size()) throw std::out_of_range("stlplus::ntree");
- // move the grandchildren first
- ntree_node<T>* child = parent.node()->m_children[offset];
- while (!child->m_children.empty())
- {
- // remove the last grandchild and insert into node just after the child to be removed
- ntree_node<T>* grandchild = child->m_children[child->m_children.size()-1];
- child->m_children.pop_back();
- node->m_children.insert(node->m_children.begin()+offset+1, grandchild);
- grandchild->m_parent = node;
- }
- // now remove the child
- node->m_children.erase(node->m_children.begin()+offset);
- delete child;
- }
-
- template<typename T>
- void ntree<T>::erase(void)
- {
- // erase the whole tree
- erase(root());
- }
-
- template<typename T>
- void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i)
- throw(wrong_object,null_dereference,end_dereference)
- {
- if (!i.end())
- {
- // erase this node and its subtree
- // do this by erasing this child of its parent
- // handle the case of erasing the root
- i.assert_valid(this);
- ntree_node<T>* node = i.node();
- if (node == m_root)
- {
- delete m_root;
- m_root = 0;
- }
- else
- {
- ntree_node<T>* parent = node->m_parent;
- // impossible for parent to be null - should assert this
- TYPENAME std::vector<ntree_node<T>*>::iterator found =
- std::find(parent->m_children.begin(), parent->m_children.end(), node);
- // impossible for find to fail - should assert this
- parent->m_children.erase(found);
- delete node;
- }
- }
- }
-
- template<typename T>
- void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i, unsigned offset)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
- {
- erase(child(i, offset));
- }
-
- template<typename T>
- ntree<T> ntree<T>::subtree(void)
- {
- return subtree(root());
- }
-
- template<typename T>
- ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i)
- throw(wrong_object,null_dereference,end_dereference)
- {
- ntree<T> result;
- if (!i.end())
- {
- i.assert_valid(this);
- result.m_root = ntree_copy(&result, i.node());
- }
- return result;
- }
-
- template<typename T>
- ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i, unsigned offset)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
- {
- return subtree(child(i, offset));
- }
-
- template<typename T>
- ntree<T> ntree<T>::cut(void)
- {
- return cut(root());
- }
-
- template<typename T>
- ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i)
- throw(wrong_object,null_dereference,end_dereference)
- {
- ntree<T> result;
- if (!i.end())
- {
- i.assert_valid(this);
- ntree_node<T>* node = i.node();
- if (node == m_root)
- {
- result.m_root = m_root;
- m_root = 0;
- }
- else
- {
- ntree_node<T>* parent = node->m_parent;
- // impossible for parent to be null - should assert this
- TYPENAME std::vector<ntree_node<T>*>::iterator found =
- std::find(parent->m_children.begin(), parent->m_children.end(), node);
- // impossible for find to fail - should assert this
- result.m_root = *found;
- parent->m_children.erase(found);
- }
- if (result.m_root)
- {
- result.m_root->m_parent = 0;
- result.m_root->set_new_owner(&result);
- }
- }
- return result;
- }
-
- template<typename T>
- ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i, unsigned offset)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
- {
- return cut(child(i, offset));
- }
-
- ////////////////////////////////////////////////////////////////////////////////
-
-} // end namespace stlplus
-
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004 onwards\r
+// License: BSD License, see ../docs/license.html\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include <vector>\r
+#include <algorithm>\r
+\r
+namespace stlplus \r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // ntree_node\r
+\r
+ template<typename T>\r
+ class ntree_node\r
+ {\r
+ public:\r
+ master_iterator<ntree<T>, ntree_node<T> > m_master;\r
+ T m_data;\r
+ ntree_node<T>* m_parent;\r
+ std::vector<ntree_node<T>*> m_children;\r
+\r
+ public:\r
+ ntree_node(const ntree<T>* owner, const T& data = T()) :\r
+ m_master(owner,this), m_data(data), m_parent(0)\r
+ {\r
+ }\r
+\r
+ void change_owner(const ntree<T>* owner)\r
+ {\r
+ m_master.change_owner(owner);\r
+ for (TYPENAME std::vector<ntree_node<T>*>::iterator i = m_children.begin(); i != m_children.end(); i++)\r
+ (*i)->change_owner(owner);\r
+ }\r
+\r
+ ~ntree_node(void)\r
+ {\r
+ m_parent = 0;\r
+ for (TYPENAME std::vector<ntree_node<T>*>::iterator i = m_children.begin(); i != m_children.end(); i++)\r
+ delete *i;\r
+ }\r
+\r
+ };\r
+\r
+ template<typename T>\r
+ static ntree_node<T>* ntree_copy(const ntree<T>* new_owner, ntree_node<T>* root)\r
+ {\r
+ if (!root) return 0;\r
+ ntree_node<T>* new_tree = new ntree_node<T>(new_owner, root->m_data);\r
+ for (TYPENAME std::vector<ntree_node<T>*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++)\r
+ {\r
+ ntree_node<T>* new_child = ntree_copy(new_owner, *i);\r
+ new_tree->m_children.push_back(new_child);\r
+ new_child->m_parent = new_tree;\r
+ }\r
+ return new_tree;\r
+ }\r
+\r
+ template<typename T>\r
+ static unsigned ntree_size(ntree_node<T>* root)\r
+ {\r
+ if (!root) return 0;\r
+ unsigned result = 1;\r
+ for (TYPENAME std::vector<ntree_node<T>*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++)\r
+ result += ntree_size(*i);\r
+ return result;\r
+ }\r
+\r
+ template<typename T>\r
+ static unsigned ntree_depth(ntree_node<T>* root)\r
+ {\r
+ unsigned depth = 0;\r
+ for (ntree_node<T>* i = root; i; i = i->m_parent)\r
+ depth++;\r
+ return depth;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // ntree_iterator\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>::ntree_iterator(void)\r
+ {\r
+ }\r
+\r
+ // used to create an alias of an iterator\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>::ntree_iterator(const safe_iterator<ntree<T>, ntree_node<T> >& iterator) :\r
+ safe_iterator<ntree<T>,ntree_node<T> >(iterator)\r
+ {\r
+ }\r
+\r
+ // constructor used by ntree to create a non-null iterator\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>::ntree_iterator(ntree_node<T>* node) :\r
+ safe_iterator<ntree<T>,ntree_node<T> >(node->m_master)\r
+ {\r
+ }\r
+\r
+ // constructor used by ntree to create an end iterator\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>::ntree_iterator(const ntree<T>* owner) :\r
+ safe_iterator<ntree<T>,ntree_node<T> >(owner)\r
+ {\r
+ }\r
+\r
+ // destructor\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>::~ntree_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_iterator<T,TRef,TPtr>::const_iterator ntree_iterator<T,TRef,TPtr>::constify(void) const\r
+ {\r
+ return ntree_iterator<T,const T&,const T*>(*this);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_iterator<T,TRef,TPtr>::iterator ntree_iterator<T,TRef,TPtr>::deconstify(void) const\r
+ {\r
+ return ntree_iterator<T,T&,T*>(*this);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return equal(r);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return !operator==(r);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return compare(r) < 0;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_iterator<T,TRef,TPtr>::reference ntree_iterator<T,TRef,TPtr>::operator*(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ this->assert_valid();\r
+ return this->node()->m_data;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_iterator<T,TRef,TPtr>::pointer ntree_iterator<T,TRef,TPtr>::operator->(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return &(operator*());\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // ntree_prefix_iterator\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_prefix_iterator<T,TRef,TPtr>::ntree_prefix_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_prefix_iterator<T,TRef,TPtr>::~ntree_prefix_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_prefix_iterator<T,TRef,TPtr>::ntree_prefix_iterator(const ntree_iterator<T,TRef,TPtr>& i) :\r
+ m_iterator(i)\r
+ {\r
+ // this is initialised with the root node\r
+ // which is also the first node in prefix traversal order\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::null(void) const\r
+ {\r
+ return m_iterator.null();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::end(void) const\r
+ {\r
+ return m_iterator.end();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::valid(void) const\r
+ {\r
+ return m_iterator.valid();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::const_iterator ntree_prefix_iterator<T,TRef,TPtr>::constify(void) const\r
+ {\r
+ return ntree_prefix_iterator<T,const T&,const T*>(m_iterator);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::iterator ntree_prefix_iterator<T,TRef,TPtr>::deconstify(void) const\r
+ {\r
+ return ntree_prefix_iterator<T,T&,T*>(m_iterator);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr> ntree_prefix_iterator<T,TRef,TPtr>::simplify(void) const\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator == r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator != r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_prefix_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator < r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& ntree_prefix_iterator<T,TRef,TPtr>::operator ++ (void)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // pre-increment operator\r
+ // algorithm: if there are any children, visit child 0, otherwise, go to\r
+ // parent and deduce which child the start node was of that parent - if\r
+ // there are further children, go into the next one. Otherwise, go up the\r
+ // tree and test again for further children. Return null if there are no\r
+ // further nodes\r
+ m_iterator.assert_valid();\r
+ ntree_node<T>* old_node = m_iterator.node();\r
+ if (!old_node->m_children.empty())\r
+ {\r
+ // simply take the first child of this node\r
+ m_iterator.set(old_node->m_children[0]->m_master);\r
+ }\r
+ else\r
+ {\r
+ // this loop walks up the parent pointers\r
+ // either it will walk off the top and exit or a new node will be found and the loop will exit\r
+ for (;;)\r
+ {\r
+ // go up a level\r
+ ntree_node<T>* parent = old_node->m_parent;\r
+ if (!parent)\r
+ {\r
+ // we've walked off the top of the tree, so return end\r
+ m_iterator.set_end();\r
+ break;\r
+ }\r
+ else\r
+ {\r
+ // otherwise walk down the next child - if there is one\r
+ // find which index the old node was relative to this node\r
+ TYPENAME std::vector<ntree_node<T>*>::iterator found = \r
+ std::find(parent->m_children.begin(), parent->m_children.end(), old_node);\r
+ // if this was found, then see if there is another and if so return that\r
+ found++;\r
+ if (found != parent->m_children.end())\r
+ {\r
+ // visit the next child\r
+ m_iterator.set((*found)->m_master);\r
+ break;\r
+ }\r
+ else\r
+ {\r
+ // keep going up\r
+ old_node = parent;\r
+ }\r
+ }\r
+ }\r
+ }\r
+ return *this;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator ntree_prefix_iterator<T,TRef,TPtr>::operator ++ (int)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // post-increment is defined in terms of the pre-increment\r
+ ntree_prefix_iterator<T,TRef,TPtr> result(*this);\r
+ ++(*this);\r
+ return result;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::reference ntree_prefix_iterator<T,TRef,TPtr>::operator*(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return m_iterator.operator*();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::pointer ntree_prefix_iterator<T,TRef,TPtr>::operator->(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return m_iterator.operator->();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ const ntree_iterator<T,TRef,TPtr>& ntree_prefix_iterator<T,TRef,TPtr>::get_iterator(void) const\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>& ntree_prefix_iterator<T,TRef,TPtr>::get_iterator(void)\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // ntree_postfix_iterator\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_postfix_iterator<T,TRef,TPtr>::ntree_postfix_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_postfix_iterator<T,TRef,TPtr>::~ntree_postfix_iterator(void)\r
+ {\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_postfix_iterator<T,TRef,TPtr>::ntree_postfix_iterator(const ntree_iterator<T,TRef,TPtr>& i) :\r
+ m_iterator(i)\r
+ {\r
+ // this is initialised with the root node\r
+ // initially traverse to the first node to be visited\r
+ if (m_iterator.valid())\r
+ {\r
+ ntree_node<T>* node = m_iterator.node();\r
+ while (!node->m_children.empty())\r
+ node = node->m_children[0];\r
+ m_iterator.set(node->m_master);\r
+ }\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::null(void) const\r
+ {\r
+ return m_iterator.null();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::end(void) const\r
+ {\r
+ return m_iterator.end();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::valid(void) const\r
+ {\r
+ return m_iterator.valid();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::const_iterator ntree_postfix_iterator<T,TRef,TPtr>::constify(void) const\r
+ {\r
+ return ntree_postfix_iterator<T,const T&,const T*>(m_iterator);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::iterator ntree_postfix_iterator<T,TRef,TPtr>::deconstify(void) const\r
+ {\r
+ return ntree_postfix_iterator<T,T&,T*>(m_iterator);\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr> ntree_postfix_iterator<T,TRef,TPtr>::simplify(void) const\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator == r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator != r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ bool ntree_postfix_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const\r
+ {\r
+ return m_iterator < r.m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& ntree_postfix_iterator<T,TRef,TPtr>::operator ++ (void)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // pre-increment operator\r
+ // algorithm: this node has been visited, therefore all children must have\r
+ // already been visited. So go to parent. Return null if the parent is null.\r
+ // Otherwise deduce which child the start node was of that parent - if there\r
+ // are further children, go into the next one and then walk down any\r
+ // subsequent first-child pointers to the bottom. Otherwise, if there are no\r
+ // children then the parent node is the next in the traversal.\r
+ m_iterator.assert_valid();\r
+ // go up a level\r
+ ntree_node<T>* old_node = m_iterator.node();\r
+ ntree_node<T>* parent = old_node->m_parent;\r
+ if (!parent)\r
+ {\r
+ // we've walked off the top of the tree, so return end\r
+ m_iterator.set_end();\r
+ }\r
+ else\r
+ {\r
+ // otherwise find which index the old node was relative to this node\r
+ TYPENAME std::vector<ntree_node<T>*>::iterator found =\r
+ std::find(parent->m_children.begin(), parent->m_children.end(), old_node);\r
+ // if this was found, then see if there is another\r
+ found++;\r
+ if (found != parent->m_children.end())\r
+ {\r
+ // if so traverse to it and walk down the leftmost child pointers to the bottom of the new sub-tree\r
+ ntree_node<T>* new_node = *found;\r
+ while (!new_node->m_children.empty())\r
+ new_node = new_node->m_children[0];\r
+ m_iterator.set(new_node->m_master);\r
+ }\r
+ else\r
+ {\r
+ // the parent's children have all been visited - so the parent is visited\r
+ m_iterator.set(parent->m_master);\r
+ }\r
+ }\r
+ return *this;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator ntree_postfix_iterator<T,TRef,TPtr>::operator ++ (int)\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ // post-increment is defined in terms of the pre-increment\r
+ ntree_postfix_iterator<T,TRef,TPtr> result(*this);\r
+ ++(*this);\r
+ return result;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::reference ntree_postfix_iterator<T,TRef,TPtr>::operator*(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return m_iterator.operator*();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::pointer ntree_postfix_iterator<T,TRef,TPtr>::operator->(void) const\r
+ throw(null_dereference,end_dereference)\r
+ {\r
+ return m_iterator.operator->();\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ const ntree_iterator<T,TRef,TPtr>& ntree_postfix_iterator<T,TRef,TPtr>::get_iterator(void) const\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ ntree_iterator<T,TRef,TPtr>& ntree_postfix_iterator<T,TRef,TPtr>::get_iterator(void)\r
+ {\r
+ return m_iterator;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // ntree\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename T>\r
+ ntree<T>::ntree(void) : m_root(0)\r
+ {\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T>::~ntree(void)\r
+ {\r
+ if (m_root) delete m_root;\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T>::ntree(const ntree<T>& r) : m_root(0)\r
+ {\r
+ *this = r;\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T>& ntree<T>::operator=(const ntree<T>& r)\r
+ {\r
+ if (m_root) delete m_root;\r
+ m_root = ntree_copy(this, r.m_root);\r
+ return *this;\r
+ }\r
+\r
+ template<typename T>\r
+ bool ntree<T>::empty(void) const\r
+ {\r
+ return m_root == 0;\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::size(void) const\r
+ {\r
+ return ntree_size(m_root);\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::size(const TYPENAME ntree<T>::const_iterator& i) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return ntree_size(i.node());\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::size(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return ntree_size(i.node());\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::depth(const TYPENAME ntree<T>::const_iterator& i) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return ntree_depth(i.node());\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::depth(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return ntree_depth(i.node());\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_iterator ntree<T>::root(void) const\r
+ {\r
+ if (!m_root) return ntree_iterator<T,const T&,const T*>(this);\r
+ return ntree_iterator<T,const T&,const T*>(m_root);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::root(void)\r
+ {\r
+ if (!m_root) return ntree_iterator<T,T&,T*>(this);\r
+ return ntree_iterator<T,T&,T*>(m_root);\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::children(const TYPENAME ntree<T>::const_iterator& i) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return i.node()->m_children.size();\r
+ }\r
+\r
+ template<typename T>\r
+ unsigned ntree<T>::children(const ntree_iterator<T,T&,T*>& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ return i.node()->m_children.size();\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_iterator ntree<T>::child(const TYPENAME ntree<T>::const_iterator& i, unsigned child) const\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ i.assert_valid(this);\r
+ if (child >= children(i)) throw std::out_of_range("stlplus::ntree");\r
+ return ntree_iterator<T,const T&,const T*>(i.node()->m_children[child]);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::child(const TYPENAME ntree<T>::iterator& i, unsigned child)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ i.assert_valid(this);\r
+ if (child >= children(i)) throw std::out_of_range("stlplus::ntree");\r
+ return ntree_iterator<T,T&,T*>(i.node()->m_children[child]);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_iterator ntree<T>::parent(const TYPENAME ntree<T>::const_iterator& i) const\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ ntree_node<T>* parent = i.node()->m_parent;\r
+ if (!parent) return ntree_iterator<T,const T&,const T*>(this);\r
+ return ntree_iterator<T,const T&,const T*>(parent);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::parent(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ i.assert_valid(this);\r
+ ntree_node<T>* parent = i.node()->m_parent;\r
+ if (!parent) return ntree_iterator<T,T&,T*>(this);\r
+ return ntree_iterator<T,T&,T*>(parent);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_prefix_iterator ntree<T>::prefix_begin(void) const\r
+ {\r
+ return ntree_prefix_iterator<T,const T&,const T*>(root());\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::prefix_iterator ntree<T>::prefix_begin(void)\r
+ {\r
+ return ntree_prefix_iterator<T,T&,T*>(root());\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_prefix_iterator ntree<T>::prefix_end(void) const\r
+ {\r
+ return ntree_prefix_iterator<T,const T&,const T*>(ntree_iterator<T,const T&,const T*>(this));\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::prefix_iterator ntree<T>::prefix_end(void)\r
+ {\r
+ return ntree_prefix_iterator<T,T&,T*>(ntree_iterator<T,T&,T*>(this));\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_postfix_iterator ntree<T>::postfix_begin(void) const\r
+ {\r
+ return ntree_postfix_iterator<T,const T&,const T*>(root());\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::postfix_iterator ntree<T>::postfix_begin(void)\r
+ {\r
+ return ntree_postfix_iterator<T,T&,T*>(root());\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::const_postfix_iterator ntree<T>::postfix_end(void) const\r
+ {\r
+ return ntree_postfix_iterator<T,const T&,const T*>(ntree_iterator<T,const T&,const T*>(this));\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::postfix_iterator ntree<T>::postfix_end(void)\r
+ {\r
+ return ntree_postfix_iterator<T,T&,T*>(ntree_iterator<T,T&,T*>(this));\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::insert(const T& data)\r
+ {\r
+ // insert a new node as the root\r
+ erase();\r
+ m_root = new ntree_node<T>(this,data);\r
+ return ntree_iterator<T,T&,T*>(m_root);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const T& data)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ // if i is the end iterator, this means insert a new root\r
+ // if (i.end())\r
+ // return insert(data);\r
+ // otherwise, insert a new child\r
+ i.assert_valid(this);\r
+ if (offset > children(i)) throw std::out_of_range("stlplus::ntree");\r
+ ntree_node<T>* new_node = new ntree_node<T>(this,data);\r
+ i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);\r
+ new_node->m_parent = i.node();\r
+ return ntree_iterator<T,T&,T*>(new_node);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, const T& data)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return insert(i, children(i), data);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const T& data)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return insert(i, children(i), data);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::insert(const ntree<T>& tree)\r
+ {\r
+ // insert a whole tree as root\r
+ erase();\r
+ m_root = ntree_copy(this, tree.m_root);\r
+ return ntree_iterator<T,T&,T*>(m_root);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const ntree<T>& tree)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ // insert a whole tree as a child of i\r
+ i.assert_valid(this);\r
+ if (offset > children(i)) throw std::out_of_range("stlplus::ntree");\r
+ ntree_node<T>* new_node = ntree_copy(this, tree.m_root);\r
+ i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);\r
+ new_node->m_parent = i.node();\r
+ return ntree_iterator<T,T&,T*>(new_node);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, const ntree<T>& tree)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return insert(i, children(i), tree);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const ntree<T>& tree)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return insert(i, children(i), tree);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::move(ntree<T>& tree)\r
+ {\r
+ // insert a whole tree as root, removing it from source\r
+ erase();\r
+ m_root = tree.m_root;\r
+ tree.m_root = 0;\r
+ if (m_root) m_root->change_owner(this);\r
+ return ntree_iterator<T,T&,T*>(m_root);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::move(const TYPENAME ntree<T>::iterator& i, unsigned offset, ntree<T>& tree)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ // insert a whole tree as a child of i\r
+ i.assert_valid(this);\r
+ if (offset > children(i)) throw std::out_of_range("stlplus::ntree");\r
+ ntree_node<T>* new_node = tree.m_root;\r
+ tree.m_root = 0;\r
+ if (new_node) new_node->change_owner(this);\r
+ i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);\r
+ new_node->m_parent = i.node();\r
+ return ntree_iterator<T,T&,T*>(new_node);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::move(const TYPENAME ntree<T>::iterator& i, ntree<T>& tree)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ return move(i, children(i), tree);\r
+ }\r
+\r
+ template<typename T>\r
+ TYPENAME ntree<T>::iterator ntree<T>::push(const TYPENAME ntree<T>::iterator& node, const T& data)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // insert a new node to replace the existing node in the tree\r
+ // making the original node the child of the new node\r
+ // i.e. (node) becomes (new)->(node)\r
+ // afterwards, the iterator still points to the old node, now the child\r
+ // returns the iterator to the new node\r
+ node.assert_valid(this);\r
+ ntree_node<T>* new_node = new ntree_node<T>(this,data);\r
+ if (node.node() == m_root)\r
+ {\r
+ // pushing the root node\r
+ m_root = new_node;\r
+ new_node->m_parent = 0;\r
+ }\r
+ else\r
+ {\r
+ // pushing a sub-node\r
+ *(std::find(node.node()->m_parent->m_children.begin(), node.node()->m_parent->m_children.end(), node.node())) = new_node;\r
+ new_node->m_parent = node.node()->m_parent;\r
+ }\r
+ // link up the old node as the child of the new node\r
+ new_node->m_children.insert(new_node->m_children.begin(),node.node());\r
+ node.node()->m_parent = new_node;\r
+ return ntree_iterator<T,T&,T*>(new_node);\r
+ }\r
+\r
+ template<typename T>\r
+ void ntree<T>::pop(const TYPENAME ntree<T>::iterator& parent, unsigned offset)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ // inverse of push\r
+ // removes the specified child of the parent node, adding its children to the parent node at the same offset\r
+ parent.assert_valid(this);\r
+ ntree_node<T>* node = parent.node();\r
+ if (offset >= node->m_children.size()) throw std::out_of_range("stlplus::ntree");\r
+ // move the grandchildren first\r
+ ntree_node<T>* child = parent.node()->m_children[offset];\r
+ while (!child->m_children.empty())\r
+ {\r
+ // remove the last grandchild and insert into node just after the child to be removed\r
+ ntree_node<T>* grandchild = child->m_children[child->m_children.size()-1];\r
+ child->m_children.pop_back();\r
+ node->m_children.insert(node->m_children.begin()+offset+1, grandchild);\r
+ grandchild->m_parent = node;\r
+ }\r
+ // now remove the child\r
+ node->m_children.erase(node->m_children.begin()+offset);\r
+ delete child;\r
+ }\r
+\r
+ template<typename T>\r
+ void ntree<T>::erase(void)\r
+ {\r
+ // erase the whole tree\r
+ erase(root());\r
+ }\r
+\r
+ template<typename T>\r
+ void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ if (!i.end())\r
+ {\r
+ // erase this node and its subtree\r
+ // do this by erasing this child of its parent\r
+ // handle the case of erasing the root\r
+ i.assert_valid(this);\r
+ ntree_node<T>* node = i.node();\r
+ if (node == m_root)\r
+ {\r
+ delete m_root;\r
+ m_root = 0;\r
+ }\r
+ else\r
+ {\r
+ ntree_node<T>* parent = node->m_parent;\r
+ // impossible for parent to be null - should assert this\r
+ TYPENAME std::vector<ntree_node<T>*>::iterator found = \r
+ std::find(parent->m_children.begin(), parent->m_children.end(), node);\r
+ // impossible for find to fail - should assert this\r
+ parent->m_children.erase(found);\r
+ delete node;\r
+ }\r
+ }\r
+ }\r
+\r
+ template<typename T>\r
+ void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i, unsigned offset)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ erase(child(i, offset));\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::subtree(void)\r
+ {\r
+ return subtree(root());\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ ntree<T> result;\r
+ if (!i.end())\r
+ {\r
+ i.assert_valid(this);\r
+ result.m_root = ntree_copy(&result, i.node());\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i, unsigned offset)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ return subtree(child(i, offset));\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::cut(void)\r
+ {\r
+ return cut(root());\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i)\r
+ throw(wrong_object,null_dereference,end_dereference)\r
+ {\r
+ ntree<T> result;\r
+ if (!i.end())\r
+ {\r
+ i.assert_valid(this);\r
+ ntree_node<T>* node = i.node();\r
+ if (node == m_root)\r
+ {\r
+ result.m_root = m_root;\r
+ m_root = 0;\r
+ }\r
+ else\r
+ {\r
+ ntree_node<T>* parent = node->m_parent;\r
+ // impossible for parent to be null - should assert this\r
+ TYPENAME std::vector<ntree_node<T>*>::iterator found = \r
+ std::find(parent->m_children.begin(), parent->m_children.end(), node);\r
+ // impossible for find to fail - should assert this\r
+ result.m_root = *found;\r
+ parent->m_children.erase(found);\r
+ }\r
+ if (result.m_root)\r
+ {\r
+ result.m_root->m_parent = 0;\r
+ result.m_root->set_new_owner(&result);\r
+ }\r
+ }\r
+ return result;\r
+ }\r
+\r
+ template<typename T>\r
+ ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i, unsigned offset)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range)\r
+ {\r
+ return cut(child(i, offset));\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
projects / chaz / yoink / blobdiff