X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2FMoof%2Fstlplus%2Fntree.hpp;fp=src%2FMoof%2Fstlplus%2Fntree.hpp;h=0000000000000000000000000000000000000000;hp=33817e2b54a816d1f77c4edfcc93f08655fc4d69;hb=831f04d4bc19a390415ac0bbac4331c7a65509bc;hpb=299af4f2047e767e5d79501c26444473bda64c64 diff --git a/src/Moof/stlplus/ntree.hpp b/src/Moof/stlplus/ntree.hpp deleted file mode 100755 index 33817e2..0000000 --- a/src/Moof/stlplus/ntree.hpp +++ /dev/null @@ -1,364 +0,0 @@ -#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 class ntree_node; - template class ntree; - template class ntree_iterator; - template class ntree_prefix_iterator; - template 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 - class ntree_iterator : public safe_iterator,ntree_node > - { - public: - // local type definitions - // an iterator points to an object whilst a const_iterator points to a const object - typedef ntree_iterator iterator; - typedef ntree_iterator const_iterator; - typedef ntree_iterator 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; - friend class ntree_prefix_iterator; - friend class ntree_postfix_iterator; - - 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* node); - // constructor used by ntree to create an end iterator - explicit ntree_iterator(const ntree* owner); - // used to create an alias of an iterator - explicit ntree_iterator(const safe_iterator, ntree_node >& 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 - class ntree_prefix_iterator - { - public: - typedef ntree_prefix_iterator iterator; - typedef ntree_prefix_iterator const_iterator; - typedef ntree_prefix_iterator this_iterator; - typedef ntree_iterator 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 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; - friend class ntree_iterator; - - private: - ntree_iterator m_iterator; - - explicit ntree_prefix_iterator(const ntree_iterator& i); - const ntree_iterator& get_iterator(void) const; - ntree_iterator& get_iterator(void); - }; - - //////////////////////////////////////////////////////////////////////////////// - - template - class ntree_postfix_iterator - { - public: - typedef ntree_postfix_iterator iterator; - typedef ntree_postfix_iterator const_iterator; - typedef ntree_postfix_iterator this_iterator; - typedef ntree_iterator 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 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; - friend class ntree_iterator; - - private: - ntree_iterator m_iterator; - - explicit ntree_postfix_iterator(const ntree_iterator& i); - const ntree_iterator& get_iterator(void) const; - ntree_iterator& get_iterator(void); - }; - - //////////////////////////////////////////////////////////////////////////////// - // The Ntree class - //////////////////////////////////////////////////////////////////////////////// - - template - class ntree - { - public: - // STL-like typedefs for the types and iterators - typedef T value_type; - - typedef ntree_iterator iterator; - typedef ntree_iterator const_iterator; - - typedef ntree_prefix_iterator prefix_iterator; - typedef ntree_prefix_iterator const_prefix_iterator; - - typedef ntree_postfix_iterator postfix_iterator; - typedef ntree_postfix_iterator const_postfix_iterator; - - ////////////////////////////////////////////////////////////////////////////// - // Constructors, destructors and copies - - ntree(void); - ~ntree(void); - - // copy constructor and assignment both copy the tree - ntree(const ntree&); - ntree& operator=(const ntree&); - - ////////////////////////////////////////////////////////////////////////////// - // 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&) - throw(wrong_object,null_dereference,end_dereference,std::out_of_range); - iterator append(const iterator& node, const ntree&) - 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 subtree(void); - ntree subtree(const iterator& node) - throw(wrong_object,null_dereference,end_dereference); - ntree subtree(const iterator& node, unsigned child) - throw(wrong_object,null_dereference,end_dereference,std::out_of_range); - - ntree cut(void); - ntree cut(const iterator& node) - throw(wrong_object,null_dereference,end_dereference); - ntree cut(const iterator& node, unsigned child) - throw(wrong_object,null_dereference,end_dereference,std::out_of_range); - - ////////////////////////////////////////////////////////////////////////////// - - private: - ntree_node* m_root; - }; - - //////////////////////////////////////////////////////////////////////////////// - -} // end namespace stlplus - -#include "ntree.tpp" -#endif