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

   1 ////////////////////////////////////////////////////////////////////////////////
   2
   3 //   Author:    Andy Rushton
   4 //   Copyright: (c) Southampton University 1999-2004
   5 //              (c) Andy Rushton           2004 onwards
   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     erase();
 688     m_root = new ntree_node<T>(this,data);
 689     return ntree_iterator<T,T&,T*>(m_root);
 690   }
 691
 692   template<typename T>
 693   TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const T& data)
 694     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 695   {
 696     // if i is the end iterator, this means insert a new root
 697     // if (i.end())
 698     //   return insert(data);
 699     // otherwise, insert a new child
 700     i.assert_valid(this);
 701     if (offset > children(i)) throw std::out_of_range("stlplus::ntree");
 702     ntree_node<T>* new_node = new ntree_node<T>(this,data);
 703     i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);
 704     new_node->m_parent = i.node();
 705     return ntree_iterator<T,T&,T*>(new_node);
 706   }
 707
 708   template<typename T>
 709   TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, const T& data)
 710     throw(wrong_object,null_dereference,end_dereference)
 711   {
 712     return insert(i, children(i), data);
 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, children(i), data);
 720   }
 721
 722   template<typename T>
 723   TYPENAME ntree<T>::iterator ntree<T>::insert(const ntree<T>& tree)
 724   {
 725     // insert a whole tree as root
 726     erase();
 727     m_root = ntree_copy(this, tree.m_root);
 728     return ntree_iterator<T,T&,T*>(m_root);
 729   }
 730
 731   template<typename T>
 732   TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, unsigned offset, const ntree<T>& tree)
 733     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 734   {
 735     // insert a whole tree as a child of i
 736     i.assert_valid(this);
 737     if (offset > children(i)) throw std::out_of_range("stlplus::ntree");
 738     ntree_node<T>* new_node = ntree_copy(this, tree.m_root);
 739     i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);
 740     new_node->m_parent = i.node();
 741     return ntree_iterator<T,T&,T*>(new_node);
 742   }
 743
 744   template<typename T>
 745   TYPENAME ntree<T>::iterator ntree<T>::insert(const TYPENAME ntree<T>::iterator& i, const ntree<T>& tree)
 746     throw(wrong_object,null_dereference,end_dereference)
 747   {
 748     return insert(i, children(i), tree);
 749   }
 750
 751   template<typename T>
 752   TYPENAME ntree<T>::iterator ntree<T>::append(const TYPENAME ntree<T>::iterator& i, const ntree<T>& tree)
 753     throw(wrong_object,null_dereference,end_dereference)
 754   {
 755     return insert(i, children(i), tree);
 756   }
 757
 758   template<typename T>
 759   TYPENAME ntree<T>::iterator ntree<T>::move(ntree<T>& tree)
 760   {
 761     // insert a whole tree as root, removing it from source
 762     erase();
 763     m_root = tree.m_root;
 764     tree.m_root = 0;
 765     if (m_root) m_root->change_owner(this);
 766     return ntree_iterator<T,T&,T*>(m_root);
 767   }
 768
 769   template<typename T>
 770   TYPENAME ntree<T>::iterator ntree<T>::move(const TYPENAME ntree<T>::iterator& i, unsigned offset, ntree<T>& tree)
 771     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 772   {
 773     // insert a whole tree as a child of i
 774     i.assert_valid(this);
 775     if (offset > children(i)) throw std::out_of_range("stlplus::ntree");
 776     ntree_node<T>* new_node = tree.m_root;
 777     tree.m_root = 0;
 778     if (new_node) new_node->change_owner(this);
 779     i.node()->m_children.insert(i.node()->m_children.begin()+offset,new_node);
 780     new_node->m_parent = i.node();
 781     return ntree_iterator<T,T&,T*>(new_node);
 782   }
 783
 784   template<typename T>
 785   TYPENAME ntree<T>::iterator ntree<T>::move(const TYPENAME ntree<T>::iterator& i, ntree<T>& tree)
 786     throw(wrong_object,null_dereference,end_dereference)
 787   {
 788     return move(i, children(i), tree);
 789   }
 790
 791   template<typename T>
 792   TYPENAME ntree<T>::iterator ntree<T>::push(const TYPENAME ntree<T>::iterator& node, const T& data)
 793     throw(wrong_object,null_dereference,end_dereference)
 794   {
 795     // insert a new node to replace the existing node in the tree
 796     // making the original node the child of the new node
 797     // i.e. (node) becomes (new)->(node)
 798     // afterwards, the iterator still points to the old node, now the child
 799     // returns the iterator to the new node
 800     node.assert_valid(this);
 801     ntree_node<T>* new_node = new ntree_node<T>(this,data);
 802     if (node.node() == m_root)
 803     {
 804       // pushing the root node
 805       m_root = new_node;
 806       new_node->m_parent = 0;
 807     }
 808     else
 809     {
 810       // pushing a sub-node
 811       *(std::find(node.node()->m_parent->m_children.begin(), node.node()->m_parent->m_children.end(), node.node())) = new_node;
 812       new_node->m_parent = node.node()->m_parent;
 813     }
 814     // link up the old node as the child of the new node
 815     new_node->m_children.insert(new_node->m_children.begin(),node.node());
 816     node.node()->m_parent = new_node;
 817     return ntree_iterator<T,T&,T*>(new_node);
 818   }
 819
 820   template<typename T>
 821   void ntree<T>::pop(const TYPENAME ntree<T>::iterator& parent, unsigned offset)
 822     throw(wrong_object,null_dereference,end_dereference)
 823   {
 824     // inverse of push
 825     // removes the specified child of the parent node, adding its children to the parent node at the same offset
 826     parent.assert_valid(this);
 827     ntree_node<T>* node = parent.node();
 828     if (offset >= node->m_children.size()) throw std::out_of_range("stlplus::ntree");
 829     // move the grandchildren first
 830     ntree_node<T>* child = parent.node()->m_children[offset];
 831     while (!child->m_children.empty())
 832     {
 833       // remove the last grandchild and insert into node just after the child to be removed
 834       ntree_node<T>* grandchild = child->m_children[child->m_children.size()-1];
 835       child->m_children.pop_back();
 836       node->m_children.insert(node->m_children.begin()+offset+1, grandchild);
 837       grandchild->m_parent = node;
 838     }
 839     // now remove the child
 840     node->m_children.erase(node->m_children.begin()+offset);
 841     delete child;
 842   }
 843
 844   template<typename T>
 845   void ntree<T>::erase(void)
 846   {
 847     // erase the whole tree
 848     erase(root());
 849   }
 850
 851   template<typename T>
 852   void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i)
 853     throw(wrong_object,null_dereference,end_dereference)
 854   {
 855     if (!i.end())
 856     {
 857       // erase this node and its subtree
 858       // do this by erasing this child of its parent
 859       // handle the case of erasing the root
 860       i.assert_valid(this);
 861       ntree_node<T>* node = i.node();
 862       if (node == m_root)
 863       {
 864         delete m_root;
 865         m_root = 0;
 866       }
 867       else
 868       {
 869         ntree_node<T>* parent = node->m_parent;
 870         // impossible for parent to be null - should assert this
 871         TYPENAME std::vector<ntree_node<T>*>::iterator found =
 872           std::find(parent->m_children.begin(), parent->m_children.end(), node);
 873         // impossible for find to fail - should assert this
 874         parent->m_children.erase(found);
 875         delete node;
 876       }
 877     }
 878   }
 879
 880   template<typename T>
 881   void ntree<T>::erase(const TYPENAME ntree<T>::iterator& i, unsigned offset)
 882     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 883   {
 884     erase(child(i, offset));
 885   }
 886
 887   template<typename T>
 888   ntree<T> ntree<T>::subtree(void)
 889   {
 890     return subtree(root());
 891   }
 892
 893   template<typename T>
 894   ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i)
 895     throw(wrong_object,null_dereference,end_dereference)
 896   {
 897     ntree<T> result;
 898     if (!i.end())
 899     {
 900       i.assert_valid(this);
 901       result.m_root = ntree_copy(&result, i.node());
 902     }
 903     return result;
 904   }
 905
 906   template<typename T>
 907   ntree<T> ntree<T>::subtree(const TYPENAME ntree<T>::iterator& i, unsigned offset)
 908     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 909   {
 910     return subtree(child(i, offset));
 911   }
 912
 913   template<typename T>
 914   ntree<T> ntree<T>::cut(void)
 915   {
 916     return cut(root());
 917   }
 918
 919   template<typename T>
 920   ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i)
 921     throw(wrong_object,null_dereference,end_dereference)
 922   {
 923     ntree<T> result;
 924     if (!i.end())
 925     {
 926       i.assert_valid(this);
 927       ntree_node<T>* node = i.node();
 928       if (node == m_root)
 929       {
 930         result.m_root = m_root;
 931         m_root = 0;
 932       }
 933       else
 934       {
 935         ntree_node<T>* parent = node->m_parent;
 936         // impossible for parent to be null - should assert this
 937         TYPENAME std::vector<ntree_node<T>*>::iterator found =
 938           std::find(parent->m_children.begin(), parent->m_children.end(), node);
 939         // impossible for find to fail - should assert this
 940         result.m_root = *found;
 941         parent->m_children.erase(found);
 942       }
 943       if (result.m_root)
 944       {
 945         result.m_root->m_parent = 0;
 946         result.m_root->set_new_owner(&result);
 947       }
 948     }
 949     return result;
 950   }
 951
 952   template<typename T>
 953   ntree<T> ntree<T>::cut(const TYPENAME ntree<T>::iterator& i, unsigned offset)
 954     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 955   {
 956     return cut(child(i, offset));
 957   }
 958
 959   ////////////////////////////////////////////////////////////////////////////////
 960
 961 } // end namespace stlplus
 962