X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2Fstlplus%2Fcontainers%2Fntree.tpp;fp=src%2Fstlplus%2Fcontainers%2Fntree.tpp;h=6fd019d9f30b7eee6fe71ebd682e9667172060c4;hp=0000000000000000000000000000000000000000;hb=6b0a0d0efafe34d48ab344fca3b479553bd4e62c;hpb=85783316365181491a3e3c0c63659972477cebba

diff --git a/src/stlplus/containers/ntree.tpp b/src/stlplus/containers/ntree.tpp
new file mode 100644
index 0000000..6fd019d
--- /dev/null
+++ b/src/stlplus/containers/ntree.tpp
@@ -0,0 +1,913 @@
+////////////////////////////////////////////////////////////////////////////////
+
+//   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
+