-#ifndef STLPLUS_NTREE
-#define STLPLUS_NTREE
-////////////////////////////////////////////////////////////////////////////////
-
-// Author: Andy Rushton
-// Copyright: (c) Southampton University 1999-2004
-// (c) Andy Rushton 2004-2009
-// License: BSD License, see ../docs/license.html
-
-// A templated n-ary tree data structure. STL-like but the definition of
-// iterators is really only applicable to one-dimensional structures. I use
-// iterators to access tree nodes, but there is no increment or decrement
-// operators for them. I also define prefix and postfix traversal iterators
-// which do have increment.
-
-////////////////////////////////////////////////////////////////////////////////
-#include "containers_fixes.hpp"
-#include "exceptions.hpp"
-#include "safe_iterator.hpp"
-
-namespace stlplus
-{
-
- ////////////////////////////////////////////////////////////////////////////////
- // Internals
-
- template<typename T> class ntree_node;
- template<typename T> class ntree;
- template<typename T, typename TRef, typename TPtr> class ntree_iterator;
- template<typename T, typename TRef, typename TPtr> class ntree_prefix_iterator;
- template<typename T, typename TRef, typename TPtr> class ntree_postfix_iterator;
-
- ////////////////////////////////////////////////////////////////////////////////
- // Iterators
-
- // Simple iterators which are just used as pointers to tree nodes. These have
- // no increment or decrement operations defined. An uninitialised iterator is
- // null - similarly, if you ask for the root of an empty tree or the parent of
- // the root node then you get a null iterator.
-
- template<typename T, typename TRef, typename TPtr>
- class ntree_iterator : public safe_iterator<ntree<T>,ntree_node<T> >
- {
- public:
- // local type definitions
- // an iterator points to an object whilst a const_iterator points to a const object
- typedef ntree_iterator<T,T&,T*> iterator;
- typedef ntree_iterator<T,const T&,const T*> const_iterator;
- typedef ntree_iterator<T,TRef,TPtr> this_iterator;
- typedef TRef reference;
- typedef TPtr pointer;
-
- // constructor to create a null iterator - you must assign a valid value to this iterator before using it
- ntree_iterator(void);
- ~ntree_iterator(void);
-
- // Type conversion methods allow const_iterator and iterator to be converted
- const_iterator constify(void) const;
- iterator deconstify(void) const;
-
- // tests useful for putting iterators into other STL structures and for testing whether iteration has completed
- bool operator == (const this_iterator& r) const;
- bool operator != (const this_iterator& r) const;
- bool operator < (const this_iterator& r) const;
-
- // access the node data - a const_iterator gives you a const element, an iterator a non-const element
- // it is illegal to dereference an invalid (i.e. null or end) iterator
- reference operator*(void) const
- throw(null_dereference,end_dereference);
- pointer operator->(void) const
- throw(null_dereference,end_dereference);
-
- friend class ntree<T>;
- friend class ntree_prefix_iterator<T,TRef,TPtr>;
- friend class ntree_postfix_iterator<T,TRef,TPtr>;
-
- public:
- // Note: I had to make this public to get round a compiler problem - it should be private
- // you cannot create a valid iterator except by calling an ntree method that returns one
- // constructor used by ntree to create a non-null iterator
- explicit ntree_iterator(ntree_node<T>* node);
- // constructor used by ntree to create an end iterator
- explicit ntree_iterator(const ntree<T>* owner);
- // used to create an alias of an iterator
- explicit ntree_iterator(const safe_iterator<ntree<T>, ntree_node<T> >& iterator);
- };
-
- // Traversal iterators are like iterators but they have increment operators (++)
- // - prefix_iterator visits the nodes of the tree in prefix order
- // - postfix_iterator visits the nodes of the tree in postfix order.
- // There is no such thing as infix order for an n-ary tree and you cannot
- // traverse backwards with these iterators. These follow the STL convention in
- // that you iterate from a begin to an end - in this case ntree exports
- // prefix_begin()/prefix_end() and postfix_begin()/postfix_end(). You can
- // simplify these iterators to the basic iterator above for functions that
- // require a simple iterator.
-
- template<typename T, typename TRef, typename TPtr>
- class ntree_prefix_iterator
- {
- public:
- typedef ntree_prefix_iterator<T,T&,T*> iterator;
- typedef ntree_prefix_iterator<T,const T&,const T*> const_iterator;
- typedef ntree_prefix_iterator<T,TRef,TPtr> this_iterator;
- typedef ntree_iterator<T,TRef,TPtr> simple_iterator;
- typedef TRef reference;
- typedef TPtr pointer;
-
- // constructor to create a null iterator - you must assign a valid value to this iterator before using it
- ntree_prefix_iterator(void);
- ~ntree_prefix_iterator(void);
-
- // tests
- // a null iterator is one that has not been initialised with a value yet
- // i.e. you just declared it but didn't assign to it
- bool null(void) const;
- // an end iterator is one that points to the end element of the list of nodes
- // in STL conventions this is one past the last valid element and must not be dereferenced
- bool end(void) const;
- // a valid iterator is one that can be dereferenced
- // i.e. non-null and non-end
- bool valid(void) const;
-
- // Type conversion methods allow const_iterator and iterator to be converted
- // convert an iterator/const_iterator to a const_iterator
- const_iterator constify(void) const;
- iterator deconstify(void) const;
-
- // generate a simple iterator from a traversal iterator
- ntree_iterator<T,TRef,TPtr> simplify(void) const;
-
- // tests useful for putting iterators into other STL structures and for testing whether iteration has completed
- bool operator == (const this_iterator& r) const;
- bool operator != (const this_iterator& r) const;
- bool operator < (const this_iterator& r) const;
-
- // increment/decrement operators used to step through the set of all nodes in a graph
- // it is only legal to increment a valid iterator
- // pre-increment
- this_iterator& operator ++ (void)
- throw(null_dereference,end_dereference);
- // post-increment
- this_iterator operator ++ (int)
- throw(null_dereference,end_dereference);
-
- // access the node data - a const_iterator gives you a const element, an iterator a non-const element
- // it is illegal to dereference an invalid (i.e. null or end) iterator
- reference operator*(void) const
- throw(null_dereference,end_dereference);
- pointer operator->(void) const
- throw(null_dereference,end_dereference);
-
- friend class ntree<T>;
- friend class ntree_iterator<T,TRef,TPtr>;
-
- private:
- ntree_iterator<T,TRef,TPtr> m_iterator;
-
- explicit ntree_prefix_iterator(const ntree_iterator<T,TRef,TPtr>& i);
- const ntree_iterator<T,TRef,TPtr>& get_iterator(void) const;
- ntree_iterator<T,TRef,TPtr>& get_iterator(void);
- };
-
- ////////////////////////////////////////////////////////////////////////////////
-
- template<typename T, typename TRef, typename TPtr>
- class ntree_postfix_iterator
- {
- public:
- typedef ntree_postfix_iterator<T,T&,T*> iterator;
- typedef ntree_postfix_iterator<T,const T&,const T*> const_iterator;
- typedef ntree_postfix_iterator<T,TRef,TPtr> this_iterator;
- typedef ntree_iterator<T,TRef,TPtr> simple_iterator;
- typedef TRef reference;
- typedef TPtr pointer;
-
- // constructor to create a null iterator - you must assign a valid value to this iterator before using it
- ntree_postfix_iterator(void);
- ~ntree_postfix_iterator(void);
-
- // tests
- // a null iterator is one that has not been initialised with a value yet
- // i.e. you just declared it but didn't assign to it
- bool null(void) const;
- // an end iterator is one that points to the end element of the list of nodes
- // in STL conventions this is one past the last valid element and must not be dereferenced
- bool end(void) const;
- // a valid iterator is one that can be dereferenced
- // i.e. non-null and non-end
- bool valid(void) const;
-
- // Type conversion methods allow const_iterator and iterator to be converted
- // convert an iterator/const_iterator to a const_iterator
- const_iterator constify(void) const;
- iterator deconstify(void) const;
-
- // generate a simple iterator from a traversal iterator
- ntree_iterator<T,TRef,TPtr> simplify(void) const;
-
- // tests useful for putting iterators into other STL structures and for testing whether iteration has completed
- bool operator == (const this_iterator& r) const;
- bool operator != (const this_iterator& r) const;
- bool operator < (const this_iterator& r) const;
-
- // increment/decrement operators used to step through the set of all nodes in a graph
- // it is only legal to increment a valid iterator
- // pre-increment
- this_iterator& operator ++ (void)
- throw(null_dereference,end_dereference);
- // post-increment
- this_iterator operator ++ (int)
- throw(null_dereference,end_dereference);
-
- // access the node data - a const_iterator gives you a const element, an iterator a non-const element
- // it is illegal to dereference an invalid (i.e. null or end) iterator
- reference operator*(void) const
- throw(null_dereference,end_dereference);
- pointer operator->(void) const
- throw(null_dereference,end_dereference);
-
- friend class ntree<T>;
- friend class ntree_iterator<T,TRef,TPtr>;
-
- private:
- ntree_iterator<T,TRef,TPtr> m_iterator;
-
- explicit ntree_postfix_iterator(const ntree_iterator<T,TRef,TPtr>& i);
- const ntree_iterator<T,TRef,TPtr>& get_iterator(void) const;
- ntree_iterator<T,TRef,TPtr>& get_iterator(void);
- };
-
- ////////////////////////////////////////////////////////////////////////////////
- // The Ntree class
- ////////////////////////////////////////////////////////////////////////////////
-
- template<typename T>
- class ntree
- {
- public:
- // STL-like typedefs for the types and iterators
- typedef T value_type;
-
- typedef ntree_iterator<T,T&,T*> iterator;
- typedef ntree_iterator<T,const T&,const T*> const_iterator;
-
- typedef ntree_prefix_iterator<T,T&,T*> prefix_iterator;
- typedef ntree_prefix_iterator<T,const T&,const T*> const_prefix_iterator;
-
- typedef ntree_postfix_iterator<T,T&,T*> postfix_iterator;
- typedef ntree_postfix_iterator<T,const T&,const T*> const_postfix_iterator;
-
- //////////////////////////////////////////////////////////////////////////////
- // Constructors, destructors and copies
-
- ntree(void);
- ~ntree(void);
-
- // copy constructor and assignment both copy the tree
- ntree(const ntree<T>&);
- ntree<T>& operator=(const ntree<T>&);
-
- //////////////////////////////////////////////////////////////////////////////
- // size tests
-
- // tests on whole tree
- bool empty(void) const;
- unsigned size(void) const;
-
- // tests for number of nodes in subtree starting at node
- unsigned size(const const_iterator& node) const
- throw(wrong_object,null_dereference,end_dereference);
- unsigned size(const iterator& node)
- throw(wrong_object,null_dereference,end_dereference);
-
- // test for depth of tree from root to node
- unsigned depth(const const_iterator& node) const
- throw(wrong_object,null_dereference,end_dereference);
- unsigned depth(const iterator& node)
- throw(wrong_object,null_dereference,end_dereference);
-
- //////////////////////////////////////////////////////////////////////////////
- // direct traversal
-
- const_iterator root(void) const;
- iterator root(void);
-
- unsigned children(const const_iterator& node) const
- throw(wrong_object,null_dereference,end_dereference);
- unsigned children(const iterator& node)
- throw(wrong_object,null_dereference,end_dereference);
-
- const_iterator child(const const_iterator& node, unsigned child) const
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
- iterator child(const iterator& node, unsigned child)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
-
- const_iterator parent(const const_iterator& node) const
- throw(wrong_object,null_dereference,end_dereference);
- iterator parent(const iterator& node)
- throw(wrong_object,null_dereference,end_dereference);
-
- //////////////////////////////////////////////////////////////////////////////
- // iterator traversal
-
- const_prefix_iterator prefix_begin(void) const;
- prefix_iterator prefix_begin(void);
- const_prefix_iterator prefix_end(void) const;
- prefix_iterator prefix_end(void);
-
- const_postfix_iterator postfix_begin(void) const;
- postfix_iterator postfix_begin(void);
- const_postfix_iterator postfix_end(void) const;
- postfix_iterator postfix_end(void);
-
- //////////////////////////////////////////////////////////////////////////////
- // modification
-
- iterator insert(const T&);
-
- iterator insert(const iterator& node, unsigned child, const T&)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
- iterator append(const iterator& node, const T&)
- throw(wrong_object,null_dereference,end_dereference);
-
- iterator insert(const iterator& node, unsigned child, const ntree<T>&)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
- iterator append(const iterator& node, const ntree<T>&)
- throw(wrong_object,null_dereference,end_dereference);
-
- iterator push(const iterator& node, const T&)
- throw(wrong_object,null_dereference,end_dereference);
- void pop(const iterator& node, unsigned child)
- throw(wrong_object,null_dereference,end_dereference);
-
- void erase(void);
- void erase(const iterator& node)
- throw(wrong_object,null_dereference,end_dereference);
- void erase(const iterator& node, unsigned child)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
-
- ntree<T> subtree(void);
- ntree<T> subtree(const iterator& node)
- throw(wrong_object,null_dereference,end_dereference);
- ntree<T> subtree(const iterator& node, unsigned child)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
-
- ntree<T> cut(void);
- ntree<T> cut(const iterator& node)
- throw(wrong_object,null_dereference,end_dereference);
- ntree<T> cut(const iterator& node, unsigned child)
- throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
-
- //////////////////////////////////////////////////////////////////////////////
-
- private:
- ntree_node<T>* m_root;
- };
-
- ////////////////////////////////////////////////////////////////////////////////
-
-} // end namespace stlplus
-
-#include "ntree.tpp"
-#endif
+#ifndef STLPLUS_NTREE\r
+#define STLPLUS_NTREE\r
+////////////////////////////////////////////////////////////////////////////////\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
+// A templated n-ary tree data structure. STL-like but the definition of\r
+// iterators is really only applicable to one-dimensional structures. I use\r
+// iterators to access tree nodes, but there is no increment or decrement\r
+// operators for them. I also define prefix and postfix traversal iterators\r
+// which do have increment.\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+#include "exceptions.hpp"\r
+#include "safe_iterator.hpp"\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Internals\r
+\r
+ template<typename T> class ntree_node;\r
+ template<typename T> class ntree;\r
+ template<typename T, typename TRef, typename TPtr> class ntree_iterator;\r
+ template<typename T, typename TRef, typename TPtr> class ntree_prefix_iterator;\r
+ template<typename T, typename TRef, typename TPtr> class ntree_postfix_iterator;\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Iterators\r
+\r
+ // Simple iterators which are just used as pointers to tree nodes. These have\r
+ // no increment or decrement operations defined. An uninitialised iterator is\r
+ // null - similarly, if you ask for the root of an empty tree or the parent of\r
+ // the root node then you get a null iterator.\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ class ntree_iterator : public safe_iterator<ntree<T>,ntree_node<T> >\r
+ {\r
+ public:\r
+ // local type definitions\r
+ // an iterator points to an object whilst a const_iterator points to a const object\r
+ typedef ntree_iterator<T,T&,T*> iterator;\r
+ typedef ntree_iterator<T,const T&,const T*> const_iterator;\r
+ typedef ntree_iterator<T,TRef,TPtr> this_iterator;\r
+ typedef TRef reference;\r
+ typedef TPtr pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ ntree_iterator(void);\r
+ ~ntree_iterator(void);\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ const_iterator constify(void) const;\r
+ iterator deconstify(void) const;\r
+\r
+ // tests useful for putting iterators into other STL structures and for testing whether iteration has completed\r
+ bool operator == (const this_iterator& r) const;\r
+ bool operator != (const this_iterator& r) const;\r
+ bool operator < (const this_iterator& r) const;\r
+\r
+ // access the node data - a const_iterator gives you a const element, an iterator a non-const element\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ friend class ntree<T>;\r
+ friend class ntree_prefix_iterator<T,TRef,TPtr>;\r
+ friend class ntree_postfix_iterator<T,TRef,TPtr>;\r
+\r
+ public:\r
+ // Note: I had to make this public to get round a problem implementing persistence - it should be private\r
+ // you cannot create a valid iterator except by calling an ntree method that returns one\r
+ // constructor used by ntree to create a non-null iterator\r
+ explicit ntree_iterator(ntree_node<T>* node);\r
+ // constructor used by ntree to create an end iterator\r
+ explicit ntree_iterator(const ntree<T>* owner);\r
+ // used to create an alias of an iterator\r
+ explicit ntree_iterator(const safe_iterator<ntree<T>, ntree_node<T> >& iterator);\r
+ };\r
+\r
+ // Traversal iterators are like iterators but they have increment operators (++)\r
+ // - prefix_iterator visits the nodes of the tree in prefix order\r
+ // - postfix_iterator visits the nodes of the tree in postfix order.\r
+ // There is no such thing as infix order for an n-ary tree and you cannot\r
+ // traverse backwards with these iterators. These follow the STL convention in\r
+ // that you iterate from a begin to an end - in this case ntree exports\r
+ // prefix_begin()/prefix_end() and postfix_begin()/postfix_end(). You can\r
+ // simplify these iterators to the basic iterator above for functions that\r
+ // require a simple iterator.\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ class ntree_prefix_iterator\r
+ {\r
+ public:\r
+ typedef ntree_prefix_iterator<T,T&,T*> iterator;\r
+ typedef ntree_prefix_iterator<T,const T&,const T*> const_iterator;\r
+ typedef ntree_prefix_iterator<T,TRef,TPtr> this_iterator;\r
+ typedef ntree_iterator<T,TRef,TPtr> simple_iterator;\r
+ typedef TRef reference;\r
+ typedef TPtr pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ ntree_prefix_iterator(void);\r
+ ~ntree_prefix_iterator(void);\r
+\r
+ // tests\r
+ // a null iterator is one that has not been initialised with a value yet\r
+ // i.e. you just declared it but didn't assign to it\r
+ bool null(void) const;\r
+ // an end iterator is one that points to the end element of the list of nodes\r
+ // in STL conventions this is one past the last valid element and must not be dereferenced\r
+ bool end(void) const;\r
+ // a valid iterator is one that can be dereferenced\r
+ // i.e. non-null and non-end\r
+ bool valid(void) const;\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ // convert an iterator/const_iterator to a const_iterator\r
+ const_iterator constify(void) const;\r
+ iterator deconstify(void) const;\r
+\r
+ // generate a simple iterator from a traversal iterator\r
+ ntree_iterator<T,TRef,TPtr> simplify(void) const;\r
+\r
+ // tests useful for putting iterators into other STL structures and for testing whether iteration has completed\r
+ bool operator == (const this_iterator& r) const;\r
+ bool operator != (const this_iterator& r) const;\r
+ bool operator < (const this_iterator& r) const;\r
+\r
+ // increment/decrement operators used to step through the set of all nodes in a graph\r
+ // it is only legal to increment a valid iterator\r
+ // pre-increment\r
+ this_iterator& operator ++ (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-increment\r
+ this_iterator operator ++ (int)\r
+ throw(null_dereference,end_dereference);\r
+\r
+ // access the node data - a const_iterator gives you a const element, an iterator a non-const element\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ friend class ntree<T>;\r
+ friend class ntree_iterator<T,TRef,TPtr>;\r
+\r
+ private:\r
+ ntree_iterator<T,TRef,TPtr> m_iterator;\r
+\r
+ explicit ntree_prefix_iterator(const ntree_iterator<T,TRef,TPtr>& i);\r
+ const ntree_iterator<T,TRef,TPtr>& get_iterator(void) const;\r
+ ntree_iterator<T,TRef,TPtr>& get_iterator(void);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename T, typename TRef, typename TPtr>\r
+ class ntree_postfix_iterator\r
+ {\r
+ public:\r
+ typedef ntree_postfix_iterator<T,T&,T*> iterator;\r
+ typedef ntree_postfix_iterator<T,const T&,const T*> const_iterator;\r
+ typedef ntree_postfix_iterator<T,TRef,TPtr> this_iterator;\r
+ typedef ntree_iterator<T,TRef,TPtr> simple_iterator;\r
+ typedef TRef reference;\r
+ typedef TPtr pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ ntree_postfix_iterator(void);\r
+ ~ntree_postfix_iterator(void);\r
+\r
+ // tests\r
+ // a null iterator is one that has not been initialised with a value yet\r
+ // i.e. you just declared it but didn't assign to it\r
+ bool null(void) const;\r
+ // an end iterator is one that points to the end element of the list of nodes\r
+ // in STL conventions this is one past the last valid element and must not be dereferenced\r
+ bool end(void) const;\r
+ // a valid iterator is one that can be dereferenced\r
+ // i.e. non-null and non-end\r
+ bool valid(void) const;\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ // convert an iterator/const_iterator to a const_iterator\r
+ const_iterator constify(void) const;\r
+ iterator deconstify(void) const;\r
+\r
+ // generate a simple iterator from a traversal iterator\r
+ ntree_iterator<T,TRef,TPtr> simplify(void) const;\r
+\r
+ // tests useful for putting iterators into other STL structures and for testing whether iteration has completed\r
+ bool operator == (const this_iterator& r) const;\r
+ bool operator != (const this_iterator& r) const;\r
+ bool operator < (const this_iterator& r) const;\r
+\r
+ // increment/decrement operators used to step through the set of all nodes in a graph\r
+ // it is only legal to increment a valid iterator\r
+ // pre-increment\r
+ this_iterator& operator ++ (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-increment\r
+ this_iterator operator ++ (int)\r
+ throw(null_dereference,end_dereference);\r
+\r
+ // access the node data - a const_iterator gives you a const element, an iterator a non-const element\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ friend class ntree<T>;\r
+ friend class ntree_iterator<T,TRef,TPtr>;\r
+\r
+ private:\r
+ ntree_iterator<T,TRef,TPtr> m_iterator;\r
+\r
+ explicit ntree_postfix_iterator(const ntree_iterator<T,TRef,TPtr>& i);\r
+ const ntree_iterator<T,TRef,TPtr>& get_iterator(void) const;\r
+ ntree_iterator<T,TRef,TPtr>& get_iterator(void);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // The Ntree class\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename T>\r
+ class ntree\r
+ {\r
+ public:\r
+ // STL-like typedefs for the types and iterators\r
+ typedef T value_type;\r
+\r
+ typedef ntree_iterator<T,T&,T*> iterator;\r
+ typedef ntree_iterator<T,const T&,const T*> const_iterator;\r
+\r
+ typedef ntree_prefix_iterator<T,T&,T*> prefix_iterator;\r
+ typedef ntree_prefix_iterator<T,const T&,const T*> const_prefix_iterator;\r
+\r
+ typedef ntree_postfix_iterator<T,T&,T*> postfix_iterator;\r
+ typedef ntree_postfix_iterator<T,const T&,const T*> const_postfix_iterator;\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // Constructors, destructors and copies\r
+\r
+ ntree(void);\r
+ ~ntree(void);\r
+\r
+ // copy constructor and assignment both copy the tree\r
+ ntree(const ntree<T>&);\r
+ ntree<T>& operator=(const ntree<T>&);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // size tests\r
+\r
+ // tests on whole tree\r
+ bool empty(void) const;\r
+ unsigned size(void) const;\r
+\r
+ // tests for number of nodes in subtree starting at node\r
+ unsigned size(const const_iterator& node) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned size(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // test for depth of tree from root to node\r
+ unsigned depth(const const_iterator& node) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned depth(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // direct traversal\r
+\r
+ const_iterator root(void) const;\r
+ iterator root(void);\r
+\r
+ unsigned children(const const_iterator& node) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned children(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ const_iterator child(const const_iterator& node, unsigned child) const\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ iterator child(const iterator& node, unsigned child)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ const_iterator parent(const const_iterator& node) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ iterator parent(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // iterator traversal\r
+\r
+ const_prefix_iterator prefix_begin(void) const;\r
+ prefix_iterator prefix_begin(void);\r
+ const_prefix_iterator prefix_end(void) const;\r
+ prefix_iterator prefix_end(void);\r
+\r
+ const_postfix_iterator postfix_begin(void) const;\r
+ postfix_iterator postfix_begin(void);\r
+ const_postfix_iterator postfix_end(void) const;\r
+ postfix_iterator postfix_end(void);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+ // modification\r
+\r
+ // discard previous contents and create a new root node\r
+ iterator insert(const T&);\r
+ // add a new child inserted into the node's children at the specified place\r
+ iterator insert(const iterator& node, unsigned child, const T&)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ // shortcut for insert at the end i.e. tree.insert(node, node.children(), value)\r
+ iterator insert(const iterator& node, const T&) \r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // old name for the above\r
+ iterator append(const iterator& node, const T&) \r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // discard previous contents and copy the tree\r
+ iterator insert(const ntree<T>&);\r
+ // add a copy of the tree as a new child inserted into the node's children at the specified place\r
+ iterator insert(const iterator& node, unsigned child, const ntree<T>&)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ // shortcut for insert at the end i.e. tree.insert(node, node.children(), value)\r
+ iterator insert(const iterator& node, const ntree<T>&)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // old name for the above\r
+ iterator append(const iterator& node, const ntree<T>&)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // discard previous contents and move the tree without copying\r
+ // invalidates all iterators to the old tree\r
+ iterator move(ntree<T>&);\r
+ // move the tree to become the designated child\r
+ // invalidates all iterators to the old tree\r
+ iterator move(const iterator& node, unsigned child, ntree<T>&)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ // shortcut for move to the last child i.e. node.move(node, node.children(), value)\r
+ iterator move(const iterator& node, ntree<T>&)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // replace the node with the new value, pushing the old node down to make it the child\r
+ // returns the iterator to the new, pushed node\r
+ iterator push(const iterator& node, const T&) \r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // erases the specified child, moving its children up to become the node's children\r
+ void pop(const iterator& node, unsigned child) \r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // erase the whole tree\r
+ void erase(void);\r
+ // erase the node and all its children\r
+ void erase(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // erase the specified child\r
+ void erase(const iterator& node, unsigned child)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ // get a copy of the tree as a tree\r
+ ntree<T> subtree(void);\r
+ // get a copy of the subtree as a tree with the specified node as root\r
+ ntree<T> subtree(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // get a copy of the subtree as a tree with the specified child as root\r
+ ntree<T> subtree(const iterator& node, unsigned child)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ // move the whole tree to make a new tree\r
+ ntree<T> cut(void);\r
+ // move the subtree to make a new tree with the specified node as root\r
+ ntree<T> cut(const iterator& node)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // move the subtree to make a new tree with the specified child as root\r
+ ntree<T> cut(const iterator& node, unsigned child)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ //////////////////////////////////////////////////////////////////////////////\r
+\r
+ private:\r
+ ntree_node<T>* m_root;\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#include "ntree.tpp"\r
+#endif\r
projects / chaz / yoink / blobdiff