Dogcows Code - chaz/yoink/blob - ntree.hpp

   1 #ifndef STLPLUS_NTREE
   2 #define STLPLUS_NTREE
   3 ////////////////////////////////////////////////////////////////////////////////
   4
   5 //   Author:    Andy Rushton
   6 //   Copyright: (c) Southampton University 1999-2004
   7 //              (c) Andy Rushton           2004-2009
   8 //   License:   BSD License, see ../docs/license.html
   9
  10 //   A templated n-ary tree data structure. STL-like but the definition of
  11 //   iterators is really only applicable to one-dimensional structures. I use
  12 //   iterators to access tree nodes, but there is no increment or decrement
  13 //   operators for them. I also define prefix and postfix traversal iterators
  14 //   which do have increment.
  15
  16 ////////////////////////////////////////////////////////////////////////////////
  17 #include "containers_fixes.hpp"
  18 #include "exceptions.hpp"
  19 #include "safe_iterator.hpp"
  20
  21 namespace stlplus
  22 {
  23
  24   ////////////////////////////////////////////////////////////////////////////////
  25   // Internals
  26
  27   template<typename T> class ntree_node;
  28   template<typename T> class ntree;
  29   template<typename T, typename TRef, typename TPtr> class ntree_iterator;
  30   template<typename T, typename TRef, typename TPtr> class ntree_prefix_iterator;
  31   template<typename T, typename TRef, typename TPtr> class ntree_postfix_iterator;
  32
  33   ////////////////////////////////////////////////////////////////////////////////
  34   // Iterators
  35
  36   // Simple iterators which are just used as pointers to tree nodes. These have
  37   // no increment or decrement operations defined. An uninitialised iterator is
  38   // null - similarly, if you ask for the root of an empty tree or the parent of
  39   // the root node then you get a null iterator.
  40
  41   template<typename T, typename TRef, typename TPtr>
  42   class ntree_iterator : public safe_iterator<ntree<T>,ntree_node<T> >
  43   {
  44   public:
  45     // local type definitions
  46     // an iterator points to an object whilst a const_iterator points to a const object
  47     typedef ntree_iterator<T,T&,T*> iterator;
  48     typedef ntree_iterator<T,const T&,const T*> const_iterator;
  49     typedef ntree_iterator<T,TRef,TPtr> this_iterator;
  50     typedef TRef reference;
  51     typedef TPtr pointer;
  52
  53     // constructor to create a null iterator - you must assign a valid value to this iterator before using it
  54     ntree_iterator(void);
  55     ~ntree_iterator(void);
  56
  57     // Type conversion methods allow const_iterator and iterator to be converted
  58     const_iterator constify(void) const;
  59     iterator deconstify(void) const;
  60
  61     // tests useful for putting iterators into other STL structures and for testing whether iteration has completed
  62     bool operator == (const this_iterator& r) const;
  63     bool operator != (const this_iterator& r) const;
  64     bool operator < (const this_iterator& r) const;
  65
  66     // access the node data - a const_iterator gives you a const element, an iterator a non-const element
  67     // it is illegal to dereference an invalid (i.e. null or end) iterator
  68     reference operator*(void) const
  69       throw(null_dereference,end_dereference);
  70     pointer operator->(void) const
  71       throw(null_dereference,end_dereference);
  72
  73     friend class ntree<T>;
  74     friend class ntree_prefix_iterator<T,TRef,TPtr>;
  75     friend class ntree_postfix_iterator<T,TRef,TPtr>;
  76
  77   public:
  78     // Note: I had to make this public to get round a compiler problem - it should be private
  79     // you cannot create a valid iterator except by calling an ntree method that returns one
  80     // constructor used by ntree to create a non-null iterator
  81     explicit ntree_iterator(ntree_node<T>* node);
  82     // constructor used by ntree to create an end iterator
  83     explicit ntree_iterator(const ntree<T>* owner);
  84     // used to create an alias of an iterator
  85     explicit ntree_iterator(const safe_iterator<ntree<T>, ntree_node<T> >& iterator);
  86   };
  87
  88   // Traversal iterators are like iterators but they have increment operators (++)
  89   // - prefix_iterator visits the nodes of the tree in prefix order
  90   // - postfix_iterator visits the nodes of the tree in postfix order.
  91   // There is no such thing as infix order for an n-ary tree and you cannot
  92   // traverse backwards with these iterators. These follow the STL convention in
  93   // that you iterate from a begin to an end - in this case ntree exports
  94   // prefix_begin()/prefix_end() and postfix_begin()/postfix_end(). You can
  95   // simplify these iterators to the basic iterator above for functions that
  96   // require a simple iterator.
  97
  98   template<typename T, typename TRef, typename TPtr>
  99   class ntree_prefix_iterator
 100   {
 101   public:
 102     typedef ntree_prefix_iterator<T,T&,T*>             iterator;
 103     typedef ntree_prefix_iterator<T,const T&,const T*> const_iterator;
 104     typedef ntree_prefix_iterator<T,TRef,TPtr>         this_iterator;
 105     typedef ntree_iterator<T,TRef,TPtr>                simple_iterator;
 106     typedef TRef                                       reference;
 107     typedef TPtr                                       pointer;
 108
 109     // constructor to create a null iterator - you must assign a valid value to this iterator before using it
 110     ntree_prefix_iterator(void);
 111     ~ntree_prefix_iterator(void);
 112
 113     // tests
 114     // a null iterator is one that has not been initialised with a value yet
 115     // i.e. you just declared it but didn't assign to it
 116     bool null(void) const;
 117     // an end iterator is one that points to the end element of the list of nodes
 118     // in STL conventions this is one past the last valid element and must not be dereferenced
 119     bool end(void) const;
 120     // a valid iterator is one that can be dereferenced
 121     // i.e. non-null and non-end
 122     bool valid(void) const;
 123
 124     // Type conversion methods allow const_iterator and iterator to be converted
 125     // convert an iterator/const_iterator to a const_iterator
 126     const_iterator constify(void) const;
 127     iterator deconstify(void) const;
 128
 129     // generate a simple iterator from a traversal iterator
 130     ntree_iterator<T,TRef,TPtr> simplify(void) const;
 131
 132     // tests useful for putting iterators into other STL structures and for testing whether iteration has completed
 133     bool operator == (const this_iterator& r) const;
 134     bool operator != (const this_iterator& r) const;
 135     bool operator < (const this_iterator& r) const;
 136
 137     // increment/decrement operators used to step through the set of all nodes in a graph
 138     // it is only legal to increment a valid iterator
 139     // pre-increment
 140     this_iterator& operator ++ (void)
 141       throw(null_dereference,end_dereference);
 142     // post-increment
 143     this_iterator operator ++ (int)
 144       throw(null_dereference,end_dereference);
 145
 146     // access the node data - a const_iterator gives you a const element, an iterator a non-const element
 147     // it is illegal to dereference an invalid (i.e. null or end) iterator
 148     reference operator*(void) const
 149       throw(null_dereference,end_dereference);
 150     pointer operator->(void) const
 151       throw(null_dereference,end_dereference);
 152
 153     friend class ntree<T>;
 154     friend class ntree_iterator<T,TRef,TPtr>;
 155
 156   private:
 157     ntree_iterator<T,TRef,TPtr> m_iterator;
 158
 159     explicit ntree_prefix_iterator(const ntree_iterator<T,TRef,TPtr>& i);
 160     const ntree_iterator<T,TRef,TPtr>& get_iterator(void) const;
 161     ntree_iterator<T,TRef,TPtr>& get_iterator(void);
 162   };
 163
 164   ////////////////////////////////////////////////////////////////////////////////
 165
 166   template<typename T, typename TRef, typename TPtr>
 167   class ntree_postfix_iterator
 168   {
 169   public:
 170     typedef ntree_postfix_iterator<T,T&,T*>             iterator;
 171     typedef ntree_postfix_iterator<T,const T&,const T*> const_iterator;
 172     typedef ntree_postfix_iterator<T,TRef,TPtr>         this_iterator;
 173     typedef ntree_iterator<T,TRef,TPtr>                 simple_iterator;
 174     typedef TRef                                        reference;
 175     typedef TPtr                                        pointer;
 176
 177     // constructor to create a null iterator - you must assign a valid value to this iterator before using it
 178     ntree_postfix_iterator(void);
 179     ~ntree_postfix_iterator(void);
 180
 181     // tests
 182     // a null iterator is one that has not been initialised with a value yet
 183     // i.e. you just declared it but didn't assign to it
 184     bool null(void) const;
 185     // an end iterator is one that points to the end element of the list of nodes
 186     // in STL conventions this is one past the last valid element and must not be dereferenced
 187     bool end(void) const;
 188     // a valid iterator is one that can be dereferenced
 189     // i.e. non-null and non-end
 190     bool valid(void) const;
 191
 192     // Type conversion methods allow const_iterator and iterator to be converted
 193     // convert an iterator/const_iterator to a const_iterator
 194     const_iterator constify(void) const;
 195     iterator deconstify(void) const;
 196
 197     // generate a simple iterator from a traversal iterator
 198     ntree_iterator<T,TRef,TPtr> simplify(void) const;
 199
 200     // tests useful for putting iterators into other STL structures and for testing whether iteration has completed
 201     bool operator == (const this_iterator& r) const;
 202     bool operator != (const this_iterator& r) const;
 203     bool operator < (const this_iterator& r) const;
 204
 205     // increment/decrement operators used to step through the set of all nodes in a graph
 206     // it is only legal to increment a valid iterator
 207     // pre-increment
 208     this_iterator& operator ++ (void)
 209       throw(null_dereference,end_dereference);
 210     // post-increment
 211     this_iterator operator ++ (int)
 212       throw(null_dereference,end_dereference);
 213
 214     // access the node data - a const_iterator gives you a const element, an iterator a non-const element
 215     // it is illegal to dereference an invalid (i.e. null or end) iterator
 216     reference operator*(void) const
 217       throw(null_dereference,end_dereference);
 218     pointer operator->(void) const
 219       throw(null_dereference,end_dereference);
 220
 221     friend class ntree<T>;
 222     friend class ntree_iterator<T,TRef,TPtr>;
 223
 224   private:
 225     ntree_iterator<T,TRef,TPtr> m_iterator;
 226
 227     explicit ntree_postfix_iterator(const ntree_iterator<T,TRef,TPtr>& i);
 228     const ntree_iterator<T,TRef,TPtr>& get_iterator(void) const;
 229     ntree_iterator<T,TRef,TPtr>& get_iterator(void);
 230   };
 231
 232   ////////////////////////////////////////////////////////////////////////////////
 233   // The Ntree class
 234   ////////////////////////////////////////////////////////////////////////////////
 235
 236   template<typename T>
 237   class ntree
 238   {
 239   public:
 240     // STL-like typedefs for the types and iterators
 241     typedef T value_type;
 242
 243     typedef ntree_iterator<T,T&,T*> iterator;
 244     typedef ntree_iterator<T,const T&,const T*> const_iterator;
 245
 246     typedef ntree_prefix_iterator<T,T&,T*> prefix_iterator;
 247     typedef ntree_prefix_iterator<T,const T&,const T*> const_prefix_iterator;
 248
 249     typedef ntree_postfix_iterator<T,T&,T*> postfix_iterator;
 250     typedef ntree_postfix_iterator<T,const T&,const T*> const_postfix_iterator;
 251
 252     //////////////////////////////////////////////////////////////////////////////
 253     // Constructors, destructors and copies
 254
 255     ntree(void);
 256     ~ntree(void);
 257
 258     // copy constructor and assignment both copy the tree
 259     ntree(const ntree<T>&);
 260     ntree<T>& operator=(const ntree<T>&);
 261
 262     //////////////////////////////////////////////////////////////////////////////
 263     // size tests
 264
 265     // tests on whole tree
 266     bool empty(void) const;
 267     unsigned size(void) const;
 268
 269     // tests for number of nodes in subtree starting at node
 270     unsigned size(const const_iterator& node) const
 271       throw(wrong_object,null_dereference,end_dereference);
 272     unsigned size(const iterator& node)
 273       throw(wrong_object,null_dereference,end_dereference);
 274
 275     // test for depth of tree from root to node
 276     unsigned depth(const const_iterator& node) const
 277       throw(wrong_object,null_dereference,end_dereference);
 278     unsigned depth(const iterator& node)
 279       throw(wrong_object,null_dereference,end_dereference);
 280
 281     //////////////////////////////////////////////////////////////////////////////
 282     // direct traversal
 283
 284     const_iterator root(void) const;
 285     iterator root(void);
 286
 287     unsigned children(const const_iterator& node) const
 288       throw(wrong_object,null_dereference,end_dereference);
 289     unsigned children(const iterator& node)
 290       throw(wrong_object,null_dereference,end_dereference);
 291
 292     const_iterator child(const const_iterator& node, unsigned child) const
 293       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 294     iterator child(const iterator& node, unsigned child)
 295       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 296
 297     const_iterator parent(const const_iterator& node) const
 298       throw(wrong_object,null_dereference,end_dereference);
 299     iterator parent(const iterator& node)
 300       throw(wrong_object,null_dereference,end_dereference);
 301
 302     //////////////////////////////////////////////////////////////////////////////
 303     // iterator traversal
 304
 305     const_prefix_iterator prefix_begin(void) const;
 306     prefix_iterator prefix_begin(void);
 307     const_prefix_iterator prefix_end(void) const;
 308     prefix_iterator prefix_end(void);
 309
 310     const_postfix_iterator postfix_begin(void) const;
 311     postfix_iterator postfix_begin(void);
 312     const_postfix_iterator postfix_end(void) const;
 313     postfix_iterator postfix_end(void);
 314
 315     //////////////////////////////////////////////////////////////////////////////
 316     // modification
 317
 318     iterator insert(const T&);
 319
 320     iterator insert(const iterator& node, unsigned child, const T&)
 321       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 322     iterator append(const iterator& node, const T&)
 323       throw(wrong_object,null_dereference,end_dereference);
 324
 325     iterator insert(const iterator& node, unsigned child, const ntree<T>&)
 326       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 327     iterator append(const iterator& node, const ntree<T>&)
 328       throw(wrong_object,null_dereference,end_dereference);
 329
 330     iterator push(const iterator& node, const T&)
 331       throw(wrong_object,null_dereference,end_dereference);
 332     void pop(const iterator& node, unsigned child)
 333       throw(wrong_object,null_dereference,end_dereference);
 334
 335     void erase(void);
 336     void erase(const iterator& node)
 337       throw(wrong_object,null_dereference,end_dereference);
 338     void erase(const iterator& node, unsigned child)
 339       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 340
 341     ntree<T> subtree(void);
 342     ntree<T> subtree(const iterator& node)
 343       throw(wrong_object,null_dereference,end_dereference);
 344     ntree<T> subtree(const iterator& node, unsigned child)
 345       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 346
 347     ntree<T> cut(void);
 348     ntree<T> cut(const iterator& node)
 349       throw(wrong_object,null_dereference,end_dereference);
 350     ntree<T> cut(const iterator& node, unsigned child)
 351       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 352
 353     //////////////////////////////////////////////////////////////////////////////
 354
 355   private:
 356     ntree_node<T>* m_root;
 357   };
 358
 359   ////////////////////////////////////////////////////////////////////////////////
 360
 361 } // end namespace stlplus
 362
 363 #include "ntree.tpp"
 364 #endif