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