File indexing completed on 2025-02-16 09:49:52
0001 /* 0002 0003 $Id: tree.hh,v 1.147 2007/10/19 11:24:24 peekas Exp $ 0004 0005 STL-like templated tree class. 0006 SPDX-FileCopyrightText: 2001-2006 Kasper Peeters <kasper.peeters@aei.mpg.de>. 0007 SPDX-License-Identifier: GPL-2.0-only or GPL-3.0-only 0008 */ 0009 0010 /** \mainpage tree.hh 0011 \author Kasper Peeters 0012 \version 2.4 0013 \date 18-Oct-2007 0014 \see http://www.aei.mpg.de/~peekas/tree/ 0015 \see http://www.aei.mpg.de/~peekas/tree/ChangeLog 0016 0017 The tree.hh library for C++ provides an STL-like container class 0018 for n-ary trees, templated over the data stored at the 0019 nodes. Various types of iterators are provided (post-order, 0020 pre-order, and others). Where possible the access methods are 0021 compatible with the STL or alternative algorithms are 0022 available. 0023 */ 0024 0025 /* 0026 The tree.hh code is free software; you can redistribute it and/or modify 0027 it under the terms of the GNU General Public License as published by 0028 the Free Software Foundation; version 2 or 3. 0029 0030 This program is distributed in the hope that it will be useful, 0031 but WITHOUT ANY WARRANTY; without even the implied warranty of 0032 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 0033 GNU General Public License for more details. 0034 0035 You should have received a copy of the GNU General Public License 0036 along with this program; if not, write to the Free Software 0037 Foundation, Inc., 51 Franklin Street, Fifth Floor, 0038 Boston, MA 02110-1301 USA 0039 */ 0040 0041 /** \todo 0042 - New-style move members are not completely finished yet. 0043 - It would be good to have an iterator which can iterate over all 0044 nodes below a given node. 0045 - Fixed depth iterators do not iterate over the entire range if there 0046 are 'holes' in the tree. 0047 - If a range uses const iter_base& as end iterator, things will 0048 inevitably go wrong, because upcast from iter_base to a non-sibling_iter 0049 is incorrect. This upcast should be removed (and then all illegal uses 0050 as previously in 'equal' will be flagged by the compiler). This requires 0051 new copy constructors though. 0052 - There's a bug in replace(sibling_iterator, ...) when the ranges 0053 sit next to each other. Turned up in append_child(iter,iter) 0054 but has been avoided now. 0055 - "std::operator<" does not work correctly on our iterators, and for some 0056 reason a globally defined template operator< did not get picked up. 0057 Using a comparison class now, but this should be investigated. 0058 */ 0059 0060 #ifndef tree_hh_ 0061 # define tree_hh_ 0062 0063 # include <cassert> 0064 # include <memory> 0065 # include <stdexcept> 0066 # include <iterator> 0067 # include <set> 0068 # include <queue> 0069 # include <iostream> 0070 0071 // HP-style construct/destroy have gone from the standard, 0072 // so here is a copy. 0073 0074 namespace kp { 0075 0076 template<class T1, class T2> 0077 void constructor(T1 *p, T2 &val) 0078 { 0079 new ((void *)p) T1(val); 0080 } 0081 0082 template<class T1> 0083 void constructor(T1 *p) 0084 { 0085 new ((void *)p) T1; 0086 } 0087 0088 template<class T1> 0089 void destructor(T1 *p) 0090 { 0091 p->~T1(); 0092 } 0093 0094 } 0095 0096 /// A node in the tree, combining links to other nodes as well as the actual data. 0097 template<class T> 0098 class tree_node_ 0099 { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8. 0100 public: 0101 tree_node_<T> *parent; 0102 tree_node_<T> *first_child, *last_child; 0103 tree_node_<T> *prev_sibling, *next_sibling; 0104 T data; 0105 }; // __attribute__((packed)); 0106 0107 template<class T, class tree_node_allocator = std::allocator<tree_node_<T>>> 0108 class tree 0109 { 0110 protected: 0111 typedef tree_node_<T> tree_node; 0112 0113 public: 0114 /// Value of the data stored at a node. 0115 typedef T value_type; 0116 0117 class iterator_base; 0118 class pre_order_iterator; 0119 class post_order_iterator; 0120 class sibling_iterator; 0121 class leaf_iterator; 0122 0123 tree(); 0124 tree(const T &); 0125 tree(const iterator_base &); 0126 tree(const tree<T, tree_node_allocator> &); 0127 ~tree(); 0128 void operator=(const tree<T, tree_node_allocator> &); 0129 0130 /// Base class for iterators, only pointers stored, no traversal logic. 0131 # ifdef __SGI_STL_PORT 0132 class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> 0133 { 0134 # else 0135 class iterator_base 0136 { 0137 # endif 0138 public: 0139 typedef T value_type; 0140 typedef T *pointer; 0141 typedef T &reference; 0142 typedef size_t size_type; 0143 typedef ptrdiff_t difference_type; 0144 typedef std::bidirectional_iterator_tag iterator_category; 0145 0146 iterator_base(); 0147 iterator_base(tree_node *); 0148 0149 T &operator*() const; 0150 T *operator->() const; 0151 0152 /// When called, the next increment/decrement skips children of this node. 0153 void skip_children(); 0154 /// Number of children of the node pointed to by the iterator. 0155 unsigned int number_of_children() const; 0156 0157 sibling_iterator begin() const; 0158 sibling_iterator end() const; 0159 0160 tree_node *node; 0161 0162 protected: 0163 bool skip_current_children_; 0164 }; 0165 0166 /// Depth-first iterator, first accessing the node, then its children. 0167 class pre_order_iterator : public iterator_base 0168 { 0169 public: 0170 pre_order_iterator(); 0171 pre_order_iterator(tree_node *); 0172 pre_order_iterator(const iterator_base &); 0173 pre_order_iterator(const sibling_iterator &); 0174 0175 bool operator==(const pre_order_iterator &) const; 0176 bool operator!=(const pre_order_iterator &) const; 0177 pre_order_iterator &operator++(); 0178 pre_order_iterator &operator--(); 0179 pre_order_iterator operator++(int); 0180 pre_order_iterator operator--(int); 0181 pre_order_iterator &operator+=(unsigned int); 0182 pre_order_iterator &operator-=(unsigned int); 0183 }; 0184 0185 /// Depth-first iterator, first accessing the children, then the node itself. 0186 class post_order_iterator : public iterator_base 0187 { 0188 public: 0189 post_order_iterator(); 0190 post_order_iterator(tree_node *); 0191 post_order_iterator(const iterator_base &); 0192 post_order_iterator(const sibling_iterator &); 0193 0194 bool operator==(const post_order_iterator &) const; 0195 bool operator!=(const post_order_iterator &) const; 0196 post_order_iterator &operator++(); 0197 post_order_iterator &operator--(); 0198 post_order_iterator operator++(int); 0199 post_order_iterator operator--(int); 0200 post_order_iterator &operator+=(unsigned int); 0201 post_order_iterator &operator-=(unsigned int); 0202 0203 /// Set iterator to the first child as deep as possible down the tree. 0204 void descend_all(); 0205 }; 0206 0207 /// Breadth-first iterator, using a queue 0208 class breadth_first_queued_iterator : public iterator_base 0209 { 0210 public: 0211 breadth_first_queued_iterator(); 0212 breadth_first_queued_iterator(tree_node *); 0213 breadth_first_queued_iterator(const iterator_base &); 0214 0215 bool operator==(const breadth_first_queued_iterator &) const; 0216 bool operator!=(const breadth_first_queued_iterator &) const; 0217 breadth_first_queued_iterator &operator++(); 0218 breadth_first_queued_iterator operator++(int); 0219 breadth_first_queued_iterator &operator+=(unsigned int); 0220 0221 private: 0222 std::queue<tree_node *> traversal_queue; 0223 }; 0224 0225 /// The default iterator types throughout the tree class. 0226 typedef pre_order_iterator iterator; 0227 typedef breadth_first_queued_iterator breadth_first_iterator; 0228 0229 /// Iterator which traverses only the nodes at a given depth from the root. 0230 class fixed_depth_iterator : public iterator_base 0231 { 0232 public: 0233 fixed_depth_iterator(); 0234 fixed_depth_iterator(tree_node *); 0235 fixed_depth_iterator(const iterator_base &); 0236 fixed_depth_iterator(const sibling_iterator &); 0237 fixed_depth_iterator(const fixed_depth_iterator &); 0238 0239 bool operator==(const fixed_depth_iterator &) const; 0240 bool operator!=(const fixed_depth_iterator &) const; 0241 fixed_depth_iterator &operator++(); 0242 fixed_depth_iterator &operator--(); 0243 fixed_depth_iterator operator++(int); 0244 fixed_depth_iterator operator--(int); 0245 fixed_depth_iterator &operator+=(unsigned int); 0246 fixed_depth_iterator &operator-=(unsigned int); 0247 0248 tree_node *first_parent_; 0249 0250 private: 0251 void set_first_parent_(); 0252 void find_leftmost_parent_(); 0253 }; 0254 0255 /// Iterator which traverses only the nodes which are siblings of each other. 0256 class sibling_iterator : public iterator_base 0257 { 0258 public: 0259 sibling_iterator(); 0260 sibling_iterator(tree_node *); 0261 sibling_iterator(const sibling_iterator &); 0262 sibling_iterator(const iterator_base &); 0263 0264 bool operator==(const sibling_iterator &) const; 0265 bool operator!=(const sibling_iterator &) const; 0266 sibling_iterator &operator++(); 0267 sibling_iterator &operator--(); 0268 sibling_iterator operator++(int); 0269 sibling_iterator operator--(int); 0270 sibling_iterator &operator+=(unsigned int); 0271 sibling_iterator &operator-=(unsigned int); 0272 0273 tree_node *range_first() const; 0274 tree_node *range_last() const; 0275 tree_node *parent_; 0276 0277 private: 0278 void set_parent_(); 0279 }; 0280 0281 /// Iterator which traverses only the leaves. 0282 class leaf_iterator : public iterator_base 0283 { 0284 public: 0285 leaf_iterator(); 0286 leaf_iterator(tree_node *); 0287 leaf_iterator(const sibling_iterator &); 0288 leaf_iterator(const iterator_base &); 0289 0290 bool operator==(const leaf_iterator &) const; 0291 bool operator!=(const leaf_iterator &) const; 0292 leaf_iterator &operator++(); 0293 leaf_iterator &operator--(); 0294 leaf_iterator operator++(int); 0295 leaf_iterator operator--(int); 0296 leaf_iterator &operator+=(unsigned int); 0297 leaf_iterator &operator-=(unsigned int); 0298 }; 0299 0300 /// Return iterator to the beginning of the tree. 0301 inline pre_order_iterator begin() const; 0302 /// Return iterator to the end of the tree. 0303 inline pre_order_iterator end() const; 0304 /// Return post-order iterator to the beginning of the tree. 0305 post_order_iterator begin_post() const; 0306 /// Return post-order iterator to the end of the tree. 0307 post_order_iterator end_post() const; 0308 /// Return fixed-depth iterator to the first node at a given depth from the given iterator. 0309 fixed_depth_iterator begin_fixed(const iterator_base &, unsigned int) const; 0310 /// Return fixed-depth iterator to end of the nodes at given depth from the given iterator. 0311 fixed_depth_iterator end_fixed(const iterator_base &, unsigned int) const; 0312 /// Return breadth-first iterator to the first node at a given depth. 0313 breadth_first_queued_iterator begin_breadth_first() const; 0314 /// Return breadth-first iterator to end of the nodes at given depth. 0315 breadth_first_queued_iterator end_breadth_first() const; 0316 /// Return sibling iterator to the first child of given node. 0317 sibling_iterator begin(const iterator_base &) const; 0318 /// Return sibling iterator to the end of the children of a given node. 0319 sibling_iterator end(const iterator_base &) const; 0320 /// Return leaf iterator to the first leaf of the tree. 0321 leaf_iterator begin_leaf() const; 0322 /// Return leaf iterator to the last leaf of the tree. 0323 leaf_iterator end_leaf() const; 0324 0325 /// Return iterator to the parent of a node. 0326 template<typename iter> 0327 static iter parent(iter); 0328 /// Return iterator to the previous sibling of a node. 0329 template<typename iter> 0330 iter previous_sibling(iter) const; 0331 /// Return iterator to the next sibling of a node. 0332 template<typename iter> 0333 iter next_sibling(iter) const; 0334 /// Return iterator to the next node at a given depth. 0335 template<typename iter> 0336 iter next_at_same_depth(iter) const; 0337 0338 /// Erase all nodes of the tree. 0339 void clear(); 0340 /// Erase element at position pointed to by iterator, return incremented iterator. 0341 template<typename iter> 0342 iter erase(iter); 0343 /// Erase all children of the node pointed to by iterator. 0344 void erase_children(const iterator_base &); 0345 0346 /// Insert empty node as last/first child of node pointed to by position. 0347 template<typename iter> 0348 iter append_child(iter position); 0349 template<typename iter> 0350 iter prepend_child(iter position); 0351 /// Insert node as last/first child of node pointed to by position. 0352 template<typename iter> 0353 iter append_child(iter position, const T &x); 0354 template<typename iter> 0355 iter prepend_child(iter position, const T &x); 0356 /// Append the node (plus its children) at other_position as last/first child of position. 0357 template<typename iter> 0358 iter append_child(iter position, iter other_position); 0359 template<typename iter> 0360 iter prepend_child(iter position, iter other_position); 0361 /// Append the nodes in the from-to range (plus their children) as last/first children of 0362 /// position. 0363 template<typename iter> 0364 iter append_children(iter position, sibling_iterator from, sibling_iterator to); 0365 template<typename iter> 0366 iter prepend_children(iter position, sibling_iterator from, sibling_iterator to); 0367 0368 /// Short-hand to insert topmost node in otherwise empty tree. 0369 pre_order_iterator set_head(const T &x); 0370 /// Insert node as previous sibling of node pointed to by position. 0371 template<typename iter> 0372 iter insert(iter position, const T &x); 0373 /// Specialisation of previous member. 0374 sibling_iterator insert(sibling_iterator position, const T &x); 0375 /// Insert node (with children) pointed to by subtree as previous sibling of node pointed to by 0376 /// position. 0377 template<typename iter> 0378 iter insert_subtree(iter position, const iterator_base &subtree); 0379 /// Insert node as next sibling of node pointed to by position. 0380 template<typename iter> 0381 iter insert_after(iter position, const T &x); 0382 /// Insert node (with children) pointed to by subtree as next sibling of node pointed to by 0383 /// position. 0384 template<typename iter> 0385 iter insert_subtree_after(iter position, const iterator_base &subtree); 0386 0387 /// Replace node at 'position' with other node (keeping same children); 'position' becomes 0388 /// invalid. 0389 template<typename iter> 0390 iter replace(iter position, const T &x); 0391 /// Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); 0392 /// see above. 0393 template<typename iter> 0394 iter replace(iter position, const iterator_base &from); 0395 /// Replace string of siblings (plus their children) with copy of a new string (with children); 0396 /// see above 0397 sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end, 0398 sibling_iterator new_begin, sibling_iterator new_end); 0399 0400 /// Move all children of node at 'position' to be siblings, returns position. 0401 template<typename iter> 0402 iter flatten(iter position); 0403 /// Move nodes in range to be children of 'position'. 0404 template<typename iter> 0405 iter reparent(iter position, sibling_iterator begin, sibling_iterator end); 0406 /// Move all child nodes of 'from' to be children of 'position'. 0407 template<typename iter> 0408 iter reparent(iter position, iter from); 0409 0410 /// Replace node with a new node, making the old node a child of the new node. 0411 template<typename iter> 0412 iter wrap(iter position, const T &x); 0413 0414 /// Move 'source' node (plus its children) to become the next sibling of 'target'. 0415 template<typename iter> 0416 iter move_after(iter target, iter source); 0417 /// Move 'source' node (plus its children) to become the previous sibling of 'target'. 0418 template<typename iter> 0419 iter move_before(iter target, iter source); 0420 sibling_iterator move_before(sibling_iterator target, sibling_iterator source); 0421 /// Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 0422 /// 'target'). 0423 template<typename iter> 0424 iter move_ontop(iter target, iter source); 0425 0426 /// Merge with other tree, creating new branches and leaves only if they are not already 0427 /// present. 0428 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, 0429 bool duplicate_leaves = false); 0430 /// Sort (std::sort only moves values of nodes, this one moves children as well). 0431 void sort(sibling_iterator from, sibling_iterator to, bool deep = false); 0432 template<class StrictWeakOrdering> 0433 void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, 0434 bool deep = false); 0435 /// Compare two ranges of nodes (compares nodes as well as tree structure). 0436 template<typename iter> 0437 bool equal(const iter &one, const iter &two, const iter &three) const; 0438 template<typename iter, class BinaryPredicate> 0439 bool equal(const iter &one, const iter &two, const iter &three, BinaryPredicate) const; 0440 template<typename iter> 0441 bool equal_subtree(const iter &one, const iter &two) const; 0442 template<typename iter, class BinaryPredicate> 0443 bool equal_subtree(const iter &one, const iter &two, BinaryPredicate) const; 0444 /// Extract a new tree formed by the range of siblings plus all their children. 0445 tree subtree(sibling_iterator from, sibling_iterator to) const; 0446 void subtree(tree &, sibling_iterator from, sibling_iterator to) const; 0447 /// Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present). 0448 void swap(sibling_iterator it); 0449 /// Exchange two nodes (plus subtrees) 0450 void swap(iterator, iterator); 0451 0452 /// Count the total number of nodes. 0453 int size() const; 0454 /// Count the total number of nodes below the indicated node (plus one). 0455 int size(const iterator_base &) const; 0456 /// Check if tree is empty. 0457 bool empty() const; 0458 /// Compute the depth to the root. 0459 int depth(const iterator_base &) const; 0460 /// Determine the maximal depth of the tree. 0461 int max_depth() const; 0462 /// Determine the maximal depth of the tree below a given one. 0463 int max_depth(const iterator_base &) const; 0464 /// Count the number of children of node at position. 0465 static unsigned int number_of_children(const iterator_base &); 0466 /// Count the number of 'next' siblings of node at iterator. 0467 unsigned int number_of_siblings(const iterator_base &) const; 0468 /// Determine whether node at position is in the subtrees with root in the range. 0469 bool is_in_subtree(const iterator_base &position, const iterator_base &begin, 0470 const iterator_base &end) const; 0471 /// Determine whether the iterator is an 'end' iterator and thus not actually pointing to a 0472 /// node. 0473 bool is_valid(const iterator_base &) const; 0474 0475 /// Determine the index of a node in the range of siblings to which it belongs. 0476 unsigned int index(sibling_iterator it) const; 0477 /// Inverse of 'index': return the n-th child of the node at position. 0478 sibling_iterator child(const iterator_base &position, unsigned int) const; 0479 0480 /// Comparator class for iterators (compares pointer values; why doesn't this work 0481 /// automatically?) 0482 class iterator_base_less 0483 { 0484 public: 0485 bool operator()(const typename tree<T, tree_node_allocator>::iterator_base &one, 0486 const typename tree<T, tree_node_allocator>::iterator_base &two) const 0487 { 0488 return one.node < two.node; 0489 } 0490 }; 0491 tree_node *head, 0492 *feet; // head/feet are always dummy; if an iterator points to them it is invalid 0493 private: 0494 tree_node_allocator alloc_; 0495 void head_initialise_(); 0496 void copy_(const tree<T, tree_node_allocator> &other); 0497 0498 /// Comparator class for two nodes of a tree (used for sorting and searching). 0499 template<class StrictWeakOrdering> 0500 class compare_nodes 0501 { 0502 public: 0503 compare_nodes(StrictWeakOrdering comp) : comp_(comp){}; 0504 0505 bool operator()(const tree_node *a, const tree_node *b) 0506 { 0507 static StrictWeakOrdering comp; 0508 return comp(a->data, b->data); 0509 } 0510 0511 private: 0512 StrictWeakOrdering comp_; 0513 }; 0514 }; 0515 0516 // template <class T, class tree_node_allocator> 0517 // class iterator_base_less { 0518 // public: 0519 // bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one, 0520 // const typename tree<T, tree_node_allocator>::iterator_base& two) const 0521 // { 0522 // txtout << "operatorclass<" << one.node < two.node << std::endl; 0523 // return one.node < two.node; 0524 // } 0525 //}; 0526 0527 // template <class T, class tree_node_allocator> 0528 // bool operator<(const typename tree<T, tree_node_allocator>::iterator& one, 0529 // const typename tree<T, tree_node_allocator>::iterator& two) 0530 // { 0531 // txtout << "operator< " << one.node < two.node << std::endl; 0532 // if(one.node < two.node) return true; 0533 // return false; 0534 // } 0535 // 0536 // template <class T, class tree_node_allocator> 0537 // bool operator==(const typename tree<T, tree_node_allocator>::iterator& one, 0538 // const typename tree<T, tree_node_allocator>::iterator& two) 0539 // { 0540 // txtout << "operator== " << one.node == two.node << std::endl; 0541 // if(one.node == two.node) return true; 0542 // return false; 0543 // } 0544 // 0545 // template <class T, class tree_node_allocator> 0546 // bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one, 0547 // const typename tree<T, tree_node_allocator>::iterator_base& two) 0548 // { 0549 // txtout << "operator> " << one.node < two.node << std::endl; 0550 // if(one.node > two.node) return true; 0551 // return false; 0552 // } 0553 0554 // Tree 0555 0556 template<class T, class tree_node_allocator> 0557 tree<T, tree_node_allocator>::tree() 0558 { 0559 head_initialise_(); 0560 } 0561 0562 template<class T, class tree_node_allocator> 0563 tree<T, tree_node_allocator>::tree(const T &x) 0564 { 0565 head_initialise_(); 0566 set_head(x); 0567 } 0568 0569 template<class T, class tree_node_allocator> 0570 tree<T, tree_node_allocator>::tree(const iterator_base &other) 0571 { 0572 head_initialise_(); 0573 set_head((*other)); 0574 replace(begin(), other); 0575 } 0576 0577 template<class T, class tree_node_allocator> 0578 tree<T, tree_node_allocator>::~tree() 0579 { 0580 clear(); 0581 alloc_.deallocate(head, 1); 0582 alloc_.deallocate(feet, 1); 0583 } 0584 0585 template<class T, class tree_node_allocator> 0586 void tree<T, tree_node_allocator>::head_initialise_() 0587 { 0588 head = alloc_.allocate(1); 0589 feet = alloc_.allocate(1); 0590 0591 head->parent = nullptr; 0592 head->first_child = nullptr; 0593 head->last_child = nullptr; 0594 head->prev_sibling = nullptr; // head; 0595 head->next_sibling = feet; // head; 0596 0597 feet->parent = nullptr; 0598 feet->first_child = nullptr; 0599 feet->last_child = nullptr; 0600 feet->prev_sibling = head; 0601 feet->next_sibling = nullptr; 0602 } 0603 0604 template<class T, class tree_node_allocator> 0605 void tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator> &other) 0606 { 0607 copy_(other); 0608 } 0609 0610 template<class T, class tree_node_allocator> 0611 tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator> &other) 0612 { 0613 head_initialise_(); 0614 copy_(other); 0615 } 0616 0617 template<class T, class tree_node_allocator> 0618 void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator> &other) 0619 { 0620 clear(); 0621 pre_order_iterator it = other.begin(), to = begin(); 0622 while (it != other.end()) { 0623 to = insert(to, (*it)); 0624 it.skip_children(); 0625 ++it; 0626 } 0627 to = begin(); 0628 it = other.begin(); 0629 while (it != other.end()) { 0630 to = replace(to, it); 0631 to.skip_children(); 0632 it.skip_children(); 0633 ++to; 0634 ++it; 0635 } 0636 } 0637 0638 template<class T, class tree_node_allocator> 0639 void tree<T, tree_node_allocator>::clear() 0640 { 0641 if (head) 0642 while (head->next_sibling != feet) 0643 erase(pre_order_iterator(head->next_sibling)); 0644 } 0645 0646 template<class T, class tree_node_allocator> 0647 void tree<T, tree_node_allocator>::erase_children(const iterator_base &it) 0648 { 0649 // std::cout << "erase_children " << it.node << std::endl; 0650 if (it.node == nullptr) 0651 return; 0652 0653 tree_node *cur = it.node->first_child; 0654 tree_node *prev = nullptr; 0655 0656 while (cur != nullptr) { 0657 prev = cur; 0658 cur = cur->next_sibling; 0659 erase_children(pre_order_iterator(prev)); 0660 kp::destructor(&prev->data); 0661 alloc_.deallocate(prev, 1); 0662 } 0663 it.node->first_child = nullptr; 0664 it.node->last_child = nullptr; 0665 // std::cout << "exit" << std::endl; 0666 } 0667 0668 template<class T, class tree_node_allocator> 0669 template<class iter> 0670 iter tree<T, tree_node_allocator>::erase(iter it) 0671 { 0672 tree_node *cur = it.node; 0673 assert(cur != head); 0674 iter ret = it; 0675 ret.skip_children(); 0676 ++ret; 0677 erase_children(it); 0678 if (cur->prev_sibling == nullptr) { 0679 cur->parent->first_child = cur->next_sibling; 0680 } else { 0681 cur->prev_sibling->next_sibling = cur->next_sibling; 0682 } 0683 if (cur->next_sibling == nullptr) { 0684 cur->parent->last_child = cur->prev_sibling; 0685 } else { 0686 cur->next_sibling->prev_sibling = cur->prev_sibling; 0687 } 0688 0689 kp::destructor(&cur->data); 0690 alloc_.deallocate(cur, 1); 0691 return ret; 0692 } 0693 0694 template<class T, class tree_node_allocator> 0695 typename tree<T, tree_node_allocator>::pre_order_iterator 0696 tree<T, tree_node_allocator>::begin() const 0697 { 0698 return pre_order_iterator(head->next_sibling); 0699 } 0700 0701 template<class T, class tree_node_allocator> 0702 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const 0703 { 0704 return pre_order_iterator(feet); 0705 } 0706 0707 template<class T, class tree_node_allocator> 0708 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator 0709 tree<T, tree_node_allocator>::begin_breadth_first() const 0710 { 0711 return breadth_first_queued_iterator(head->next_sibling); 0712 } 0713 0714 template<class T, class tree_node_allocator> 0715 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator 0716 tree<T, tree_node_allocator>::end_breadth_first() const 0717 { 0718 return breadth_first_queued_iterator(); 0719 } 0720 0721 template<class T, class tree_node_allocator> 0722 typename tree<T, tree_node_allocator>::post_order_iterator 0723 tree<T, tree_node_allocator>::begin_post() const 0724 { 0725 tree_node *tmp = head->next_sibling; 0726 if (tmp != feet) { 0727 while (tmp->first_child) 0728 tmp = tmp->first_child; 0729 } 0730 return post_order_iterator(tmp); 0731 } 0732 0733 template<class T, class tree_node_allocator> 0734 typename tree<T, tree_node_allocator>::post_order_iterator 0735 tree<T, tree_node_allocator>::end_post() const 0736 { 0737 return post_order_iterator(feet); 0738 } 0739 0740 template<class T, class tree_node_allocator> 0741 typename tree<T, tree_node_allocator>::fixed_depth_iterator 0742 tree<T, tree_node_allocator>::begin_fixed(const iterator_base &pos, unsigned int dp) const 0743 { 0744 tree_node *tmp = pos.node; 0745 unsigned int curdepth = 0; 0746 while (curdepth < dp) { // go down one level 0747 while (tmp->first_child == 0) { 0748 if (tmp->next_sibling == 0) { 0749 // try to walk up and then right again 0750 do { 0751 tmp = tmp->parent; 0752 if (tmp == 0) 0753 throw std::range_error("tree: begin_fixed out of range"); 0754 --curdepth; 0755 } while (tmp->next_sibling == 0); 0756 } 0757 tmp = tmp->next_sibling; 0758 } 0759 tmp = tmp->first_child; 0760 ++curdepth; 0761 } 0762 return tmp; 0763 } 0764 0765 template<class T, class tree_node_allocator> 0766 typename tree<T, tree_node_allocator>::fixed_depth_iterator 0767 tree<T, tree_node_allocator>::end_fixed(const iterator_base &pos, unsigned int dp) const 0768 { 0769 assert(1 == 0); // FIXME: not correct yet: use is_valid() as a temporary workaround 0770 tree_node *tmp = pos.node; 0771 unsigned int curdepth = 1; 0772 while (curdepth < dp) { // go down one level 0773 while (tmp->first_child == 0) { 0774 tmp = tmp->next_sibling; 0775 if (tmp == 0) 0776 throw std::range_error("tree: end_fixed out of range"); 0777 } 0778 tmp = tmp->first_child; 0779 ++curdepth; 0780 } 0781 return tmp; 0782 } 0783 0784 template<class T, class tree_node_allocator> 0785 typename tree<T, tree_node_allocator>::sibling_iterator 0786 tree<T, tree_node_allocator>::begin(const iterator_base &pos) const 0787 { 0788 assert(pos.node != nullptr); 0789 if (pos.node->first_child == nullptr) { 0790 return end(pos); 0791 } 0792 return pos.node->first_child; 0793 } 0794 0795 template<class T, class tree_node_allocator> 0796 typename tree<T, tree_node_allocator>::sibling_iterator 0797 tree<T, tree_node_allocator>::end(const iterator_base &pos) const 0798 { 0799 sibling_iterator ret(nullptr); 0800 ret.parent_ = pos.node; 0801 return ret; 0802 } 0803 0804 template<class T, class tree_node_allocator> 0805 typename tree<T, tree_node_allocator>::leaf_iterator 0806 tree<T, tree_node_allocator>::begin_leaf() const 0807 { 0808 tree_node *tmp = head->next_sibling; 0809 if (tmp != feet) { 0810 while (tmp->first_child) 0811 tmp = tmp->first_child; 0812 } 0813 return leaf_iterator(tmp); 0814 } 0815 0816 template<class T, class tree_node_allocator> 0817 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf() const 0818 { 0819 return leaf_iterator(feet); 0820 } 0821 0822 template<class T, class tree_node_allocator> 0823 template<typename iter> 0824 iter tree<T, tree_node_allocator>::parent(iter position) 0825 { 0826 assert(position.node != 0); 0827 return iter(position.node->parent); 0828 } 0829 0830 template<class T, class tree_node_allocator> 0831 template<typename iter> 0832 iter tree<T, tree_node_allocator>::previous_sibling(iter position) const 0833 { 0834 assert(position.node != 0); 0835 iter ret(position); 0836 ret.node = position.node->prev_sibling; 0837 return ret; 0838 } 0839 0840 template<class T, class tree_node_allocator> 0841 template<typename iter> 0842 iter tree<T, tree_node_allocator>::next_sibling(iter position) const 0843 { 0844 assert(position.node != 0); 0845 iter ret(position); 0846 ret.node = position.node->next_sibling; 0847 return ret; 0848 } 0849 0850 template<class T, class tree_node_allocator> 0851 template<typename iter> 0852 iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const 0853 { 0854 assert(position.node != 0); 0855 iter ret(position); 0856 0857 if (position.node->next_sibling) { 0858 ret.node = position.node->next_sibling; 0859 } else { 0860 int relative_depth = 0; 0861 upper: 0862 do { 0863 ret.node = ret.node->parent; 0864 if (ret.node == 0) 0865 return ret; 0866 --relative_depth; 0867 } while (ret.node->next_sibling == 0); 0868 lower: 0869 ret.node = ret.node->next_sibling; 0870 while (ret.node->first_child == 0) { 0871 if (ret.node->next_sibling == 0) 0872 goto upper; 0873 ret.node = ret.node->next_sibling; 0874 if (ret.node == 0) 0875 return ret; 0876 } 0877 while (relative_depth < 0 && ret.node->first_child != 0) { 0878 ret.node = ret.node->first_child; 0879 ++relative_depth; 0880 } 0881 if (relative_depth < 0) { 0882 if (ret.node->next_sibling == 0) 0883 goto upper; 0884 else 0885 goto lower; 0886 } 0887 } 0888 return ret; 0889 } 0890 0891 template<class T, class tree_node_allocator> 0892 template<typename iter> 0893 iter tree<T, tree_node_allocator>::append_child(iter position) 0894 { 0895 assert(position.node != head); 0896 assert(position.node); 0897 0898 tree_node *tmp = alloc_.allocate(1, 0); 0899 kp::constructor(&tmp->data); 0900 tmp->first_child = 0; 0901 tmp->last_child = 0; 0902 0903 tmp->parent = position.node; 0904 if (position.node->last_child != 0) { 0905 position.node->last_child->next_sibling = tmp; 0906 } else { 0907 position.node->first_child = tmp; 0908 } 0909 tmp->prev_sibling = position.node->last_child; 0910 position.node->last_child = tmp; 0911 tmp->next_sibling = 0; 0912 return tmp; 0913 } 0914 0915 template<class T, class tree_node_allocator> 0916 template<typename iter> 0917 iter tree<T, tree_node_allocator>::prepend_child(iter position) 0918 { 0919 assert(position.node != head); 0920 assert(position.node); 0921 0922 tree_node *tmp = alloc_.allocate(1, 0); 0923 kp::constructor(&tmp->data); 0924 tmp->first_child = 0; 0925 tmp->last_child = 0; 0926 0927 tmp->parent = position.node; 0928 if (position.node->first_child != 0) { 0929 position.node->first_child->prev_sibling = tmp; 0930 } else { 0931 position.node->last_child = tmp; 0932 } 0933 tmp->next_sibling = position.node->first_child; 0934 position.node->prev_child = tmp; 0935 tmp->prev_sibling = 0; 0936 return tmp; 0937 } 0938 0939 template<class T, class tree_node_allocator> 0940 template<class iter> 0941 iter tree<T, tree_node_allocator>::append_child(iter position, const T &x) 0942 { 0943 // If your program fails here you probably used 'append_child' to add the top 0944 // node to an empty tree. From version 1.45 the top element should be added 0945 // using 'insert'. See the documentation for further information, and sorry about 0946 // the API change. 0947 assert(position.node != head); 0948 assert(position.node); 0949 0950 tree_node *tmp = alloc_.allocate(1); 0951 kp::constructor(&tmp->data, x); 0952 tmp->first_child = nullptr; 0953 tmp->last_child = nullptr; 0954 0955 tmp->parent = position.node; 0956 if (position.node->last_child != nullptr) { 0957 position.node->last_child->next_sibling = tmp; 0958 } else { 0959 position.node->first_child = tmp; 0960 } 0961 tmp->prev_sibling = position.node->last_child; 0962 position.node->last_child = tmp; 0963 tmp->next_sibling = nullptr; 0964 return tmp; 0965 } 0966 0967 template<class T, class tree_node_allocator> 0968 template<class iter> 0969 iter tree<T, tree_node_allocator>::prepend_child(iter position, const T &x) 0970 { 0971 assert(position.node != head); 0972 assert(position.node); 0973 0974 tree_node *tmp = alloc_.allocate(1, 0); 0975 kp::constructor(&tmp->data, x); 0976 tmp->first_child = 0; 0977 tmp->last_child = 0; 0978 0979 tmp->parent = position.node; 0980 if (position.node->first_child != 0) { 0981 position.node->first_child->prev_sibling = tmp; 0982 } else { 0983 position.node->last_child = tmp; 0984 } 0985 tmp->next_sibling = position.node->first_child; 0986 position.node->first_child = tmp; 0987 tmp->prev_sibling = 0; 0988 return tmp; 0989 } 0990 0991 template<class T, class tree_node_allocator> 0992 template<class iter> 0993 iter tree<T, tree_node_allocator>::append_child(iter position, iter other) 0994 { 0995 assert(position.node != head); 0996 assert(position.node); 0997 0998 sibling_iterator aargh = append_child(position, value_type()); 0999 return replace(aargh, other); 1000 } 1001 1002 template<class T, class tree_node_allocator> 1003 template<class iter> 1004 iter tree<T, tree_node_allocator>::prepend_child(iter position, iter other) 1005 { 1006 assert(position.node != head); 1007 assert(position.node); 1008 1009 sibling_iterator aargh = prepend_child(position, value_type()); 1010 return replace(aargh, other); 1011 } 1012 1013 template<class T, class tree_node_allocator> 1014 template<class iter> 1015 iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, 1016 sibling_iterator to) 1017 { 1018 assert(position.node != head); 1019 assert(position.node); 1020 1021 iter ret = from; 1022 1023 while (from != to) { 1024 insert_subtree(position.end(), from); 1025 ++from; 1026 } 1027 return ret; 1028 } 1029 1030 template<class T, class tree_node_allocator> 1031 template<class iter> 1032 iter tree<T, tree_node_allocator>::prepend_children(iter position, sibling_iterator from, 1033 sibling_iterator to) 1034 { 1035 assert(position.node != head); 1036 assert(position.node); 1037 1038 iter ret = from; 1039 1040 while (from != to) { 1041 insert_subtree(position.begin(), from); 1042 ++from; 1043 } 1044 return ret; 1045 } 1046 1047 template<class T, class tree_node_allocator> 1048 typename tree<T, tree_node_allocator>::pre_order_iterator 1049 tree<T, tree_node_allocator>::set_head(const T &x) 1050 { 1051 assert(head->next_sibling == feet); 1052 return insert(iterator(feet), x); 1053 } 1054 1055 template<class T, class tree_node_allocator> 1056 template<class iter> 1057 iter tree<T, tree_node_allocator>::insert(iter position, const T &x) 1058 { 1059 if (position.node == nullptr) { 1060 position.node = feet; // Backward compatibility: when calling insert on a null node, 1061 // insert before the feet. 1062 } 1063 tree_node *tmp = alloc_.allocate(1); 1064 kp::constructor(&tmp->data, x); 1065 tmp->first_child = nullptr; 1066 tmp->last_child = nullptr; 1067 1068 tmp->parent = position.node->parent; 1069 tmp->next_sibling = position.node; 1070 tmp->prev_sibling = position.node->prev_sibling; 1071 position.node->prev_sibling = tmp; 1072 1073 if (tmp->prev_sibling == nullptr) { 1074 if (tmp->parent) // when inserting nodes at the head, there is no parent 1075 tmp->parent->first_child = tmp; 1076 } else 1077 tmp->prev_sibling->next_sibling = tmp; 1078 return tmp; 1079 } 1080 1081 template<class T, class tree_node_allocator> 1082 typename tree<T, tree_node_allocator>::sibling_iterator 1083 tree<T, tree_node_allocator>::insert(sibling_iterator position, const T &x) 1084 { 1085 tree_node *tmp = alloc_.allocate(1, nullptr); 1086 kp::constructor(&tmp->data, x); 1087 tmp->first_child = nullptr; 1088 tmp->last_child = nullptr; 1089 1090 tmp->next_sibling = position.node; 1091 if (position.node == nullptr) { // iterator points to end of a subtree 1092 tmp->parent = position.parent_; 1093 tmp->prev_sibling = position.range_last(); 1094 tmp->parent->last_child = tmp; 1095 } else { 1096 tmp->parent = position.node->parent; 1097 tmp->prev_sibling = position.node->prev_sibling; 1098 position.node->prev_sibling = tmp; 1099 } 1100 1101 if (tmp->prev_sibling == nullptr) { 1102 if (tmp->parent) // when inserting nodes at the head, there is no parent 1103 tmp->parent->first_child = tmp; 1104 } else 1105 tmp->prev_sibling->next_sibling = tmp; 1106 return tmp; 1107 } 1108 1109 template<class T, class tree_node_allocator> 1110 template<class iter> 1111 iter tree<T, tree_node_allocator>::insert_after(iter position, const T &x) 1112 { 1113 tree_node *tmp = alloc_.allocate(1, nullptr); 1114 kp::constructor(&tmp->data, x); 1115 tmp->first_child = nullptr; 1116 tmp->last_child = nullptr; 1117 1118 tmp->parent = position.node->parent; 1119 tmp->prev_sibling = position.node; 1120 tmp->next_sibling = position.node->next_sibling; 1121 position.node->next_sibling = tmp; 1122 1123 if (tmp->next_sibling == nullptr) { 1124 if (tmp->parent) // when inserting nodes at the head, there is no parent 1125 tmp->parent->last_child = tmp; 1126 } else { 1127 tmp->next_sibling->prev_sibling = tmp; 1128 } 1129 return tmp; 1130 } 1131 1132 template<class T, class tree_node_allocator> 1133 template<class iter> 1134 iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base &subtree) 1135 { 1136 // insert dummy 1137 iter it = insert(position, value_type()); 1138 // replace dummy with subtree 1139 return replace(it, subtree); 1140 } 1141 1142 template<class T, class tree_node_allocator> 1143 template<class iter> 1144 iter tree<T, tree_node_allocator>::insert_subtree_after(iter position, const iterator_base &subtree) 1145 { 1146 // insert dummy 1147 iter it = insert_after(position, value_type()); 1148 // replace dummy with subtree 1149 return replace(it, subtree); 1150 } 1151 1152 // template <class T, class tree_node_allocator> 1153 // template <class iter> 1154 // iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree) 1155 // { 1156 // // insert dummy 1157 // iter it(insert(position, value_type())); 1158 // // replace dummy with subtree 1159 // return replace(it, subtree); 1160 // } 1161 1162 template<class T, class tree_node_allocator> 1163 template<class iter> 1164 iter tree<T, tree_node_allocator>::replace(iter position, const T &x) 1165 { 1166 kp::destructor(&position.node->data); 1167 kp::constructor(&position.node->data, x); 1168 return position; 1169 } 1170 1171 template<class T, class tree_node_allocator> 1172 template<class iter> 1173 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base &from) 1174 { 1175 assert(position.node != head); 1176 tree_node *current_from = from.node; 1177 tree_node *start_from = from.node; 1178 tree_node *current_to = position.node; 1179 1180 // replace the node at position with head of the replacement tree at from 1181 // std::cout << "warning!" << position.node << std::endl; 1182 erase_children(position); 1183 // std::cout << "no warning!" << std::endl; 1184 tree_node *tmp = alloc_.allocate(1, nullptr); 1185 kp::constructor(&tmp->data, (*from)); 1186 tmp->first_child = nullptr; 1187 tmp->last_child = nullptr; 1188 if (current_to->prev_sibling == nullptr) { 1189 if (current_to->parent != nullptr) 1190 current_to->parent->first_child = tmp; 1191 } else { 1192 current_to->prev_sibling->next_sibling = tmp; 1193 } 1194 tmp->prev_sibling = current_to->prev_sibling; 1195 if (current_to->next_sibling == nullptr) { 1196 if (current_to->parent != nullptr) 1197 current_to->parent->last_child = tmp; 1198 } else { 1199 current_to->next_sibling->prev_sibling = tmp; 1200 } 1201 tmp->next_sibling = current_to->next_sibling; 1202 tmp->parent = current_to->parent; 1203 kp::destructor(¤t_to->data); 1204 alloc_.deallocate(current_to, 1); 1205 current_to = tmp; 1206 1207 // only at this stage can we fix 'last' 1208 tree_node *last = from.node->next_sibling; 1209 1210 pre_order_iterator toit = tmp; 1211 // copy all children 1212 do { 1213 assert(current_from != nullptr); 1214 if (current_from->first_child != nullptr) { 1215 current_from = current_from->first_child; 1216 toit = append_child(toit, current_from->data); 1217 } else { 1218 while (current_from->next_sibling == nullptr && current_from != start_from) { 1219 current_from = current_from->parent; 1220 toit = parent(toit); 1221 assert(current_from != nullptr); 1222 } 1223 current_from = current_from->next_sibling; 1224 if (current_from != last) { 1225 toit = append_child(parent(toit), current_from->data); 1226 } 1227 } 1228 } while (current_from != last); 1229 1230 return current_to; 1231 } 1232 1233 template<class T, class tree_node_allocator> 1234 typename tree<T, tree_node_allocator>::sibling_iterator 1235 tree<T, tree_node_allocator>::replace(sibling_iterator orig_begin, sibling_iterator orig_end, 1236 sibling_iterator new_begin, sibling_iterator new_end) 1237 { 1238 tree_node *orig_first = orig_begin.node; 1239 tree_node *new_first = new_begin.node; 1240 tree_node *orig_last = orig_first; 1241 while ((++orig_begin) != orig_end) 1242 orig_last = orig_last->next_sibling; 1243 tree_node *new_last = new_first; 1244 while ((++new_begin) != new_end) 1245 new_last = new_last->next_sibling; 1246 1247 // insert all siblings in new_first..new_last before orig_first 1248 bool first = true; 1249 pre_order_iterator ret; 1250 while (1 == 1) { 1251 pre_order_iterator tt = 1252 insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first)); 1253 if (first) { 1254 ret = tt; 1255 first = false; 1256 } 1257 if (new_first == new_last) 1258 break; 1259 new_first = new_first->next_sibling; 1260 } 1261 1262 // erase old range of siblings 1263 bool last = false; 1264 tree_node *next = orig_first; 1265 while (1 == 1) { 1266 if (next == orig_last) 1267 last = true; 1268 next = next->next_sibling; 1269 erase((pre_order_iterator)orig_first); 1270 if (last) 1271 break; 1272 orig_first = next; 1273 } 1274 return ret; 1275 } 1276 1277 template<class T, class tree_node_allocator> 1278 template<typename iter> 1279 iter tree<T, tree_node_allocator>::flatten(iter position) 1280 { 1281 if (position.node->first_child == nullptr) 1282 return position; 1283 1284 tree_node *tmp = position.node->first_child; 1285 while (tmp) { 1286 tmp->parent = position.node->parent; 1287 tmp = tmp->next_sibling; 1288 } 1289 if (position.node->next_sibling) { 1290 position.node->last_child->next_sibling = position.node->next_sibling; 1291 position.node->next_sibling->prev_sibling = position.node->last_child; 1292 } else { 1293 position.node->parent->last_child = position.node->last_child; 1294 } 1295 position.node->next_sibling = position.node->first_child; 1296 position.node->next_sibling->prev_sibling = position.node; 1297 position.node->first_child = nullptr; 1298 position.node->last_child = nullptr; 1299 1300 return position; 1301 } 1302 1303 template<class T, class tree_node_allocator> 1304 template<typename iter> 1305 iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, 1306 sibling_iterator end) 1307 { 1308 tree_node *first = begin.node; 1309 tree_node *last = first; 1310 1311 assert(first != position.node); 1312 1313 if (begin == end) 1314 return begin; 1315 // determine last node 1316 while ((++begin) != end) { 1317 last = last->next_sibling; 1318 } 1319 // move subtree 1320 if (first->prev_sibling == nullptr) { 1321 first->parent->first_child = last->next_sibling; 1322 } else { 1323 first->prev_sibling->next_sibling = last->next_sibling; 1324 } 1325 if (last->next_sibling == nullptr) { 1326 last->parent->last_child = first->prev_sibling; 1327 } else { 1328 last->next_sibling->prev_sibling = first->prev_sibling; 1329 } 1330 if (position.node->first_child == nullptr) { 1331 position.node->first_child = first; 1332 position.node->last_child = last; 1333 first->prev_sibling = nullptr; 1334 } else { 1335 position.node->last_child->next_sibling = first; 1336 first->prev_sibling = position.node->last_child; 1337 position.node->last_child = last; 1338 } 1339 last->next_sibling = nullptr; 1340 1341 tree_node *pos = first; 1342 while (1 == 1) { 1343 pos->parent = position.node; 1344 if (pos == last) 1345 break; 1346 pos = pos->next_sibling; 1347 } 1348 1349 return first; 1350 } 1351 1352 template<class T, class tree_node_allocator> 1353 template<typename iter> 1354 iter tree<T, tree_node_allocator>::reparent(iter position, iter from) 1355 { 1356 if (from.node->first_child == nullptr) 1357 return position; 1358 return reparent(position, from.node->first_child, end(from)); 1359 } 1360 1361 template<class T, class tree_node_allocator> 1362 template<typename iter> 1363 iter tree<T, tree_node_allocator>::wrap(iter position, const T &x) 1364 { 1365 assert(position.node != nullptr); 1366 sibling_iterator fr = position, to = position; 1367 ++to; 1368 iter ret = insert(position, x); 1369 reparent(ret, fr, to); 1370 return ret; 1371 } 1372 1373 template<class T, class tree_node_allocator> 1374 template<typename iter> 1375 iter tree<T, tree_node_allocator>::move_after(iter target, iter source) 1376 { 1377 tree_node *dst = target.node; 1378 tree_node *src = source.node; 1379 assert(dst); 1380 assert(src); 1381 1382 if (dst == src) 1383 return source; 1384 if (dst->next_sibling) 1385 if (dst->next_sibling == src) // already in the right spot 1386 return source; 1387 1388 // take src out of the tree 1389 if (src->prev_sibling != nullptr) 1390 src->prev_sibling->next_sibling = src->next_sibling; 1391 else 1392 src->parent->first_child = src->next_sibling; 1393 if (src->next_sibling != nullptr) 1394 src->next_sibling->prev_sibling = src->prev_sibling; 1395 else 1396 src->parent->last_child = src->prev_sibling; 1397 1398 // connect it to the new point 1399 if (dst->next_sibling != nullptr) 1400 dst->next_sibling->prev_sibling = src; 1401 else 1402 dst->parent->last_child = src; 1403 src->next_sibling = dst->next_sibling; 1404 dst->next_sibling = src; 1405 src->prev_sibling = dst; 1406 src->parent = dst->parent; 1407 return src; 1408 } 1409 1410 template<class T, class tree_node_allocator> 1411 template<typename iter> 1412 iter tree<T, tree_node_allocator>::move_before(iter target, iter source) 1413 { 1414 tree_node *dst = target.node; 1415 tree_node *src = source.node; 1416 assert(dst); 1417 assert(src); 1418 1419 if (dst == src) 1420 return source; 1421 if (dst->prev_sibling) 1422 if (dst->prev_sibling == src) // already in the right spot 1423 return source; 1424 1425 // take src out of the tree 1426 if (src->prev_sibling != nullptr) 1427 src->prev_sibling->next_sibling = src->next_sibling; 1428 else 1429 src->parent->first_child = src->next_sibling; 1430 if (src->next_sibling != nullptr) 1431 src->next_sibling->prev_sibling = src->prev_sibling; 1432 else 1433 src->parent->last_child = src->prev_sibling; 1434 1435 // connect it to the new point 1436 if (dst->prev_sibling != nullptr) 1437 dst->prev_sibling->next_sibling = src; 1438 else 1439 dst->parent->first_child = src; 1440 src->prev_sibling = dst->prev_sibling; 1441 dst->prev_sibling = src; 1442 src->next_sibling = dst; 1443 src->parent = dst->parent; 1444 return src; 1445 } 1446 1447 // specialisation for sibling_iterators 1448 template<class T, class tree_node_allocator> 1449 typename tree<T, tree_node_allocator>::sibling_iterator 1450 tree<T, tree_node_allocator>::move_before(sibling_iterator target, sibling_iterator source) 1451 { 1452 tree_node *dst = target.node; 1453 tree_node *src = source.node; 1454 tree_node *dst_prev_sibling; 1455 if (dst == nullptr) { // must then be an end iterator 1456 dst_prev_sibling = target.parent_->last_child; 1457 assert(dst_prev_sibling); 1458 } else 1459 dst_prev_sibling = dst->prev_sibling; 1460 assert(src); 1461 1462 if (dst == src) 1463 return source; 1464 if (dst_prev_sibling) 1465 if (dst_prev_sibling == src) // already in the right spot 1466 return source; 1467 1468 // take src out of the tree 1469 if (src->prev_sibling != nullptr) 1470 src->prev_sibling->next_sibling = src->next_sibling; 1471 else 1472 src->parent->first_child = src->next_sibling; 1473 if (src->next_sibling != nullptr) 1474 src->next_sibling->prev_sibling = src->prev_sibling; 1475 else 1476 src->parent->last_child = src->prev_sibling; 1477 1478 // connect it to the new point 1479 if (dst_prev_sibling != nullptr) 1480 dst_prev_sibling->next_sibling = src; 1481 else 1482 target.parent_->first_child = src; 1483 src->prev_sibling = dst_prev_sibling; 1484 if (dst) { 1485 dst->prev_sibling = src; 1486 src->parent = dst->parent; 1487 } 1488 src->next_sibling = dst; 1489 return src; 1490 } 1491 1492 template<class T, class tree_node_allocator> 1493 template<typename iter> 1494 iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source) 1495 { 1496 tree_node *dst = target.node; 1497 tree_node *src = source.node; 1498 assert(dst); 1499 assert(src); 1500 1501 if (dst == src) 1502 return source; 1503 1504 // remember connection points 1505 tree_node *b_prev_sibling = dst->prev_sibling; 1506 tree_node *b_next_sibling = dst->next_sibling; 1507 tree_node *b_parent = dst->parent; 1508 1509 // remove target 1510 erase(target); 1511 1512 // take src out of the tree 1513 if (src->prev_sibling != nullptr) 1514 src->prev_sibling->next_sibling = src->next_sibling; 1515 else 1516 src->parent->first_child = src->next_sibling; 1517 if (src->next_sibling != nullptr) 1518 src->next_sibling->prev_sibling = src->prev_sibling; 1519 else 1520 src->parent->last_child = src->prev_sibling; 1521 1522 // connect it to the new point 1523 if (b_prev_sibling != nullptr) 1524 b_prev_sibling->next_sibling = src; 1525 else 1526 b_parent->first_child = src; 1527 if (b_next_sibling != nullptr) 1528 b_next_sibling->prev_sibling = src; 1529 else 1530 b_parent->last_child = src; 1531 src->prev_sibling = b_prev_sibling; 1532 src->next_sibling = b_next_sibling; 1533 src->parent = b_parent; 1534 return src; 1535 } 1536 1537 template<class T, class tree_node_allocator> 1538 void tree<T, tree_node_allocator>::merge(sibling_iterator to1, sibling_iterator to2, 1539 sibling_iterator from1, sibling_iterator from2, 1540 bool duplicate_leaves) 1541 { 1542 sibling_iterator fnd; 1543 while (from1 != from2) { 1544 if ((fnd = std::find(to1, to2, (*from1))) != to2) { // element found 1545 if (from1.begin() == from1.end()) { // full depth reached 1546 if (duplicate_leaves) 1547 append_child(parent(to1), (*from1)); 1548 } else { // descend further 1549 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves); 1550 } 1551 } else { // element missing 1552 insert_subtree(to2, from1); 1553 } 1554 ++from1; 1555 } 1556 } 1557 1558 template<class T, class tree_node_allocator> 1559 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep) 1560 { 1561 std::less<T> comp; 1562 sort(from, to, comp, deep); 1563 } 1564 1565 template<class T, class tree_node_allocator> 1566 template<class StrictWeakOrdering> 1567 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, 1568 StrictWeakOrdering comp, bool deep) 1569 { 1570 if (from == to) 1571 return; 1572 // make list of sorted nodes 1573 // CHECK: if multiset stores equivalent nodes in the order in which they 1574 // are inserted, then this routine should be called 'stable_sort'. 1575 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering>> nodes(comp); 1576 sibling_iterator it = from, it2 = to; 1577 while (it != to) { 1578 nodes.insert(it.node); 1579 ++it; 1580 } 1581 // reassemble 1582 --it2; 1583 1584 // prev and next are the nodes before and after the sorted range 1585 tree_node *prev = from.node->prev_sibling; 1586 tree_node *next = it2.node->next_sibling; 1587 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering>>::iterator 1588 nit = nodes.begin(), 1589 eit = nodes.end(); 1590 if (prev == nullptr) { 1591 if ((*nit)->parent 1592 != nullptr) // to catch "sorting the head" situations, when there is no parent 1593 (*nit)->parent->first_child = (*nit); 1594 } else 1595 prev->next_sibling = (*nit); 1596 1597 --eit; 1598 while (nit != eit) { 1599 (*nit)->prev_sibling = prev; 1600 if (prev) 1601 prev->next_sibling = (*nit); 1602 prev = (*nit); 1603 ++nit; 1604 } 1605 // prev now points to the last-but-one node in the sorted range 1606 if (prev) 1607 prev->next_sibling = (*eit); 1608 1609 // eit points to the last node in the sorted range. 1610 (*eit)->next_sibling = next; 1611 (*eit)->prev_sibling = prev; // missed in the loop above 1612 if (next == nullptr) { 1613 if ((*eit)->parent 1614 != nullptr) // to catch "sorting the head" situations, when there is no parent 1615 (*eit)->parent->last_child = (*eit); 1616 } else 1617 next->prev_sibling = (*eit); 1618 1619 if (deep) { // sort the children of each node too 1620 sibling_iterator bcs(*nodes.begin()); 1621 sibling_iterator ecs(*eit); 1622 ++ecs; 1623 while (bcs != ecs) { 1624 sort(begin(bcs), end(bcs), comp, deep); 1625 ++bcs; 1626 } 1627 } 1628 } 1629 1630 template<class T, class tree_node_allocator> 1631 template<typename iter> 1632 bool tree<T, tree_node_allocator>::equal(const iter &one_, const iter &two, 1633 const iter &three_) const 1634 { 1635 std::equal_to<T> comp; 1636 return equal(one_, two, three_, comp); 1637 } 1638 1639 template<class T, class tree_node_allocator> 1640 template<typename iter> 1641 bool tree<T, tree_node_allocator>::equal_subtree(const iter &one_, const iter &two_) const 1642 { 1643 std::equal_to<T> comp; 1644 return equal_subtree(one_, two_, comp); 1645 } 1646 1647 template<class T, class tree_node_allocator> 1648 template<typename iter, class BinaryPredicate> 1649 bool tree<T, tree_node_allocator>::equal(const iter &one_, const iter &two, const iter &three_, 1650 BinaryPredicate fun) const 1651 { 1652 pre_order_iterator one(one_), three(three_); 1653 1654 // if(one==two && is_valid(three) && three.number_of_children()!=nullptr) 1655 // return false; 1656 while (one != two && is_valid(three)) { 1657 if (!fun(*one, *three)) 1658 return false; 1659 if (one.number_of_children() != three.number_of_children()) 1660 return false; 1661 ++one; 1662 ++three; 1663 } 1664 return true; 1665 } 1666 1667 template<class T, class tree_node_allocator> 1668 template<typename iter, class BinaryPredicate> 1669 bool tree<T, tree_node_allocator>::equal_subtree(const iter &one_, const iter &two_, 1670 BinaryPredicate fun) const 1671 { 1672 pre_order_iterator one(one_), two(two_); 1673 1674 if (!fun(*one, *two)) 1675 return false; 1676 if (number_of_children(one) != number_of_children(two)) 1677 return false; 1678 return equal(begin(one), end(one), begin(two), fun); 1679 } 1680 1681 template<class T, class tree_node_allocator> 1682 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, 1683 sibling_iterator to) const 1684 { 1685 tree tmp; 1686 tmp.set_head(value_type()); 1687 tmp.replace(tmp.begin(), tmp.end(), from, to); 1688 return tmp; 1689 } 1690 1691 template<class T, class tree_node_allocator> 1692 void tree<T, tree_node_allocator>::subtree(tree &tmp, sibling_iterator from, 1693 sibling_iterator to) const 1694 { 1695 tmp.set_head(value_type()); 1696 tmp.replace(tmp.begin(), tmp.end(), from, to); 1697 } 1698 1699 template<class T, class tree_node_allocator> 1700 int tree<T, tree_node_allocator>::size() const 1701 { 1702 int i = 0; 1703 pre_order_iterator it = begin(), eit = end(); 1704 while (it != eit) { 1705 ++i; 1706 ++it; 1707 } 1708 return i; 1709 } 1710 1711 template<class T, class tree_node_allocator> 1712 int tree<T, tree_node_allocator>::size(const iterator_base &top) const 1713 { 1714 int i = 0; 1715 pre_order_iterator it = top, eit = top; 1716 eit.skip_children(); 1717 ++eit; 1718 while (it != eit) { 1719 ++i; 1720 ++it; 1721 } 1722 return i; 1723 } 1724 1725 template<class T, class tree_node_allocator> 1726 bool tree<T, tree_node_allocator>::empty() const 1727 { 1728 pre_order_iterator it = begin(), eit = end(); 1729 return (it == eit); 1730 } 1731 1732 template<class T, class tree_node_allocator> 1733 int tree<T, tree_node_allocator>::depth(const iterator_base &it) const 1734 { 1735 tree_node *pos = it.node; 1736 assert(pos != nullptr); 1737 int ret = 0; 1738 while (pos->parent != nullptr) { 1739 pos = pos->parent; 1740 ++ret; 1741 } 1742 return ret; 1743 } 1744 1745 template<class T, class tree_node_allocator> 1746 int tree<T, tree_node_allocator>::max_depth() const 1747 { 1748 return max_depth(begin()); 1749 } 1750 1751 template<class T, class tree_node_allocator> 1752 int tree<T, tree_node_allocator>::max_depth(const iterator_base &pos) const 1753 { 1754 tree_node *tmp = pos.node; 1755 int curdepth = 0, maxdepth = 0; 1756 while (true) { // try to walk the bottom of the tree 1757 while (tmp->first_child == 0) { 1758 if (tmp == pos.node) 1759 return maxdepth; 1760 if (tmp->next_sibling == 0) { 1761 // try to walk up and then right again 1762 do { 1763 tmp = tmp->parent; 1764 if (tmp == 0) 1765 return maxdepth; 1766 --curdepth; 1767 } while (tmp->next_sibling == 0); 1768 } 1769 if (tmp == pos.node) 1770 return maxdepth; 1771 tmp = tmp->next_sibling; 1772 } 1773 tmp = tmp->first_child; 1774 ++curdepth; 1775 maxdepth = std::max(curdepth, maxdepth); 1776 } 1777 } 1778 1779 template<class T, class tree_node_allocator> 1780 unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base &it) 1781 { 1782 tree_node *pos = it.node->first_child; 1783 if (pos == 0) 1784 return 0; 1785 1786 unsigned int ret = 1; 1787 // while(pos!=it.node->last_child) { 1788 // ++ret; 1789 // pos=pos->next_sibling; 1790 // } 1791 while ((pos = pos->next_sibling)) 1792 ++ret; 1793 return ret; 1794 } 1795 1796 template<class T, class tree_node_allocator> 1797 unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base &it) const 1798 { 1799 tree_node *pos = it.node; 1800 unsigned int ret = 0; 1801 // count forward 1802 while (pos->next_sibling && pos->next_sibling != head && pos->next_sibling != feet) { 1803 ++ret; 1804 pos = pos->next_sibling; 1805 } 1806 // count backward 1807 pos = it.node; 1808 while (pos->prev_sibling && pos->prev_sibling != head && pos->prev_sibling != feet) { 1809 ++ret; 1810 pos = pos->prev_sibling; 1811 } 1812 1813 return ret; 1814 } 1815 1816 template<class T, class tree_node_allocator> 1817 void tree<T, tree_node_allocator>::swap(sibling_iterator it) 1818 { 1819 tree_node *nxt = it.node->next_sibling; 1820 if (nxt) { 1821 if (it.node->prev_sibling) 1822 it.node->prev_sibling->next_sibling = nxt; 1823 else 1824 it.node->parent->first_child = nxt; 1825 nxt->prev_sibling = it.node->prev_sibling; 1826 tree_node *nxtnxt = nxt->next_sibling; 1827 if (nxtnxt) 1828 nxtnxt->prev_sibling = it.node; 1829 else 1830 it.node->parent->last_child = it.node; 1831 nxt->next_sibling = it.node; 1832 it.node->prev_sibling = nxt; 1833 it.node->next_sibling = nxtnxt; 1834 } 1835 } 1836 1837 template<class T, class tree_node_allocator> 1838 void tree<T, tree_node_allocator>::swap(iterator one, iterator two) 1839 { 1840 // if one and two are adjacent siblings, use the sibling swap 1841 if (one.node->next_sibling == two.node) 1842 swap(one); 1843 else if (two.node->next_sibling == one.node) 1844 swap(two); 1845 else { 1846 tree_node *nxt1 = one.node->next_sibling; 1847 tree_node *nxt2 = two.node->next_sibling; 1848 tree_node *pre1 = one.node->prev_sibling; 1849 tree_node *pre2 = two.node->prev_sibling; 1850 tree_node *par1 = one.node->parent; 1851 tree_node *par2 = two.node->parent; 1852 1853 // reconnect 1854 one.node->parent = par2; 1855 one.node->next_sibling = nxt2; 1856 if (nxt2) 1857 nxt2->prev_sibling = one.node; 1858 else 1859 par2->last_child = one.node; 1860 one.node->prev_sibling = pre2; 1861 if (pre2) 1862 pre2->next_sibling = one.node; 1863 else 1864 par2->first_child = one.node; 1865 1866 two.node->parent = par1; 1867 two.node->next_sibling = nxt1; 1868 if (nxt1) 1869 nxt1->prev_sibling = two.node; 1870 else 1871 par1->last_child = two.node; 1872 two.node->prev_sibling = pre1; 1873 if (pre1) 1874 pre1->next_sibling = two.node; 1875 else 1876 par1->first_child = two.node; 1877 } 1878 } 1879 1880 // template <class BinaryPredicate> 1881 // tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree( 1882 // sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to, 1883 // BinaryPredicate fun) const 1884 // { 1885 // assert(1==0); // this routine is not finished yet. 1886 // while(from!=to) { 1887 // if(fun(*subfrom, *from)) { 1888 // 1889 // } 1890 // } 1891 // return to; 1892 // } 1893 1894 template<class T, class tree_node_allocator> 1895 bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base &it, 1896 const iterator_base &begin, 1897 const iterator_base &end) const 1898 { 1899 // FIXME: this should be optimised. 1900 pre_order_iterator tmp = begin; 1901 while (tmp != end) { 1902 if (tmp == it) 1903 return true; 1904 ++tmp; 1905 } 1906 return false; 1907 } 1908 1909 template<class T, class tree_node_allocator> 1910 bool tree<T, tree_node_allocator>::is_valid(const iterator_base &it) const 1911 { 1912 if (it.node == 0 || it.node == feet || it.node == head) 1913 return false; 1914 else 1915 return true; 1916 } 1917 1918 template<class T, class tree_node_allocator> 1919 unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const 1920 { 1921 unsigned int ind = 0; 1922 if (it.node->parent == 0) { 1923 while (it.node->prev_sibling != head) { 1924 it.node = it.node->prev_sibling; 1925 ++ind; 1926 } 1927 } else { 1928 while (it.node->prev_sibling != 0) { 1929 it.node = it.node->prev_sibling; 1930 ++ind; 1931 } 1932 } 1933 return ind; 1934 } 1935 1936 template<class T, class tree_node_allocator> 1937 typename tree<T, tree_node_allocator>::sibling_iterator 1938 tree<T, tree_node_allocator>::child(const iterator_base &it, unsigned int num) const 1939 { 1940 tree_node *tmp = it.node->first_child; 1941 while (num--) { 1942 assert(tmp != 0); 1943 tmp = tmp->next_sibling; 1944 } 1945 return tmp; 1946 } 1947 1948 // Iterator base 1949 1950 template<class T, class tree_node_allocator> 1951 tree<T, tree_node_allocator>::iterator_base::iterator_base() 1952 : node(0), skip_current_children_(false) 1953 { 1954 } 1955 1956 template<class T, class tree_node_allocator> 1957 tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn) 1958 : node(tn), skip_current_children_(false) 1959 { 1960 } 1961 1962 template<class T, class tree_node_allocator> 1963 T &tree<T, tree_node_allocator>::iterator_base::operator*() const 1964 { 1965 return node->data; 1966 } 1967 1968 template<class T, class tree_node_allocator> 1969 T *tree<T, tree_node_allocator>::iterator_base::operator->() const 1970 { 1971 return &(node->data); 1972 } 1973 1974 template<class T, class tree_node_allocator> 1975 bool tree<T, tree_node_allocator>::post_order_iterator::operator!=( 1976 const post_order_iterator &other) const 1977 { 1978 if (other.node != this->node) 1979 return true; 1980 else 1981 return false; 1982 } 1983 1984 template<class T, class tree_node_allocator> 1985 bool tree<T, tree_node_allocator>::post_order_iterator::operator==( 1986 const post_order_iterator &other) const 1987 { 1988 if (other.node == this->node) 1989 return true; 1990 else 1991 return false; 1992 } 1993 1994 template<class T, class tree_node_allocator> 1995 bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=( 1996 const pre_order_iterator &other) const 1997 { 1998 if (other.node != this->node) 1999 return true; 2000 else 2001 return false; 2002 } 2003 2004 template<class T, class tree_node_allocator> 2005 bool tree<T, tree_node_allocator>::pre_order_iterator::operator==( 2006 const pre_order_iterator &other) const 2007 { 2008 if (other.node == this->node) 2009 return true; 2010 else 2011 return false; 2012 } 2013 2014 template<class T, class tree_node_allocator> 2015 bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator &other) const 2016 { 2017 if (other.node != this->node) 2018 return true; 2019 else 2020 return false; 2021 } 2022 2023 template<class T, class tree_node_allocator> 2024 bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator &other) const 2025 { 2026 if (other.node == this->node) 2027 return true; 2028 else 2029 return false; 2030 } 2031 2032 template<class T, class tree_node_allocator> 2033 bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const leaf_iterator &other) const 2034 { 2035 if (other.node != this->node) 2036 return true; 2037 else 2038 return false; 2039 } 2040 2041 template<class T, class tree_node_allocator> 2042 bool tree<T, tree_node_allocator>::leaf_iterator::operator==(const leaf_iterator &other) const 2043 { 2044 if (other.node == this->node) 2045 return true; 2046 else 2047 return false; 2048 } 2049 2050 template<class T, class tree_node_allocator> 2051 typename tree<T, tree_node_allocator>::sibling_iterator 2052 tree<T, tree_node_allocator>::iterator_base::begin() const 2053 { 2054 if (node->first_child == 0) 2055 return end(); 2056 2057 sibling_iterator ret(node->first_child); 2058 ret.parent_ = this->node; 2059 return ret; 2060 } 2061 2062 template<class T, class tree_node_allocator> 2063 typename tree<T, tree_node_allocator>::sibling_iterator 2064 tree<T, tree_node_allocator>::iterator_base::end() const 2065 { 2066 sibling_iterator ret(0); 2067 ret.parent_ = node; 2068 return ret; 2069 } 2070 2071 template<class T, class tree_node_allocator> 2072 void tree<T, tree_node_allocator>::iterator_base::skip_children() 2073 { 2074 skip_current_children_ = true; 2075 } 2076 2077 template<class T, class tree_node_allocator> 2078 unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const 2079 { 2080 tree_node *pos = node->first_child; 2081 if (pos == 0) 2082 return 0; 2083 2084 unsigned int ret = 1; 2085 while (pos != node->last_child) { 2086 ++ret; 2087 pos = pos->next_sibling; 2088 } 2089 return ret; 2090 } 2091 2092 // Pre-order iterator 2093 2094 template<class T, class tree_node_allocator> 2095 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator() : iterator_base(nullptr) 2096 { 2097 } 2098 2099 template<class T, class tree_node_allocator> 2100 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn) 2101 : iterator_base(tn) 2102 { 2103 } 2104 2105 template<class T, class tree_node_allocator> 2106 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const iterator_base &other) 2107 : iterator_base(other.node) 2108 { 2109 } 2110 2111 template<class T, class tree_node_allocator> 2112 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator &other) 2113 : iterator_base(other.node) 2114 { 2115 if (this->node == nullptr) { 2116 if (other.range_last() != nullptr) 2117 this->node = other.range_last(); 2118 else 2119 this->node = other.parent_; 2120 this->skip_children(); 2121 ++(*this); 2122 } 2123 } 2124 2125 template<class T, class tree_node_allocator> 2126 typename tree<T, tree_node_allocator>::pre_order_iterator & 2127 tree<T, tree_node_allocator>::pre_order_iterator::operator++() 2128 { 2129 assert(this->node != nullptr); 2130 if (!this->skip_current_children_ && this->node->first_child != nullptr) { 2131 this->node = this->node->first_child; 2132 } else { 2133 this->skip_current_children_ = false; 2134 while (this->node->next_sibling == nullptr) { 2135 this->node = this->node->parent; 2136 if (this->node == nullptr) 2137 return *this; 2138 } 2139 this->node = this->node->next_sibling; 2140 } 2141 return *this; 2142 } 2143 2144 template<class T, class tree_node_allocator> 2145 typename tree<T, tree_node_allocator>::pre_order_iterator & 2146 tree<T, tree_node_allocator>::pre_order_iterator::operator--() 2147 { 2148 assert(this->node != 0); 2149 if (this->node->prev_sibling) { 2150 this->node = this->node->prev_sibling; 2151 while (this->node->last_child) 2152 this->node = this->node->last_child; 2153 } else { 2154 this->node = this->node->parent; 2155 if (this->node == 0) 2156 return *this; 2157 } 2158 return *this; 2159 } 2160 2161 template<class T, class tree_node_allocator> 2162 typename tree<T, tree_node_allocator>::pre_order_iterator 2163 tree<T, tree_node_allocator>::pre_order_iterator::operator++(int) 2164 { 2165 pre_order_iterator copy = *this; 2166 ++(*this); 2167 return copy; 2168 } 2169 2170 template<class T, class tree_node_allocator> 2171 typename tree<T, tree_node_allocator>::pre_order_iterator 2172 tree<T, tree_node_allocator>::pre_order_iterator::operator--(int) 2173 { 2174 pre_order_iterator copy = *this; 2175 --(*this); 2176 return copy; 2177 } 2178 2179 template<class T, class tree_node_allocator> 2180 typename tree<T, tree_node_allocator>::pre_order_iterator & 2181 tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num) 2182 { 2183 while (num > 0) { 2184 ++(*this); 2185 --num; 2186 } 2187 return (*this); 2188 } 2189 2190 template<class T, class tree_node_allocator> 2191 typename tree<T, tree_node_allocator>::pre_order_iterator & 2192 tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num) 2193 { 2194 while (num > 0) { 2195 --(*this); 2196 --num; 2197 } 2198 return (*this); 2199 } 2200 2201 // Post-order iterator 2202 2203 template<class T, class tree_node_allocator> 2204 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator() : iterator_base(0) 2205 { 2206 } 2207 2208 template<class T, class tree_node_allocator> 2209 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn) 2210 : iterator_base(tn) 2211 { 2212 } 2213 2214 template<class T, class tree_node_allocator> 2215 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const iterator_base &other) 2216 : iterator_base(other.node) 2217 { 2218 } 2219 2220 template<class T, class tree_node_allocator> 2221 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator( 2222 const sibling_iterator &other) 2223 : iterator_base(other.node) 2224 { 2225 if (this->node == 0) { 2226 if (other.range_last() != 0) 2227 this->node = other.range_last(); 2228 else 2229 this->node = other.parent_; 2230 this->skip_children(); 2231 ++(*this); 2232 } 2233 } 2234 2235 template<class T, class tree_node_allocator> 2236 typename tree<T, tree_node_allocator>::post_order_iterator & 2237 tree<T, tree_node_allocator>::post_order_iterator::operator++() 2238 { 2239 assert(this->node != 0); 2240 if (this->node->next_sibling == 0) { 2241 this->node = this->node->parent; 2242 this->skip_current_children_ = false; 2243 } else { 2244 this->node = this->node->next_sibling; 2245 if (this->skip_current_children_) { 2246 this->skip_current_children_ = false; 2247 } else { 2248 while (this->node->first_child) 2249 this->node = this->node->first_child; 2250 } 2251 } 2252 return *this; 2253 } 2254 2255 template<class T, class tree_node_allocator> 2256 typename tree<T, tree_node_allocator>::post_order_iterator & 2257 tree<T, tree_node_allocator>::post_order_iterator::operator--() 2258 { 2259 assert(this->node != 0); 2260 if (this->skip_current_children_ || this->node->last_child == 0) { 2261 this->skip_current_children_ = false; 2262 while (this->node->prev_sibling == 0) 2263 this->node = this->node->parent; 2264 this->node = this->node->prev_sibling; 2265 } else { 2266 this->node = this->node->last_child; 2267 } 2268 return *this; 2269 } 2270 2271 template<class T, class tree_node_allocator> 2272 typename tree<T, tree_node_allocator>::post_order_iterator 2273 tree<T, tree_node_allocator>::post_order_iterator::operator++(int) 2274 { 2275 post_order_iterator copy = *this; 2276 ++(*this); 2277 return copy; 2278 } 2279 2280 template<class T, class tree_node_allocator> 2281 typename tree<T, tree_node_allocator>::post_order_iterator 2282 tree<T, tree_node_allocator>::post_order_iterator::operator--(int) 2283 { 2284 post_order_iterator copy = *this; 2285 --(*this); 2286 return copy; 2287 } 2288 2289 template<class T, class tree_node_allocator> 2290 typename tree<T, tree_node_allocator>::post_order_iterator & 2291 tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num) 2292 { 2293 while (num > 0) { 2294 ++(*this); 2295 --num; 2296 } 2297 return (*this); 2298 } 2299 2300 template<class T, class tree_node_allocator> 2301 typename tree<T, tree_node_allocator>::post_order_iterator & 2302 tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num) 2303 { 2304 while (num > 0) { 2305 --(*this); 2306 --num; 2307 } 2308 return (*this); 2309 } 2310 2311 template<class T, class tree_node_allocator> 2312 void tree<T, tree_node_allocator>::post_order_iterator::descend_all() 2313 { 2314 assert(this->node != 0); 2315 while (this->node->first_child) 2316 this->node = this->node->first_child; 2317 } 2318 2319 // Breadth-first iterator 2320 2321 template<class T, class tree_node_allocator> 2322 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator() 2323 : iterator_base() 2324 { 2325 } 2326 2327 template<class T, class tree_node_allocator> 2328 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator( 2329 tree_node *tn) 2330 : iterator_base(tn) 2331 { 2332 traversal_queue.push(tn); 2333 } 2334 2335 template<class T, class tree_node_allocator> 2336 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator( 2337 const iterator_base &other) 2338 : iterator_base(other.node) 2339 { 2340 traversal_queue.push(other.node); 2341 } 2342 2343 template<class T, class tree_node_allocator> 2344 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator!=( 2345 const breadth_first_queued_iterator &other) const 2346 { 2347 if (other.node != this->node) 2348 return true; 2349 else 2350 return false; 2351 } 2352 2353 template<class T, class tree_node_allocator> 2354 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator==( 2355 const breadth_first_queued_iterator &other) const 2356 { 2357 if (other.node == this->node) 2358 return true; 2359 else 2360 return false; 2361 } 2362 2363 template<class T, class tree_node_allocator> 2364 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator & 2365 tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++() 2366 { 2367 assert(this->node != 0); 2368 2369 // Add child nodes and pop current node 2370 sibling_iterator sib = this->begin(); 2371 while (sib != this->end()) { 2372 traversal_queue.push(sib.node); 2373 ++sib; 2374 } 2375 traversal_queue.pop(); 2376 if (traversal_queue.size() > 0) 2377 this->node = traversal_queue.front(); 2378 else 2379 this->node = 0; 2380 return (*this); 2381 } 2382 2383 template<class T, class tree_node_allocator> 2384 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator 2385 tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++(int) 2386 { 2387 breadth_first_queued_iterator copy = *this; 2388 ++(*this); 2389 return copy; 2390 } 2391 2392 template<class T, class tree_node_allocator> 2393 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator & 2394 tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int num) 2395 { 2396 while (num > 0) { 2397 ++(*this); 2398 --num; 2399 } 2400 return (*this); 2401 } 2402 2403 // Fixed depth iterator 2404 2405 template<class T, class tree_node_allocator> 2406 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator() : iterator_base() 2407 { 2408 set_first_parent_(); 2409 } 2410 2411 template<class T, class tree_node_allocator> 2412 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn) 2413 : iterator_base(tn) 2414 { 2415 set_first_parent_(); 2416 } 2417 2418 template<class T, class tree_node_allocator> 2419 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const iterator_base &other) 2420 : iterator_base(other.node) 2421 { 2422 set_first_parent_(); 2423 } 2424 2425 template<class T, class tree_node_allocator> 2426 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator( 2427 const sibling_iterator &other) 2428 : iterator_base(other.node), first_parent_(other.parent_) 2429 { 2430 find_leftmost_parent_(); 2431 } 2432 2433 template<class T, class tree_node_allocator> 2434 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator( 2435 const fixed_depth_iterator &other) 2436 : iterator_base(other.node), first_parent_(other.first_parent_) 2437 { 2438 } 2439 2440 template<class T, class tree_node_allocator> 2441 bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator==( 2442 const fixed_depth_iterator &other) const 2443 { 2444 if (other.node == this->node && other.first_parent_ == first_parent_) 2445 return true; 2446 else 2447 return false; 2448 } 2449 2450 template<class T, class tree_node_allocator> 2451 bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator!=( 2452 const fixed_depth_iterator &other) const 2453 { 2454 if (other.node != this->node || other.first_parent_ != first_parent_) 2455 return true; 2456 else 2457 return false; 2458 } 2459 2460 template<class T, class tree_node_allocator> 2461 void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_() 2462 { 2463 return; // FIXME: we do not use first_parent_ yet, and it actually needs some serious reworking 2464 // if it is ever to work at the 'head' level. 2465 first_parent_ = 0; 2466 if (this->node == 0) 2467 return; 2468 if (this->node->parent != 0) 2469 first_parent_ = this->node->parent; 2470 if (first_parent_) 2471 find_leftmost_parent_(); 2472 } 2473 2474 template<class T, class tree_node_allocator> 2475 void tree<T, tree_node_allocator>::fixed_depth_iterator::find_leftmost_parent_() 2476 { 2477 return; // FIXME: see 'set_first_parent()' 2478 tree_node *tmppar = first_parent_; 2479 while (tmppar->prev_sibling) { 2480 tmppar = tmppar->prev_sibling; 2481 if (tmppar->first_child) 2482 first_parent_ = tmppar; 2483 } 2484 } 2485 2486 template<class T, class tree_node_allocator> 2487 typename tree<T, tree_node_allocator>::fixed_depth_iterator & 2488 tree<T, tree_node_allocator>::fixed_depth_iterator::operator++() 2489 { 2490 assert(this->node != 0); 2491 2492 if (this->node->next_sibling) { 2493 this->node = this->node->next_sibling; 2494 } else { 2495 int relative_depth = 0; 2496 upper: 2497 do { 2498 this->node = this->node->parent; 2499 if (this->node == 0) 2500 return *this; 2501 --relative_depth; 2502 } while (this->node->next_sibling == 0); 2503 lower: 2504 this->node = this->node->next_sibling; 2505 while (this->node->first_child == 0) { 2506 if (this->node->next_sibling == 0) 2507 goto upper; 2508 this->node = this->node->next_sibling; 2509 if (this->node == 0) 2510 return *this; 2511 } 2512 while (relative_depth < 0 && this->node->first_child != 0) { 2513 this->node = this->node->first_child; 2514 ++relative_depth; 2515 } 2516 if (relative_depth < 0) { 2517 if (this->node->next_sibling == 0) 2518 goto upper; 2519 else 2520 goto lower; 2521 } 2522 } 2523 return *this; 2524 2525 // if(this->node->next_sibling!=0) { 2526 // this->node=this->node->next_sibling; 2527 // assert(this->node!=0); 2528 // if(this->node->parent==0 && this->node->next_sibling==0) // feet element 2529 // this->node=0; 2530 // } 2531 // else { 2532 // tree_node *par=this->node->parent; 2533 // do { 2534 // par=par->next_sibling; 2535 // if(par==0) { // FIXME: need to keep track of this! 2536 // this->node=0; 2537 // return *this; 2538 // } 2539 // } while(par->first_child==0); 2540 // this->node=par->first_child; 2541 // } 2542 return *this; 2543 } 2544 2545 template<class T, class tree_node_allocator> 2546 typename tree<T, tree_node_allocator>::fixed_depth_iterator & 2547 tree<T, tree_node_allocator>::fixed_depth_iterator::operator--() 2548 { 2549 assert(this->node != 0); 2550 if (this->node->prev_sibling != 0) { 2551 this->node = this->node->prev_sibling; 2552 assert(this->node != 0); 2553 if (this->node->parent == 0 && this->node->prev_sibling == 0) // head element 2554 this->node = 0; 2555 } else { 2556 tree_node *par = this->node->parent; 2557 do { 2558 par = par->prev_sibling; 2559 if (par == 0) { // FIXME: need to keep track of this! 2560 this->node = 0; 2561 return *this; 2562 } 2563 } while (par->last_child == 0); 2564 this->node = par->last_child; 2565 } 2566 return *this; 2567 } 2568 2569 template<class T, class tree_node_allocator> 2570 typename tree<T, tree_node_allocator>::fixed_depth_iterator 2571 tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(int) 2572 { 2573 fixed_depth_iterator copy = *this; 2574 ++(*this); 2575 return copy; 2576 } 2577 2578 template<class T, class tree_node_allocator> 2579 typename tree<T, tree_node_allocator>::fixed_depth_iterator 2580 tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(int) 2581 { 2582 fixed_depth_iterator copy = *this; 2583 --(*this); 2584 return copy; 2585 } 2586 2587 template<class T, class tree_node_allocator> 2588 typename tree<T, tree_node_allocator>::fixed_depth_iterator & 2589 tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num) 2590 { 2591 while (num > 0) { 2592 --(*this); 2593 --(num); 2594 } 2595 return (*this); 2596 } 2597 2598 template<class T, class tree_node_allocator> 2599 typename tree<T, tree_node_allocator>::fixed_depth_iterator & 2600 tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num) 2601 { 2602 while (num > 0) { 2603 ++(*this); 2604 --(num); 2605 } 2606 return *this; 2607 } 2608 2609 // FIXME: add the other members of fixed_depth_iterator. 2610 2611 // Sibling iterator 2612 2613 template<class T, class tree_node_allocator> 2614 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator() : iterator_base() 2615 { 2616 set_parent_(); 2617 } 2618 2619 template<class T, class tree_node_allocator> 2620 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn) : iterator_base(tn) 2621 { 2622 set_parent_(); 2623 } 2624 2625 template<class T, class tree_node_allocator> 2626 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const iterator_base &other) 2627 : iterator_base(other.node) 2628 { 2629 set_parent_(); 2630 } 2631 2632 template<class T, class tree_node_allocator> 2633 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const sibling_iterator &) = 2634 default; 2635 2636 template<class T, class tree_node_allocator> 2637 void tree<T, tree_node_allocator>::sibling_iterator::set_parent_() 2638 { 2639 parent_ = nullptr; 2640 if (this->node == nullptr) 2641 return; 2642 if (this->node->parent != nullptr) 2643 parent_ = this->node->parent; 2644 } 2645 2646 template<class T, class tree_node_allocator> 2647 typename tree<T, tree_node_allocator>::sibling_iterator & 2648 tree<T, tree_node_allocator>::sibling_iterator::operator++() 2649 { 2650 if (this->node) 2651 this->node = this->node->next_sibling; 2652 return *this; 2653 } 2654 2655 template<class T, class tree_node_allocator> 2656 typename tree<T, tree_node_allocator>::sibling_iterator & 2657 tree<T, tree_node_allocator>::sibling_iterator::operator--() 2658 { 2659 if (this->node) 2660 this->node = this->node->prev_sibling; 2661 else { 2662 assert(parent_); 2663 this->node = parent_->last_child; 2664 } 2665 return *this; 2666 } 2667 2668 template<class T, class tree_node_allocator> 2669 typename tree<T, tree_node_allocator>::sibling_iterator 2670 tree<T, tree_node_allocator>::sibling_iterator::operator++(int) 2671 { 2672 sibling_iterator copy = *this; 2673 ++(*this); 2674 return copy; 2675 } 2676 2677 template<class T, class tree_node_allocator> 2678 typename tree<T, tree_node_allocator>::sibling_iterator 2679 tree<T, tree_node_allocator>::sibling_iterator::operator--(int) 2680 { 2681 sibling_iterator copy = *this; 2682 --(*this); 2683 return copy; 2684 } 2685 2686 template<class T, class tree_node_allocator> 2687 typename tree<T, tree_node_allocator>::sibling_iterator & 2688 tree<T, tree_node_allocator>::sibling_iterator::operator+=(unsigned int num) 2689 { 2690 while (num > 0) { 2691 ++(*this); 2692 --num; 2693 } 2694 return (*this); 2695 } 2696 2697 template<class T, class tree_node_allocator> 2698 typename tree<T, tree_node_allocator>::sibling_iterator & 2699 tree<T, tree_node_allocator>::sibling_iterator::operator-=(unsigned int num) 2700 { 2701 while (num > 0) { 2702 --(*this); 2703 --num; 2704 } 2705 return (*this); 2706 } 2707 2708 template<class T, class tree_node_allocator> 2709 typename tree<T, tree_node_allocator>::tree_node * 2710 tree<T, tree_node_allocator>::sibling_iterator::range_first() const 2711 { 2712 tree_node *tmp = parent_->first_child; 2713 return tmp; 2714 } 2715 2716 template<class T, class tree_node_allocator> 2717 typename tree<T, tree_node_allocator>::tree_node * 2718 tree<T, tree_node_allocator>::sibling_iterator::range_last() const 2719 { 2720 return parent_->last_child; 2721 } 2722 2723 // Leaf iterator 2724 2725 template<class T, class tree_node_allocator> 2726 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator() : iterator_base(0) 2727 { 2728 } 2729 2730 template<class T, class tree_node_allocator> 2731 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(tree_node *tn) : iterator_base(tn) 2732 { 2733 } 2734 2735 template<class T, class tree_node_allocator> 2736 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const iterator_base &other) 2737 : iterator_base(other.node) 2738 { 2739 } 2740 2741 template<class T, class tree_node_allocator> 2742 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const sibling_iterator &other) 2743 : iterator_base(other.node) 2744 { 2745 if (this->node == nullptr) { 2746 if (other.range_last() != nullptr) 2747 this->node = other.range_last(); 2748 else 2749 this->node = other.parent_; 2750 ++(*this); 2751 } 2752 } 2753 2754 template<class T, class tree_node_allocator> 2755 typename tree<T, tree_node_allocator>::leaf_iterator & 2756 tree<T, tree_node_allocator>::leaf_iterator::operator++() 2757 { 2758 assert(this->node != nullptr); 2759 while (this->node->next_sibling == nullptr) { 2760 if (this->node->parent == nullptr) 2761 return *this; 2762 this->node = this->node->parent; 2763 } 2764 this->node = this->node->next_sibling; 2765 while (this->node->first_child) 2766 this->node = this->node->first_child; 2767 return *this; 2768 } 2769 2770 template<class T, class tree_node_allocator> 2771 typename tree<T, tree_node_allocator>::leaf_iterator & 2772 tree<T, tree_node_allocator>::leaf_iterator::operator--() 2773 { 2774 assert(this->node != nullptr); 2775 while (this->node->prev_sibling == nullptr) { 2776 if (this->node->parent == nullptr) 2777 return *this; 2778 this->node = this->node->parent; 2779 } 2780 this->node = this->node->prev_sibling; 2781 while (this->node->last_child) 2782 this->node = this->node->last_child; 2783 return *this; 2784 } 2785 2786 template<class T, class tree_node_allocator> 2787 typename tree<T, tree_node_allocator>::leaf_iterator 2788 tree<T, tree_node_allocator>::leaf_iterator::operator++(int) 2789 { 2790 leaf_iterator copy = *this; 2791 ++(*this); 2792 return copy; 2793 } 2794 2795 template<class T, class tree_node_allocator> 2796 typename tree<T, tree_node_allocator>::leaf_iterator 2797 tree<T, tree_node_allocator>::leaf_iterator::operator--(int) 2798 { 2799 leaf_iterator copy = *this; 2800 --(*this); 2801 return copy; 2802 } 2803 2804 template<class T, class tree_node_allocator> 2805 typename tree<T, tree_node_allocator>::leaf_iterator & 2806 tree<T, tree_node_allocator>::leaf_iterator::operator+=(unsigned int num) 2807 { 2808 while (num > 0) { 2809 ++(*this); 2810 --num; 2811 } 2812 return (*this); 2813 } 2814 2815 template<class T, class tree_node_allocator> 2816 typename tree<T, tree_node_allocator>::leaf_iterator & 2817 tree<T, tree_node_allocator>::leaf_iterator::operator-=(unsigned int num) 2818 { 2819 while (num > 0) { 2820 --(*this); 2821 --num; 2822 } 2823 return (*this); 2824 } 2825 2826 #endif 2827 2828 // Local variables: 2829 // default-tab-width: 3 2830 // End: