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