00001
00002
00003
00004
00005
00006
00007
00008
00009
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00060 #ifndef tree_hh_
00061 #define tree_hh_
00062
00063 #include <cassert>
00064 #include <memory>
00065 #include <stdexcept>
00066 #include <iterator>
00067 #include <set>
00068 #include <queue>
00069 #include <iostream>
00070
00071
00072
00073
00074 namespace kp {
00075
00076 template <class T1, class T2>
00077 void constructor(T1* p, T2& val)
00078 {
00079 new ((void *) p) T1(val);
00080 }
00081
00082 template <class T1>
00083 void constructor(T1* p)
00084 {
00085 new ((void *) p) T1;
00086 }
00087
00088 template <class T1>
00089 void destructor(T1* p)
00090 {
00091 p->~T1();
00092 }
00093
00094 };
00095
00097 template<class T>
00098 class tree_node_ {
00099 public:
00100 tree_node_<T> *parent;
00101 tree_node_<T> *first_child, *last_child;
00102 tree_node_<T> *prev_sibling, *next_sibling;
00103 T data;
00104 };
00105
00106 template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
00107 class tree {
00108 protected:
00109 typedef tree_node_<T> tree_node;
00110 public:
00112 typedef T value_type;
00113
00114 class iterator_base;
00115 class pre_order_iterator;
00116 class post_order_iterator;
00117 class sibling_iterator;
00118 class leaf_iterator;
00119
00120 tree();
00121 tree(const T&);
00122 tree(const iterator_base&);
00123 tree(const tree<T, tree_node_allocator>&);
00124 ~tree();
00125 void operator=(const tree<T, tree_node_allocator>&);
00126
00128 #ifdef __SGI_STL_PORT
00129 class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
00130 #else
00131 class iterator_base {
00132 #endif
00133 public:
00134 typedef T value_type;
00135 typedef T* pointer;
00136 typedef T& reference;
00137 typedef size_t size_type;
00138 typedef ptrdiff_t difference_type;
00139 typedef std::bidirectional_iterator_tag iterator_category;
00140
00141 iterator_base();
00142 iterator_base(tree_node *);
00143
00144 T& operator*() const;
00145 T* operator->() const;
00146
00148 void skip_children();
00150 unsigned int number_of_children() const;
00151
00152 sibling_iterator begin() const;
00153 sibling_iterator end() const;
00154
00155 tree_node *node;
00156 protected:
00157 bool skip_current_children_;
00158 };
00159
00161 class pre_order_iterator : public iterator_base {
00162 public:
00163 pre_order_iterator();
00164 pre_order_iterator(tree_node *);
00165 pre_order_iterator(const iterator_base&);
00166 pre_order_iterator(const sibling_iterator&);
00167
00168 bool operator==(const pre_order_iterator&) const;
00169 bool operator!=(const pre_order_iterator&) const;
00170 pre_order_iterator& operator++();
00171 pre_order_iterator& operator--();
00172 pre_order_iterator operator++(int);
00173 pre_order_iterator operator--(int);
00174 pre_order_iterator& operator+=(unsigned int);
00175 pre_order_iterator& operator-=(unsigned int);
00176 };
00177
00179 class post_order_iterator : public iterator_base {
00180 public:
00181 post_order_iterator();
00182 post_order_iterator(tree_node *);
00183 post_order_iterator(const iterator_base&);
00184 post_order_iterator(const sibling_iterator&);
00185
00186 bool operator==(const post_order_iterator&) const;
00187 bool operator!=(const post_order_iterator&) const;
00188 post_order_iterator& operator++();
00189 post_order_iterator& operator--();
00190 post_order_iterator operator++(int);
00191 post_order_iterator operator--(int);
00192 post_order_iterator& operator+=(unsigned int);
00193 post_order_iterator& operator-=(unsigned int);
00194
00196 void descend_all();
00197 };
00198
00200 class breadth_first_queued_iterator : public iterator_base {
00201 public:
00202 breadth_first_queued_iterator();
00203 breadth_first_queued_iterator(tree_node *);
00204 breadth_first_queued_iterator(const iterator_base&);
00205
00206 bool operator==(const breadth_first_queued_iterator&) const;
00207 bool operator!=(const breadth_first_queued_iterator&) const;
00208 breadth_first_queued_iterator& operator++();
00209 breadth_first_queued_iterator operator++(int);
00210 breadth_first_queued_iterator& operator+=(unsigned int);
00211
00212 private:
00213 std::queue<tree_node *> traversal_queue;
00214 };
00215
00217 typedef pre_order_iterator iterator;
00218 typedef breadth_first_queued_iterator breadth_first_iterator;
00219
00221 class fixed_depth_iterator : public iterator_base {
00222 public:
00223 fixed_depth_iterator();
00224 fixed_depth_iterator(tree_node *);
00225 fixed_depth_iterator(const iterator_base&);
00226 fixed_depth_iterator(const sibling_iterator&);
00227 fixed_depth_iterator(const fixed_depth_iterator&);
00228
00229 bool operator==(const fixed_depth_iterator&) const;
00230 bool operator!=(const fixed_depth_iterator&) const;
00231 fixed_depth_iterator& operator++();
00232 fixed_depth_iterator& operator--();
00233 fixed_depth_iterator operator++(int);
00234 fixed_depth_iterator operator--(int);
00235 fixed_depth_iterator& operator+=(unsigned int);
00236 fixed_depth_iterator& operator-=(unsigned int);
00237
00238 tree_node *first_parent_;
00239 private:
00240 void set_first_parent_();
00241 void find_leftmost_parent_();
00242 };
00243
00245 class sibling_iterator : public iterator_base {
00246 public:
00247 sibling_iterator();
00248 sibling_iterator(tree_node *);
00249 sibling_iterator(const sibling_iterator&);
00250 sibling_iterator(const iterator_base&);
00251
00252 bool operator==(const sibling_iterator&) const;
00253 bool operator!=(const sibling_iterator&) const;
00254 sibling_iterator& operator++();
00255 sibling_iterator& operator--();
00256 sibling_iterator operator++(int);
00257 sibling_iterator operator--(int);
00258 sibling_iterator& operator+=(unsigned int);
00259 sibling_iterator& operator-=(unsigned int);
00260
00261 tree_node *range_first() const;
00262 tree_node *range_last() const;
00263 tree_node *parent_;
00264 private:
00265 void set_parent_();
00266 };
00267
00269 class leaf_iterator : public iterator_base {
00270 public:
00271 leaf_iterator();
00272 leaf_iterator(tree_node *);
00273 leaf_iterator(const sibling_iterator&);
00274 leaf_iterator(const iterator_base&);
00275
00276 bool operator==(const leaf_iterator&) const;
00277 bool operator!=(const leaf_iterator&) const;
00278 leaf_iterator& operator++();
00279 leaf_iterator& operator--();
00280 leaf_iterator operator++(int);
00281 leaf_iterator operator--(int);
00282 leaf_iterator& operator+=(unsigned int);
00283 leaf_iterator& operator-=(unsigned int);
00284 };
00285
00287 inline pre_order_iterator begin() const;
00289 inline pre_order_iterator end() const;
00291 post_order_iterator begin_post() const;
00293 post_order_iterator end_post() const;
00295 fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
00297 fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
00299 breadth_first_queued_iterator begin_breadth_first() const;
00301 breadth_first_queued_iterator end_breadth_first() const;
00303 sibling_iterator begin(const iterator_base&) const;
00305 sibling_iterator end(const iterator_base&) const;
00307 leaf_iterator begin_leaf() const;
00309 leaf_iterator end_leaf() const;
00310
00312 template<typename iter> static iter parent(iter);
00314 template<typename iter> iter previous_sibling(iter) const;
00316 template<typename iter> iter next_sibling(iter) const;
00318 template<typename iter> iter next_at_same_depth(iter) const;
00319
00321 void clear();
00323 template<typename iter> iter erase(iter);
00325 void erase_children(const iterator_base&);
00326
00328 template<typename iter> iter append_child(iter position);
00329 template<typename iter> iter prepend_child(iter position);
00331 template<typename iter> iter append_child(iter position, const T& x);
00332 template<typename iter> iter prepend_child(iter position, const T& x);
00334 template<typename iter> iter append_child(iter position, iter other_position);
00335 template<typename iter> iter prepend_child(iter position, iter other_position);
00337 template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
00338 template<typename iter> iter prepend_children(iter position, sibling_iterator from, sibling_iterator to);
00339
00341 pre_order_iterator set_head(const T& x);
00343 template<typename iter> iter insert(iter position, const T& x);
00345 sibling_iterator insert(sibling_iterator position, const T& x);
00347 template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
00349 template<typename iter> iter insert_after(iter position, const T& x);
00351 template<typename iter> iter insert_subtree_after(iter position, const iterator_base& subtree);
00352
00354 template<typename iter> iter replace(iter position, const T& x);
00356 template<typename iter> iter replace(iter position, const iterator_base& from);
00358 sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
00359 sibling_iterator new_begin, sibling_iterator new_end);
00360
00362 template<typename iter> iter flatten(iter position);
00364 template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
00366 template<typename iter> iter reparent(iter position, iter from);
00367
00369 template<typename iter> iter wrap(iter position, const T& x);
00370
00372 template<typename iter> iter move_after(iter target, iter source);
00374 template<typename iter> iter move_before(iter target, iter source);
00375 sibling_iterator move_before(sibling_iterator target, sibling_iterator source);
00377 template<typename iter> iter move_ontop(iter target, iter source);
00378
00380 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
00381 bool duplicate_leaves=false);
00383 void sort(sibling_iterator from, sibling_iterator to, bool deep=false);
00384 template<class StrictWeakOrdering>
00385 void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);
00387 template<typename iter>
00388 bool equal(const iter& one, const iter& two, const iter& three) const;
00389 template<typename iter, class BinaryPredicate>
00390 bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
00391 template<typename iter>
00392 bool equal_subtree(const iter& one, const iter& two) const;
00393 template<typename iter, class BinaryPredicate>
00394 bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
00396 tree subtree(sibling_iterator from, sibling_iterator to) const;
00397 void subtree(tree&, sibling_iterator from, sibling_iterator to) const;
00399 void swap(sibling_iterator it);
00401 void swap(iterator, iterator);
00402
00404 int size() const;
00406 int size(const iterator_base&) const;
00408 bool empty() const;
00410 int depth(const iterator_base&) const;
00412 int max_depth() const;
00414 int max_depth(const iterator_base&) const;
00416 static unsigned int number_of_children(const iterator_base&);
00418 unsigned int number_of_siblings(const iterator_base&) const;
00420 bool is_in_subtree(const iterator_base& position, const iterator_base& begin,
00421 const iterator_base& end) const;
00423 bool is_valid(const iterator_base&) const;
00424
00426 unsigned int index(sibling_iterator it) const;
00428 sibling_iterator child(const iterator_base& position, unsigned int) const;
00429
00431 class iterator_base_less {
00432 public:
00433 bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
00434 const typename tree<T, tree_node_allocator>::iterator_base& two) const
00435 {
00436 return one.node < two.node;
00437 }
00438 };
00439 tree_node *head, *feet;
00440 private:
00441 tree_node_allocator alloc_;
00442 void head_initialise_();
00443 void copy_(const tree<T, tree_node_allocator>& other);
00444
00446 template<class StrictWeakOrdering>
00447 class compare_nodes {
00448 public:
00449 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
00450
00451 bool operator()(const tree_node *a, const tree_node *b)
00452 {
00453 static StrictWeakOrdering comp;
00454 return comp(a->data, b->data);
00455 }
00456 private:
00457 StrictWeakOrdering comp_;
00458 };
00459 };
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477
00478
00479
00480
00481
00482
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503 template <class T, class tree_node_allocator>
00504 tree<T, tree_node_allocator>::tree()
00505 {
00506 head_initialise_();
00507 }
00508
00509 template <class T, class tree_node_allocator>
00510 tree<T, tree_node_allocator>::tree(const T& x)
00511 {
00512 head_initialise_();
00513 set_head(x);
00514 }
00515
00516 template <class T, class tree_node_allocator>
00517 tree<T, tree_node_allocator>::tree(const iterator_base& other)
00518 {
00519 head_initialise_();
00520 set_head((*other));
00521 replace(begin(), other);
00522 }
00523
00524 template <class T, class tree_node_allocator>
00525 tree<T, tree_node_allocator>::~tree()
00526 {
00527 clear();
00528 alloc_.deallocate(head,1);
00529 alloc_.deallocate(feet,1);
00530 }
00531
00532 template <class T, class tree_node_allocator>
00533 void tree<T, tree_node_allocator>::head_initialise_()
00534 {
00535 head = alloc_.allocate(1,0);
00536 feet = alloc_.allocate(1,0);
00537
00538 head->parent=0;
00539 head->first_child=0;
00540 head->last_child=0;
00541 head->prev_sibling=0;
00542 head->next_sibling=feet;
00543
00544 feet->parent=0;
00545 feet->first_child=0;
00546 feet->last_child=0;
00547 feet->prev_sibling=head;
00548 feet->next_sibling=0;
00549 }
00550
00551 template <class T, class tree_node_allocator>
00552 void tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)
00553 {
00554 copy_(other);
00555 }
00556
00557 template <class T, class tree_node_allocator>
00558 tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
00559 {
00560 head_initialise_();
00561 copy_(other);
00562 }
00563
00564 template <class T, class tree_node_allocator>
00565 void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other)
00566 {
00567 clear();
00568 pre_order_iterator it=other.begin(), to=begin();
00569 while(it!=other.end()) {
00570 to=insert(to, (*it));
00571 it.skip_children();
00572 ++it;
00573 }
00574 to=begin();
00575 it=other.begin();
00576 while(it!=other.end()) {
00577 to=replace(to, it);
00578 to.skip_children();
00579 it.skip_children();
00580 ++to;
00581 ++it;
00582 }
00583 }
00584
00585 template <class T, class tree_node_allocator>
00586 void tree<T, tree_node_allocator>::clear()
00587 {
00588 if(head)
00589 while(head->next_sibling!=feet)
00590 erase(pre_order_iterator(head->next_sibling));
00591 }
00592
00593 template<class T, class tree_node_allocator>
00594 void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
00595 {
00596
00597 if(it.node==0) return;
00598
00599 tree_node *cur=it.node->first_child;
00600 tree_node *prev=0;
00601
00602 while(cur!=0) {
00603 prev=cur;
00604 cur=cur->next_sibling;
00605 erase_children(pre_order_iterator(prev));
00606 kp::destructor(&prev->data);
00607 alloc_.deallocate(prev,1);
00608 }
00609 it.node->first_child=0;
00610 it.node->last_child=0;
00611
00612 }
00613
00614 template<class T, class tree_node_allocator>
00615 template<class iter>
00616 iter tree<T, tree_node_allocator>::erase(iter it)
00617 {
00618 tree_node *cur=it.node;
00619 assert(cur!=head);
00620 iter ret=it;
00621 ret.skip_children();
00622 ++ret;
00623 erase_children(it);
00624 if(cur->prev_sibling==0) {
00625 cur->parent->first_child=cur->next_sibling;
00626 }
00627 else {
00628 cur->prev_sibling->next_sibling=cur->next_sibling;
00629 }
00630 if(cur->next_sibling==0) {
00631 cur->parent->last_child=cur->prev_sibling;
00632 }
00633 else {
00634 cur->next_sibling->prev_sibling=cur->prev_sibling;
00635 }
00636
00637 kp::destructor(&cur->data);
00638 alloc_.deallocate(cur,1);
00639 return ret;
00640 }
00641
00642 template <class T, class tree_node_allocator>
00643 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin() const
00644 {
00645 return pre_order_iterator(head->next_sibling);
00646 }
00647
00648 template <class T, class tree_node_allocator>
00649 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const
00650 {
00651 return pre_order_iterator(feet);
00652 }
00653
00654 template <class T, class tree_node_allocator>
00655 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::begin_breadth_first() const
00656 {
00657 return breadth_first_queued_iterator(head->next_sibling);
00658 }
00659
00660 template <class T, class tree_node_allocator>
00661 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::end_breadth_first() const
00662 {
00663 return breadth_first_queued_iterator();
00664 }
00665
00666 template <class T, class tree_node_allocator>
00667 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post() const
00668 {
00669 tree_node *tmp=head->next_sibling;
00670 if(tmp!=feet) {
00671 while(tmp->first_child)
00672 tmp=tmp->first_child;
00673 }
00674 return post_order_iterator(tmp);
00675 }
00676
00677 template <class T, class tree_node_allocator>
00678 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post() const
00679 {
00680 return post_order_iterator(feet);
00681 }
00682
00683 template <class T, class tree_node_allocator>
00684 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp) const
00685 {
00686 tree_node *tmp=pos.node;
00687 unsigned int curdepth=0;
00688 while(curdepth<dp) {
00689 while(tmp->first_child==0) {
00690 if(tmp->next_sibling==0) {
00691
00692 do {
00693 tmp=tmp->parent;
00694 if(tmp==0)
00695 throw std::range_error("tree: begin_fixed out of range");
00696 --curdepth;
00697 } while(tmp->next_sibling==0);
00698 }
00699 tmp=tmp->next_sibling;
00700 }
00701 tmp=tmp->first_child;
00702 ++curdepth;
00703 }
00704 return tmp;
00705 }
00706
00707 template <class T, class tree_node_allocator>
00708 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const
00709 {
00710 assert(1==0);
00711 tree_node *tmp=pos.node;
00712 unsigned int curdepth=1;
00713 while(curdepth<dp) {
00714 while(tmp->first_child==0) {
00715 tmp=tmp->next_sibling;
00716 if(tmp==0)
00717 throw std::range_error("tree: end_fixed out of range");
00718 }
00719 tmp=tmp->first_child;
00720 ++curdepth;
00721 }
00722 return tmp;
00723 }
00724
00725 template <class T, class tree_node_allocator>
00726 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(const iterator_base& pos) const
00727 {
00728 assert(pos.node!=0);
00729 if(pos.node->first_child==0) {
00730 return end(pos);
00731 }
00732 return pos.node->first_child;
00733 }
00734
00735 template <class T, class tree_node_allocator>
00736 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(const iterator_base& pos) const
00737 {
00738 sibling_iterator ret(0);
00739 ret.parent_=pos.node;
00740 return ret;
00741 }
00742
00743 template <class T, class tree_node_allocator>
00744 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf() const
00745 {
00746 tree_node *tmp=head->next_sibling;
00747 if(tmp!=feet) {
00748 while(tmp->first_child)
00749 tmp=tmp->first_child;
00750 }
00751 return leaf_iterator(tmp);
00752 }
00753
00754 template <class T, class tree_node_allocator>
00755 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf() const
00756 {
00757 return leaf_iterator(feet);
00758 }
00759
00760 template <class T, class tree_node_allocator>
00761 template <typename iter>
00762 iter tree<T, tree_node_allocator>::parent(iter position)
00763 {
00764 assert(position.node!=0);
00765 return iter(position.node->parent);
00766 }
00767
00768 template <class T, class tree_node_allocator>
00769 template <typename iter>
00770 iter tree<T, tree_node_allocator>::previous_sibling(iter position) const
00771 {
00772 assert(position.node!=0);
00773 iter ret(position);
00774 ret.node=position.node->prev_sibling;
00775 return ret;
00776 }
00777
00778 template <class T, class tree_node_allocator>
00779 template <typename iter>
00780 iter tree<T, tree_node_allocator>::next_sibling(iter position) const
00781 {
00782 assert(position.node!=0);
00783 iter ret(position);
00784 ret.node=position.node->next_sibling;
00785 return ret;
00786 }
00787
00788 template <class T, class tree_node_allocator>
00789 template <typename iter>
00790 iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const
00791 {
00792 assert(position.node!=0);
00793 iter ret(position);
00794
00795 if(position.node->next_sibling) {
00796 ret.node=position.node->next_sibling;
00797 }
00798 else {
00799 int relative_depth=0;
00800 upper:
00801 do {
00802 ret.node=ret.node->parent;
00803 if(ret.node==0) return ret;
00804 --relative_depth;
00805 } while(ret.node->next_sibling==0);
00806 lower:
00807 ret.node=ret.node->next_sibling;
00808 while(ret.node->first_child==0) {
00809 if(ret.node->next_sibling==0)
00810 goto upper;
00811 ret.node=ret.node->next_sibling;
00812 if(ret.node==0) return ret;
00813 }
00814 while(relative_depth<0 && ret.node->first_child!=0) {
00815 ret.node=ret.node->first_child;
00816 ++relative_depth;
00817 }
00818 if(relative_depth<0) {
00819 if(ret.node->next_sibling==0) goto upper;
00820 else goto lower;
00821 }
00822 }
00823 return ret;
00824 }
00825
00826 template <class T, class tree_node_allocator>
00827 template <typename iter>
00828 iter tree<T, tree_node_allocator>::append_child(iter position)
00829 {
00830 assert(position.node!=head);
00831 assert(position.node);
00832
00833 tree_node *tmp=alloc_.allocate(1,0);
00834 kp::constructor(&tmp->data);
00835 tmp->first_child=0;
00836 tmp->last_child=0;
00837
00838 tmp->parent=position.node;
00839 if(position.node->last_child!=0) {
00840 position.node->last_child->next_sibling=tmp;
00841 }
00842 else {
00843 position.node->first_child=tmp;
00844 }
00845 tmp->prev_sibling=position.node->last_child;
00846 position.node->last_child=tmp;
00847 tmp->next_sibling=0;
00848 return tmp;
00849 }
00850
00851 template <class T, class tree_node_allocator>
00852 template <typename iter>
00853 iter tree<T, tree_node_allocator>::prepend_child(iter position)
00854 {
00855 assert(position.node!=head);
00856 assert(position.node);
00857
00858 tree_node *tmp=alloc_.allocate(1,0);
00859 kp::constructor(&tmp->data);
00860 tmp->first_child=0;
00861 tmp->last_child=0;
00862
00863 tmp->parent=position.node;
00864 if(position.node->first_child!=0) {
00865 position.node->first_child->prev_sibling=tmp;
00866 }
00867 else {
00868 position.node->last_child=tmp;
00869 }
00870 tmp->next_sibling=position.node->first_child;
00871 position.node->prev_child=tmp;
00872 tmp->prev_sibling=0;
00873 return tmp;
00874 }
00875
00876 template <class T, class tree_node_allocator>
00877 template <class iter>
00878 iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
00879 {
00880
00881
00882
00883
00884 assert(position.node!=head);
00885 assert(position.node);
00886
00887 tree_node* tmp = alloc_.allocate(1,0);
00888 kp::constructor(&tmp->data, x);
00889 tmp->first_child=0;
00890 tmp->last_child=0;
00891
00892 tmp->parent=position.node;
00893 if(position.node->last_child!=0) {
00894 position.node->last_child->next_sibling=tmp;
00895 }
00896 else {
00897 position.node->first_child=tmp;
00898 }
00899 tmp->prev_sibling=position.node->last_child;
00900 position.node->last_child=tmp;
00901 tmp->next_sibling=0;
00902 return tmp;
00903 }
00904
00905 template <class T, class tree_node_allocator>
00906 template <class iter>
00907 iter tree<T, tree_node_allocator>::prepend_child(iter position, const T& x)
00908 {
00909 assert(position.node!=head);
00910 assert(position.node);
00911
00912 tree_node* tmp = alloc_.allocate(1,0);
00913 kp::constructor(&tmp->data, x);
00914 tmp->first_child=0;
00915 tmp->last_child=0;
00916
00917 tmp->parent=position.node;
00918 if(position.node->first_child!=0) {
00919 position.node->first_child->prev_sibling=tmp;
00920 }
00921 else {
00922 position.node->last_child=tmp;
00923 }
00924 tmp->next_sibling=position.node->first_child;
00925 position.node->first_child=tmp;
00926 tmp->prev_sibling=0;
00927 return tmp;
00928 }
00929
00930 template <class T, class tree_node_allocator>
00931 template <class iter>
00932 iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
00933 {
00934 assert(position.node!=head);
00935 assert(position.node);
00936
00937 sibling_iterator aargh=append_child(position, value_type());
00938 return replace(aargh, other);
00939 }
00940
00941 template <class T, class tree_node_allocator>
00942 template <class iter>
00943 iter tree<T, tree_node_allocator>::prepend_child(iter position, iter other)
00944 {
00945 assert(position.node!=head);
00946 assert(position.node);
00947
00948 sibling_iterator aargh=prepend_child(position, value_type());
00949 return replace(aargh, other);
00950 }
00951
00952 template <class T, class tree_node_allocator>
00953 template <class iter>
00954 iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)
00955 {
00956 assert(position.node!=head);
00957 assert(position.node);
00958
00959 iter ret=from;
00960
00961 while(from!=to) {
00962 insert_subtree(position.end(), from);
00963 ++from;
00964 }
00965 return ret;
00966 }
00967
00968 template <class T, class tree_node_allocator>
00969 template <class iter>
00970 iter tree<T, tree_node_allocator>::prepend_children(iter position, sibling_iterator from, sibling_iterator to)
00971 {
00972 assert(position.node!=head);
00973 assert(position.node);
00974
00975 iter ret=from;
00976
00977 while(from!=to) {
00978 insert_subtree(position.begin(), from);
00979 ++from;
00980 }
00981 return ret;
00982 }
00983
00984 template <class T, class tree_node_allocator>
00985 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(const T& x)
00986 {
00987 assert(head->next_sibling==feet);
00988 return insert(iterator(feet), x);
00989 }
00990
00991 template <class T, class tree_node_allocator>
00992 template <class iter>
00993 iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
00994 {
00995 if(position.node==0) {
00996 position.node=feet;
00997
00998 }
00999 tree_node* tmp = alloc_.allocate(1,0);
01000 kp::constructor(&tmp->data, x);
01001 tmp->first_child=0;
01002 tmp->last_child=0;
01003
01004 tmp->parent=position.node->parent;
01005 tmp->next_sibling=position.node;
01006 tmp->prev_sibling=position.node->prev_sibling;
01007 position.node->prev_sibling=tmp;
01008
01009 if(tmp->prev_sibling==0) {
01010 if(tmp->parent)
01011 tmp->parent->first_child=tmp;
01012 }
01013 else
01014 tmp->prev_sibling->next_sibling=tmp;
01015 return tmp;
01016 }
01017
01018 template <class T, class tree_node_allocator>
01019 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::insert(sibling_iterator position, const T& x)
01020 {
01021 tree_node* tmp = alloc_.allocate(1,0);
01022 kp::constructor(&tmp->data, x);
01023 tmp->first_child=0;
01024 tmp->last_child=0;
01025
01026 tmp->next_sibling=position.node;
01027 if(position.node==0) {
01028 tmp->parent=position.parent_;
01029 tmp->prev_sibling=position.range_last();
01030 tmp->parent->last_child=tmp;
01031 }
01032 else {
01033 tmp->parent=position.node->parent;
01034 tmp->prev_sibling=position.node->prev_sibling;
01035 position.node->prev_sibling=tmp;
01036 }
01037
01038 if(tmp->prev_sibling==0) {
01039 if(tmp->parent)
01040 tmp->parent->first_child=tmp;
01041 }
01042 else
01043 tmp->prev_sibling->next_sibling=tmp;
01044 return tmp;
01045 }
01046
01047 template <class T, class tree_node_allocator>
01048 template <class iter>
01049 iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
01050 {
01051 tree_node* tmp = alloc_.allocate(1,0);
01052 kp::constructor(&tmp->data, x);
01053 tmp->first_child=0;
01054 tmp->last_child=0;
01055
01056 tmp->parent=position.node->parent;
01057 tmp->prev_sibling=position.node;
01058 tmp->next_sibling=position.node->next_sibling;
01059 position.node->next_sibling=tmp;
01060
01061 if(tmp->next_sibling==0) {
01062 if(tmp->parent)
01063 tmp->parent->last_child=tmp;
01064 }
01065 else {
01066 tmp->next_sibling->prev_sibling=tmp;
01067 }
01068 return tmp;
01069 }
01070
01071 template <class T, class tree_node_allocator>
01072 template <class iter>
01073 iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base& subtree)
01074 {
01075
01076 iter it=insert(position, value_type());
01077
01078 return replace(it, subtree);
01079 }
01080
01081 template <class T, class tree_node_allocator>
01082 template <class iter>
01083 iter tree<T, tree_node_allocator>::insert_subtree_after(iter position, const iterator_base& subtree)
01084 {
01085
01086 iter it=insert_after(position, value_type());
01087
01088 return replace(it, subtree);
01089 }
01090
01091
01092
01093
01094
01095
01096
01097
01098
01099
01100
01101 template <class T, class tree_node_allocator>
01102 template <class iter>
01103 iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
01104 {
01105 kp::destructor(&position.node->data);
01106 kp::constructor(&position.node->data, x);
01107 return position;
01108 }
01109
01110 template <class T, class tree_node_allocator>
01111 template <class iter>
01112 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
01113 {
01114 assert(position.node!=head);
01115 tree_node *current_from=from.node;
01116 tree_node *start_from=from.node;
01117 tree_node *current_to =position.node;
01118
01119
01120
01121 erase_children(position);
01122
01123 tree_node* tmp = alloc_.allocate(1,0);
01124 kp::constructor(&tmp->data, (*from));
01125 tmp->first_child=0;
01126 tmp->last_child=0;
01127 if(current_to->prev_sibling==0) {
01128 if(current_to->parent!=0)
01129 current_to->parent->first_child=tmp;
01130 }
01131 else {
01132 current_to->prev_sibling->next_sibling=tmp;
01133 }
01134 tmp->prev_sibling=current_to->prev_sibling;
01135 if(current_to->next_sibling==0) {
01136 if(current_to->parent!=0)
01137 current_to->parent->last_child=tmp;
01138 }
01139 else {
01140 current_to->next_sibling->prev_sibling=tmp;
01141 }
01142 tmp->next_sibling=current_to->next_sibling;
01143 tmp->parent=current_to->parent;
01144 kp::destructor(¤t_to->data);
01145 alloc_.deallocate(current_to,1);
01146 current_to=tmp;
01147
01148
01149 tree_node *last=from.node->next_sibling;
01150
01151 pre_order_iterator toit=tmp;
01152
01153 do {
01154 assert(current_from!=0);
01155 if(current_from->first_child != 0) {
01156 current_from=current_from->first_child;
01157 toit=append_child(toit, current_from->data);
01158 }
01159 else {
01160 while(current_from->next_sibling==0 && current_from!=start_from) {
01161 current_from=current_from->parent;
01162 toit=parent(toit);
01163 assert(current_from!=0);
01164 }
01165 current_from=current_from->next_sibling;
01166 if(current_from!=last) {
01167 toit=append_child(parent(toit), current_from->data);
01168 }
01169 }
01170 } while(current_from!=last);
01171
01172 return current_to;
01173 }
01174
01175 template <class T, class tree_node_allocator>
01176 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::replace(
01177 sibling_iterator orig_begin,
01178 sibling_iterator orig_end,
01179 sibling_iterator new_begin,
01180 sibling_iterator new_end)
01181 {
01182 tree_node *orig_first=orig_begin.node;
01183 tree_node *new_first=new_begin.node;
01184 tree_node *orig_last=orig_first;
01185 while((++orig_begin)!=orig_end)
01186 orig_last=orig_last->next_sibling;
01187 tree_node *new_last=new_first;
01188 while((++new_begin)!=new_end)
01189 new_last=new_last->next_sibling;
01190
01191
01192 bool first=true;
01193 pre_order_iterator ret;
01194 while(1==1) {
01195 pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
01196 if(first) {
01197 ret=tt;
01198 first=false;
01199 }
01200 if(new_first==new_last)
01201 break;
01202 new_first=new_first->next_sibling;
01203 }
01204
01205
01206 bool last=false;
01207 tree_node *next=orig_first;
01208 while(1==1) {
01209 if(next==orig_last)
01210 last=true;
01211 next=next->next_sibling;
01212 erase((pre_order_iterator)orig_first);
01213 if(last)
01214 break;
01215 orig_first=next;
01216 }
01217 return ret;
01218 }
01219
01220 template <class T, class tree_node_allocator>
01221 template <typename iter>
01222 iter tree<T, tree_node_allocator>::flatten(iter position)
01223 {
01224 if(position.node->first_child==0)
01225 return position;
01226
01227 tree_node *tmp=position.node->first_child;
01228 while(tmp) {
01229 tmp->parent=position.node->parent;
01230 tmp=tmp->next_sibling;
01231 }
01232 if(position.node->next_sibling) {
01233 position.node->last_child->next_sibling=position.node->next_sibling;
01234 position.node->next_sibling->prev_sibling=position.node->last_child;
01235 }
01236 else {
01237 position.node->parent->last_child=position.node->last_child;
01238 }
01239 position.node->next_sibling=position.node->first_child;
01240 position.node->next_sibling->prev_sibling=position.node;
01241 position.node->first_child=0;
01242 position.node->last_child=0;
01243
01244 return position;
01245 }
01246
01247
01248 template <class T, class tree_node_allocator>
01249 template <typename iter>
01250 iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)
01251 {
01252 tree_node *first=begin.node;
01253 tree_node *last=first;
01254
01255 assert(first!=position.node);
01256
01257 if(begin==end) return begin;
01258
01259 while((++begin)!=end) {
01260 last=last->next_sibling;
01261 }
01262
01263 if(first->prev_sibling==0) {
01264 first->parent->first_child=last->next_sibling;
01265 }
01266 else {
01267 first->prev_sibling->next_sibling=last->next_sibling;
01268 }
01269 if(last->next_sibling==0) {
01270 last->parent->last_child=first->prev_sibling;
01271 }
01272 else {
01273 last->next_sibling->prev_sibling=first->prev_sibling;
01274 }
01275 if(position.node->first_child==0) {
01276 position.node->first_child=first;
01277 position.node->last_child=last;
01278 first->prev_sibling=0;
01279 }
01280 else {
01281 position.node->last_child->next_sibling=first;
01282 first->prev_sibling=position.node->last_child;
01283 position.node->last_child=last;
01284 }
01285 last->next_sibling=0;
01286
01287 tree_node *pos=first;
01288 while(1==1) {
01289 pos->parent=position.node;
01290 if(pos==last) break;
01291 pos=pos->next_sibling;
01292 }
01293
01294 return first;
01295 }
01296
01297 template <class T, class tree_node_allocator>
01298 template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
01299 {
01300 if(from.node->first_child==0) return position;
01301 return reparent(position, from.node->first_child, end(from));
01302 }
01303
01304 template <class T, class tree_node_allocator>
01305 template <typename iter> iter tree<T, tree_node_allocator>::wrap(iter position, const T& x)
01306 {
01307 assert(position.node!=0);
01308 sibling_iterator fr=position, to=position;
01309 ++to;
01310 iter ret = insert(position, x);
01311 reparent(ret, fr, to);
01312 return ret;
01313 }
01314
01315 template <class T, class tree_node_allocator>
01316 template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)
01317 {
01318 tree_node *dst=target.node;
01319 tree_node *src=source.node;
01320 assert(dst);
01321 assert(src);
01322
01323 if(dst==src) return source;
01324 if(dst->next_sibling)
01325 if(dst->next_sibling==src)
01326 return source;
01327
01328
01329 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01330 else src->parent->first_child=src->next_sibling;
01331 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01332 else src->parent->last_child=src->prev_sibling;
01333
01334
01335 if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
01336 else dst->parent->last_child=src;
01337 src->next_sibling=dst->next_sibling;
01338 dst->next_sibling=src;
01339 src->prev_sibling=dst;
01340 src->parent=dst->parent;
01341 return src;
01342 }
01343
01344 template <class T, class tree_node_allocator>
01345 template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
01346 {
01347 tree_node *dst=target.node;
01348 tree_node *src=source.node;
01349 assert(dst);
01350 assert(src);
01351
01352 if(dst==src) return source;
01353 if(dst->prev_sibling)
01354 if(dst->prev_sibling==src)
01355 return source;
01356
01357
01358 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01359 else src->parent->first_child=src->next_sibling;
01360 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01361 else src->parent->last_child=src->prev_sibling;
01362
01363
01364 if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
01365 else dst->parent->first_child=src;
01366 src->prev_sibling=dst->prev_sibling;
01367 dst->prev_sibling=src;
01368 src->next_sibling=dst;
01369 src->parent=dst->parent;
01370 return src;
01371 }
01372
01373
01374 template <class T, class tree_node_allocator>
01375 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::move_before(sibling_iterator target,
01376 sibling_iterator source)
01377 {
01378 tree_node *dst=target.node;
01379 tree_node *src=source.node;
01380 tree_node *dst_prev_sibling;
01381 if(dst==0) {
01382 dst_prev_sibling=target.parent_->last_child;
01383 assert(dst_prev_sibling);
01384 }
01385 else dst_prev_sibling=dst->prev_sibling;
01386 assert(src);
01387
01388 if(dst==src) return source;
01389 if(dst_prev_sibling)
01390 if(dst_prev_sibling==src)
01391 return source;
01392
01393
01394 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01395 else src->parent->first_child=src->next_sibling;
01396 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01397 else src->parent->last_child=src->prev_sibling;
01398
01399
01400 if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
01401 else target.parent_->first_child=src;
01402 src->prev_sibling=dst_prev_sibling;
01403 if(dst) {
01404 dst->prev_sibling=src;
01405 src->parent=dst->parent;
01406 }
01407 src->next_sibling=dst;
01408 return src;
01409 }
01410
01411 template <class T, class tree_node_allocator>
01412 template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
01413 {
01414 tree_node *dst=target.node;
01415 tree_node *src=source.node;
01416 assert(dst);
01417 assert(src);
01418
01419 if(dst==src) return source;
01420
01421
01422 tree_node *b_prev_sibling=dst->prev_sibling;
01423 tree_node *b_next_sibling=dst->next_sibling;
01424 tree_node *b_parent=dst->parent;
01425
01426
01427 erase(target);
01428
01429
01430 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01431 else src->parent->first_child=src->next_sibling;
01432 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01433 else src->parent->last_child=src->prev_sibling;
01434
01435
01436 if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
01437 else b_parent->first_child=src;
01438 if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
01439 else b_parent->last_child=src;
01440 src->prev_sibling=b_prev_sibling;
01441 src->next_sibling=b_next_sibling;
01442 src->parent=b_parent;
01443 return src;
01444 }
01445
01446 template <class T, class tree_node_allocator>
01447 void tree<T, tree_node_allocator>::merge(sibling_iterator to1, sibling_iterator to2,
01448 sibling_iterator from1, sibling_iterator from2,
01449 bool duplicate_leaves)
01450 {
01451 sibling_iterator fnd;
01452 while(from1!=from2) {
01453 if((fnd=std::find(to1, to2, (*from1))) != to2) {
01454 if(from1.begin()==from1.end()) {
01455 if(duplicate_leaves)
01456 append_child(parent(to1), (*from1));
01457 }
01458 else {
01459 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
01460 }
01461 }
01462 else {
01463 insert_subtree(to2, from1);
01464 }
01465 ++from1;
01466 }
01467 }
01468
01469
01470 template <class T, class tree_node_allocator>
01471 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
01472 {
01473 std::less<T> comp;
01474 sort(from, to, comp, deep);
01475 }
01476
01477 template <class T, class tree_node_allocator>
01478 template <class StrictWeakOrdering>
01479 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,
01480 StrictWeakOrdering comp, bool deep)
01481 {
01482 if(from==to) return;
01483
01484
01485
01486 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
01487 sibling_iterator it=from, it2=to;
01488 while(it != to) {
01489 nodes.insert(it.node);
01490 ++it;
01491 }
01492
01493 --it2;
01494
01495
01496 tree_node *prev=from.node->prev_sibling;
01497 tree_node *next=it2.node->next_sibling;
01498 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
01499 if(prev==0) {
01500 if((*nit)->parent!=0)
01501 (*nit)->parent->first_child=(*nit);
01502 }
01503 else prev->next_sibling=(*nit);
01504
01505 --eit;
01506 while(nit!=eit) {
01507 (*nit)->prev_sibling=prev;
01508 if(prev)
01509 prev->next_sibling=(*nit);
01510 prev=(*nit);
01511 ++nit;
01512 }
01513
01514 if(prev)
01515 prev->next_sibling=(*eit);
01516
01517
01518 (*eit)->next_sibling=next;
01519 (*eit)->prev_sibling=prev;
01520 if(next==0) {
01521 if((*eit)->parent!=0)
01522 (*eit)->parent->last_child=(*eit);
01523 }
01524 else next->prev_sibling=(*eit);
01525
01526 if(deep) {
01527 sibling_iterator bcs(*nodes.begin());
01528 sibling_iterator ecs(*eit);
01529 ++ecs;
01530 while(bcs!=ecs) {
01531 sort(begin(bcs), end(bcs), comp, deep);
01532 ++bcs;
01533 }
01534 }
01535 }
01536
01537 template <class T, class tree_node_allocator>
01538 template <typename iter>
01539 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
01540 {
01541 std::equal_to<T> comp;
01542 return equal(one_, two, three_, comp);
01543 }
01544
01545 template <class T, class tree_node_allocator>
01546 template <typename iter>
01547 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
01548 {
01549 std::equal_to<T> comp;
01550 return equal_subtree(one_, two_, comp);
01551 }
01552
01553 template <class T, class tree_node_allocator>
01554 template <typename iter, class BinaryPredicate>
01555 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
01556 {
01557 pre_order_iterator one(one_), three(three_);
01558
01559
01560
01561 while(one!=two && is_valid(three)) {
01562 if(!fun(*one,*three))
01563 return false;
01564 if(one.number_of_children()!=three.number_of_children())
01565 return false;
01566 ++one;
01567 ++three;
01568 }
01569 return true;
01570 }
01571
01572 template <class T, class tree_node_allocator>
01573 template <typename iter, class BinaryPredicate>
01574 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
01575 {
01576 pre_order_iterator one(one_), two(two_);
01577
01578 if(!fun(*one,*two)) return false;
01579 if(number_of_children(one)!=number_of_children(two)) return false;
01580 return equal(begin(one),end(one),begin(two),fun);
01581 }
01582
01583 template <class T, class tree_node_allocator>
01584 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
01585 {
01586 tree tmp;
01587 tmp.set_head(value_type());
01588 tmp.replace(tmp.begin(), tmp.end(), from, to);
01589 return tmp;
01590 }
01591
01592 template <class T, class tree_node_allocator>
01593 void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const
01594 {
01595 tmp.set_head(value_type());
01596 tmp.replace(tmp.begin(), tmp.end(), from, to);
01597 }
01598
01599 template <class T, class tree_node_allocator>
01600 int tree<T, tree_node_allocator>::size() const
01601 {
01602 int i=0;
01603 pre_order_iterator it=begin(), eit=end();
01604 while(it!=eit) {
01605 ++i;
01606 ++it;
01607 }
01608 return i;
01609 }
01610
01611 template <class T, class tree_node_allocator>
01612 int tree<T, tree_node_allocator>::size(const iterator_base& top) const
01613 {
01614 int i=0;
01615 pre_order_iterator it=top, eit=top;
01616 eit.skip_children();
01617 ++eit;
01618 while(it!=eit) {
01619 ++i;
01620 ++it;
01621 }
01622 return i;
01623 }
01624
01625 template <class T, class tree_node_allocator>
01626 bool tree<T, tree_node_allocator>::empty() const
01627 {
01628 pre_order_iterator it=begin(), eit=end();
01629 return (it==eit);
01630 }
01631
01632 template <class T, class tree_node_allocator>
01633 int tree<T, tree_node_allocator>::depth(const iterator_base& it) const
01634 {
01635 tree_node* pos=it.node;
01636 assert(pos!=0);
01637 int ret=0;
01638 while(pos->parent!=0) {
01639 pos=pos->parent;
01640 ++ret;
01641 }
01642 return ret;
01643 }
01644
01645 template <class T, class tree_node_allocator>
01646 int tree<T, tree_node_allocator>::max_depth() const
01647 {
01648 return max_depth(begin());
01649 }
01650
01651
01652 template <class T, class tree_node_allocator>
01653 int tree<T, tree_node_allocator>::max_depth(const iterator_base& pos) const
01654 {
01655 tree_node *tmp=pos.node;
01656 int curdepth=0, maxdepth=0;
01657 while(true) {
01658 while(tmp->first_child==0) {
01659 if(tmp==pos.node) return maxdepth;
01660 if(tmp->next_sibling==0) {
01661
01662 do {
01663 tmp=tmp->parent;
01664 if(tmp==0) return maxdepth;
01665 --curdepth;
01666 } while(tmp->next_sibling==0);
01667 }
01668 if(tmp==pos.node) return maxdepth;
01669 tmp=tmp->next_sibling;
01670 }
01671 tmp=tmp->first_child;
01672 ++curdepth;
01673 maxdepth=std::max(curdepth, maxdepth);
01674 }
01675 }
01676
01677 template <class T, class tree_node_allocator>
01678 unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it)
01679 {
01680 tree_node *pos=it.node->first_child;
01681 if(pos==0) return 0;
01682
01683 unsigned int ret=1;
01684
01685
01686
01687
01688 while((pos=pos->next_sibling))
01689 ++ret;
01690 return ret;
01691 }
01692
01693 template <class T, class tree_node_allocator>
01694 unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base& it) const
01695 {
01696 tree_node *pos=it.node;
01697 unsigned int ret=0;
01698
01699 while(pos->next_sibling &&
01700 pos->next_sibling!=head &&
01701 pos->next_sibling!=feet) {
01702 ++ret;
01703 pos=pos->next_sibling;
01704 }
01705
01706 pos=it.node;
01707 while(pos->prev_sibling &&
01708 pos->prev_sibling!=head &&
01709 pos->prev_sibling!=feet) {
01710 ++ret;
01711 pos=pos->prev_sibling;
01712 }
01713
01714 return ret;
01715 }
01716
01717 template <class T, class tree_node_allocator>
01718 void tree<T, tree_node_allocator>::swap(sibling_iterator it)
01719 {
01720 tree_node *nxt=it.node->next_sibling;
01721 if(nxt) {
01722 if(it.node->prev_sibling)
01723 it.node->prev_sibling->next_sibling=nxt;
01724 else
01725 it.node->parent->first_child=nxt;
01726 nxt->prev_sibling=it.node->prev_sibling;
01727 tree_node *nxtnxt=nxt->next_sibling;
01728 if(nxtnxt)
01729 nxtnxt->prev_sibling=it.node;
01730 else
01731 it.node->parent->last_child=it.node;
01732 nxt->next_sibling=it.node;
01733 it.node->prev_sibling=nxt;
01734 it.node->next_sibling=nxtnxt;
01735 }
01736 }
01737
01738 template <class T, class tree_node_allocator>
01739 void tree<T, tree_node_allocator>::swap(iterator one, iterator two)
01740 {
01741
01742 if(one.node->next_sibling==two.node) swap(one);
01743 else if(two.node->next_sibling==one.node) swap(two);
01744 else {
01745 tree_node *nxt1=one.node->next_sibling;
01746 tree_node *nxt2=two.node->next_sibling;
01747 tree_node *pre1=one.node->prev_sibling;
01748 tree_node *pre2=two.node->prev_sibling;
01749 tree_node *par1=one.node->parent;
01750 tree_node *par2=two.node->parent;
01751
01752
01753 one.node->parent=par2;
01754 one.node->next_sibling=nxt2;
01755 if(nxt2) nxt2->prev_sibling=one.node;
01756 else par2->last_child=one.node;
01757 one.node->prev_sibling=pre2;
01758 if(pre2) pre2->next_sibling=one.node;
01759 else par2->first_child=one.node;
01760
01761 two.node->parent=par1;
01762 two.node->next_sibling=nxt1;
01763 if(nxt1) nxt1->prev_sibling=two.node;
01764 else par1->last_child=two.node;
01765 two.node->prev_sibling=pre1;
01766 if(pre1) pre1->next_sibling=two.node;
01767 else par1->first_child=two.node;
01768 }
01769 }
01770
01771
01772
01773
01774
01775
01776
01777
01778
01779
01780
01781
01782
01783
01784
01785 template <class T, class tree_node_allocator>
01786 bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& begin,
01787 const iterator_base& end) const
01788 {
01789
01790 pre_order_iterator tmp=begin;
01791 while(tmp!=end) {
01792 if(tmp==it) return true;
01793 ++tmp;
01794 }
01795 return false;
01796 }
01797
01798 template <class T, class tree_node_allocator>
01799 bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
01800 {
01801 if(it.node==0 || it.node==feet || it.node==head) return false;
01802 else return true;
01803 }
01804
01805 template <class T, class tree_node_allocator>
01806 unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
01807 {
01808 unsigned int ind=0;
01809 if(it.node->parent==0) {
01810 while(it.node->prev_sibling!=head) {
01811 it.node=it.node->prev_sibling;
01812 ++ind;
01813 }
01814 }
01815 else {
01816 while(it.node->prev_sibling!=0) {
01817 it.node=it.node->prev_sibling;
01818 ++ind;
01819 }
01820 }
01821 return ind;
01822 }
01823
01824
01825 template <class T, class tree_node_allocator>
01826 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num) const
01827 {
01828 tree_node *tmp=it.node->first_child;
01829 while(num--) {
01830 assert(tmp!=0);
01831 tmp=tmp->next_sibling;
01832 }
01833 return tmp;
01834 }
01835
01836
01837
01838
01839
01840
01841 template <class T, class tree_node_allocator>
01842 tree<T, tree_node_allocator>::iterator_base::iterator_base()
01843 : node(0), skip_current_children_(false)
01844 {
01845 }
01846
01847 template <class T, class tree_node_allocator>
01848 tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
01849 : node(tn), skip_current_children_(false)
01850 {
01851 }
01852
01853 template <class T, class tree_node_allocator>
01854 T& tree<T, tree_node_allocator>::iterator_base::operator*() const
01855 {
01856 return node->data;
01857 }
01858
01859 template <class T, class tree_node_allocator>
01860 T* tree<T, tree_node_allocator>::iterator_base::operator->() const
01861 {
01862 return &(node->data);
01863 }
01864
01865 template <class T, class tree_node_allocator>
01866 bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const
01867 {
01868 if(other.node!=this->node) return true;
01869 else return false;
01870 }
01871
01872 template <class T, class tree_node_allocator>
01873 bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const
01874 {
01875 if(other.node==this->node) return true;
01876 else return false;
01877 }
01878
01879 template <class T, class tree_node_allocator>
01880 bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const
01881 {
01882 if(other.node!=this->node) return true;
01883 else return false;
01884 }
01885
01886 template <class T, class tree_node_allocator>
01887 bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const
01888 {
01889 if(other.node==this->node) return true;
01890 else return false;
01891 }
01892
01893 template <class T, class tree_node_allocator>
01894 bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator& other) const
01895 {
01896 if(other.node!=this->node) return true;
01897 else return false;
01898 }
01899
01900 template <class T, class tree_node_allocator>
01901 bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const
01902 {
01903 if(other.node==this->node) return true;
01904 else return false;
01905 }
01906
01907 template <class T, class tree_node_allocator>
01908 bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const leaf_iterator& other) const
01909 {
01910 if(other.node!=this->node) return true;
01911 else return false;
01912 }
01913
01914 template <class T, class tree_node_allocator>
01915 bool tree<T, tree_node_allocator>::leaf_iterator::operator==(const leaf_iterator& other) const
01916 {
01917 if(other.node==this->node) return true;
01918 else return false;
01919 }
01920
01921 template <class T, class tree_node_allocator>
01922 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin() const
01923 {
01924 if(node->first_child==0)
01925 return end();
01926
01927 sibling_iterator ret(node->first_child);
01928 ret.parent_=this->node;
01929 return ret;
01930 }
01931
01932 template <class T, class tree_node_allocator>
01933 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end() const
01934 {
01935 sibling_iterator ret(0);
01936 ret.parent_=node;
01937 return ret;
01938 }
01939
01940 template <class T, class tree_node_allocator>
01941 void tree<T, tree_node_allocator>::iterator_base::skip_children()
01942 {
01943 skip_current_children_=true;
01944 }
01945
01946 template <class T, class tree_node_allocator>
01947 unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const
01948 {
01949 tree_node *pos=node->first_child;
01950 if(pos==0) return 0;
01951
01952 unsigned int ret=1;
01953 while(pos!=node->last_child) {
01954 ++ret;
01955 pos=pos->next_sibling;
01956 }
01957 return ret;
01958 }
01959
01960
01961
01962
01963
01964 template <class T, class tree_node_allocator>
01965 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
01966 : iterator_base(0)
01967 {
01968 }
01969
01970 template <class T, class tree_node_allocator>
01971 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
01972 : iterator_base(tn)
01973 {
01974 }
01975
01976 template <class T, class tree_node_allocator>
01977 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const iterator_base &other)
01978 : iterator_base(other.node)
01979 {
01980 }
01981
01982 template <class T, class tree_node_allocator>
01983 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator& other)
01984 : iterator_base(other.node)
01985 {
01986 if(this->node==0) {
01987 if(other.range_last()!=0)
01988 this->node=other.range_last();
01989 else
01990 this->node=other.parent_;
01991 this->skip_children();
01992 ++(*this);
01993 }
01994 }
01995
01996 template <class T, class tree_node_allocator>
01997 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
01998 {
01999 assert(this->node!=0);
02000 if(!this->skip_current_children_ && this->node->first_child != 0) {
02001 this->node=this->node->first_child;
02002 }
02003 else {
02004 this->skip_current_children_=false;
02005 while(this->node->next_sibling==0) {
02006 this->node=this->node->parent;
02007 if(this->node==0)
02008 return *this;
02009 }
02010 this->node=this->node->next_sibling;
02011 }
02012 return *this;
02013 }
02014
02015 template <class T, class tree_node_allocator>
02016 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
02017 {
02018 assert(this->node!=0);
02019 if(this->node->prev_sibling) {
02020 this->node=this->node->prev_sibling;
02021 while(this->node->last_child)
02022 this->node=this->node->last_child;
02023 }
02024 else {
02025 this->node=this->node->parent;
02026 if(this->node==0)
02027 return *this;
02028 }
02029 return *this;
02030 }
02031
02032 template <class T, class tree_node_allocator>
02033 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int n)
02034 {
02035 pre_order_iterator copy = *this;
02036 ++(*this);
02037 return copy;
02038 }
02039
02040 template <class T, class tree_node_allocator>
02041 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int n)
02042 {
02043 pre_order_iterator copy = *this;
02044 --(*this);
02045 return copy;
02046 }
02047
02048 template <class T, class tree_node_allocator>
02049 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
02050 {
02051 while(num>0) {
02052 ++(*this);
02053 --num;
02054 }
02055 return (*this);
02056 }
02057
02058 template <class T, class tree_node_allocator>
02059 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
02060 {
02061 while(num>0) {
02062 --(*this);
02063 --num;
02064 }
02065 return (*this);
02066 }
02067
02068
02069
02070
02071
02072 template <class T, class tree_node_allocator>
02073 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
02074 : iterator_base(0)
02075 {
02076 }
02077
02078 template <class T, class tree_node_allocator>
02079 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
02080 : iterator_base(tn)
02081 {
02082 }
02083
02084 template <class T, class tree_node_allocator>
02085 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const iterator_base &other)
02086 : iterator_base(other.node)
02087 {
02088 }
02089
02090 template <class T, class tree_node_allocator>
02091 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const sibling_iterator& other)
02092 : iterator_base(other.node)
02093 {
02094 if(this->node==0) {
02095 if(other.range_last()!=0)
02096 this->node=other.range_last();
02097 else
02098 this->node=other.parent_;
02099 this->skip_children();
02100 ++(*this);
02101 }
02102 }
02103
02104 template <class T, class tree_node_allocator>
02105 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
02106 {
02107 assert(this->node!=0);
02108 if(this->node->next_sibling==0) {
02109 this->node=this->node->parent;
02110 this->skip_current_children_=false;
02111 }
02112 else {
02113 this->node=this->node->next_sibling;
02114 if(this->skip_current_children_) {
02115 this->skip_current_children_=false;
02116 }
02117 else {
02118 while(this->node->first_child)
02119 this->node=this->node->first_child;
02120 }
02121 }
02122 return *this;
02123 }
02124
02125 template <class T, class tree_node_allocator>
02126 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
02127 {
02128 assert(this->node!=0);
02129 if(this->skip_current_children_ || this->node->last_child==0) {
02130 this->skip_current_children_=false;
02131 while(this->node->prev_sibling==0)
02132 this->node=this->node->parent;
02133 this->node=this->node->prev_sibling;
02134 }
02135 else {
02136 this->node=this->node->last_child;
02137 }
02138 return *this;
02139 }
02140
02141 template <class T, class tree_node_allocator>
02142 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(int)
02143 {
02144 post_order_iterator copy = *this;
02145 ++(*this);
02146 return copy;
02147 }
02148
02149 template <class T, class tree_node_allocator>
02150 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(int)
02151 {
02152 post_order_iterator copy = *this;
02153 --(*this);
02154 return copy;
02155 }
02156
02157
02158 template <class T, class tree_node_allocator>
02159 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
02160 {
02161 while(num>0) {
02162 ++(*this);
02163 --num;
02164 }
02165 return (*this);
02166 }
02167
02168 template <class T, class tree_node_allocator>
02169 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
02170 {
02171 while(num>0) {
02172 --(*this);
02173 --num;
02174 }
02175 return (*this);
02176 }
02177
02178 template <class T, class tree_node_allocator>
02179 void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
02180 {
02181 assert(this->node!=0);
02182 while(this->node->first_child)
02183 this->node=this->node->first_child;
02184 }
02185
02186
02187
02188
02189 template <class T, class tree_node_allocator>
02190 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator()
02191 : iterator_base()
02192 {
02193 }
02194
02195 template <class T, class tree_node_allocator>
02196 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(tree_node *tn)
02197 : iterator_base(tn)
02198 {
02199 traversal_queue.push(tn);
02200 }
02201
02202 template <class T, class tree_node_allocator>
02203 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(const iterator_base& other)
02204 : iterator_base(other.node)
02205 {
02206 traversal_queue.push(other.node);
02207 }
02208
02209 template <class T, class tree_node_allocator>
02210 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator!=(const breadth_first_queued_iterator& other) const
02211 {
02212 if(other.node!=this->node) return true;
02213 else return false;
02214 }
02215
02216 template <class T, class tree_node_allocator>
02217 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator==(const breadth_first_queued_iterator& other) const
02218 {
02219 if(other.node==this->node) return true;
02220 else return false;
02221 }
02222
02223 template <class T, class tree_node_allocator>
02224 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++()
02225 {
02226 assert(this->node!=0);
02227
02228
02229 sibling_iterator sib=this->begin();
02230 while(sib!=this->end()) {
02231 traversal_queue.push(sib.node);
02232 ++sib;
02233 }
02234 traversal_queue.pop();
02235 if(traversal_queue.size()>0)
02236 this->node=traversal_queue.front();
02237 else
02238 this->node=0;
02239 return (*this);
02240 }
02241
02242 template <class T, class tree_node_allocator>
02243 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++(int n)
02244 {
02245 breadth_first_queued_iterator copy = *this;
02246 ++(*this);
02247 return copy;
02248 }
02249
02250 template <class T, class tree_node_allocator>
02251 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int num)
02252 {
02253 while(num>0) {
02254 ++(*this);
02255 --num;
02256 }
02257 return (*this);
02258 }
02259
02260
02261
02262
02263
02264 template <class T, class tree_node_allocator>
02265 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
02266 : iterator_base()
02267 {
02268 set_first_parent_();
02269 }
02270
02271 template <class T, class tree_node_allocator>
02272 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
02273 : iterator_base(tn)
02274 {
02275 set_first_parent_();
02276 }
02277
02278 template <class T, class tree_node_allocator>
02279 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const iterator_base& other)
02280 : iterator_base(other.node)
02281 {
02282 set_first_parent_();
02283 }
02284
02285 template <class T, class tree_node_allocator>
02286 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const sibling_iterator& other)
02287 : iterator_base(other.node), first_parent_(other.parent_)
02288 {
02289 find_leftmost_parent_();
02290 }
02291
02292 template <class T, class tree_node_allocator>
02293 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const fixed_depth_iterator& other)
02294 : iterator_base(other.node), first_parent_(other.first_parent_)
02295 {
02296 }
02297
02298 template <class T, class tree_node_allocator>
02299 bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator==(const fixed_depth_iterator& other) const
02300 {
02301 if(other.node==this->node && other.first_parent_==first_parent_) return true;
02302 else return false;
02303 }
02304
02305 template <class T, class tree_node_allocator>
02306 bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator!=(const fixed_depth_iterator& other) const
02307 {
02308 if(other.node!=this->node || other.first_parent_!=first_parent_) return true;
02309 else return false;
02310 }
02311
02312 template <class T, class tree_node_allocator>
02313 void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_()
02314 {
02315 return;
02316
02317 first_parent_=0;
02318 if(this->node==0) return;
02319 if(this->node->parent!=0)
02320 first_parent_=this->node->parent;
02321 if(first_parent_)
02322 find_leftmost_parent_();
02323 }
02324
02325 template <class T, class tree_node_allocator>
02326 void tree<T, tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_()
02327 {
02328 return;
02329 tree_node *tmppar=first_parent_;
02330 while(tmppar->prev_sibling) {
02331 tmppar=tmppar->prev_sibling;
02332 if(tmppar->first_child)
02333 first_parent_=tmppar;
02334 }
02335 }
02336
02337 template <class T, class tree_node_allocator>
02338 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()
02339 {
02340 assert(this->node!=0);
02341
02342 if(this->node->next_sibling) {
02343 this->node=this->node->next_sibling;
02344 }
02345 else {
02346 int relative_depth=0;
02347 upper:
02348 do {
02349 this->node=this->node->parent;
02350 if(this->node==0) return *this;
02351 --relative_depth;
02352 } while(this->node->next_sibling==0);
02353 lower:
02354 this->node=this->node->next_sibling;
02355 while(this->node->first_child==0) {
02356 if(this->node->next_sibling==0)
02357 goto upper;
02358 this->node=this->node->next_sibling;
02359 if(this->node==0) return *this;
02360 }
02361 while(relative_depth<0 && this->node->first_child!=0) {
02362 this->node=this->node->first_child;
02363 ++relative_depth;
02364 }
02365 if(relative_depth<0) {
02366 if(this->node->next_sibling==0) goto upper;
02367 else goto lower;
02368 }
02369 }
02370 return *this;
02371
02372
02373
02374
02375
02376
02377
02378
02379
02380
02381
02382
02383
02384
02385
02386
02387
02388
02389 return *this;
02390 }
02391
02392 template <class T, class tree_node_allocator>
02393 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()
02394 {
02395 assert(this->node!=0);
02396 if(this->node->prev_sibling!=0) {
02397 this->node=this->node->prev_sibling;
02398 assert(this->node!=0);
02399 if(this->node->parent==0 && this->node->prev_sibling==0)
02400 this->node=0;
02401 }
02402 else {
02403 tree_node *par=this->node->parent;
02404 do {
02405 par=par->prev_sibling;
02406 if(par==0) {
02407 this->node=0;
02408 return *this;
02409 }
02410 } while(par->last_child==0);
02411 this->node=par->last_child;
02412 }
02413 return *this;
02414 }
02415
02416 template <class T, class tree_node_allocator>
02417 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(int)
02418 {
02419 fixed_depth_iterator copy = *this;
02420 ++(*this);
02421 return copy;
02422 }
02423
02424 template <class T, class tree_node_allocator>
02425 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(int)
02426 {
02427 fixed_depth_iterator copy = *this;
02428 --(*this);
02429 return copy;
02430 }
02431
02432 template <class T, class tree_node_allocator>
02433 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)
02434 {
02435 while(num>0) {
02436 --(*this);
02437 --(num);
02438 }
02439 return (*this);
02440 }
02441
02442 template <class T, class tree_node_allocator>
02443 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)
02444 {
02445 while(num>0) {
02446 ++(*this);
02447 --(num);
02448 }
02449 return *this;
02450 }
02451
02452
02453
02454
02455
02456
02457 template <class T, class tree_node_allocator>
02458 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
02459 : iterator_base()
02460 {
02461 set_parent_();
02462 }
02463
02464 template <class T, class tree_node_allocator>
02465 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
02466 : iterator_base(tn)
02467 {
02468 set_parent_();
02469 }
02470
02471 template <class T, class tree_node_allocator>
02472 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const iterator_base& other)
02473 : iterator_base(other.node)
02474 {
02475 set_parent_();
02476 }
02477
02478 template <class T, class tree_node_allocator>
02479 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const sibling_iterator& other)
02480 : iterator_base(other), parent_(other.parent_)
02481 {
02482 }
02483
02484 template <class T, class tree_node_allocator>
02485 void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
02486 {
02487 parent_=0;
02488 if(this->node==0) return;
02489 if(this->node->parent!=0)
02490 parent_=this->node->parent;
02491 }
02492
02493 template <class T, class tree_node_allocator>
02494 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()
02495 {
02496 if(this->node)
02497 this->node=this->node->next_sibling;
02498 return *this;
02499 }
02500
02501 template <class T, class tree_node_allocator>
02502 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()
02503 {
02504 if(this->node) this->node=this->node->prev_sibling;
02505 else {
02506 assert(parent_);
02507 this->node=parent_->last_child;
02508 }
02509 return *this;
02510 }
02511
02512 template <class T, class tree_node_allocator>
02513 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(int)
02514 {
02515 sibling_iterator copy = *this;
02516 ++(*this);
02517 return copy;
02518 }
02519
02520 template <class T, class tree_node_allocator>
02521 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(int)
02522 {
02523 sibling_iterator copy = *this;
02524 --(*this);
02525 return copy;
02526 }
02527
02528 template <class T, class tree_node_allocator>
02529 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)
02530 {
02531 while(num>0) {
02532 ++(*this);
02533 --num;
02534 }
02535 return (*this);
02536 }
02537
02538 template <class T, class tree_node_allocator>
02539 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)
02540 {
02541 while(num>0) {
02542 --(*this);
02543 --num;
02544 }
02545 return (*this);
02546 }
02547
02548 template <class T, class tree_node_allocator>
02549 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first() const
02550 {
02551 tree_node *tmp=parent_->first_child;
02552 return tmp;
02553 }
02554
02555 template <class T, class tree_node_allocator>
02556 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last() const
02557 {
02558 return parent_->last_child;
02559 }
02560
02561
02562
02563 template <class T, class tree_node_allocator>
02564 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator()
02565 : iterator_base(0)
02566 {
02567 }
02568
02569 template <class T, class tree_node_allocator>
02570 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(tree_node *tn)
02571 : iterator_base(tn)
02572 {
02573 }
02574
02575 template <class T, class tree_node_allocator>
02576 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const iterator_base &other)
02577 : iterator_base(other.node)
02578 {
02579 }
02580
02581 template <class T, class tree_node_allocator>
02582 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const sibling_iterator& other)
02583 : iterator_base(other.node)
02584 {
02585 if(this->node==0) {
02586 if(other.range_last()!=0)
02587 this->node=other.range_last();
02588 else
02589 this->node=other.parent_;
02590 ++(*this);
02591 }
02592 }
02593
02594 template <class T, class tree_node_allocator>
02595 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator++()
02596 {
02597 assert(this->node!=0);
02598 while(this->node->next_sibling==0) {
02599 if (this->node->parent==0) return *this;
02600 this->node=this->node->parent;
02601 }
02602 this->node=this->node->next_sibling;
02603 while(this->node->first_child)
02604 this->node=this->node->first_child;
02605 return *this;
02606 }
02607
02608 template <class T, class tree_node_allocator>
02609 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator--()
02610 {
02611 assert(this->node!=0);
02612 while (this->node->prev_sibling==0) {
02613 if (this->node->parent==0) return *this;
02614 this->node=this->node->parent;
02615 }
02616 this->node=this->node->prev_sibling;
02617 while(this->node->last_child)
02618 this->node=this->node->last_child;
02619 return *this;
02620 }
02621
02622 template <class T, class tree_node_allocator>
02623 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator++(int)
02624 {
02625 leaf_iterator copy = *this;
02626 ++(*this);
02627 return copy;
02628 }
02629
02630 template <class T, class tree_node_allocator>
02631 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator--(int)
02632 {
02633 leaf_iterator copy = *this;
02634 --(*this);
02635 return copy;
02636 }
02637
02638
02639 template <class T, class tree_node_allocator>
02640 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator+=(unsigned int num)
02641 {
02642 while(num>0) {
02643 ++(*this);
02644 --num;
02645 }
02646 return (*this);
02647 }
02648
02649 template <class T, class tree_node_allocator>
02650 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator-=(unsigned int num)
02651 {
02652 while(num>0) {
02653 --(*this);
02654 --num;
02655 }
02656 return (*this);
02657 }
02658
02659 #endif
02660
02661
02662
02663