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