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