Dogcows Code - chaz/yoink/blob - src/Moof/stlplus/ntree.tpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2
   3 //   Author:    Andy Rushton
   4 //   Copyright: (c) Southampton University 1999-2004
   5 //              (c) Andy Rushton           2004-2009
   6 //   License:   BSD License, see ../docs/license.html
   7
   8 ////////////////////////////////////////////////////////////////////////////////
   9 #include <vector>
  10 #include <algorithm>
  11
  12 namespace stlplus
  13 {
  14
  15   ////////////////////////////////////////////////////////////////////////////////
  16   // ntree_node
  17
  18   template<typename T>
  19   class ntree_node
  20   {
  21   public:
  22     master_iterator<ntree<T>, ntree_node<T> > m_master;
  23     T m_data;
  24     ntree_node<T>* m_parent;
  25     std::vector<ntree_node<T>*> m_children;
  26
  27   public:
  28     ntree_node(const ntree<T>* owner, const T& data = T()) :
  29       m_master(owner,this), m_data(data), m_parent(0)
  30       {
  31       }
  32
  33     void change_owner(const ntree<T>* owner)
  34       {
  35         m_master.change_owner(owner);
  36         for (TYPENAME std::vector<ntree_node<T>*>::iterator i = m_children.begin(); i != m_children.end(); i++)
  37           (*i)->change_owner(owner);
  38       }
  39
  40     ~ntree_node(void)
  41       {
  42         m_parent = 0;
  43         for (TYPENAME std::vector<ntree_node<T>*>::iterator i = m_children.begin(); i != m_children.end(); i++)
  44           delete *i;
  45       }
  46
  47   };
  48
  49   template<typename T>
  50   static ntree_node<T>* ntree_copy(const ntree<T>* new_owner, ntree_node<T>* root)
  51   {
  52     if (!root) return 0;
  53     ntree_node<T>* new_tree = new ntree_node<T>(new_owner, root->m_data);
  54     for (TYPENAME std::vector<ntree_node<T>*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++)
  55     {
  56       ntree_node<T>* new_child = ntree_copy(new_owner, *i);
  57       new_tree->m_children.push_back(new_child);
  58       new_child->m_parent = new_tree;
  59     }
  60     return new_tree;
  61   }
  62
  63   template<typename T>
  64   static unsigned ntree_size(ntree_node<T>* root)
  65   {
  66     if (!root) return 0;
  67     unsigned result = 1;
  68     for (TYPENAME std::vector<ntree_node<T>*>::iterator i = root->m_children.begin(); i != root->m_children.end(); i++)
  69       result += ntree_size(*i);
  70     return result;
  71   }
  72
  73   template<typename T>
  74   static unsigned ntree_depth(ntree_node<T>* root)
  75   {
  76     unsigned depth = 0;
  77     for (ntree_node<T>* i = root; i; i = i->m_parent)
  78       depth++;
  79     return depth;
  80   }
  81
  82   ////////////////////////////////////////////////////////////////////////////////
  83   // ntree_iterator
  84
  85   // constructor to create a null iterator - you must assign a valid value to this iterator before using it
  86   template<typename T, typename TRef, typename TPtr>
  87   ntree_iterator<T,TRef,TPtr>::ntree_iterator(void)
  88   {
  89   }
  90
  91   // used to create an alias of an iterator
  92   template<typename T, typename TRef, typename TPtr>
  93   ntree_iterator<T,TRef,TPtr>::ntree_iterator(const safe_iterator<ntree<T>, ntree_node<T> >& iterator) :
  94     safe_iterator<ntree<T>,ntree_node<T> >(iterator)
  95   {
  96   }
  97
  98   // constructor used by ntree to create a non-null iterator
  99   template<typename T, typename TRef, typename TPtr>
 100   ntree_iterator<T,TRef,TPtr>::ntree_iterator(ntree_node<T>* node) :
 101     safe_iterator<ntree<T>,ntree_node<T> >(node->m_master)
 102   {
 103   }
 104
 105   // constructor used by ntree to create an end iterator
 106   template<typename T, typename TRef, typename TPtr>
 107   ntree_iterator<T,TRef,TPtr>::ntree_iterator(const ntree<T>* owner) :
 108     safe_iterator<ntree<T>,ntree_node<T> >(owner)
 109   {
 110   }
 111
 112   // destructor
 113   template<typename T, typename TRef, typename TPtr>
 114   ntree_iterator<T,TRef,TPtr>::~ntree_iterator(void)
 115   {
 116   }
 117
 118   template<typename T, typename TRef, typename TPtr>
 119   TYPENAME ntree_iterator<T,TRef,TPtr>::const_iterator ntree_iterator<T,TRef,TPtr>::constify(void) const
 120   {
 121     return ntree_iterator<T,const T&,const T*>(*this);
 122   }
 123
 124   template<typename T, typename TRef, typename TPtr>
 125   TYPENAME ntree_iterator<T,TRef,TPtr>::iterator ntree_iterator<T,TRef,TPtr>::deconstify(void) const
 126   {
 127     return ntree_iterator<T,T&,T*>(*this);
 128   }
 129
 130   template<typename T, typename TRef, typename TPtr>
 131   bool ntree_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const
 132   {
 133     return equal(r);
 134   }
 135
 136   template<typename T, typename TRef, typename TPtr>
 137   bool ntree_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const
 138   {
 139     return !operator==(r);
 140   }
 141
 142   template<typename T, typename TRef, typename TPtr>
 143   bool ntree_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_iterator<T,TRef,TPtr>::this_iterator& r) const
 144   {
 145     return compare(r) < 0;
 146   }
 147
 148   template<typename T, typename TRef, typename TPtr>
 149   TYPENAME ntree_iterator<T,TRef,TPtr>::reference ntree_iterator<T,TRef,TPtr>::operator*(void) const
 150     throw(null_dereference,end_dereference)
 151   {
 152     this->assert_valid();
 153     return this->node()->m_data;
 154   }
 155
 156   template<typename T, typename TRef, typename TPtr>
 157   TYPENAME ntree_iterator<T,TRef,TPtr>::pointer ntree_iterator<T,TRef,TPtr>::operator->(void) const
 158     throw(null_dereference,end_dereference)
 159   {
 160     return &(operator*());
 161   }
 162
 163   ////////////////////////////////////////////////////////////////////////////////
 164   // ntree_prefix_iterator
 165
 166   template<typename T, typename TRef, typename TPtr>
 167   ntree_prefix_iterator<T,TRef,TPtr>::ntree_prefix_iterator(void)
 168   {
 169   }
 170
 171   template<typename T, typename TRef, typename TPtr>
 172   ntree_prefix_iterator<T,TRef,TPtr>::~ntree_prefix_iterator(void)
 173   {
 174   }
 175
 176   template<typename T, typename TRef, typename TPtr>
 177   ntree_prefix_iterator<T,TRef,TPtr>::ntree_prefix_iterator(const ntree_iterator<T,TRef,TPtr>& i) :
 178     m_iterator(i)
 179   {
 180     // this is initialised with the root node
 181     // which is also the first node in prefix traversal order
 182   }
 183
 184   template<typename T, typename TRef, typename TPtr>
 185   bool ntree_prefix_iterator<T,TRef,TPtr>::null(void) const
 186   {
 187     return m_iterator.null();
 188   }
 189
 190   template<typename T, typename TRef, typename TPtr>
 191   bool ntree_prefix_iterator<T,TRef,TPtr>::end(void) const
 192   {
 193     return m_iterator.end();
 194   }
 195
 196   template<typename T, typename TRef, typename TPtr>
 197   bool ntree_prefix_iterator<T,TRef,TPtr>::valid(void) const
 198   {
 199     return m_iterator.valid();
 200   }
 201
 202   template<typename T, typename TRef, typename TPtr>
 203   TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::const_iterator ntree_prefix_iterator<T,TRef,TPtr>::constify(void) const
 204   {
 205     return ntree_prefix_iterator<T,const T&,const T*>(m_iterator);
 206   }
 207
 208   template<typename T, typename TRef, typename TPtr>
 209   TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::iterator ntree_prefix_iterator<T,TRef,TPtr>::deconstify(void) const
 210   {
 211     return ntree_prefix_iterator<T,T&,T*>(m_iterator);
 212   }
 213
 214   template<typename T, typename TRef, typename TPtr>
 215   ntree_iterator<T,TRef,TPtr> ntree_prefix_iterator<T,TRef,TPtr>::simplify(void) const
 216   {
 217     return m_iterator;
 218   }
 219
 220   template<typename T, typename TRef, typename TPtr>
 221   bool ntree_prefix_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const
 222   {
 223     return m_iterator == r.m_iterator;
 224   }
 225
 226   template<typename T, typename TRef, typename TPtr>
 227   bool ntree_prefix_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const
 228   {
 229     return m_iterator != r.m_iterator;
 230   }
 231
 232   template<typename T, typename TRef, typename TPtr>
 233   bool ntree_prefix_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& r) const
 234   {
 235     return m_iterator < r.m_iterator;
 236   }
 237
 238   template<typename T, typename TRef, typename TPtr>
 239   TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator& ntree_prefix_iterator<T,TRef,TPtr>::operator ++ (void)
 240     throw(null_dereference,end_dereference)
 241   {
 242     // pre-increment operator
 243     // algorithm: if there are any children, visit child 0, otherwise, go to
 244     // parent and deduce which child the start node was of that parent - if
 245     // there are further children, go into the next one. Otherwise, go up the
 246     // tree and test again for further children. Return null if there are no
 247     // further nodes
 248     m_iterator.assert_valid();
 249     ntree_node<T>* old_node = m_iterator.node();
 250     if (!old_node->m_children.empty())
 251     {
 252       // simply take the first child of this node
 253       m_iterator.set(old_node->m_children[0]->m_master);
 254     }
 255     else
 256     {
 257       // this loop walks up the parent pointers
 258       // either it will walk off the top and exit or a new node will be found and the loop will exit
 259       for (;;)
 260       {
 261         // go up a level
 262         ntree_node<T>* parent = old_node->m_parent;
 263         if (!parent)
 264         {
 265           // we've walked off the top of the tree, so return end
 266           m_iterator.set_end();
 267           break;
 268         }
 269         else
 270         {
 271           // otherwise walk down the next child - if there is one
 272           // find which index the old node was relative to this node
 273           TYPENAME std::vector<ntree_node<T>*>::iterator found =
 274             std::find(parent->m_children.begin(), parent->m_children.end(), old_node);
 275           // if this was found, then see if there is another and if so return that
 276           found++;
 277           if (found != parent->m_children.end())
 278           {
 279             // visit the next child
 280             m_iterator.set((*found)->m_master);
 281             break;
 282           }
 283           else
 284           {
 285             // keep going up
 286             old_node = parent;
 287           }
 288         }
 289       }
 290     }
 291     return *this;
 292   }
 293
 294   template<typename T, typename TRef, typename TPtr>
 295   TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::this_iterator ntree_prefix_iterator<T,TRef,TPtr>::operator ++ (int)
 296     throw(null_dereference,end_dereference)
 297   {
 298     // post-increment is defined in terms of the pre-increment
 299     ntree_prefix_iterator<T,TRef,TPtr> result(*this);
 300     ++(*this);
 301     return result;
 302   }
 303
 304   template<typename T, typename TRef, typename TPtr>
 305   TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::reference ntree_prefix_iterator<T,TRef,TPtr>::operator*(void) const
 306     throw(null_dereference,end_dereference)
 307   {
 308     return m_iterator.operator*();
 309   }
 310
 311   template<typename T, typename TRef, typename TPtr>
 312   TYPENAME ntree_prefix_iterator<T,TRef,TPtr>::pointer ntree_prefix_iterator<T,TRef,TPtr>::operator->(void) const
 313     throw(null_dereference,end_dereference)
 314   {
 315     return m_iterator.operator->();
 316   }
 317
 318   template<typename T, typename TRef, typename TPtr>
 319   const ntree_iterator<T,TRef,TPtr>& ntree_prefix_iterator<T,TRef,TPtr>::get_iterator(void) const
 320   {
 321     return m_iterator;
 322   }
 323
 324   template<typename T, typename TRef, typename TPtr>
 325   ntree_iterator<T,TRef,TPtr>& ntree_prefix_iterator<T,TRef,TPtr>::get_iterator(void)
 326   {
 327     return m_iterator;
 328   }
 329
 330   ////////////////////////////////////////////////////////////////////////////////
 331   // ntree_postfix_iterator
 332
 333   template<typename T, typename TRef, typename TPtr>
 334   ntree_postfix_iterator<T,TRef,TPtr>::ntree_postfix_iterator(void)
 335   {
 336   }
 337
 338   template<typename T, typename TRef, typename TPtr>
 339   ntree_postfix_iterator<T,TRef,TPtr>::~ntree_postfix_iterator(void)
 340   {
 341   }
 342
 343   template<typename T, typename TRef, typename TPtr>
 344   ntree_postfix_iterator<T,TRef,TPtr>::ntree_postfix_iterator(const ntree_iterator<T,TRef,TPtr>& i) :
 345     m_iterator(i)
 346   {
 347     // this is initialised with the root node
 348     // initially traverse to the first node to be visited
 349     if (m_iterator.valid())
 350     {
 351       ntree_node<T>* node = m_iterator.node();
 352       while (!node->m_children.empty())
 353         node = node->m_children[0];
 354       m_iterator.set(node->m_master);
 355     }
 356   }
 357
 358   template<typename T, typename TRef, typename TPtr>
 359   bool ntree_postfix_iterator<T,TRef,TPtr>::null(void) const
 360   {
 361     return m_iterator.null();
 362   }
 363
 364   template<typename T, typename TRef, typename TPtr>
 365   bool ntree_postfix_iterator<T,TRef,TPtr>::end(void) const
 366   {
 367     return m_iterator.end();
 368   }
 369
 370   template<typename T, typename TRef, typename TPtr>
 371   bool ntree_postfix_iterator<T,TRef,TPtr>::valid(void) const
 372   {
 373     return m_iterator.valid();
 374   }
 375
 376   template<typename T, typename TRef, typename TPtr>
 377   TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::const_iterator ntree_postfix_iterator<T,TRef,TPtr>::constify(void) const
 378   {
 379     return ntree_postfix_iterator<T,const T&,const T*>(m_iterator);
 380   }
 381
 382   template<typename T, typename TRef, typename TPtr>
 383   TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::iterator ntree_postfix_iterator<T,TRef,TPtr>::deconstify(void) const
 384   {
 385     return ntree_postfix_iterator<T,T&,T*>(m_iterator);
 386   }
 387
 388   template<typename T, typename TRef, typename TPtr>
 389   ntree_iterator<T,TRef,TPtr> ntree_postfix_iterator<T,TRef,TPtr>::simplify(void) const
 390   {
 391     return m_iterator;
 392   }
 393
 394   template<typename T, typename TRef, typename TPtr>
 395   bool ntree_postfix_iterator<T,TRef,TPtr>::operator == (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const
 396   {
 397     return m_iterator == r.m_iterator;
 398   }
 399
 400   template<typename T, typename TRef, typename TPtr>
 401   bool ntree_postfix_iterator<T,TRef,TPtr>::operator != (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const
 402   {
 403     return m_iterator != r.m_iterator;
 404   }
 405
 406   template<typename T, typename TRef, typename TPtr>
 407   bool ntree_postfix_iterator<T,TRef,TPtr>::operator < (const TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& r) const
 408   {
 409     return m_iterator < r.m_iterator;
 410   }
 411
 412   template<typename T, typename TRef, typename TPtr>
 413   TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator& ntree_postfix_iterator<T,TRef,TPtr>::operator ++ (void)
 414     throw(null_dereference,end_dereference)
 415   {
 416     // pre-increment operator
 417     // algorithm: this node has been visited, therefore all children must have
 418     // already been visited. So go to parent. Return null if the parent is null.
 419     // Otherwise deduce which child the start node was of that parent - if there
 420     // are further children, go into the next one and then walk down any
 421     // subsequent first-child pointers to the bottom. Otherwise, if there are no
 422     // children then the parent node is the next in the traversal.
 423     m_iterator.assert_valid();
 424     // go up a level
 425     ntree_node<T>* old_node = m_iterator.node();
 426     ntree_node<T>* parent = old_node->m_parent;
 427     if (!parent)
 428     {
 429       // we've walked off the top of the tree, so return end
 430       m_iterator.set_end();
 431     }
 432     else
 433     {
 434       // otherwise find which index the old node was relative to this node
 435       TYPENAME std::vector<ntree_node<T>*>::iterator found =
 436         std::find(parent->m_children.begin(), parent->m_children.end(), old_node);
 437       // if this was found, then see if there is another
 438       found++;
 439       if (found != parent->m_children.end())
 440       {
 441         // if so traverse to it and walk down the leftmost child pointers to the bottom of the new sub-tree
 442         ntree_node<T>* new_node = *found;
 443         while (!new_node->m_children.empty())
 444           new_node = new_node->m_children[0];
 445         m_iterator.set(new_node->m_master);
 446       }
 447       else
 448       {
 449         // the parent's children have all been visited - so the parent is visited
 450         m_iterator.set(parent->m_master);
 451       }
 452     }
 453     return *this;
 454   }
 455
 456   template<typename T, typename TRef, typename TPtr>
 457   TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::this_iterator ntree_postfix_iterator<T,TRef,TPtr>::operator ++ (int)
 458     throw(null_dereference,end_dereference)
 459   {
 460     // post-increment is defined in terms of the pre-increment
 461     ntree_postfix_iterator<T,TRef,TPtr> result(*this);
 462     ++(*this);
 463     return result;
 464   }
 465
 466   template<typename T, typename TRef, typename TPtr>
 467   TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::reference ntree_postfix_iterator<T,TRef,TPtr>::operator*(void) const
 468     throw(null_dereference,end_dereference)
 469   {
 470     return m_iterator.operator*();
 471   }
 472
 473   template<typename T, typename TRef, typename TPtr>
 474   TYPENAME ntree_postfix_iterator<T,TRef,TPtr>::pointer ntree_postfix_iterator<T,TRef,TPtr>::operator->(void) const
 475     throw(null_dereference,end_dereference)
 476   {
 477     return m_iterator.operator->();
 478   }
 479
 480   template<typename T, typename TRef, typename TPtr>
 481   const ntree_iterator<T,TRef,TPtr>& ntree_postfix_iterator<T,TRef,TPtr>::get_iterator(void) const
 482   {
 483     return m_iterator;
 484   }
 485
 486   template<typename T, typename TRef, typename TPtr>
 487   ntree_iterator<T,TRef,TPtr>& ntree_postfix_iterator<T,TRef,TPtr>::get_iterator(void)
 488   {
 489     return m_iterator;
 490   }
 491
 492   ////////////////////////////////////////////////////////////////////////////////
 493   ////////////////////////////////////////////////////////////////////////////////
 494   // ntree
 495   ////////////////////////////////////////////////////////////////////////////////
 496   ////////////////////////////////////////////////////////////////////////////////
 497
 498   template<typename T>
 499   ntree<T>::ntree(void) : m_root(0)
 500   {
 501   }
 502
 503   template<typename T>
 504   ntree<T>::~ntree(void)
 505   {
 506     if (m_root) delete m_root;
 507   }
 508
 509   template<typename T>
 510   ntree<T>::ntree(const ntree<T>& r) : m_root(0)
 511   {
 512     *this = r;
 513   }
 514
 515   template<typename T>
 516   ntree<T>& ntree<T>::operator=(const ntree<T>& r)
 517   {
 518     if (m_root) delete m_root;
 519     m_root = ntree_copy(this, r.m_root);
 520     return *this;
 521   }
 522
 523   template<typename T>
 524   bool ntree<T>::empty(void) const
 525   {
 526     return m_root == 0;
 527   }
 528
 529   template<typename T>
 530   unsigned ntree<T>::size(void) const
 531   {
 532     return ntree_size(m_root);
 533   }
 534
 535   template<typename T>
 536   unsigned ntree<T>::size(const TYPENAME ntree<T>::const_iterator& i) const
 537     throw(wrong_object,null_dereference,end_dereference)
 538   {
 539     i.assert_valid(this);
 540     return ntree_size(i.node());
 541   }
 542
 543   template<typename T>
 544   unsigned ntree<T>::size(const TYPENAME ntree<T>::iterator& i)
 545     throw(wrong_object,null_dereference,end_dereference)
 546   {
 547     i.assert_valid(this);
 548     return ntree_size(i.node());
 549   }
 550
 551   template<typename T>
 552   unsigned ntree<T>::depth(const TYPENAME ntree<T>::const_iterator& i) const
 553     throw(wrong_object,null_dereference,end_dereference)
 554   {
 555     i.assert_valid(this);
 556     return ntree_depth(i.node());
 557   }
 558
 559   template<typename T>
 560   unsigned ntree<T>::depth(const TYPENAME ntree<T>::iterator& i)
 561     throw(wrong_object,null_dereference,end_dereference)
 562   {
 563     i.assert_valid(this);
 564     return ntree_depth(i.node());
 565   }
 566
 567   template<typename T>
 568   TYPENAME ntree<T>::const_iterator ntree<T>::root(void) const
 569   {
 570     if (!m_root) return ntree_iterator<T,const T&,const T*>(this);
 571     return ntree_iterator<T,const T&,const T*>(m_root);
 572   }
 573
 574   template<typename T>
 575   TYPENAME ntree<T>::iterator ntree<T>::root(void)
 576   {
 577     if (!m_root) return ntree_iterator<T,T&,T*>(this);
 578     return ntree_iterator<T,T&,T*>(m_root);
 579   }
 580
 581   template<typename T>
 582   unsigned ntree<T>::children(const TYPENAME ntree<T>::const_iterator& i) const
 583     throw(wrong_object,null_dereference,end_dereference)
 584   {
 585     i.assert_valid(this);
 586     return i.node()->m_children.size();
 587   }
 588
 589   template<typename T>
 590   unsigned ntree<T>::children(const ntree_iterator<T,T&,T*>& i)
 591     throw(wrong_object,null_dereference,end_dereference)
 592   {
 593     i.assert_valid(this);
 594     return i.node()->m_children.size();
 595   }
 596
 597   template<typename T>
 598   TYPENAME ntree<T>::const_iterator ntree<T>::child(const TYPENAME ntree<T>::const_iterator& i, unsigned child) const
 599     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 600   {
 601     i.assert_valid(this);
 602     if (child >= children(i)) throw std::out_of_range("stlplus::ntree");
 603     return ntree_iterator<T,const T&,const T*>(i.node()->m_children[child]);
 604   }
 605
 606   template<typename T>
 607   TYPENAME ntree<T>::iterator ntree<T>::child(const TYPENAME ntree<T>::iterator& i, unsigned child)
 608     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 609   {
 610     i.assert_valid(this);
 611     if (child >= children(i)) throw std::out_of_range("stlplus::ntree");
 612     return ntree_iterator<T,T&,T*>(i.node()->m_children[child]);
 613   }
 614
 615   template<typename T>
 616   TYPENAME ntree<T>::const_iterator ntree<T>::parent(const TYPENAME ntree<T>::const_iterator& i) const
 617     throw(wrong_object,null_dereference,end_dereference)
 618   {
 619     i.assert_valid(this);
 620     ntree_node<T>* parent = i.node()->m_parent;
 621     if (!parent) return ntree_iterator<T,const T&,const T*>(this);
 622     return ntree_iterator<T,const T&,const T*>(parent);
 623   }
 624
 625   template<typename T>
 626   TYPENAME ntree<T>::iterator ntree<T>::parent(const TYPENAME ntree<T>::iterator& i)
 627     throw(wrong_object,null_dereference,end_dereference)
 628   {
 629     i.assert_valid(this);
 630     ntree_node<T>* parent = i.node()->m_parent;
 631     if (!parent) return ntree_iterator<T,T&,T*>(this);
 632     return ntree_iterator<T,T&,T*>(parent);
 633   }
 634
 635   template<typename T>
 636   TYPENAME ntree<T>::const_prefix_iterator ntree<T>::prefix_begin(void) const
 637   {
 638     return ntree_prefix_iterator<T,const T&,const T*>(root());
 639   }
 640
 641   template<typename T>
 642   TYPENAME ntree<T>::prefix_iterator ntree<T>::prefix_begin(void)
 643   {
 644     return ntree_prefix_iterator<T,T&,T*>(root());
 645   }
 646
 647   template<typename T>
 648   TYPENAME ntree<T>::const_prefix_iterator ntree<T>::prefix_end(void) const
 649   {
 650     return ntree_prefix_iterator<T,const T&,const T*>(ntree_iterator<T,const T&,const T*>(this));
 651   }
 652
 653   template<typename T>
 654   TYPENAME ntree<T>::prefix_iterator ntree<T>::prefix_end(void)
 655   {
 656     return ntree_prefix_iterator<T,T&,T*>(ntree_iterator<T,T&,T*>(this));
 657   }
 658
 659   template<typename T>
 660   TYPENAME ntree<T>::const_postfix_iterator ntree<T>::postfix_begin(void) const
 661   {
 662     return ntree_postfix_iterator<T,const T&,const T*>(root());
 663   }
 664
 665   template<typename T>
 666   TYPENAME ntree<T>::postfix_iterator ntree<T>::postfix_begin(void)
 667   {
 668     return ntree_postfix_iterator<T,T&,T*>(root());
 669   }
 670
 671   template<typename T>
 672   TYPENAME ntree<T>::const_postfix_iterator ntree<T>::postfix_end(void) const
 673   {
 674     return ntree_postfix_iterator<T,const T&,const T*>(ntree_iterator<T,const T&,const T*>(this));
 675   }
 676
 677   template<typename T>
 678   TYPENAME ntree<T>::postfix_iterator ntree<T>::postfix_end(void)
 679   {
 680     return ntree_postfix_iterator<T,T&,T*>(ntree_iterator<T,T&,T*>(this));
 681   }
 682
 683   template<typename T>
 684   TYPENAME ntree<T>::iterator ntree<T>::insert(const T& data)
 685   {
 686     // insert a new node as the root
 687     return insert(ntree_iterator<T,T&,T*>(this), 0, data);
 688   }
 689
 690   template<typename T>
 691   TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const T& data)
 692     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 693   {
 694     // if i is the end iterator, this means insert a new root
 695     if (i.end())
 696       erase();
 697     else
 698     {
 699       i.assert_valid(this);
 700       if (offset > children(i)) throw std::out_of_range("stlplus::ntree");
 701     }
 702     ntree_node<T>* new_node = new ntree_node<T>(this,data);
 703     if (i.end())
 704     {
 705       m_root = new_node;
 706     }
 707     else
 708     {
 709       i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);
 710       new_node->m_parent = i.node();
 711     }
 712     return ntree_iterator<T,T&,T*>(new_node);
 713   }
 714
 715   template<typename T>
 716   TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const T& data)
 717     throw(wrong_object,null_dereference,end_dereference)
 718   {
 719     return insert(i, i.node()->m_children.size(), data);
 720   }
 721
 722   template<typename T>
 723   TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const ntree<T>& tree)
 724     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 725   {
 726     // insert a whole tree as a child of i
 727     i.assert_valid(this);
 728     if (offset > children(i)) throw std::out_of_range("stlplus::ntree");
 729     ntree_node<T>* new_node = ntree_copy(this, tree.m_root);
 730     i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);
 731     new_node->m_parent = i.node();
 732     return ntree_iterator<T,T&,T*>(new_node);
 733   }
 734
 735   template<typename T>
 736   TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const ntree<T>& tree)
 737     throw(wrong_object,null_dereference,end_dereference)
 738   {
 739     return insert(i, children(i), tree);
 740   }
 741
 742   template<typename T>
 743   TYPENAME ntree<T>::iterator ntree<T>::push(const TYPENAME ntree<T>::iterator& node, const T& data)
 744     throw(wrong_object,null_dereference,end_dereference)
 745   {
 746     // insert a new node to replace the existing node in the tree
 747     // making the original node the child of the new node
 748     // i.e. (node) becomes (new)->(node)
 749     // afterwards, the iterator still points to the old node, now the child
 750     // returns the iterator to the new node
 751     node.assert_valid(this);
 752     ntree_node<T>* new_node = new ntree_node<T>(this,data);
 753     if (node.node() == m_root)
 754     {
 755       // pushing the root node
 756       m_root = new_node;
 757       new_node->m_parent = 0;
 758     }
 759     else
 760     {
 761       // pushing a sub-node
 762       *(std::find(node.node()->m_parent->m_children.begin(), node.node()->m_parent->m_children.end(), node.node())) = new_node;
 763       new_node->m_parent = node.node()->m_parent;
 764     }
 765     // link up the old node as the child of the new node
 766     new_node->m_children.insert(new_node->m_children.begin(),node.node());
 767     node.node()->m_parent = new_node;
 768     return ntree_iterator<T,T&,T*>(new_node);
 769   }
 770
 771   template<typename T>
 772   void ntree<T>::pop(const TYPENAME ntree<T>::iterator& parent, unsigned offset)
 773     throw(wrong_object,null_dereference,end_dereference)
 774   {
 775     // inverse of push
 776     // removes the specified child of the parent node, adding its children to the parent node at the same offset
 777     parent.assert_valid(this);
 778     ntree_node<T>* node = parent.node();
 779     if (offset >= node->m_children.size()) throw std::out_of_range("stlplus::ntree");
 780     // move the grandchildren first
 781     ntree_node<T>* child = parent.node()->m_children[offset];
 782     while (!child->m_children.empty())
 783     {
 784       // remove the last grandchild and insert into node just after the child to be removed
 785       ntree_node<T>* grandchild = child->m_children[child->m_children.size()-1];
 786       child->m_children.pop_back();
 787       node->m_children.insert(node->m_children.begin()+offset+1, grandchild);
 788       grandchild->m_parent = node;
 789     }
 790     // now remove the child
 791     node->m_children.erase(node->m_children.begin()+offset);
 792     delete child;
 793   }
 794
 795   template<typename T>
 796   void ntree<T>::erase(void)
 797   {
 798     // erase the whole tree
 799     erase(root());
 800   }
 801
 802   template<typename T>
 803   void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i)
 804     throw(wrong_object,null_dereference,end_dereference)
 805   {
 806     if (!i.end())
 807     {
 808       // erase this node and its subtree
 809       // do this by erasing this child of its parent
 810       // handle the case of erasing the root
 811       i.assert_valid(this);
 812       ntree_node<T>* node = i.node();
 813       if (node == m_root)
 814       {
 815         delete m_root;
 816         m_root = 0;
 817       }
 818       else
 819       {
 820         ntree_node<T>* parent = node->m_parent;
 821         // impossible for parent to be null - should assert this
 822         TYPENAME std::vector<ntree_node<T>*>::iterator found =
 823           std::find(parent->m_children.begin(), parent->m_children.end(), node);
 824         // impossible for find to fail - should assert this
 825         parent->m_children.erase(found);
 826         delete node;
 827       }
 828     }
 829   }
 830
 831   template<typename T>
 832   void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i, unsigned offset)
 833     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 834   {
 835     erase(child(i, offset));
 836   }
 837
 838   template<typename T>
 839   ntree<T> ntree<T>::subtree(void)
 840   {
 841     return subtree(root());
 842   }
 843
 844   template<typename T>
 845   ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i)
 846     throw(wrong_object,null_dereference,end_dereference)
 847   {
 848     ntree<T> result;
 849     if (!i.end())
 850     {
 851       i.assert_valid(this);
 852       result.m_root = ntree_copy(&result, i.node());
 853     }
 854     return result;
 855   }
 856
 857   template<typename T>
 858   ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i, unsigned offset)
 859     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 860   {
 861     return subtree(child(i, offset));
 862   }
 863
 864   template<typename T>
 865   ntree<T> ntree<T>::cut(void)
 866   {
 867     return cut(root());
 868   }
 869
 870   template<typename T>
 871   ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i)
 872     throw(wrong_object,null_dereference,end_dereference)
 873   {
 874     ntree<T> result;
 875     if (!i.end())
 876     {
 877       i.assert_valid(this);
 878       ntree_node<T>* node = i.node();
 879       if (node == m_root)
 880       {
 881         result.m_root = m_root;
 882         m_root = 0;
 883       }
 884       else
 885       {
 886         ntree_node<T>* parent = node->m_parent;
 887         // impossible for parent to be null - should assert this
 888         TYPENAME std::vector<ntree_node<T>*>::iterator found =
 889           std::find(parent->m_children.begin(), parent->m_children.end(), node);
 890         // impossible for find to fail - should assert this
 891         result.m_root = *found;
 892         parent->m_children.erase(found);
 893       }
 894       if (result.m_root)
 895       {
 896         result.m_root->m_parent = 0;
 897         result.m_root->set_new_owner(&result);
 898       }
 899     }
 900     return result;
 901   }
 902
 903   template<typename T>
 904   ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i, unsigned offset)
 905     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 906   {
 907     return cut(child(i, offset));
 908   }
 909
 910   ////////////////////////////////////////////////////////////////////////////////
 911
 912 } // end namespace stlplus
 913