00001
00002
00003
00004
00005
00006
00007
00008
00009
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00058 #ifndef tree_hh_
00059 #define tree_hh_
00060
00061 #include <cassert>
00062 #include <memory>
00063 #include <stdexcept>
00064 #include <iterator>
00065 #include <set>
00066
00067
00068
00069
00070 namespace kp {
00071
00072 template <class T1, class T2>
00073 void constructor(T1* p, T2& val)
00074 {
00075 new ((void *) p) T1(val);
00076 }
00077
00078 template <class T1>
00079 void constructor(T1* p)
00080 {
00081 new ((void *) p) T1;
00082 }
00083
00084 template <class T1>
00085 void destructor(T1* p)
00086 {
00087 p->~T1();
00088 }
00089
00090 };
00091
00093 template<class T>
00094 class tree_node_ {
00095 public:
00096 tree_node_<T> *parent;
00097 tree_node_<T> *first_child, *last_child;
00098 tree_node_<T> *prev_sibling, *next_sibling;
00099 T data;
00100 };
00101
00102 template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
00103 class tree {
00104 protected:
00105 typedef tree_node_<T> tree_node;
00106 public:
00108 typedef T value_type;
00109
00110 class iterator_base;
00111 class pre_order_iterator;
00112 class post_order_iterator;
00113 class sibling_iterator;
00114
00115 tree();
00116 tree(const T&);
00117 tree(const iterator_base&);
00118 tree(const tree<T, tree_node_allocator>&);
00119 ~tree();
00120 void operator=(const tree<T, tree_node_allocator>&);
00121
00123 #ifdef __SGI_STL_PORT
00124 class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
00125 #else
00126 class iterator_base {
00127 #endif
00128 public:
00129 typedef T value_type;
00130 typedef T* pointer;
00131 typedef T& reference;
00132 typedef size_t size_type;
00133 typedef ptrdiff_t difference_type;
00134 typedef std::bidirectional_iterator_tag iterator_category;
00135
00136 iterator_base();
00137 iterator_base(tree_node *);
00138
00139 T& operator*() const;
00140 T* operator->() const;
00141
00143 void skip_children();
00145 unsigned int number_of_children() const;
00146
00147 sibling_iterator begin() const;
00148 sibling_iterator end() const;
00149
00150 tree_node *node;
00151 protected:
00152 bool skip_current_children_;
00153 };
00154
00156 class pre_order_iterator : public iterator_base {
00157 public:
00158 pre_order_iterator();
00159 pre_order_iterator(tree_node *);
00160 pre_order_iterator(const iterator_base&);
00161 pre_order_iterator(const sibling_iterator&);
00162
00163 bool operator==(const pre_order_iterator&) const;
00164 bool operator!=(const pre_order_iterator&) const;
00165 pre_order_iterator& operator++();
00166 pre_order_iterator& operator--();
00167 pre_order_iterator operator++(int);
00168 pre_order_iterator operator--(int);
00169 pre_order_iterator& operator+=(unsigned int);
00170 pre_order_iterator& operator-=(unsigned int);
00171 };
00172
00174 class post_order_iterator : public iterator_base {
00175 public:
00176 post_order_iterator();
00177 post_order_iterator(tree_node *);
00178 post_order_iterator(const iterator_base&);
00179 post_order_iterator(const sibling_iterator&);
00180
00181 bool operator==(const post_order_iterator&) const;
00182 bool operator!=(const post_order_iterator&) const;
00183 post_order_iterator& operator++();
00184 post_order_iterator& operator--();
00185 post_order_iterator operator++(int);
00186 post_order_iterator operator--(int);
00187 post_order_iterator& operator+=(unsigned int);
00188 post_order_iterator& operator-=(unsigned int);
00189
00191 void descend_all();
00192 };
00193
00195 typedef pre_order_iterator iterator;
00196
00198 class fixed_depth_iterator : public iterator_base {
00199 public:
00200 fixed_depth_iterator();
00201 fixed_depth_iterator(tree_node *);
00202 fixed_depth_iterator(const iterator_base&);
00203 fixed_depth_iterator(const sibling_iterator&);
00204 fixed_depth_iterator(const fixed_depth_iterator&);
00205
00206 bool operator==(const fixed_depth_iterator&) const;
00207 bool operator!=(const fixed_depth_iterator&) const;
00208 fixed_depth_iterator& operator++();
00209 fixed_depth_iterator& operator--();
00210 fixed_depth_iterator operator++(int);
00211 fixed_depth_iterator operator--(int);
00212 fixed_depth_iterator& operator+=(unsigned int);
00213 fixed_depth_iterator& operator-=(unsigned int);
00214
00215 tree_node *first_parent_;
00216 private:
00217 void set_first_parent_();
00218 void find_leftmost_parent_();
00219 };
00220
00222 class sibling_iterator : public iterator_base {
00223 public:
00224 sibling_iterator();
00225 sibling_iterator(tree_node *);
00226 sibling_iterator(const sibling_iterator&);
00227 sibling_iterator(const iterator_base&);
00228
00229 bool operator==(const sibling_iterator&) const;
00230 bool operator!=(const sibling_iterator&) const;
00231 sibling_iterator& operator++();
00232 sibling_iterator& operator--();
00233 sibling_iterator operator++(int);
00234 sibling_iterator operator--(int);
00235 sibling_iterator& operator+=(unsigned int);
00236 sibling_iterator& operator-=(unsigned int);
00237
00238 tree_node *range_first() const;
00239 tree_node *range_last() const;
00240 tree_node *parent_;
00241 private:
00242 void set_parent_();
00243 };
00244
00246 inline pre_order_iterator begin() const;
00248 inline pre_order_iterator end() const;
00250 post_order_iterator begin_post() const;
00252 post_order_iterator end_post() const;
00254 fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
00256 fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
00258 sibling_iterator begin(const iterator_base&) const;
00260 sibling_iterator end(const iterator_base&) const;
00261
00263 template<typename iter> iter parent(iter) const;
00265 template<typename iter> iter previous_sibling(iter) const;
00267 template<typename iter> iter next_sibling(iter) const;
00269 template<typename iter> iter next_at_same_depth(iter) const;
00270
00272 void clear();
00274 template<typename iter> iter erase(iter);
00276 void erase_children(const iterator_base&);
00277
00279 template<typename iter> iter append_child(iter position);
00281 template<typename iter> iter append_child(iter position, const T& x);
00283 template<typename iter> iter append_child(iter position, iter other_position);
00285 template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
00286
00288 pre_order_iterator set_head(const T& x);
00290 template<typename iter> iter insert(iter position, const T& x);
00292 sibling_iterator insert(sibling_iterator position, const T& x);
00294 template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
00296 template<typename iter> iter insert_after(iter position, const T& x);
00297
00299 template<typename iter> iter replace(iter position, const T& x);
00301 template<typename iter> iter replace(iter position, const iterator_base& from);
00303 sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
00304 sibling_iterator new_begin, sibling_iterator new_end);
00305
00307 template<typename iter> iter flatten(iter position);
00309 template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
00311 template<typename iter> iter reparent(iter position, iter from);
00312
00314 template<typename iter> iter move_after(iter target, iter source);
00316 template<typename iter> iter move_before(iter target, iter source);
00318 template<typename iter> iter move_ontop(iter target, iter source);
00319
00321 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
00322 bool duplicate_leaves=false);
00324 void sort(sibling_iterator from, sibling_iterator to, bool deep=false);
00325 template<class StrictWeakOrdering>
00326 void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);
00328 template<typename iter>
00329 bool equal(const iter& one, const iter& two, const iter& three) const;
00330 template<typename iter, class BinaryPredicate>
00331 bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
00332 template<typename iter>
00333 bool equal_subtree(const iter& one, const iter& two) const;
00334 template<typename iter, class BinaryPredicate>
00335 bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
00337 tree subtree(sibling_iterator from, sibling_iterator to) const;
00338 void subtree(tree&, sibling_iterator from, sibling_iterator to) const;
00340 void swap(sibling_iterator it);
00341
00343 int size() const;
00345 bool empty() const;
00347 int depth(const iterator_base&) const;
00349 unsigned int number_of_children(const iterator_base&) const;
00351 unsigned int number_of_siblings(const iterator_base&) const;
00353 bool is_in_subtree(const iterator_base& position, const iterator_base& begin,
00354 const iterator_base& end) const;
00356 bool is_valid(const iterator_base&) const;
00357
00359 unsigned int index(sibling_iterator it) const;
00361 sibling_iterator child(const iterator_base& position, unsigned int) const;
00362
00364 class iterator_base_less {
00365 public:
00366 bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
00367 const typename tree<T, tree_node_allocator>::iterator_base& two) const
00368 {
00369 return one.node < two.node;
00370 }
00371 };
00372 tree_node *head, *feet;
00373 private:
00374 tree_node_allocator alloc_;
00375 void head_initialise_();
00376 void copy_(const tree<T, tree_node_allocator>& other);
00377
00379 template<class StrictWeakOrdering>
00380 class compare_nodes {
00381 public:
00382 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
00383
00384 bool operator()(const tree_node *a, const tree_node *b)
00385 {
00386 static StrictWeakOrdering comp;
00387 return comp(a->data, b->data);
00388 }
00389 private:
00390 StrictWeakOrdering comp_;
00391 };
00392 };
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414 template <class T, class tree_node_allocator>
00415 bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
00416 const typename tree<T, tree_node_allocator>::iterator_base& two)
00417 {
00418 if(one.node > two.node) return true;
00419 return false;
00420 }
00421
00422
00423
00424
00425
00426 template <class T, class tree_node_allocator>
00427 tree<T, tree_node_allocator>::tree()
00428 {
00429 head_initialise_();
00430 }
00431
00432 template <class T, class tree_node_allocator>
00433 tree<T, tree_node_allocator>::tree(const T& x)
00434 {
00435 head_initialise_();
00436 set_head(x);
00437 }
00438
00439 template <class T, class tree_node_allocator>
00440 tree<T, tree_node_allocator>::tree(const iterator_base& other)
00441 {
00442 head_initialise_();
00443 set_head((*other));
00444 replace(begin(), other);
00445 }
00446
00447 template <class T, class tree_node_allocator>
00448 tree<T, tree_node_allocator>::~tree()
00449 {
00450 clear();
00451 alloc_.deallocate(head,1);
00452 alloc_.deallocate(feet,1);
00453 }
00454
00455 template <class T, class tree_node_allocator>
00456 void tree<T, tree_node_allocator>::head_initialise_()
00457 {
00458 head = alloc_.allocate(1,0);
00459 feet = alloc_.allocate(1,0);
00460
00461 head->parent=0;
00462 head->first_child=0;
00463 head->last_child=0;
00464 head->prev_sibling=0;
00465 head->next_sibling=feet;
00466
00467 feet->parent=0;
00468 feet->first_child=0;
00469 feet->last_child=0;
00470 feet->prev_sibling=head;
00471 feet->next_sibling=0;
00472 }
00473
00474 template <class T, class tree_node_allocator>
00475 void tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)
00476 {
00477 copy_(other);
00478 }
00479
00480 template <class T, class tree_node_allocator>
00481 tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
00482 {
00483 head_initialise_();
00484 copy_(other);
00485 }
00486
00487 template <class T, class tree_node_allocator>
00488 void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other)
00489 {
00490 clear();
00491 pre_order_iterator it=other.begin(), to=begin();
00492 while(it!=other.end()) {
00493 to=insert(to, (*it));
00494 it.skip_children();
00495 ++it;
00496 }
00497 to=begin();
00498 it=other.begin();
00499 while(it!=other.end()) {
00500 to=replace(to, it);
00501 to.skip_children();
00502 it.skip_children();
00503 ++to;
00504 ++it;
00505 }
00506 }
00507
00508 template <class T, class tree_node_allocator>
00509 void tree<T, tree_node_allocator>::clear()
00510 {
00511 if(head)
00512 while(head->next_sibling!=feet)
00513 erase(pre_order_iterator(head->next_sibling));
00514 }
00515
00516 template<class T, class tree_node_allocator>
00517 void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
00518 {
00519 tree_node *cur=it.node->first_child;
00520 tree_node *prev=0;
00521
00522 while(cur!=0) {
00523 prev=cur;
00524 cur=cur->next_sibling;
00525 erase_children(pre_order_iterator(prev));
00526 kp::destructor(&prev->data);
00527 alloc_.deallocate(prev,1);
00528 }
00529 it.node->first_child=0;
00530 it.node->last_child=0;
00531 }
00532
00533 template<class T, class tree_node_allocator>
00534 template<class iter>
00535 iter tree<T, tree_node_allocator>::erase(iter it)
00536 {
00537 tree_node *cur=it.node;
00538 assert(cur!=head);
00539 iter ret=it;
00540 ret.skip_children();
00541 ++ret;
00542 erase_children(it);
00543 if(cur->prev_sibling==0) {
00544 cur->parent->first_child=cur->next_sibling;
00545 }
00546 else {
00547 cur->prev_sibling->next_sibling=cur->next_sibling;
00548 }
00549 if(cur->next_sibling==0) {
00550 cur->parent->last_child=cur->prev_sibling;
00551 }
00552 else {
00553 cur->next_sibling->prev_sibling=cur->prev_sibling;
00554 }
00555
00556 kp::destructor(&cur->data);
00557 alloc_.deallocate(cur,1);
00558 return ret;
00559 }
00560
00561 template <class T, class tree_node_allocator>
00562 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin() const
00563 {
00564 return pre_order_iterator(head->next_sibling);
00565 }
00566
00567 template <class T, class tree_node_allocator>
00568 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const
00569 {
00570 return pre_order_iterator(feet);
00571 }
00572
00573 template <class T, class tree_node_allocator>
00574 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post() const
00575 {
00576 tree_node *tmp=head->next_sibling;
00577 if(tmp!=feet) {
00578 while(tmp->first_child)
00579 tmp=tmp->first_child;
00580 }
00581 return post_order_iterator(tmp);
00582 }
00583
00584 template <class T, class tree_node_allocator>
00585 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post() const
00586 {
00587 return post_order_iterator(feet);
00588 }
00589
00590 template <class T, class tree_node_allocator>
00591 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp) const
00592 {
00593 tree_node *tmp=pos.node;
00594 unsigned int curdepth=0;
00595 while(curdepth<dp) {
00596 while(tmp->first_child==0) {
00597 tmp=tmp->next_sibling;
00598 if(tmp==0)
00599 throw std::range_error("tree: begin_fixed out of range");
00600 }
00601 tmp=tmp->first_child;
00602 ++curdepth;
00603 }
00604 return tmp;
00605 }
00606
00607 template <class T, class tree_node_allocator>
00608 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const
00609 {
00610 assert(1==0);
00611 tree_node *tmp=pos.node;
00612 unsigned int curdepth=1;
00613 while(curdepth<dp) {
00614 while(tmp->first_child==0) {
00615 tmp=tmp->next_sibling;
00616 if(tmp==0)
00617 throw std::range_error("tree: end_fixed out of range");
00618 }
00619 tmp=tmp->first_child;
00620 ++curdepth;
00621 }
00622 return tmp;
00623 }
00624
00625 template <class T, class tree_node_allocator>
00626 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(const iterator_base& pos) const
00627 {
00628 if(pos.node->first_child==0) {
00629 return end(pos);
00630 }
00631 return pos.node->first_child;
00632 }
00633
00634 template <class T, class tree_node_allocator>
00635 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(const iterator_base& pos) const
00636 {
00637 sibling_iterator ret(0);
00638 ret.parent_=pos.node;
00639 return ret;
00640 }
00641
00642 template <class T, class tree_node_allocator>
00643 template <typename iter>
00644 iter tree<T, tree_node_allocator>::parent(iter position) const
00645 {
00646 assert(position.node!=0);
00647 return iter(position.node->parent);
00648 }
00649
00650 template <class T, class tree_node_allocator>
00651 template <typename iter>
00652 iter tree<T, tree_node_allocator>::previous_sibling(iter position) const
00653 {
00654 assert(position.node!=0);
00655 iter ret(position);
00656 ret.node=position.node->prev_sibling;
00657 return ret;
00658 }
00659
00660 template <class T, class tree_node_allocator>
00661 template <typename iter>
00662 iter tree<T, tree_node_allocator>::next_sibling(iter position) const
00663 {
00664 assert(position.node!=0);
00665 iter ret(position);
00666 ret.node=position.node->next_sibling;
00667 return ret;
00668 }
00669
00670 template <class T, class tree_node_allocator>
00671 template <typename iter>
00672 iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const
00673 {
00674 assert(position.node!=0);
00675 iter ret(position);
00676
00677 if(position.node->next_sibling) {
00678 ret.node=position.node->next_sibling;
00679 }
00680 else {
00681 int relative_depth=0;
00682 upper:
00683 do {
00684 ret.node=ret.node->parent;
00685 if(ret.node==0) return ret;
00686 --relative_depth;
00687 } while(ret.node->next_sibling==0);
00688 lower:
00689 ret.node=ret.node->next_sibling;
00690 while(ret.node->first_child==0) {
00691 if(ret.node->next_sibling==0)
00692 goto upper;
00693 ret.node=ret.node->next_sibling;
00694 if(ret.node==0) return ret;
00695 }
00696 while(relative_depth<0 && ret.node->first_child!=0) {
00697 ret.node=ret.node->first_child;
00698 ++relative_depth;
00699 }
00700 if(relative_depth<0) {
00701 if(ret.node->next_sibling==0) goto upper;
00702 else goto lower;
00703 }
00704 }
00705 return ret;
00706 }
00707
00708 template <class T, class tree_node_allocator>
00709 template <typename iter>
00710 iter tree<T, tree_node_allocator>::append_child(iter position)
00711 {
00712 assert(position.node!=head);
00713
00714 tree_node* tmp = alloc_.allocate(1,0);
00715 kp::constructor(&tmp->data);
00716 tmp->first_child=0;
00717 tmp->last_child=0;
00718
00719 tmp->parent=position.node;
00720 if(position.node->last_child!=0) {
00721 position.node->last_child->next_sibling=tmp;
00722 }
00723 else {
00724 position.node->first_child=tmp;
00725 }
00726 tmp->prev_sibling=position.node->last_child;
00727 position.node->last_child=tmp;
00728 tmp->next_sibling=0;
00729 return tmp;
00730 }
00731
00732 template <class T, class tree_node_allocator>
00733 template <class iter>
00734 iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
00735 {
00736
00737
00738
00739
00740 assert(position.node!=head);
00741
00742 tree_node* tmp = alloc_.allocate(1,0);
00743 kp::constructor(&tmp->data, x);
00744 tmp->first_child=0;
00745 tmp->last_child=0;
00746
00747 tmp->parent=position.node;
00748 if(position.node->last_child!=0) {
00749 position.node->last_child->next_sibling=tmp;
00750 }
00751 else {
00752 position.node->first_child=tmp;
00753 }
00754 tmp->prev_sibling=position.node->last_child;
00755 position.node->last_child=tmp;
00756 tmp->next_sibling=0;
00757 return tmp;
00758 }
00759
00760 template <class T, class tree_node_allocator>
00761 template <class iter>
00762 iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
00763 {
00764 assert(position.node!=head);
00765
00766 sibling_iterator aargh=append_child(position, value_type());
00767 return replace(aargh, other);
00768 }
00769
00770 template <class T, class tree_node_allocator>
00771 template <class iter>
00772 iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)
00773 {
00774 iter ret=from;
00775
00776 while(from!=to) {
00777 insert_subtree(position.end(), from);
00778 ++from;
00779 }
00780 return ret;
00781 }
00782
00783 template <class T, class tree_node_allocator>
00784 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(const T& x)
00785 {
00786 assert(head->next_sibling==feet);
00787 return insert(iterator(feet), x);
00788 }
00789
00790 template <class T, class tree_node_allocator>
00791 template <class iter>
00792 iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
00793 {
00794 if(position.node==0) {
00795 position.node=feet;
00796
00797 }
00798 tree_node* tmp = alloc_.allocate(1,0);
00799 kp::constructor(&tmp->data, x);
00800 tmp->first_child=0;
00801 tmp->last_child=0;
00802
00803 tmp->parent=position.node->parent;
00804 tmp->next_sibling=position.node;
00805 tmp->prev_sibling=position.node->prev_sibling;
00806 position.node->prev_sibling=tmp;
00807
00808 if(tmp->prev_sibling==0) {
00809 if(tmp->parent)
00810 tmp->parent->first_child=tmp;
00811 }
00812 else
00813 tmp->prev_sibling->next_sibling=tmp;
00814 return tmp;
00815 }
00816
00817 template <class T, class tree_node_allocator>
00818 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::insert(sibling_iterator position, const T& x)
00819 {
00820 tree_node* tmp = alloc_.allocate(1,0);
00821 kp::constructor(&tmp->data, x);
00822 tmp->first_child=0;
00823 tmp->last_child=0;
00824
00825 tmp->next_sibling=position.node;
00826 if(position.node==0) {
00827 tmp->parent=position.parent_;
00828 tmp->prev_sibling=position.range_last();
00829 tmp->parent->last_child=tmp;
00830 }
00831 else {
00832 tmp->parent=position.node->parent;
00833 tmp->prev_sibling=position.node->prev_sibling;
00834 position.node->prev_sibling=tmp;
00835 }
00836
00837 if(tmp->prev_sibling==0) {
00838 if(tmp->parent)
00839 tmp->parent->first_child=tmp;
00840 }
00841 else
00842 tmp->prev_sibling->next_sibling=tmp;
00843 return tmp;
00844 }
00845
00846 template <class T, class tree_node_allocator>
00847 template <class iter>
00848 iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
00849 {
00850 tree_node* tmp = alloc_.allocate(1,0);
00851 kp::constructor(&tmp->data, x);
00852 tmp->first_child=0;
00853 tmp->last_child=0;
00854
00855 tmp->parent=position.node->parent;
00856 tmp->prev_sibling=position.node;
00857 tmp->next_sibling=position.node->next_sibling;
00858 position.node->next_sibling=tmp;
00859
00860 if(tmp->next_sibling==0) {
00861 if(tmp->parent)
00862 tmp->parent->last_child=tmp;
00863 }
00864 else {
00865 tmp->next_sibling->prev_sibling=tmp;
00866 }
00867 return tmp;
00868 }
00869
00870 template <class T, class tree_node_allocator>
00871 template <class iter>
00872 iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base& subtree)
00873 {
00874
00875 iter it=insert(position, value_type());
00876
00877 return replace(it, subtree);
00878 }
00879
00880
00881
00882
00883
00884
00885
00886
00887
00888
00889
00890 template <class T, class tree_node_allocator>
00891 template <class iter>
00892 iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
00893 {
00894 kp::destructor(&position.node->data);
00895 kp::constructor(&position.node->data, x);
00896 return position;
00897 }
00898
00899 template <class T, class tree_node_allocator>
00900 template <class iter>
00901 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
00902 {
00903 assert(position.node!=head);
00904 tree_node *current_from=from.node;
00905 tree_node *start_from=from.node;
00906 tree_node *current_to =position.node;
00907
00908
00909 erase_children(position);
00910 tree_node* tmp = alloc_.allocate(1,0);
00911 kp::constructor(&tmp->data, (*from));
00912 tmp->first_child=0;
00913 tmp->last_child=0;
00914 if(current_to->prev_sibling==0) {
00915 current_to->parent->first_child=tmp;
00916 }
00917 else {
00918 current_to->prev_sibling->next_sibling=tmp;
00919 }
00920 tmp->prev_sibling=current_to->prev_sibling;
00921 if(current_to->next_sibling==0) {
00922 current_to->parent->last_child=tmp;
00923 }
00924 else {
00925 current_to->next_sibling->prev_sibling=tmp;
00926 }
00927 tmp->next_sibling=current_to->next_sibling;
00928 tmp->parent=current_to->parent;
00929 kp::destructor(¤t_to->data);
00930 alloc_.deallocate(current_to,1);
00931 current_to=tmp;
00932
00933
00934 tree_node *last=from.node->next_sibling;
00935
00936 pre_order_iterator toit=tmp;
00937
00938 do {
00939 assert(current_from!=0);
00940 if(current_from->first_child != 0) {
00941 current_from=current_from->first_child;
00942 toit=append_child(toit, current_from->data);
00943 }
00944 else {
00945 while(current_from->next_sibling==0 && current_from!=start_from) {
00946 current_from=current_from->parent;
00947 toit=parent(toit);
00948 assert(current_from!=0);
00949 }
00950 current_from=current_from->next_sibling;
00951 if(current_from!=last) {
00952 toit=append_child(parent(toit), current_from->data);
00953 }
00954 }
00955 } while(current_from!=last);
00956
00957 return current_to;
00958 }
00959
00960 template <class T, class tree_node_allocator>
00961 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::replace(
00962 sibling_iterator orig_begin,
00963 sibling_iterator orig_end,
00964 sibling_iterator new_begin,
00965 sibling_iterator new_end)
00966 {
00967 tree_node *orig_first=orig_begin.node;
00968 tree_node *new_first=new_begin.node;
00969 tree_node *orig_last=orig_first;
00970 while((++orig_begin)!=orig_end)
00971 orig_last=orig_last->next_sibling;
00972 tree_node *new_last=new_first;
00973 while((++new_begin)!=new_end)
00974 new_last=new_last->next_sibling;
00975
00976
00977 bool first=true;
00978 pre_order_iterator ret;
00979 while(1==1) {
00980 pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
00981 if(first) {
00982 ret=tt;
00983 first=false;
00984 }
00985 if(new_first==new_last)
00986 break;
00987 new_first=new_first->next_sibling;
00988 }
00989
00990
00991 bool last=false;
00992 tree_node *next=orig_first;
00993 while(1==1) {
00994 if(next==orig_last)
00995 last=true;
00996 next=next->next_sibling;
00997 erase((pre_order_iterator)orig_first);
00998 if(last)
00999 break;
01000 orig_first=next;
01001 }
01002 return ret;
01003 }
01004
01005 template <class T, class tree_node_allocator>
01006 template <typename iter>
01007 iter tree<T, tree_node_allocator>::flatten(iter position)
01008 {
01009 if(position.node->first_child==0)
01010 return position;
01011
01012 tree_node *tmp=position.node->first_child;
01013 while(tmp) {
01014 tmp->parent=position.node->parent;
01015 tmp=tmp->next_sibling;
01016 }
01017 if(position.node->next_sibling) {
01018 position.node->last_child->next_sibling=position.node->next_sibling;
01019 position.node->next_sibling->prev_sibling=position.node->last_child;
01020 }
01021 else {
01022 position.node->parent->last_child=position.node->last_child;
01023 }
01024 position.node->next_sibling=position.node->first_child;
01025 position.node->next_sibling->prev_sibling=position.node;
01026 position.node->first_child=0;
01027 position.node->last_child=0;
01028
01029 return position;
01030 }
01031
01032
01033 template <class T, class tree_node_allocator>
01034 template <typename iter>
01035 iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)
01036 {
01037 tree_node *first=begin.node;
01038 tree_node *last=first;
01039 if(begin==end) return begin;
01040
01041 while((++begin)!=end) {
01042 last=last->next_sibling;
01043 }
01044
01045 if(first->prev_sibling==0) {
01046 first->parent->first_child=last->next_sibling;
01047 }
01048 else {
01049 first->prev_sibling->next_sibling=last->next_sibling;
01050 }
01051 if(last->next_sibling==0) {
01052 last->parent->last_child=first->prev_sibling;
01053 }
01054 else {
01055 last->next_sibling->prev_sibling=first->prev_sibling;
01056 }
01057 if(position.node->first_child==0) {
01058 position.node->first_child=first;
01059 position.node->last_child=last;
01060 first->prev_sibling=0;
01061 }
01062 else {
01063 position.node->last_child->next_sibling=first;
01064 first->prev_sibling=position.node->last_child;
01065 position.node->last_child=last;
01066 }
01067 last->next_sibling=0;
01068
01069 tree_node *pos=first;
01070 while(1==1) {
01071 pos->parent=position.node;
01072 if(pos==last) break;
01073 pos=pos->next_sibling;
01074 }
01075
01076 return first;
01077 }
01078
01079 template <class T, class tree_node_allocator>
01080 template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
01081 {
01082 if(from.node->first_child==0) return position;
01083 return reparent(position, from.node->first_child, end(from));
01084 }
01085
01086 template <class T, class tree_node_allocator>
01087 template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)
01088 {
01089 tree_node *dst=target.node;
01090 tree_node *src=source.node;
01091 assert(dst);
01092 assert(src);
01093
01094 if(dst==src) return source;
01095
01096
01097 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01098 else src->parent->first_child=src->next_sibling;
01099 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01100 else src->parent->last_child=src->prev_sibling;
01101
01102
01103 if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
01104 else dst->parent->last_child=src;
01105 src->next_sibling=dst->next_sibling;
01106 dst->next_sibling=src;
01107 src->prev_sibling=dst;
01108 src->parent=dst->parent;
01109 return src;
01110 }
01111
01112
01113 template <class T, class tree_node_allocator>
01114 template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
01115 {
01116 tree_node *dst=target.node;
01117 tree_node *src=source.node;
01118 assert(dst);
01119 assert(src);
01120
01121 if(dst==src) return source;
01122
01123
01124 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01125 else src->parent->first_child=src->next_sibling;
01126 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01127 else src->parent->last_child=src->prev_sibling;
01128
01129
01130 if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
01131 else dst->parent->first_child=src;
01132 src->prev_sibling=dst->prev_sibling;
01133 dst->prev_sibling=src;
01134 src->next_sibling=dst;
01135 src->parent=dst->parent;
01136 return src;
01137 }
01138
01139 template <class T, class tree_node_allocator>
01140 template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
01141 {
01142 tree_node *dst=target.node;
01143 tree_node *src=source.node;
01144 assert(dst);
01145 assert(src);
01146
01147 if(dst==src) return source;
01148
01149
01150 tree_node *b_prev_sibling=dst->prev_sibling;
01151 tree_node *b_next_sibling=dst->next_sibling;
01152 tree_node *b_parent=dst->parent;
01153
01154
01155 erase(target);
01156
01157
01158 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
01159 else src->parent->first_child=src->next_sibling;
01160 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
01161 else src->parent->last_child=src->prev_sibling;
01162
01163
01164 if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
01165 else b_parent->first_child=src;
01166 if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
01167 else b_parent->last_child=src;
01168 src->prev_sibling=b_prev_sibling;
01169 src->next_sibling=b_next_sibling;
01170 src->parent=b_parent;
01171 return src;
01172 }
01173
01174 template <class T, class tree_node_allocator>
01175 void tree<T, tree_node_allocator>::merge(sibling_iterator to1, sibling_iterator to2,
01176 sibling_iterator from1, sibling_iterator from2,
01177 bool duplicate_leaves)
01178 {
01179 sibling_iterator fnd;
01180 while(from1!=from2) {
01181 if((fnd=std::find(to1, to2, (*from1))) != to2) {
01182 if(from1.begin()==from1.end()) {
01183 if(duplicate_leaves)
01184 append_child(parent(to1), (*from1));
01185 }
01186 else {
01187 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
01188 }
01189 }
01190 else {
01191 insert_subtree(to2, from1);
01192 }
01193 ++from1;
01194 }
01195 }
01196
01197
01198 template <class T, class tree_node_allocator>
01199 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
01200 {
01201 std::less<T> comp;
01202 sort(from, to, comp, deep);
01203 }
01204
01205 template <class T, class tree_node_allocator>
01206 template <class StrictWeakOrdering>
01207 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,
01208 StrictWeakOrdering comp, bool deep)
01209 {
01210 if(from==to) return;
01211
01212
01213
01214 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
01215 sibling_iterator it=from, it2=to;
01216 while(it != to) {
01217 nodes.insert(it.node);
01218 ++it;
01219 }
01220
01221 --it2;
01222
01223
01224 tree_node *prev=from.node->prev_sibling;
01225 tree_node *next=it2.node->next_sibling;
01226 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
01227 if(prev==0) {
01228 if((*nit)->parent!=0)
01229 (*nit)->parent->first_child=(*nit);
01230 }
01231 else prev->next_sibling=(*nit);
01232
01233 --eit;
01234 while(nit!=eit) {
01235 (*nit)->prev_sibling=prev;
01236 if(prev)
01237 prev->next_sibling=(*nit);
01238 prev=(*nit);
01239 ++nit;
01240 }
01241
01242 if(prev)
01243 prev->next_sibling=(*eit);
01244
01245
01246 (*eit)->next_sibling=next;
01247 (*eit)->prev_sibling=prev;
01248 if(next==0) {
01249 if((*eit)->parent!=0)
01250 (*eit)->parent->last_child=(*eit);
01251 }
01252 else next->prev_sibling=(*eit);
01253
01254 if(deep) {
01255 sibling_iterator bcs(*nodes.begin());
01256 sibling_iterator ecs(*eit);
01257 ++ecs;
01258 while(bcs!=ecs) {
01259 sort(begin(bcs), end(bcs), comp, deep);
01260 ++bcs;
01261 }
01262 }
01263 }
01264
01265 template <class T, class tree_node_allocator>
01266 template <typename iter>
01267 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
01268 {
01269 std::equal_to<T> comp;
01270 return equal(one_, two, three_, comp);
01271 }
01272
01273 template <class T, class tree_node_allocator>
01274 template <typename iter>
01275 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
01276 {
01277 std::equal_to<T> comp;
01278 return equal_subtree(one_, two_, comp);
01279 }
01280
01281 template <class T, class tree_node_allocator>
01282 template <typename iter, class BinaryPredicate>
01283 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
01284 {
01285 pre_order_iterator one(one_), three(three_);
01286
01287
01288
01289 while(one!=two && is_valid(three)) {
01290 if(!fun(*one,*three))
01291 return false;
01292 if(one.number_of_children()!=three.number_of_children())
01293 return false;
01294 ++one;
01295 ++three;
01296 }
01297 return true;
01298 }
01299
01300 template <class T, class tree_node_allocator>
01301 template <typename iter, class BinaryPredicate>
01302 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
01303 {
01304 pre_order_iterator one(one_), two(two_);
01305
01306 if(!fun(*one,*two)) return false;
01307 if(number_of_children(one)!=number_of_children(two)) return false;
01308 return equal(begin(one),end(one),begin(two),fun);
01309 }
01310
01311 template <class T, class tree_node_allocator>
01312 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
01313 {
01314 tree tmp;
01315 tmp.set_head(value_type());
01316 tmp.replace(tmp.begin(), tmp.end(), from, to);
01317 return tmp;
01318 }
01319
01320 template <class T, class tree_node_allocator>
01321 void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const
01322 {
01323 tmp.set_head(value_type());
01324 tmp.replace(tmp.begin(), tmp.end(), from, to);
01325 }
01326
01327 template <class T, class tree_node_allocator>
01328 int tree<T, tree_node_allocator>::size() const
01329 {
01330 int i=0;
01331 pre_order_iterator it=begin(), eit=end();
01332 while(it!=eit) {
01333 ++i;
01334 ++it;
01335 }
01336 return i;
01337 }
01338
01339 template <class T, class tree_node_allocator>
01340 bool tree<T, tree_node_allocator>::empty() const
01341 {
01342 pre_order_iterator it=begin(), eit=end();
01343 return (it==eit);
01344 }
01345
01346 template <class T, class tree_node_allocator>
01347 int tree<T, tree_node_allocator>::depth(const iterator_base& it) const
01348 {
01349 tree_node* pos=it.node;
01350 assert(pos!=0);
01351 int ret=0;
01352 while(pos->parent!=0) {
01353 pos=pos->parent;
01354 ++ret;
01355 }
01356 return ret;
01357 }
01358
01359 template <class T, class tree_node_allocator>
01360 unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it) const
01361 {
01362 tree_node *pos=it.node->first_child;
01363 if(pos==0) return 0;
01364
01365 unsigned int ret=1;
01366
01367
01368
01369
01370 while((pos=pos->next_sibling))
01371 ++ret;
01372 return ret;
01373 }
01374
01375 template <class T, class tree_node_allocator>
01376 unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base& it) const
01377 {
01378 tree_node *pos=it.node;
01379 unsigned int ret=0;
01380 while(pos->next_sibling &&
01381 pos->next_sibling!=head &&
01382 pos->next_sibling!=feet) {
01383 ++ret;
01384 pos=pos->next_sibling;
01385 }
01386 return ret;
01387 }
01388
01389 template <class T, class tree_node_allocator>
01390 void tree<T, tree_node_allocator>::swap(sibling_iterator it)
01391 {
01392 tree_node *nxt=it.node->next_sibling;
01393 if(nxt) {
01394 if(it.node->prev_sibling)
01395 it.node->prev_sibling->next_sibling=nxt;
01396 else
01397 it.node->parent->first_child=nxt;
01398 nxt->prev_sibling=it.node->prev_sibling;
01399 tree_node *nxtnxt=nxt->next_sibling;
01400 if(nxtnxt)
01401 nxtnxt->prev_sibling=it.node;
01402 else
01403 it.node->parent->last_child=it.node;
01404 nxt->next_sibling=it.node;
01405 it.node->prev_sibling=nxt;
01406 it.node->next_sibling=nxtnxt;
01407 }
01408 }
01409
01410
01411
01412
01413
01414
01415
01416
01417
01418
01419
01420
01421
01422
01423
01424 template <class T, class tree_node_allocator>
01425 bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& begin,
01426 const iterator_base& end) const
01427 {
01428
01429 pre_order_iterator tmp=begin;
01430 while(tmp!=end) {
01431 if(tmp==it) return true;
01432 ++tmp;
01433 }
01434 return false;
01435 }
01436
01437 template <class T, class tree_node_allocator>
01438 bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
01439 {
01440 if(it.node==0 || it.node==feet) return false;
01441 else return true;
01442 }
01443
01444 template <class T, class tree_node_allocator>
01445 unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
01446 {
01447 unsigned int ind=0;
01448 if(it.node->parent==0) {
01449 while(it.node->prev_sibling!=head) {
01450 it.node=it.node->prev_sibling;
01451 ++ind;
01452 }
01453 }
01454 else {
01455 while(it.node->prev_sibling!=0) {
01456 it.node=it.node->prev_sibling;
01457 ++ind;
01458 }
01459 }
01460 return ind;
01461 }
01462
01463
01464 template <class T, class tree_node_allocator>
01465 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num) const
01466 {
01467 tree_node *tmp=it.node->first_child;
01468 while(num--) {
01469 assert(tmp!=0);
01470 tmp=tmp->next_sibling;
01471 }
01472 return tmp;
01473 }
01474
01475
01476
01477
01478
01479
01480 template <class T, class tree_node_allocator>
01481 tree<T, tree_node_allocator>::iterator_base::iterator_base()
01482 : node(0), skip_current_children_(false)
01483 {
01484 }
01485
01486 template <class T, class tree_node_allocator>
01487 tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
01488 : node(tn), skip_current_children_(false)
01489 {
01490 }
01491
01492 template <class T, class tree_node_allocator>
01493 T& tree<T, tree_node_allocator>::iterator_base::operator*() const
01494 {
01495 return node->data;
01496 }
01497
01498 template <class T, class tree_node_allocator>
01499 T* tree<T, tree_node_allocator>::iterator_base::operator->() const
01500 {
01501 return &(node->data);
01502 }
01503
01504 template <class T, class tree_node_allocator>
01505 bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const
01506 {
01507 if(other.node!=this->node) return true;
01508 else return false;
01509 }
01510
01511 template <class T, class tree_node_allocator>
01512 bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const
01513 {
01514 if(other.node==this->node) return true;
01515 else return false;
01516 }
01517
01518 template <class T, class tree_node_allocator>
01519 bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const
01520 {
01521 if(other.node!=this->node) return true;
01522 else return false;
01523 }
01524
01525 template <class T, class tree_node_allocator>
01526 bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const
01527 {
01528 if(other.node==this->node) return true;
01529 else return false;
01530 }
01531
01532 template <class T, class tree_node_allocator>
01533 bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator& other) const
01534 {
01535 if(other.node!=this->node) return true;
01536 else return false;
01537 }
01538
01539 template <class T, class tree_node_allocator>
01540 bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const
01541 {
01542 if(other.node==this->node) return true;
01543 else return false;
01544 }
01545
01546 template <class T, class tree_node_allocator>
01547 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin() const
01548 {
01549 sibling_iterator ret(node->first_child);
01550 ret.parent_=this->node;
01551 return ret;
01552 }
01553
01554 template <class T, class tree_node_allocator>
01555 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end() const
01556 {
01557 sibling_iterator ret(0);
01558 ret.parent_=node;
01559 return ret;
01560 }
01561
01562 template <class T, class tree_node_allocator>
01563 void tree<T, tree_node_allocator>::iterator_base::skip_children()
01564 {
01565 skip_current_children_=true;
01566 }
01567
01568 template <class T, class tree_node_allocator>
01569 unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const
01570 {
01571 tree_node *pos=node->first_child;
01572 if(pos==0) return 0;
01573
01574 unsigned int ret=1;
01575 while(pos!=node->last_child) {
01576 ++ret;
01577 pos=pos->next_sibling;
01578 }
01579 return ret;
01580 }
01581
01582
01583
01584
01585
01586 template <class T, class tree_node_allocator>
01587 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
01588 : iterator_base(0)
01589 {
01590 }
01591
01592 template <class T, class tree_node_allocator>
01593 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
01594 : iterator_base(tn)
01595 {
01596 }
01597
01598 template <class T, class tree_node_allocator>
01599 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const iterator_base &other)
01600 : iterator_base(other.node)
01601 {
01602 }
01603
01604 template <class T, class tree_node_allocator>
01605 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator& other)
01606 : iterator_base(other.node)
01607 {
01608 if(this->node==0) {
01609 if(other.range_last()!=0)
01610 this->node=other.range_last();
01611 else
01612 this->node=other.parent_;
01613 this->skip_children();
01614 ++(*this);
01615 }
01616 }
01617
01618 template <class T, class tree_node_allocator>
01619 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
01620 {
01621 assert(this->node!=0);
01622 if(!this->skip_current_children_ && this->node->first_child != 0) {
01623 this->node=this->node->first_child;
01624 }
01625 else {
01626 this->skip_current_children_=false;
01627 while(this->node->next_sibling==0) {
01628 this->node=this->node->parent;
01629 if(this->node==0)
01630 return *this;
01631 }
01632 this->node=this->node->next_sibling;
01633 }
01634 return *this;
01635 }
01636
01637 template <class T, class tree_node_allocator>
01638 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
01639 {
01640 assert(this->node!=0);
01641 if(this->node->prev_sibling) {
01642 this->node=this->node->prev_sibling;
01643 while(this->node->last_child)
01644 this->node=this->node->last_child;
01645 }
01646 else {
01647 this->node=this->node->parent;
01648 if(this->node==0)
01649 return *this;
01650 }
01651 return *this;
01652 }
01653
01654 template <class T, class tree_node_allocator>
01655 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int n)
01656 {
01657 pre_order_iterator copy = *this;
01658 ++(*this);
01659 return copy;
01660 }
01661
01662 template <class T, class tree_node_allocator>
01663 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int n)
01664 {
01665 pre_order_iterator copy = *this;
01666 --(*this);
01667 return copy;
01668 }
01669
01670 template <class T, class tree_node_allocator>
01671 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
01672 {
01673 while(num>0) {
01674 ++(*this);
01675 --num;
01676 }
01677 return (*this);
01678 }
01679
01680 template <class T, class tree_node_allocator>
01681 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
01682 {
01683 while(num>0) {
01684 --(*this);
01685 --num;
01686 }
01687 return (*this);
01688 }
01689
01690
01691
01692
01693
01694 template <class T, class tree_node_allocator>
01695 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
01696 : iterator_base(0)
01697 {
01698 }
01699
01700 template <class T, class tree_node_allocator>
01701 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
01702 : iterator_base(tn)
01703 {
01704 }
01705
01706 template <class T, class tree_node_allocator>
01707 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const iterator_base &other)
01708 : iterator_base(other.node)
01709 {
01710 }
01711
01712 template <class T, class tree_node_allocator>
01713 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const sibling_iterator& other)
01714 : iterator_base(other.node)
01715 {
01716 if(this->node==0) {
01717 if(other.range_last()!=0)
01718 this->node=other.range_last();
01719 else
01720 this->node=other.parent_;
01721 this->skip_children();
01722 ++(*this);
01723 }
01724 }
01725
01726 template <class T, class tree_node_allocator>
01727 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
01728 {
01729 assert(this->node!=0);
01730 if(this->node->next_sibling==0) {
01731 this->node=this->node->parent;
01732 this->skip_current_children_=false;
01733 }
01734 else {
01735 this->node=this->node->next_sibling;
01736 if(this->skip_current_children_) {
01737 this->skip_current_children_=false;
01738 }
01739 else {
01740 while(this->node->first_child)
01741 this->node=this->node->first_child;
01742 }
01743 }
01744 return *this;
01745 }
01746
01747 template <class T, class tree_node_allocator>
01748 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
01749 {
01750 assert(this->node!=0);
01751 if(this->skip_current_children_ || this->node->last_child==0) {
01752 this->skip_current_children_=false;
01753 while(this->node->prev_sibling==0)
01754 this->node=this->node->parent;
01755 this->node=this->node->prev_sibling;
01756 }
01757 else {
01758 this->node=this->node->last_child;
01759 }
01760 return *this;
01761 }
01762
01763 template <class T, class tree_node_allocator>
01764 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(int)
01765 {
01766 post_order_iterator copy = *this;
01767 ++(*this);
01768 return copy;
01769 }
01770
01771 template <class T, class tree_node_allocator>
01772 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(int)
01773 {
01774 post_order_iterator copy = *this;
01775 --(*this);
01776 return copy;
01777 }
01778
01779
01780 template <class T, class tree_node_allocator>
01781 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
01782 {
01783 while(num>0) {
01784 ++(*this);
01785 --num;
01786 }
01787 return (*this);
01788 }
01789
01790 template <class T, class tree_node_allocator>
01791 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
01792 {
01793 while(num>0) {
01794 --(*this);
01795 --num;
01796 }
01797 return (*this);
01798 }
01799
01800 template <class T, class tree_node_allocator>
01801 void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
01802 {
01803 assert(this->node!=0);
01804 while(this->node->first_child)
01805 this->node=this->node->first_child;
01806 }
01807
01808
01809
01810
01811 template <class T, class tree_node_allocator>
01812 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
01813 : iterator_base()
01814 {
01815 set_first_parent_();
01816 }
01817
01818 template <class T, class tree_node_allocator>
01819 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
01820 : iterator_base(tn)
01821 {
01822 set_first_parent_();
01823 }
01824
01825 template <class T, class tree_node_allocator>
01826 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const iterator_base& other)
01827 : iterator_base(other.node)
01828 {
01829 set_first_parent_();
01830 }
01831
01832 template <class T, class tree_node_allocator>
01833 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const sibling_iterator& other)
01834 : iterator_base(other.node), first_parent_(other.parent_)
01835 {
01836 find_leftmost_parent_();
01837 }
01838
01839 template <class T, class tree_node_allocator>
01840 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const fixed_depth_iterator& other)
01841 : iterator_base(other.node), first_parent_(other.first_parent_)
01842 {
01843 }
01844
01845 template <class T, class tree_node_allocator>
01846 void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_()
01847 {
01848 return;
01849
01850 first_parent_=0;
01851 if(this->node==0) return;
01852 if(this->node->parent!=0)
01853 first_parent_=this->node->parent;
01854 if(first_parent_)
01855 find_leftmost_parent_();
01856 }
01857
01858 template <class T, class tree_node_allocator>
01859 void tree<T, tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_()
01860 {
01861 return;
01862 tree_node *tmppar=first_parent_;
01863 while(tmppar->prev_sibling) {
01864 tmppar=tmppar->prev_sibling;
01865 if(tmppar->first_child)
01866 first_parent_=tmppar;
01867 }
01868 }
01869
01870 template <class T, class tree_node_allocator>
01871 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()
01872 {
01873 assert(this->node!=0);
01874
01875 if(this->node->next_sibling) {
01876 this->node=this->node->next_sibling;
01877 }
01878 else {
01879 int relative_depth=0;
01880 upper:
01881 do {
01882 this->node=this->node->parent;
01883 if(this->node==0) return *this;
01884 --relative_depth;
01885 } while(this->node->next_sibling==0);
01886 lower:
01887 this->node=this->node->next_sibling;
01888 while(this->node->first_child==0) {
01889 if(this->node->next_sibling==0)
01890 goto upper;
01891 this->node=this->node->next_sibling;
01892 if(this->node==0) return *this;
01893 }
01894 while(relative_depth<0 && this->node->first_child!=0) {
01895 this->node=this->node->first_child;
01896 ++relative_depth;
01897 }
01898 if(relative_depth<0) {
01899 if(this->node->next_sibling==0) goto upper;
01900 else goto lower;
01901 }
01902 }
01903 return *this;
01904
01905
01906
01907
01908
01909
01910
01911
01912
01913
01914
01915
01916
01917
01918
01919
01920
01921
01922 return *this;
01923 }
01924
01925 template <class T, class tree_node_allocator>
01926 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()
01927 {
01928 assert(this->node!=0);
01929 if(this->node->prev_sibling!=0) {
01930 this->node=this->node->prev_sibling;
01931 assert(this->node!=0);
01932 if(this->node->parent==0 && this->node->prev_sibling==0)
01933 this->node=0;
01934 }
01935 else {
01936 tree_node *par=this->node->parent;
01937 do {
01938 par=par->prev_sibling;
01939 if(par==0) {
01940 this->node=0;
01941 return *this;
01942 }
01943 } while(par->last_child==0);
01944 this->node=par->last_child;
01945 }
01946 return *this;
01947 }
01948
01949 template <class T, class tree_node_allocator>
01950 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(int)
01951 {
01952 fixed_depth_iterator copy = *this;
01953 ++(*this);
01954 return copy;
01955 }
01956
01957 template <class T, class tree_node_allocator>
01958 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(int)
01959 {
01960 fixed_depth_iterator copy = *this;
01961 --(*this);
01962 return copy;
01963 }
01964
01965 template <class T, class tree_node_allocator>
01966 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)
01967 {
01968 while(num>0) {
01969 --(*this);
01970 --(num);
01971 }
01972 return (*this);
01973 }
01974
01975 template <class T, class tree_node_allocator>
01976 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)
01977 {
01978 while(num>0) {
01979 ++(*this);
01980 --(num);
01981 }
01982 return *this;
01983 }
01984
01985
01986
01987
01988
01989
01990 template <class T, class tree_node_allocator>
01991 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
01992 : iterator_base()
01993 {
01994 set_parent_();
01995 }
01996
01997 template <class T, class tree_node_allocator>
01998 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
01999 : iterator_base(tn)
02000 {
02001 set_parent_();
02002 }
02003
02004 template <class T, class tree_node_allocator>
02005 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const iterator_base& other)
02006 : iterator_base(other.node)
02007 {
02008 set_parent_();
02009 }
02010
02011 template <class T, class tree_node_allocator>
02012 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const sibling_iterator& other)
02013 : iterator_base(other), parent_(other.parent_)
02014 {
02015 }
02016
02017 template <class T, class tree_node_allocator>
02018 void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
02019 {
02020 parent_=0;
02021 if(this->node==0) return;
02022 if(this->node->parent!=0)
02023 parent_=this->node->parent;
02024 }
02025
02026 template <class T, class tree_node_allocator>
02027 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()
02028 {
02029 if(this->node)
02030 this->node=this->node->next_sibling;
02031 return *this;
02032 }
02033
02034 template <class T, class tree_node_allocator>
02035 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()
02036 {
02037 if(this->node) this->node=this->node->prev_sibling;
02038 else {
02039 assert(parent_);
02040 this->node=parent_->last_child;
02041 }
02042 return *this;
02043 }
02044
02045 template <class T, class tree_node_allocator>
02046 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(int)
02047 {
02048 sibling_iterator copy = *this;
02049 ++(*this);
02050 return copy;
02051 }
02052
02053 template <class T, class tree_node_allocator>
02054 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(int)
02055 {
02056 sibling_iterator copy = *this;
02057 --(*this);
02058 return copy;
02059 }
02060
02061 template <class T, class tree_node_allocator>
02062 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)
02063 {
02064 while(num>0) {
02065 ++(*this);
02066 --num;
02067 }
02068 return (*this);
02069 }
02070
02071 template <class T, class tree_node_allocator>
02072 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)
02073 {
02074 while(num>0) {
02075 --(*this);
02076 --num;
02077 }
02078 return (*this);
02079 }
02080
02081 template <class T, class tree_node_allocator>
02082 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first() const
02083 {
02084 tree_node *tmp=parent_->first_child;
02085 return tmp;
02086 }
02087
02088 template <class T, class tree_node_allocator>
02089 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last() const
02090 {
02091 return parent_->last_child;
02092 }
02093
02094
02095 #endif
02096
02097
02098
02099