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