00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00040 #ifndef tree_hh_
00041 #define tree_hh_
00042
00043 #error This file should not be used, DEPRECATED
00044
00045 #include <cassert>
00046 #include <memory>
00047 #include <stdexcept>
00048 #include <iterator>
00049 #include <set>
00050 #include <queue>
00051 #include <algorithm>
00052
00053
00054
00055
00056 namespace kp {
00057
00058 template <class T1, class T2>
00059 void constructor(T1* p, T2& val)
00060 {
00061 new ((void *) p) T1(val);
00062 }
00063
00064 template <class T1>
00065 void constructor(T1* p)
00066 {
00067 new ((void *) p) T1;
00068 }
00069
00070 template <class T1>
00071 void destructor(T1* p)
00072 {
00073 p->~T1();
00074 }
00075 }
00076
00078 template<class T>
00079 class tree_node_ {
00080 public:
00081 tree_node_<T> *parent;
00082 tree_node_<T> *first_child, *last_child;
00083 tree_node_<T> *prev_sibling, *next_sibling;
00084 T data;
00085 };
00086
00087 template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
00088 class tree {
00089 protected:
00090 typedef tree_node_<T> tree_node;
00091 public:
00093 typedef T value_type;
00094
00095 class iterator_base;
00096 class pre_order_iterator;
00097 class post_order_iterator;
00098 class children_iterator;
00099 class leaf_iterator;
00100
00101 tree();
00102 tree(const T&);
00103 tree(const tree<T, tree_node_allocator>&);
00104 ~tree();
00105 tree<T,tree_node_allocator>& operator=(const tree<T, tree_node_allocator>&);
00106
00108 #ifdef __SGI_STL_PORT
00109 class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
00110 #else
00111 class iterator_base {
00112 #endif
00113 public:
00114 typedef T value_type;
00115 typedef T* pointer;
00116 typedef T& reference;
00117 typedef size_t size_type;
00118 typedef ptrdiff_t difference_type;
00119 typedef std::bidirectional_iterator_tag iterator_category;
00120
00121 iterator_base();
00122 iterator_base(tree_node *);
00123
00124 T& operator*() const;
00125 T* operator->() const;
00126
00128 unsigned int number_of_children() const;
00129
00130 children_iterator begin_children_iterator() const;
00131 children_iterator end_children_iterator() const;
00132
00133 tree_node *node;
00134 };
00135
00137 class pre_order_iterator : public iterator_base {
00138 public:
00139 pre_order_iterator();
00140 pre_order_iterator(tree_node *);
00141
00142 bool operator==(const pre_order_iterator&) const;
00143 bool operator!=(const pre_order_iterator&) const;
00144 pre_order_iterator& operator++();
00145 pre_order_iterator& operator--();
00146 pre_order_iterator operator++(int);
00147 pre_order_iterator operator--(int);
00148 pre_order_iterator& operator+=(unsigned int);
00149 pre_order_iterator& operator-=(unsigned int);
00150 };
00151
00153 class post_order_iterator : public iterator_base {
00154 public:
00155 post_order_iterator();
00156 post_order_iterator(tree_node *);
00157
00158 bool operator==(const post_order_iterator&) const;
00159 bool operator!=(const post_order_iterator&) const;
00160 post_order_iterator& operator++();
00161 post_order_iterator& operator--();
00162 post_order_iterator operator++(int);
00163 post_order_iterator operator--(int);
00164 post_order_iterator& operator+=(unsigned int);
00165 post_order_iterator& operator-=(unsigned int);
00166
00168 void descend_all();
00169 };
00170
00172 class breadth_first_queued_iterator : public iterator_base {
00173 public:
00174 breadth_first_queued_iterator();
00175 breadth_first_queued_iterator(tree_node *);
00176
00177 bool operator==(const breadth_first_queued_iterator&) const;
00178 bool operator!=(const breadth_first_queued_iterator&) const;
00179 breadth_first_queued_iterator& operator++();
00180 breadth_first_queued_iterator operator++(int);
00181 breadth_first_queued_iterator& operator+=(unsigned int);
00182
00183 private:
00184 std::queue<tree_node *> traversal_queue;
00185 };
00186
00188 class children_iterator : public iterator_base {
00189 public:
00190 children_iterator();
00191 children_iterator(tree_node *);
00192
00193 bool operator==(const children_iterator&) const;
00194 bool operator!=(const children_iterator&) const;
00195 children_iterator& operator++();
00196 children_iterator& operator--();
00197 children_iterator operator++(int);
00198 children_iterator operator--(int);
00199 children_iterator& operator+=(unsigned int);
00200 children_iterator& operator-=(unsigned int);
00201
00202 tree_node *range_first() const;
00203 tree_node *range_last() const;
00204 tree_node *parent_;
00205 private:
00206 void set_parent_();
00207 };
00208
00210 class leaf_iterator : public iterator_base {
00211 public:
00212 leaf_iterator();
00213 leaf_iterator(tree_node *, tree_node *top=0);
00214
00215 bool operator==(const leaf_iterator&) const;
00216 bool operator!=(const leaf_iterator&) const;
00217 leaf_iterator& operator++();
00218 leaf_iterator& operator--();
00219 leaf_iterator operator++(int);
00220 leaf_iterator operator--(int);
00221 leaf_iterator& operator+=(unsigned int);
00222 leaf_iterator& operator-=(unsigned int);
00223 private:
00224 tree_node *top_node;
00225 };
00226
00228 inline pre_order_iterator root() const;
00229
00231 inline pre_order_iterator begin_pre_order_iterator(const iterator_base&) const;
00233 inline pre_order_iterator end_pre_order_iterator(const iterator_base&) const;
00235 post_order_iterator begin_post_order_iterator(const iterator_base&) const;
00237 post_order_iterator end_post_order_iterator(const iterator_base&) const;
00238
00239
00241 breadth_first_queued_iterator begin_breadth_first_iterator(const iterator_base&) const;
00243 breadth_first_queued_iterator end_breadth_first_iterator(const iterator_base&) const;
00244
00245
00247 children_iterator begin_children_iterator(const iterator_base&) const;
00249 children_iterator end_children_iterator(const iterator_base&) const;
00250
00252 leaf_iterator begin_leaf_iterator(const iterator_base& top) const;
00254 leaf_iterator end_leaf_iterator(const iterator_base& top) const;
00255
00257 template<typename iter> static iter parent(iter);
00259 template<typename iter> iter previous_sibling(iter) const;
00261 template<typename iter> iter next_sibling(iter) const;
00262
00264 void clear();
00266 template<typename iter> iter erase(iter);
00268 void erase_children(const iterator_base&);
00269
00270
00272 pre_order_iterator set_root(const T& x);
00273
00275 template<typename iter> iter append_child(iter position, const T& x);
00276 template<typename iter> iter prepend_child(iter position, const T& x);
00277
00279 template<typename iter> iter insert_before(iter position, const T& x);
00281 template<typename iter> iter insert_after(iter position, const T& x);
00282
00284 template<typename iter> iter replace(iter position, const T& x);
00286 template<typename iter> iter replace(iter position, const iterator_base& from);
00287
00289 pre_order_iterator reparent_root(const T& x);
00290
00292 template<typename iter> iter move_after(iter target, iter source);
00294 template<typename iter> iter move_before(iter target, iter source);
00295
00297 size_t size() const;
00299 size_t size(const iterator_base&) const;
00301 bool empty() const;
00303 static int depth(const iterator_base&);
00304 static int depth(const iterator_base&, const iterator_base&);
00306 int max_depth() const;
00308 int max_depth(const iterator_base&) const;
00310 static unsigned int number_of_children(const iterator_base&);
00312 bool is_valid(const iterator_base&) const;
00313
00315 unsigned int index(children_iterator it) const;
00317 static children_iterator child(const iterator_base& position, unsigned int);
00318
00320 class iterator_base_less {
00321 public:
00322 bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
00323 const typename tree<T, tree_node_allocator>::iterator_base& two) const
00324 {
00325 return one.node < two.node;
00326 }
00327 };
00328 tree_node *head, *feet;
00329 private:
00330 tree_node_allocator alloc_;
00331 void head_initialise_();
00332 void copy_(const tree<T, tree_node_allocator>& other);
00333
00335 template<class StrictWeakOrdering>
00336 class compare_nodes {
00337 public:
00338 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
00339
00340 bool operator()(const tree_node *a, const tree_node *b)
00341 {
00342 return comp_(a->data, b->data);
00343 }
00344 private:
00345 StrictWeakOrdering comp_;
00346 };
00347 };
00348
00349
00350
00351
00352
00353 template <class T, class tree_node_allocator>
00354 tree<T, tree_node_allocator>::tree()
00355 {
00356 head_initialise_();
00357 }
00358
00359 template <class T, class tree_node_allocator>
00360 tree<T, tree_node_allocator>::tree(const T& x)
00361 {
00362 head_initialise_();
00363 set_root(x);
00364 }
00365
00366 template <class T, class tree_node_allocator>
00367 tree<T, tree_node_allocator>::~tree()
00368 {
00369 clear();
00370 alloc_.deallocate(head,1);
00371 alloc_.deallocate(feet,1);
00372 }
00373
00374 template <class T, class tree_node_allocator>
00375 void tree<T, tree_node_allocator>::head_initialise_()
00376 {
00377 head = alloc_.allocate(1,0);
00378 feet = alloc_.allocate(1,0);
00379
00380 head->parent=0;
00381 head->first_child=0;
00382 head->last_child=0;
00383 head->prev_sibling=0;
00384 head->next_sibling=feet;
00385
00386 feet->parent=0;
00387 feet->first_child=0;
00388 feet->last_child=0;
00389 feet->prev_sibling=head;
00390 feet->next_sibling=0;
00391 }
00392
00393 template <class T, class tree_node_allocator>
00394 tree<T,tree_node_allocator>& tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)
00395 {
00396 if (this != &other)
00397 {
00398 copy_(other);
00399 }
00400 return (*this);
00401 }
00402
00403 template <class T, class tree_node_allocator>
00404 tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
00405 {
00406 head_initialise_();
00407 copy_(other);
00408 }
00409
00410 template <class T, class tree_node_allocator>
00411 void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other)
00412 {
00413
00414 if (this == &other)
00415 {
00416 return;
00417 }
00418 clear();
00419 pre_order_iterator it=other.begin_pre_order_iterator(other.root()), to=begin_pre_order_iterator(root());
00420 while(it!=other.end_pre_order_iterator(other.root())) {
00421 to=insert_before(to, (*it));
00422 ++it;
00423 }
00424 to=begin_pre_order_iterator(root());
00425 it=other.begin_pre_order_iterator(other.root());
00426 while(it!=other.end_pre_order_iterator(other.root())) {
00427 to=replace(to, it);
00428 ++to;
00429 ++it;
00430 }
00431 }
00432
00433 template <class T, class tree_node_allocator>
00434 void tree<T, tree_node_allocator>::clear()
00435 {
00436 if(head)
00437 while(head->next_sibling!=feet)
00438 erase(pre_order_iterator(head->next_sibling));
00439 }
00440
00441 template<class T, class tree_node_allocator>
00442 void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
00443 {
00444
00445 if(it.node==0) return;
00446
00447 tree_node *cur=it.node->first_child;
00448 tree_node *prev=0;
00449
00450 while(cur!=0) {
00451 prev=cur;
00452 cur=cur->next_sibling;
00453 erase_children(pre_order_iterator(prev));
00454 kp::destructor(&prev->data);
00455 alloc_.deallocate(prev,1);
00456 }
00457 it.node->first_child=0;
00458 it.node->last_child=0;
00459
00460 }
00461
00462 template<class T, class tree_node_allocator>
00463 template<class iter>
00464 iter tree<T, tree_node_allocator>::erase(iter it)
00465 {
00466 tree_node *cur=it.node;
00467 assert(cur!=head);
00468 iter ret=it;
00469 ++ret;
00470 erase_children(it);
00471 if(cur->prev_sibling==0) {
00472 cur->parent->first_child=cur->next_sibling;
00473 }
00474 else {
00475 cur->prev_sibling->next_sibling=cur->next_sibling;
00476 }
00477 if(cur->next_sibling==0) {
00478 cur->parent->last_child=cur->prev_sibling;
00479 }
00480 else {
00481 cur->next_sibling->prev_sibling=cur->prev_sibling;
00482 }
00483
00484 kp::destructor(&cur->data);
00485 alloc_.deallocate(cur,1);
00486 return ret;
00487 }
00488
00489 template <class T, class tree_node_allocator>
00490 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::root() const
00491 {
00492 return pre_order_iterator(head->next_sibling);
00493 }
00494
00495
00496 template <class T, class tree_node_allocator>
00497 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin_pre_order_iterator(const iterator_base& pos) const
00498 {
00499 return pre_order_iterator(pos.node);
00500 }
00501
00502 template <class T, class tree_node_allocator>
00503 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end_pre_order_iterator(const iterator_base& pos) const
00504 {
00505 return pre_order_iterator(pos.node->next_sibling);
00506 }
00507
00508
00509
00510 template <class T, class tree_node_allocator>
00511 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::begin_breadth_first_iterator(const iterator_base& pos) const
00512 {
00513 return breadth_first_queued_iterator(pos.node);
00514 }
00515
00516 template <class T, class tree_node_allocator>
00517 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::end_breadth_first_iterator(const iterator_base& pos) const
00518 {
00519 return breadth_first_queued_iterator();
00520 }
00521
00522
00523 template <class T, class tree_node_allocator>
00524 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post_order_iterator(const iterator_base& pos) const
00525 {
00526 tree_node *tmp=pos.node;
00527 if(tmp!=feet) {
00528 while(tmp->first_child)
00529 tmp=tmp->first_child;
00530 }
00531 return post_order_iterator(tmp);
00532 }
00533
00534 template <class T, class tree_node_allocator>
00535 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post_order_iterator(const iterator_base& pos) const
00536 {
00537 return post_order_iterator(pos.node->next_sibling);
00538 }
00539
00540
00541 template <class T, class tree_node_allocator>
00542 typename tree<T, tree_node_allocator>::children_iterator tree<T, tree_node_allocator>::begin_children_iterator(const iterator_base& pos) const
00543 {
00544 assert(pos.node!=0);
00545 if(pos.node->first_child==0) {
00546 return end_children_iterator(pos);
00547 }
00548 return pos.node->first_child;
00549 }
00550
00551 template <class T, class tree_node_allocator>
00552 typename tree<T, tree_node_allocator>::children_iterator tree<T, tree_node_allocator>::end_children_iterator(const iterator_base& pos) const
00553 {
00554 children_iterator ret(0);
00555 ret.parent_=pos.node;
00556 return ret;
00557 }
00558
00559 template <class T, class tree_node_allocator>
00560 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf_iterator(const iterator_base& top) const
00561 {
00562 tree_node *tmp=top.node;
00563 while(tmp->first_child)
00564 tmp=tmp->first_child;
00565 return leaf_iterator(tmp, top.node);
00566 }
00567
00568 template <class T, class tree_node_allocator>
00569 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf_iterator(const iterator_base& top) const
00570 {
00571 return leaf_iterator(top.node, top.node);
00572 }
00573
00574 template <class T, class tree_node_allocator>
00575 template <typename iter>
00576 iter tree<T, tree_node_allocator>::parent(iter position)
00577 {
00578 assert(position.node!=0);
00579 return iter(position.node->parent);
00580 }
00581
00582 template <class T, class tree_node_allocator>
00583 template <typename iter>
00584 iter tree<T, tree_node_allocator>::previous_sibling(iter position) const
00585 {
00586 assert(position.node!=0);
00587 iter ret(position);
00588 ret.node=position.node->prev_sibling;
00589 return ret;
00590 }
00591
00592 template <class T, class tree_node_allocator>
00593 template <typename iter>
00594 iter tree<T, tree_node_allocator>::next_sibling(iter position) const
00595 {
00596 assert(position.node!=0);
00597 iter ret(position);
00598 ret.node=position.node->next_sibling;
00599 return ret;
00600 }
00601
00602 template <class T, class tree_node_allocator>
00603 template <class iter>
00604 iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
00605 {
00606
00607
00608
00609
00610 assert(position.node!=head);
00611 assert(position.node);
00612
00613 tree_node* tmp = alloc_.allocate(1,0);
00614 kp::constructor(&tmp->data, x);
00615 tmp->first_child=0;
00616 tmp->last_child=0;
00617
00618 tmp->parent=position.node;
00619 if(position.node->last_child!=0) {
00620 position.node->last_child->next_sibling=tmp;
00621 }
00622 else {
00623 position.node->first_child=tmp;
00624 }
00625 tmp->prev_sibling=position.node->last_child;
00626 position.node->last_child=tmp;
00627 tmp->next_sibling=0;
00628 return tmp;
00629 }
00630
00631 template <class T, class tree_node_allocator>
00632 template <class iter>
00633 iter tree<T, tree_node_allocator>::prepend_child(iter position, const T& x)
00634 {
00635 assert(position.node!=head);
00636 assert(position.node);
00637
00638 tree_node* tmp = alloc_.allocate(1,0);
00639 kp::constructor(&tmp->data, x);
00640 tmp->first_child=0;
00641 tmp->last_child=0;
00642
00643 tmp->parent=position.node;
00644 if(position.node->first_child!=0) {
00645 position.node->first_child->prev_sibling=tmp;
00646 }
00647 else {
00648 position.node->last_child=tmp;
00649 }
00650 tmp->next_sibling=position.node->first_child;
00651 position.node->first_child=tmp;
00652 tmp->prev_sibling=0;
00653 return tmp;
00654 }
00655
00656
00657 template <class T, class tree_node_allocator>
00658 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_root(const T& x)
00659 {
00660 assert(head->next_sibling==feet);
00661 return insert_before(pre_order_iterator(feet), x);
00662 }
00663
00664 template <class T, class tree_node_allocator>
00665 template <class iter>
00666 iter tree<T, tree_node_allocator>::insert_before(iter position, const T& x)
00667 {
00668 if(position.node==0) {
00669 position.node=feet;
00670
00671 }
00672 tree_node* tmp = alloc_.allocate(1,0);
00673 kp::constructor(&tmp->data, x);
00674 tmp->first_child=0;
00675 tmp->last_child=0;
00676
00677 tmp->parent=position.node->parent;
00678 tmp->next_sibling=position.node;
00679 tmp->prev_sibling=position.node->prev_sibling;
00680 position.node->prev_sibling=tmp;
00681
00682 if(tmp->prev_sibling==0) {
00683 if(tmp->parent)
00684 tmp->parent->first_child=tmp;
00685 }
00686 else
00687 tmp->prev_sibling->next_sibling=tmp;
00688 return tmp;
00689 }
00690
00691
00692 template <class T, class tree_node_allocator>
00693 template <class iter>
00694 iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
00695 {
00696 tree_node* tmp = alloc_.allocate(1,0);
00697 kp::constructor(&tmp->data, x);
00698 tmp->first_child=0;
00699 tmp->last_child=0;
00700
00701 tmp->parent=position.node->parent;
00702 tmp->prev_sibling=position.node;
00703 tmp->next_sibling=position.node->next_sibling;
00704 position.node->next_sibling=tmp;
00705
00706 if(tmp->next_sibling==0) {
00707 if(tmp->parent)
00708 tmp->parent->last_child=tmp;
00709 }
00710 else {
00711 tmp->next_sibling->prev_sibling=tmp;
00712 }
00713 return tmp;
00714 }
00715
00716
00717 template <class T, class tree_node_allocator>
00718 template <class iter>
00719 iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
00720 {
00721 kp::destructor(&position.node->data);
00722 kp::constructor(&position.node->data, x);
00723 return position;
00724 }
00725
00726 template <class T, class tree_node_allocator>
00727 template <class iter>
00728 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
00729 {
00730 assert(position.node!=head);
00731 tree_node *current_from=from.node;
00732 tree_node *start_from=from.node;
00733 tree_node *current_to =position.node;
00734
00735
00736
00737 erase_children(position);
00738
00739 tree_node* tmp = alloc_.allocate(1,0);
00740 kp::constructor(&tmp->data, (*from));
00741 tmp->first_child=0;
00742 tmp->last_child=0;
00743 if(current_to->prev_sibling==0) {
00744 if(current_to->parent!=0)
00745 current_to->parent->first_child=tmp;
00746 }
00747 else {
00748 current_to->prev_sibling->next_sibling=tmp;
00749 }
00750 tmp->prev_sibling=current_to->prev_sibling;
00751 if(current_to->next_sibling==0) {
00752 if(current_to->parent!=0)
00753 current_to->parent->last_child=tmp;
00754 }
00755 else {
00756 current_to->next_sibling->prev_sibling=tmp;
00757 }
00758 tmp->next_sibling=current_to->next_sibling;
00759 tmp->parent=current_to->parent;
00760 kp::destructor(¤t_to->data);
00761 alloc_.deallocate(current_to,1);
00762 current_to=tmp;
00763
00764
00765 tree_node *last=from.node->next_sibling;
00766
00767 pre_order_iterator toit=tmp;
00768
00769 do {
00770 assert(current_from!=0);
00771 if(current_from->first_child != 0) {
00772 current_from=current_from->first_child;
00773 toit=append_child(toit, current_from->data);
00774 }
00775 else {
00776 while(current_from->next_sibling==0 && current_from!=start_from) {
00777 current_from=current_from->parent;
00778 toit=parent(toit);
00779 assert(current_from!=0);
00780 }
00781 current_from=current_from->next_sibling;
00782 if(current_from!=last) {
00783 toit=append_child(parent(toit), current_from->data);
00784 }
00785 }
00786 } while(current_from!=last);
00787
00788 return current_to;
00789 }
00790
00791
00793 template <class T, class tree_node_allocator>
00794 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::reparent_root(const T& x)
00795 {
00796 if(head->next_sibling == feet->prev_sibling)
00797 {
00798 return this->set_root(x);
00799 }
00800 else
00801 {
00802
00803 tree_node *old_head_node = head->next_sibling;
00804
00805
00806 insert_before(pre_order_iterator(feet), x);
00807
00808
00809 tree_node *new_head_node = head->next_sibling->next_sibling;
00810 head->next_sibling = new_head_node;
00811
00812
00813 new_head_node->first_child = old_head_node;
00814 new_head_node->last_child = old_head_node;
00815 new_head_node->next_sibling = feet;
00816 new_head_node->prev_sibling = head;
00817
00818
00819 feet->prev_sibling = new_head_node;
00820
00821
00822 old_head_node->next_sibling = 0;
00823 old_head_node->prev_sibling = 0;
00824 old_head_node->parent = new_head_node;
00825
00826 return begin_pre_order_iterator(root());
00827 }
00828 }
00829
00830 template <class T, class tree_node_allocator>
00831 template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)
00832 {
00833 tree_node *dst=target.node;
00834 tree_node *src=source.node;
00835 assert(dst);
00836 assert(src);
00837
00838 if(dst==src) return source;
00839 if(dst->next_sibling)
00840 if(dst->next_sibling==src)
00841 return source;
00842
00843
00844 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
00845 else src->parent->first_child=src->next_sibling;
00846 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
00847 else src->parent->last_child=src->prev_sibling;
00848
00849
00850 if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
00851 else dst->parent->last_child=src;
00852 src->next_sibling=dst->next_sibling;
00853 dst->next_sibling=src;
00854 src->prev_sibling=dst;
00855 src->parent=dst->parent;
00856 return src;
00857 }
00858
00859 template <class T, class tree_node_allocator>
00860 template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
00861 {
00862 tree_node *dst=target.node;
00863 tree_node *src=source.node;
00864 assert(dst);
00865 assert(src);
00866
00867 if(dst==src) return source;
00868 if(dst->prev_sibling)
00869 if(dst->prev_sibling==src)
00870 return source;
00871
00872
00873 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
00874 else src->parent->first_child=src->next_sibling;
00875 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
00876 else src->parent->last_child=src->prev_sibling;
00877
00878
00879 if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
00880 else dst->parent->first_child=src;
00881 src->prev_sibling=dst->prev_sibling;
00882 dst->prev_sibling=src;
00883 src->next_sibling=dst;
00884 src->parent=dst->parent;
00885 return src;
00886 }
00887
00888
00889 template <class T, class tree_node_allocator>
00890 size_t tree<T, tree_node_allocator>::size() const
00891 {
00892 size_t i=0;
00893 pre_order_iterator it=begin_pre_order_iterator(), eit=end_pre_order_iterator();
00894 while(it!=eit) {
00895 ++i;
00896 ++it;
00897 }
00898 return i;
00899 }
00900
00901 template <class T, class tree_node_allocator>
00902 size_t tree<T, tree_node_allocator>::size(const iterator_base& top) const
00903 {
00904 size_t i=0;
00905 pre_order_iterator it=top, eit=top;
00906 ++eit;
00907 while(it!=eit) {
00908 ++i;
00909 ++it;
00910 }
00911 return i;
00912 }
00913
00914 template <class T, class tree_node_allocator>
00915 bool tree<T, tree_node_allocator>::empty() const
00916 {
00917 pre_order_iterator it=begin_pre_order_iterator(), eit=end_pre_order_iterator();
00918 return (it==eit);
00919 }
00920
00921 template <class T, class tree_node_allocator>
00922 int tree<T, tree_node_allocator>::depth(const iterator_base& it)
00923 {
00924 tree_node* pos=it.node;
00925 assert(pos!=0);
00926 int ret=0;
00927 while(pos->parent!=0) {
00928 pos=pos->parent;
00929 ++ret;
00930 }
00931 return ret;
00932 }
00933
00934 template <class T, class tree_node_allocator>
00935 int tree<T, tree_node_allocator>::depth(const iterator_base& it, const iterator_base& root)
00936 {
00937 tree_node* pos=it.node;
00938 assert(pos!=0);
00939 int ret=0;
00940 while(pos->parent!=0 && pos!=root.node) {
00941 pos=pos->parent;
00942 ++ret;
00943 }
00944 return ret;
00945 }
00946
00947 template <class T, class tree_node_allocator>
00948 int tree<T, tree_node_allocator>::max_depth() const
00949 {
00950 int maxd=-1;
00951 for(tree_node *it = head->next_sibling; it!=feet; it=it->next_sibling)
00952 maxd=std::max(maxd, max_depth(it));
00953
00954 return maxd;
00955 }
00956
00957
00958 template <class T, class tree_node_allocator>
00959 int tree<T, tree_node_allocator>::max_depth(const iterator_base& pos) const
00960 {
00961 tree_node *tmp=pos.node;
00962
00963 if(tmp==0 || tmp==head || tmp==feet) return -1;
00964
00965 int curdepth=0, maxdepth=0;
00966 while(true) {
00967 while(tmp->first_child==0) {
00968 if(tmp==pos.node) return maxdepth;
00969 if(tmp->next_sibling==0) {
00970
00971 do {
00972 tmp=tmp->parent;
00973 if(tmp==0) return maxdepth;
00974 --curdepth;
00975 } while(tmp->next_sibling==0);
00976 }
00977 if(tmp==pos.node) return maxdepth;
00978 tmp=tmp->next_sibling;
00979 }
00980 tmp=tmp->first_child;
00981 ++curdepth;
00982 maxdepth=std::max(curdepth, maxdepth);
00983 }
00984 }
00985
00986 template <class T, class tree_node_allocator>
00987 unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it)
00988 {
00989 tree_node *pos=it.node->first_child;
00990 if(pos==0) return 0;
00991
00992 unsigned int ret=1;
00993
00994
00995
00996
00997 while((pos=pos->next_sibling))
00998 ++ret;
00999 return ret;
01000 }
01001
01002 template <class T, class tree_node_allocator>
01003 bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
01004 {
01005 if(it.node==0 || it.node==feet || it.node==head) return false;
01006 else return true;
01007 }
01008
01009 template <class T, class tree_node_allocator>
01010 unsigned int tree<T, tree_node_allocator>::index(children_iterator it) const
01011 {
01012 unsigned int ind=0;
01013 if(it.node->parent==0) {
01014 while(it.node->prev_sibling!=head) {
01015 it.node=it.node->prev_sibling;
01016 ++ind;
01017 }
01018 }
01019 else {
01020 while(it.node->prev_sibling!=0) {
01021 it.node=it.node->prev_sibling;
01022 ++ind;
01023 }
01024 }
01025 return ind;
01026 }
01027
01028 template <class T, class tree_node_allocator>
01029 typename tree<T, tree_node_allocator>::children_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num)
01030 {
01031 tree_node *tmp=it.node->first_child;
01032 while(num--) {
01033 assert(tmp!=0);
01034 tmp=tmp->next_sibling;
01035 }
01036 return tmp;
01037 }
01038
01039
01040
01041
01042
01043
01044 template <class T, class tree_node_allocator>
01045 tree<T, tree_node_allocator>::iterator_base::iterator_base()
01046 : node(0)
01047 {
01048 }
01049
01050 template <class T, class tree_node_allocator>
01051 tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
01052 : node(tn)
01053 {
01054 }
01055
01056 template <class T, class tree_node_allocator>
01057 T& tree<T, tree_node_allocator>::iterator_base::operator*() const
01058 {
01059 return node->data;
01060 }
01061
01062 template <class T, class tree_node_allocator>
01063 T* tree<T, tree_node_allocator>::iterator_base::operator->() const
01064 {
01065 return &(node->data);
01066 }
01067
01068 template <class T, class tree_node_allocator>
01069 bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const
01070 {
01071 if(other.node!=this->node) return true;
01072 else return false;
01073 }
01074
01075 template <class T, class tree_node_allocator>
01076 bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const
01077 {
01078 if(other.node==this->node) return true;
01079 else return false;
01080 }
01081
01082 template <class T, class tree_node_allocator>
01083 bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const
01084 {
01085 if(other.node!=this->node) return true;
01086 else return false;
01087 }
01088
01089 template <class T, class tree_node_allocator>
01090 bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const
01091 {
01092 if(other.node==this->node) return true;
01093 else return false;
01094 }
01095
01096 template <class T, class tree_node_allocator>
01097 bool tree<T, tree_node_allocator>::children_iterator::operator!=(const children_iterator& other) const
01098 {
01099 if(other.node!=this->node) return true;
01100 else return false;
01101 }
01102
01103 template <class T, class tree_node_allocator>
01104 bool tree<T, tree_node_allocator>::children_iterator::operator==(const children_iterator& other) const
01105 {
01106 if(other.node==this->node) return true;
01107 else return false;
01108 }
01109
01110 template <class T, class tree_node_allocator>
01111 bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const leaf_iterator& other) const
01112 {
01113 if(other.node!=this->node) return true;
01114 else return false;
01115 }
01116
01117 template <class T, class tree_node_allocator>
01118 bool tree<T, tree_node_allocator>::leaf_iterator::operator==(const leaf_iterator& other) const
01119 {
01120 if(other.node==this->node && other.top_node==this->top_node) return true;
01121 else return false;
01122 }
01123
01124 template <class T, class tree_node_allocator>
01125 typename tree<T, tree_node_allocator>::children_iterator tree<T, tree_node_allocator>::iterator_base::begin_children_iterator() const
01126 {
01127 if(node->first_child==0)
01128 return end_children_iterator();
01129
01130 children_iterator ret(node->first_child);
01131 ret.parent_=this->node;
01132 return ret;
01133 }
01134
01135 template <class T, class tree_node_allocator>
01136 typename tree<T, tree_node_allocator>::children_iterator tree<T, tree_node_allocator>::iterator_base::end_children_iterator() const
01137 {
01138 children_iterator ret(0);
01139 ret.parent_=node;
01140 return ret;
01141 }
01142
01143 template <class T, class tree_node_allocator>
01144 unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const
01145 {
01146 tree_node *pos=node->first_child;
01147 if(pos==0) return 0;
01148
01149 unsigned int ret=1;
01150 while(pos!=node->last_child) {
01151 ++ret;
01152 pos=pos->next_sibling;
01153 }
01154 return ret;
01155 }
01156
01157
01158
01159
01160
01161 template <class T, class tree_node_allocator>
01162 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
01163 : iterator_base(0)
01164 {
01165 }
01166
01167 template <class T, class tree_node_allocator>
01168 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
01169 : iterator_base(tn)
01170 {
01171 }
01172
01173 template <class T, class tree_node_allocator>
01174 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
01175 {
01176 assert(this->node!=0);
01177 if(this->node->first_child != 0) {
01178 this->node=this->node->first_child;
01179 }
01180 else {
01181 while(this->node->next_sibling==0) {
01182 this->node=this->node->parent;
01183 if(this->node==0)
01184 return *this;
01185 }
01186 this->node=this->node->next_sibling;
01187 }
01188 return *this;
01189 }
01190
01191 template <class T, class tree_node_allocator>
01192 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
01193 {
01194 assert(this->node!=0);
01195 if(this->node->prev_sibling) {
01196 this->node=this->node->prev_sibling;
01197 while(this->node->last_child)
01198 this->node=this->node->last_child;
01199 }
01200 else {
01201 this->node=this->node->parent;
01202 if(this->node==0)
01203 return *this;
01204 }
01205 return *this;
01206 }
01207
01208 template <class T, class tree_node_allocator>
01209 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int)
01210 {
01211 pre_order_iterator copy = *this;
01212 ++(*this);
01213 return copy;
01214 }
01215
01216 template <class T, class tree_node_allocator>
01217 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int)
01218 {
01219 pre_order_iterator copy = *this;
01220 --(*this);
01221 return copy;
01222 }
01223
01224 template <class T, class tree_node_allocator>
01225 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
01226 {
01227 while(num>0) {
01228 ++(*this);
01229 --num;
01230 }
01231 return (*this);
01232 }
01233
01234 template <class T, class tree_node_allocator>
01235 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
01236 {
01237 while(num>0) {
01238 --(*this);
01239 --num;
01240 }
01241 return (*this);
01242 }
01243
01244
01245
01246
01247
01248 template <class T, class tree_node_allocator>
01249 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
01250 : iterator_base(0)
01251 {
01252 }
01253
01254 template <class T, class tree_node_allocator>
01255 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
01256 : iterator_base(tn)
01257 {
01258 }
01259
01260 template <class T, class tree_node_allocator>
01261 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
01262 {
01263 assert(this->node!=0);
01264 if(this->node->next_sibling==0) {
01265 this->node=this->node->parent;
01266 }
01267 else {
01268 this->node=this->node->next_sibling;
01269 while(this->node->first_child)
01270 this->node=this->node->first_child;
01271 }
01272 return *this;
01273 }
01274
01275 template <class T, class tree_node_allocator>
01276 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
01277 {
01278 assert(this->node!=0);
01279 if(this->skip_current_children_ || this->node->last_child==0) {
01280 this->skip_current_children_=false;
01281 while(this->node->prev_sibling==0)
01282 this->node=this->node->parent;
01283 this->node=this->node->prev_sibling;
01284 }
01285 else {
01286 this->node=this->node->last_child;
01287 }
01288 return *this;
01289 }
01290
01291 template <class T, class tree_node_allocator>
01292 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(int)
01293 {
01294 post_order_iterator copy = *this;
01295 ++(*this);
01296 return copy;
01297 }
01298
01299 template <class T, class tree_node_allocator>
01300 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(int)
01301 {
01302 post_order_iterator copy = *this;
01303 --(*this);
01304 return copy;
01305 }
01306
01307
01308 template <class T, class tree_node_allocator>
01309 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
01310 {
01311 while(num>0) {
01312 ++(*this);
01313 --num;
01314 }
01315 return (*this);
01316 }
01317
01318 template <class T, class tree_node_allocator>
01319 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
01320 {
01321 while(num>0) {
01322 --(*this);
01323 --num;
01324 }
01325 return (*this);
01326 }
01327
01328 template <class T, class tree_node_allocator>
01329 void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
01330 {
01331 assert(this->node!=0);
01332 while(this->node->first_child)
01333 this->node=this->node->first_child;
01334 }
01335
01336
01337
01338
01339 template <class T, class tree_node_allocator>
01340 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator()
01341 : iterator_base()
01342 {
01343 }
01344
01345 template <class T, class tree_node_allocator>
01346 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(tree_node *tn)
01347 : iterator_base(tn)
01348 {
01349 traversal_queue.push(tn);
01350 }
01351
01352 template <class T, class tree_node_allocator>
01353 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator!=(const breadth_first_queued_iterator& other) const
01354 {
01355 if(other.node!=this->node) return true;
01356 else return false;
01357 }
01358
01359 template <class T, class tree_node_allocator>
01360 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator==(const breadth_first_queued_iterator& other) const
01361 {
01362 if(other.node==this->node) return true;
01363 else return false;
01364 }
01365
01366 template <class T, class tree_node_allocator>
01367 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++()
01368 {
01369 assert(this->node!=0);
01370
01371
01372 children_iterator sib=this->begin_children_iterator();
01373 while(sib!=this->end_children_iterator()) {
01374 traversal_queue.push(sib.node);
01375 ++sib;
01376 }
01377 traversal_queue.pop();
01378 if(traversal_queue.size()>0)
01379 this->node=traversal_queue.front();
01380 else
01381 this->node=0;
01382 return (*this);
01383 }
01384
01385 template <class T, class tree_node_allocator>
01386 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++(int)
01387 {
01388 breadth_first_queued_iterator copy = *this;
01389 ++(*this);
01390 return copy;
01391 }
01392
01393 template <class T, class tree_node_allocator>
01394 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int num)
01395 {
01396 while(num>0) {
01397 ++(*this);
01398 --num;
01399 }
01400 return (*this);
01401 }
01402
01403
01404
01405 template <class T, class tree_node_allocator>
01406 tree<T, tree_node_allocator>::children_iterator::children_iterator()
01407 : iterator_base()
01408 {
01409 set_parent_();
01410 }
01411
01412 template <class T, class tree_node_allocator>
01413 tree<T, tree_node_allocator>::children_iterator::children_iterator(tree_node *tn)
01414 : iterator_base(tn)
01415 {
01416 set_parent_();
01417 }
01418
01419 template <class T, class tree_node_allocator>
01420 void tree<T, tree_node_allocator>::children_iterator::set_parent_()
01421 {
01422 parent_=0;
01423 if(this->node==0) return;
01424 if(this->node->parent!=0)
01425 parent_=this->node->parent;
01426 }
01427
01428 template <class T, class tree_node_allocator>
01429 typename tree<T, tree_node_allocator>::children_iterator& tree<T, tree_node_allocator>::children_iterator::operator++()
01430 {
01431 if(this->node)
01432 this->node=this->node->next_sibling;
01433 return *this;
01434 }
01435
01436 template <class T, class tree_node_allocator>
01437 typename tree<T, tree_node_allocator>::children_iterator& tree<T, tree_node_allocator>::children_iterator::operator--()
01438 {
01439 if(this->node) this->node=this->node->prev_sibling;
01440 else {
01441 assert(parent_);
01442 this->node=parent_->last_child;
01443 }
01444 return *this;
01445 }
01446
01447 template <class T, class tree_node_allocator>
01448 typename tree<T, tree_node_allocator>::children_iterator tree<T, tree_node_allocator>::children_iterator::operator++(int)
01449 {
01450 children_iterator copy = *this;
01451 ++(*this);
01452 return copy;
01453 }
01454
01455 template <class T, class tree_node_allocator>
01456 typename tree<T, tree_node_allocator>::children_iterator tree<T, tree_node_allocator>::children_iterator::operator--(int)
01457 {
01458 children_iterator copy = *this;
01459 --(*this);
01460 return copy;
01461 }
01462
01463 template <class T, class tree_node_allocator>
01464 typename tree<T, tree_node_allocator>::children_iterator& tree<T, tree_node_allocator>::children_iterator::operator+=(unsigned int num)
01465 {
01466 while(num>0) {
01467 ++(*this);
01468 --num;
01469 }
01470 return (*this);
01471 }
01472
01473 template <class T, class tree_node_allocator>
01474 typename tree<T, tree_node_allocator>::children_iterator& tree<T, tree_node_allocator>::children_iterator::operator-=(unsigned int num)
01475 {
01476 while(num>0) {
01477 --(*this);
01478 --num;
01479 }
01480 return (*this);
01481 }
01482
01483 template <class T, class tree_node_allocator>
01484 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::children_iterator::range_first() const
01485 {
01486 tree_node *tmp=parent_->first_child;
01487 return tmp;
01488 }
01489
01490 template <class T, class tree_node_allocator>
01491 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::children_iterator::range_last() const
01492 {
01493 return parent_->last_child;
01494 }
01495
01496
01497
01498 template <class T, class tree_node_allocator>
01499 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator()
01500 : iterator_base(0), top_node(0)
01501 {
01502 }
01503
01504 template <class T, class tree_node_allocator>
01505 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(tree_node *tn, tree_node *top)
01506 : iterator_base(tn), top_node(top)
01507 {
01508 }
01509
01510
01511 template <class T, class tree_node_allocator>
01512 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator++()
01513 {
01514 assert(this->node!=0);
01515 if(this->node->first_child!=0) {
01516 while(this->node->first_child)
01517 this->node=this->node->first_child;
01518 }
01519 else {
01520 while(this->node->next_sibling==0) {
01521 if (this->node->parent==0) return *this;
01522 this->node=this->node->parent;
01523 if (top_node != 0 && this->node==top_node) return *this;
01524 }
01525 this->node=this->node->next_sibling;
01526 while(this->node->first_child)
01527 this->node=this->node->first_child;
01528 }
01529 return *this;
01530 }
01531
01532 template <class T, class tree_node_allocator>
01533 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator--()
01534 {
01535 assert(this->node!=0);
01536 while (this->node->prev_sibling==0) {
01537 if (this->node->parent==0) return *this;
01538 this->node=this->node->parent;
01539 if (top_node !=0 && this->node==top_node) return *this;
01540 }
01541 this->node=this->node->prev_sibling;
01542 while(this->node->last_child)
01543 this->node=this->node->last_child;
01544 return *this;
01545 }
01546
01547 template <class T, class tree_node_allocator>
01548 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator++(int)
01549 {
01550 leaf_iterator copy = *this;
01551 ++(*this);
01552 return copy;
01553 }
01554
01555 template <class T, class tree_node_allocator>
01556 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator--(int)
01557 {
01558 leaf_iterator copy = *this;
01559 --(*this);
01560 return copy;
01561 }
01562
01563
01564 template <class T, class tree_node_allocator>
01565 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator+=(unsigned int num)
01566 {
01567 while(num>0) {
01568 ++(*this);
01569 --num;
01570 }
01571 return (*this);
01572 }
01573
01574 template <class T, class tree_node_allocator>
01575 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator-=(unsigned int num)
01576 {
01577 while(num>0) {
01578 --(*this);
01579 --num;
01580 }
01581 return (*this);
01582 }
01583
01584 #endif