Main Page | Class Hierarchy | Data Structures | File List | Data Fields | Globals

tree.hh

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

Generated on Fri Oct 8 20:34:48 2004 for LibOFX by doxygen 1.3.7