FastJet 3.0.2
|
00001 //STARTHEADER 00002 // $Id: SearchTree.hh 2577 2011-09-13 15:11:38Z salam $ 00003 // 00004 // Copyright (c) 2005-2011, Matteo Cacciari, Gavin P. Salam and Gregory Soyez 00005 // 00006 //---------------------------------------------------------------------- 00007 // This file is part of FastJet. 00008 // 00009 // FastJet is free software; you can redistribute it and/or modify 00010 // it under the terms of the GNU General Public License as published by 00011 // the Free Software Foundation; either version 2 of the License, or 00012 // (at your option) any later version. 00013 // 00014 // The algorithms that underlie FastJet have required considerable 00015 // development and are described in hep-ph/0512210. If you use 00016 // FastJet as part of work towards a scientific publication, please 00017 // include a citation to the FastJet paper. 00018 // 00019 // FastJet 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 FastJet. If not, see <http://www.gnu.org/licenses/>. 00026 //---------------------------------------------------------------------- 00027 //ENDHEADER 00028 00029 00030 #ifndef __FASTJET_SEARCHTREE_HH__ 00031 #define __FASTJET_SEARCHTREE_HH__ 00032 00033 #include<vector> 00034 #include<cassert> 00035 #include<cstddef> 00036 #include "fastjet/internal/base.hh" 00037 00038 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh 00039 00040 00041 //====================================================================== 00042 /// \if internal_doc 00043 /// @ingroup internal 00044 /// \class SearchTree 00045 /// Efficient class for a search tree 00046 /// 00047 /// This is the class for a search tree designed to be especially efficient 00048 /// when looking for successors and predecessors (to be used in Chan's 00049 /// CP algorithm). It has the requirement that the maximum size of the 00050 /// search tree must be known in advance. 00051 /// \endif 00052 template<class T> class SearchTree { 00053 public: 00054 00055 class Node; 00056 class circulator; 00057 class const_circulator; 00058 00059 /// constructor for a search tree from an ordered vector 00060 SearchTree(const std::vector<T> & init); 00061 00062 /// constructor for a search tree from an ordered vector allowing 00063 /// for future growth beyond the current size, up to max_size 00064 SearchTree(const std::vector<T> & init, unsigned int max_size); 00065 00066 /// remove the node corresponding to node_index from the search tree 00067 void remove(unsigned node_index); 00068 void remove(typename SearchTree::Node * node); 00069 void remove(typename SearchTree::circulator & circ); 00070 00071 /// insert the supplied value into the tree and return a pointer to 00072 /// the relevant SearchTreeNode. 00073 //Node * insert(const T & value); 00074 circulator insert(const T & value); 00075 00076 const Node & operator[](int i) const {return _nodes[i];}; 00077 00078 /// return the number of elements currently in the search tree 00079 unsigned int size() const {return _nodes.size() - _available_nodes.size();} 00080 00081 /// check that the structure we've obtained makes sense... 00082 void verify_structure(); 00083 void verify_structure_linear() const; 00084 void verify_structure_recursive(const Node * , const Node * , const Node * ) const; 00085 00086 /// print out all elements... 00087 void print_elements(); 00088 00089 // tracking the depth may have some speed overhead -- so leave it 00090 // out for the time being... 00091 #ifdef TRACK_DEPTH 00092 /// the max depth the tree has ever reached 00093 inline unsigned int max_depth() const {return _max_depth;}; 00094 #else 00095 inline unsigned int max_depth() const {return 0;}; 00096 #endif 00097 00098 int loc(const Node * node) const ; 00099 00100 /// return predecessor by walking through the tree 00101 Node * _find_predecessor(const Node *); 00102 /// return successor by walking through the tree 00103 Node * _find_successor(const Node *); 00104 00105 const Node & operator[](unsigned int i) const {return _nodes[i];}; 00106 00107 /// return a circulator to some place in the tree (with a circulator 00108 /// you don't care where...) 00109 const_circulator somewhere() const; 00110 circulator somewhere(); 00111 00112 private: 00113 00114 void _initialize(const std::vector<T> & init); 00115 00116 std::vector<Node> _nodes; 00117 std::vector<Node *> _available_nodes; 00118 Node * _top_node; 00119 unsigned int _n_removes; 00120 00121 00122 /// recursive routine for doing the initial connections assuming things 00123 /// are ordered. Assumes this_one's parent is labelled, and was 00124 /// generated at a scale "scale" -- connections will be carried out 00125 /// including left edge and excluding right edge 00126 void _do_initial_connections(unsigned int this_one, unsigned int scale, 00127 unsigned int left_edge, unsigned int right_edge, 00128 unsigned int depth); 00129 00130 00131 #ifdef TRACK_DEPTH 00132 unsigned int _max_depth; 00133 #endif 00134 00135 }; 00136 00137 00138 //====================================================================== 00139 /// \if internal_doc 00140 /// @ingroup internal 00141 /// \class SearchTree::Node 00142 /// A node in the search tree 00143 /// \endif 00144 template<class T> class SearchTree<T>::Node{ 00145 public: 00146 Node() {}; /// default constructor 00147 00148 00149 /// returns tree if all the tree-related links are set to null for this node 00150 bool treelinks_null() const { 00151 return ((parent==0) && (left==0) && (right==0));}; 00152 00153 /// set all the tree-related links are set to null for this node 00154 inline void nullify_treelinks() { 00155 parent = NULL; 00156 left = NULL; 00157 right = NULL; 00158 }; 00159 00160 /// if my parent exists, determine whether I am it's left or right 00161 /// node and set the relevant link equal to XX. 00162 void reset_parents_link_to_me(Node * XX); 00163 00164 T value; 00165 Node * left; 00166 Node * right; 00167 Node * parent; 00168 Node * successor; 00169 Node * predecessor; 00170 }; 00171 00172 //---------------------------------------------------------------------- 00173 template<class T> void SearchTree<T>::Node::reset_parents_link_to_me(typename SearchTree<T>::Node * XX) { 00174 if (parent == NULL) {return;} 00175 if (parent->right == this) {parent->right = XX;} 00176 else {parent->left = XX;} 00177 } 00178 00179 00180 00181 //====================================================================== 00182 /// \if internal_doc 00183 /// @ingroup internal 00184 /// \class SearchTree::circulator 00185 /// circulator for the search tree 00186 /// \endif 00187 template<class T> class SearchTree<T>::circulator{ 00188 public: 00189 00190 // so that it can access out _node object; 00191 friend class SearchTree<T>::const_circulator; 00192 friend class SearchTree<T>; 00193 00194 circulator() : _node(NULL) {} 00195 00196 circulator(Node * node) : _node(node) {} 00197 00198 const T * operator->() const {return &(_node->value);} 00199 T * operator->() {return &(_node->value);} 00200 const T & operator*() const {return _node->value;} 00201 T & operator*() {return _node->value;} 00202 00203 /// prefix increment (structure copied from stl_bvector.h) 00204 circulator & operator++() { 00205 _node = _node->successor; 00206 return *this;} 00207 00208 /// postfix increment ["int" argument tells compiler it's postfix] 00209 /// (structure copied from stl_bvector.h) 00210 circulator operator++(int) { 00211 circulator tmp = *this; 00212 _node = _node->successor; 00213 return tmp;} 00214 00215 /// prefix decrement (structure copied from stl_bvector.h) 00216 circulator & operator--() { 00217 _node = _node->predecessor; 00218 return *this;} 00219 00220 /// postfix decrement ["int" argument tells compiler it's postfix] 00221 /// (structure copied from stl_bvector.h) 00222 circulator operator--(int) { 00223 circulator tmp = *this; 00224 _node = _node->predecessor; 00225 return tmp;} 00226 00227 /// return a circulator referring to the next node 00228 circulator next() const { 00229 return circulator(_node->successor);} 00230 00231 /// return a circulator referring to the previous node 00232 circulator previous() const { 00233 return circulator(_node->predecessor);} 00234 00235 bool operator!=(const circulator & other) const {return other._node != _node;} 00236 bool operator==(const circulator & other) const {return other._node == _node;} 00237 00238 private: 00239 Node * _node; 00240 }; 00241 00242 00243 //====================================================================== 00244 /// \if internal_doc 00245 /// @ingroup internal 00246 /// \class SearchTree::const_circulator 00247 /// A const_circulator for the search tree 00248 /// \endif 00249 template<class T> class SearchTree<T>::const_circulator{ 00250 public: 00251 00252 const_circulator() : _node(NULL) {} 00253 00254 const_circulator(const Node * node) : _node(node) {} 00255 const_circulator(const circulator & circ) :_node(circ._node) {} 00256 00257 const T * operator->() {return &(_node->value);} 00258 const T & operator*() const {return _node->value;} 00259 00260 /// prefix increment (structure copied from stl_bvector.h) 00261 const_circulator & operator++() { 00262 _node = _node->successor; 00263 return *this;} 00264 00265 /// postfix increment ["int" argument tells compiler it's postfix] 00266 /// (structure copied from stl_bvector.h) 00267 const_circulator operator++(int) { 00268 const_circulator tmp = *this; 00269 _node = _node->successor; 00270 return tmp;} 00271 00272 00273 /// prefix decrement (structure copied from stl_bvector.h) 00274 const_circulator & operator--() { 00275 _node = _node->predecessor; 00276 return *this;} 00277 00278 /// postfix decrement ["int" argument tells compiler it's postfix] 00279 /// (structure copied from stl_bvector.h) 00280 const_circulator operator--(int) { 00281 const_circulator tmp = *this; 00282 _node = _node->predecessor; 00283 return tmp;} 00284 00285 /// return a circulator referring to the next node 00286 const_circulator next() const { 00287 return const_circulator(_node->successor);} 00288 00289 /// return a circulator referring to the previous node 00290 const_circulator previous() const { 00291 return const_circulator(_node->predecessor);} 00292 00293 00294 00295 bool operator!=(const const_circulator & other) const {return other._node != _node;} 00296 bool operator==(const const_circulator & other) const {return other._node == _node;} 00297 00298 private: 00299 const Node * _node; 00300 }; 00301 00302 00303 00304 00305 //---------------------------------------------------------------------- 00306 /// initialise from a sorted initial array allowing for a larger 00307 /// maximum size of the array... 00308 template<class T> SearchTree<T>::SearchTree(const std::vector<T> & init, 00309 unsigned int max_size) : 00310 _nodes(max_size) { 00311 00312 _available_nodes.reserve(max_size); 00313 _available_nodes.resize(max_size - init.size()); 00314 for (unsigned int i = init.size(); i < max_size; i++) { 00315 _available_nodes[i-init.size()] = &(_nodes[i]); 00316 } 00317 00318 _initialize(init); 00319 } 00320 00321 //---------------------------------------------------------------------- 00322 /// initialise from a sorted initial array 00323 template<class T> SearchTree<T>::SearchTree(const std::vector<T> & init) : 00324 _nodes(init.size()), _available_nodes(0) { 00325 00326 // reserve space for the list of available nodes 00327 _available_nodes.reserve(init.size()); 00328 _initialize(init); 00329 } 00330 00331 //---------------------------------------------------------------------- 00332 /// do the actual hard work of initialization 00333 template<class T> void SearchTree<T>::_initialize(const std::vector<T> & init) { 00334 00335 _n_removes = 0; 00336 unsigned n = init.size(); 00337 assert(n>=1); 00338 00339 // reserve space for the list of available nodes 00340 //_available_nodes.reserve(); 00341 00342 #ifdef TRACK_DEPTH 00343 _max_depth = 0; 00344 #endif 00345 00346 00347 // validate the input 00348 for (unsigned int i = 1; i<n; i++) { 00349 assert(!(init[i] < init[i-1])); 00350 } 00351 00352 // now initialise the vector; link neighbours in the sequence 00353 for(unsigned int i = 0; i < n; i++) { 00354 _nodes[i].value = init[i]; 00355 _nodes[i].predecessor = (& (_nodes[i])) - 1; 00356 _nodes[i].successor = (& (_nodes[i])) + 1; 00357 _nodes[i].nullify_treelinks(); 00358 } 00359 // make a loop structure so that we can circulate... 00360 _nodes[0].predecessor = (& (_nodes[n-1])); 00361 _nodes[n-1].successor = (& (_nodes[0])); 00362 00363 // now label the rest of the nodes 00364 unsigned int scale = (n+1)/2; 00365 unsigned int top = std::min(n-1,scale); 00366 _nodes[top].parent = NULL; 00367 _top_node = &(_nodes[top]); 00368 _do_initial_connections(top, scale, 0, n, 0); 00369 00370 // make sure things are sensible... 00371 //verify_structure(); 00372 } 00373 00374 00375 00376 //---------------------------------------------------------------------- 00377 template<class T> inline int SearchTree<T>::loc(const Node * node) const {return node == NULL? 00378 -999 : node - &(_nodes[0]);} 00379 00380 00381 //---------------------------------------------------------------------- 00382 /// Recursive creation of connections, assuming the _nodes vector is 00383 /// completely filled and ordered 00384 template<class T> void SearchTree<T>::_do_initial_connections( 00385 unsigned int this_one, 00386 unsigned int scale, 00387 unsigned int left_edge, 00388 unsigned int right_edge, 00389 unsigned int depth 00390 ) { 00391 00392 #ifdef TRACK_DEPTH 00393 // keep track of tree depth for checking things stay reasonable... 00394 _max_depth = max(depth, _max_depth); 00395 #endif 00396 00397 //std::cout << this_one << " "<< scale<< std::endl; 00398 unsigned int ref_new_scale = (scale+1)/2; 00399 00400 // work through children to our left 00401 unsigned new_scale = ref_new_scale; 00402 bool did_child = false; 00403 while(true) { 00404 int left = this_one - new_scale; // be careful here to use signed int... 00405 // if there is something unitialised to our left, link to it 00406 if (left >= static_cast<int>(left_edge) 00407 && _nodes[left].treelinks_null() ) { 00408 _nodes[left].parent = &(_nodes[this_one]); 00409 _nodes[this_one].left = &(_nodes[left]); 00410 // create connections between left_edge and this_one 00411 _do_initial_connections(left, new_scale, left_edge, this_one, depth+1); 00412 did_child = true; 00413 break; 00414 } 00415 // reduce the scale so as to try again 00416 unsigned int old_new_scale = new_scale; 00417 new_scale = (old_new_scale + 1)/2; 00418 // unless we've reached end of tree 00419 if (new_scale == old_new_scale) break; 00420 } 00421 if (!did_child) {_nodes[this_one].left = NULL;} 00422 00423 00424 // work through children to our right 00425 new_scale = ref_new_scale; 00426 did_child = false; 00427 while(true) { 00428 unsigned int right = this_one + new_scale; 00429 if (right < right_edge && _nodes[right].treelinks_null()) { 00430 _nodes[right].parent = &(_nodes[this_one]); 00431 _nodes[this_one].right = &(_nodes[right]); 00432 // create connections between this_one+1 and right_edge 00433 _do_initial_connections(right, new_scale, this_one+1,right_edge,depth+1); 00434 did_child = true; 00435 break; 00436 } 00437 // reduce the scale so as to try again 00438 unsigned int old_new_scale = new_scale; 00439 new_scale = (old_new_scale + 1)/2; 00440 // unless we've reached end of tree 00441 if (new_scale == old_new_scale) break; 00442 } 00443 if (!did_child) {_nodes[this_one].right = NULL;} 00444 00445 } 00446 00447 00448 00449 //---------------------------------------------------------------------- 00450 template<class T> void SearchTree<T>::remove(unsigned int node_index) { 00451 remove(&(_nodes[node_index])); 00452 } 00453 00454 //---------------------------------------------------------------------- 00455 template<class T> void SearchTree<T>::remove(circulator & circ) { 00456 remove(circ._node); 00457 } 00458 00459 //---------------------------------------------------------------------- 00460 // Useful reference for this: 00461 // http://en.wikipedia.org/wiki/Binary_search_tree#Deletion 00462 template<class T> void SearchTree<T>::remove(typename SearchTree<T>::Node * node) { 00463 00464 // we don't remove things from the tree if we've reached the last 00465 // elements... (is this wise?) 00466 assert(size() > 1); // switch this to throw...? 00467 assert(!node->treelinks_null()); 00468 00469 // deal with relinking predecessor and successor 00470 node->predecessor->successor = node->successor; 00471 node->successor->predecessor = node->predecessor; 00472 00473 if (node->left == NULL && node->right == NULL) { 00474 // node has no children, so remove it by nullifying the pointer 00475 // from the parent 00476 node->reset_parents_link_to_me(NULL); 00477 00478 } else if (node->left != NULL && node->right == NULL){ 00479 // make parent point to my child 00480 node->reset_parents_link_to_me(node->left); 00481 // and child to parent 00482 node->left->parent = node->parent; 00483 // sort out the top node... 00484 if (_top_node == node) {_top_node = node->left;} 00485 00486 } else if (node->left == NULL && node->right != NULL){ 00487 // make parent point to my child 00488 node->reset_parents_link_to_me(node->right); 00489 // and child to parent 00490 node->right->parent = node->parent; 00491 // sort out the top node... 00492 if (_top_node == node) {_top_node = node->right;} 00493 00494 } else { 00495 // we have two children; we will put a replacement in our place 00496 Node * replacement; 00497 //SearchTree<T>::Node * replacements_child; 00498 // chose predecessor or successor (one, then other, then first, etc...) 00499 bool use_predecessor = (_n_removes % 2 == 1); 00500 if (use_predecessor) { 00501 // Option 1: put predecessor in our place, and have its parent 00502 // point to its left child (as a predecessor it has no right child) 00503 replacement = node->predecessor; 00504 assert(replacement->right == NULL); // guaranteed if it's our predecessor 00505 // we have to be careful of replacing certain links when the 00506 // replacement is this node's child 00507 if (replacement != node->left) { 00508 if (replacement->left != NULL) { 00509 replacement->left->parent = replacement->parent;} 00510 replacement->reset_parents_link_to_me(replacement->left); 00511 replacement->left = node->left; 00512 } 00513 replacement->parent = node->parent; 00514 replacement->right = node->right; 00515 } else { 00516 // Option 2: put successor in our place, and have its parent 00517 // point to its right child (as a successor it has no left child) 00518 replacement = node->successor; 00519 assert(replacement->left == NULL); // guaranteed if it's our successor 00520 if (replacement != node->right) { 00521 if (replacement->right != NULL) { 00522 replacement->right->parent = replacement->parent;} 00523 replacement->reset_parents_link_to_me(replacement->right); 00524 replacement->right = node->right; 00525 } 00526 replacement->parent = node->parent; 00527 replacement->left = node->left; 00528 } 00529 node->reset_parents_link_to_me(replacement); 00530 00531 // make sure node's original children now point to the replacement 00532 if (node->left != replacement) {node->left->parent = replacement;} 00533 if (node->right != replacement) {node->right->parent = replacement;} 00534 00535 // sort out the top node... 00536 if (_top_node == node) {_top_node = replacement;} 00537 } 00538 00539 // make sure we leave something nice and clean... 00540 node->nullify_treelinks(); 00541 node->predecessor = NULL; 00542 node->successor = NULL; 00543 00544 // for bookkeeping (and choosing whether to use pred. or succ.) 00545 _n_removes++; 00546 // for when we next need access to a free node... 00547 _available_nodes.push_back(node); 00548 } 00549 00550 00551 //---------------------------------------------------------------------- 00552 //template<class T> typename SearchTree<T>::Node * SearchTree<T>::insert(const T & value) { 00553 00554 //---------------------------------------------------------------------- 00555 template<class T> typename SearchTree<T>::circulator SearchTree<T>::insert(const T & value) { 00556 // make sure we don't exceed allowed number of nodes... 00557 assert(_available_nodes.size() > 0); 00558 00559 Node * node = _available_nodes.back(); 00560 _available_nodes.pop_back(); 00561 node->value = value; 00562 00563 Node * location = _top_node; 00564 Node * old_location = NULL; 00565 bool on_left = true; // (init not needed -- but soothes g++4) 00566 // work through tree until we reach its end 00567 #ifdef TRACK_DEPTH 00568 unsigned int depth = 0; 00569 #endif 00570 while(location != NULL) { 00571 #ifdef TRACK_DEPTH 00572 depth++; 00573 #endif 00574 old_location = location; 00575 on_left = value < location->value; 00576 if (on_left) {location = location->left;} 00577 else {location = location->right;} 00578 } 00579 #ifdef TRACK_DEPTH 00580 _max_depth = max(depth, _max_depth); 00581 #endif 00582 // now create tree links 00583 node->parent = old_location; 00584 if (on_left) {node->parent->left = node;} 00585 else {node->parent->right = node;} 00586 node->left = NULL; 00587 node->right = NULL; 00588 // and create predecessor / successor links 00589 node->predecessor = _find_predecessor(node); 00590 if (node->predecessor != NULL) { 00591 // it exists, so make use of its info (will include a cyclic case, 00592 // when successor is round the bend) 00593 node->successor = node->predecessor->successor; 00594 node->predecessor->successor = node; 00595 node->successor->predecessor = node; 00596 } else { 00597 // deal with case when we are left-most edge of tree (then successor 00598 // will exist...) 00599 node->successor = _find_successor(node); 00600 assert(node->successor != NULL); // can only happen if we're sole element 00601 // (but not allowed, since tree size>=1) 00602 node->predecessor = node->successor->predecessor; 00603 node->successor->predecessor = node; 00604 node->predecessor->successor = node; 00605 } 00606 00607 return circulator(node); 00608 } 00609 00610 00611 //---------------------------------------------------------------------- 00612 template<class T> void SearchTree<T>::verify_structure() { 00613 00614 // do a check running through all elements 00615 verify_structure_linear(); 00616 00617 // do a recursive check down tree from top 00618 00619 // first establish the extremities 00620 const Node * left_limit = _top_node; 00621 while (left_limit->left != NULL) {left_limit = left_limit->left;} 00622 const Node * right_limit = _top_node; 00623 while (right_limit->right != NULL) {right_limit = right_limit->right;} 00624 00625 // then actually do recursion 00626 verify_structure_recursive(_top_node, left_limit, right_limit); 00627 } 00628 00629 00630 //---------------------------------------------------------------------- 00631 template<class T> void SearchTree<T>::verify_structure_recursive( 00632 const typename SearchTree<T>::Node * element, 00633 const typename SearchTree<T>::Node * left_limit, 00634 const typename SearchTree<T>::Node * right_limit) const { 00635 00636 assert(!(element->value < left_limit->value)); 00637 assert(!(right_limit->value < element->value)); 00638 00639 const Node * left = element->left; 00640 if (left != NULL) { 00641 assert(!(element->value < left->value)); 00642 if (left != left_limit) { 00643 // recurse down the tree with this element as the right-hand limit 00644 verify_structure_recursive(left, left_limit, element);} 00645 } 00646 00647 const Node * right = element->right; 00648 if (right != NULL) { 00649 assert(!(right->value < element->value)); 00650 if (right != right_limit) { 00651 // recurse down the tree with this element as the left-hand limit 00652 verify_structure_recursive(right, element, right_limit);} 00653 } 00654 } 00655 00656 //---------------------------------------------------------------------- 00657 template<class T> void SearchTree<T>::verify_structure_linear() const { 00658 00659 //print_elements(); 00660 00661 unsigned n_top = 0; 00662 unsigned n_null = 0; 00663 for(unsigned i = 0; i < _nodes.size(); i++) { 00664 const typename SearchTree<T>::Node * node = &(_nodes[i]); 00665 // make sure node is defined 00666 if (node->treelinks_null()) {n_null++; continue;} 00667 00668 // make sure of the number of "top" nodes 00669 if (node->parent == NULL) { 00670 n_top++; 00671 //assert(node->left != NULL); 00672 //assert(node->right != NULL); 00673 } else { 00674 // make sure that I am a child of my parent... 00675 //assert((node->parent->left == node) || (node->parent->right == node)); 00676 assert((node->parent->left == node) ^ (node->parent->right == node)); 00677 } 00678 00679 // when there is a left child make sure it's value is ordered 00680 // (note use of !(b<a), to allow for a<=b while using just the < 00681 // operator) 00682 if (node->left != NULL) { 00683 assert(!(node->value < node->left->value ));} 00684 00685 // when there is a right child make sure it's value is ordered 00686 if (node->right != NULL) { 00687 assert(!(node->right->value < node->value ));} 00688 00689 } 00690 assert(n_top == 1 || (n_top == 0 && size() <= 1) ); 00691 assert(n_null == _available_nodes.size() || 00692 (n_null == _available_nodes.size() + 1 && size() == 1)); 00693 } 00694 00695 00696 //---------------------------------------------------------------------- 00697 template<class T> typename SearchTree<T>::Node * SearchTree<T>::_find_predecessor(const typename SearchTree<T>::Node * node) { 00698 00699 typename SearchTree<T>::Node * newnode; 00700 if (node->left != NULL) { 00701 // go down left, and then down right as far as possible. 00702 newnode = node->left; 00703 while(newnode->right != NULL) {newnode = newnode->right;} 00704 return newnode; 00705 } else { 00706 const typename SearchTree<T>::Node * lastnode = node; 00707 newnode = node->parent; 00708 // go up the tree as long as we're going right (when we go left then 00709 // we've found something smaller, so stop) 00710 while(newnode != NULL) { 00711 if (newnode->right == lastnode) {return newnode;} 00712 lastnode = newnode; 00713 newnode = newnode->parent; 00714 } 00715 return newnode; 00716 } 00717 } 00718 00719 00720 //---------------------------------------------------------------------- 00721 template<class T> typename SearchTree<T>::Node * SearchTree<T>::_find_successor(const typename SearchTree<T>::Node * node) { 00722 00723 typename SearchTree<T>::Node * newnode; 00724 if (node->right != NULL) { 00725 // go down right, and then down left as far as possible. 00726 newnode = node->right; 00727 while(newnode->left != NULL) {newnode = newnode->left;} 00728 return newnode; 00729 } else { 00730 const typename SearchTree<T>::Node * lastnode = node; 00731 newnode = node->parent; 00732 // go up the tree as long as we're going left (when we go right then 00733 // we've found something larger, so stop) 00734 while(newnode != NULL) { 00735 if (newnode->left == lastnode) {return newnode;} 00736 lastnode = newnode; 00737 newnode = newnode->parent; 00738 } 00739 return newnode; 00740 } 00741 } 00742 00743 00744 //---------------------------------------------------------------------- 00745 // print out all the elements for visual checking... 00746 template<class T> void SearchTree<T>::print_elements() { 00747 typename SearchTree<T>::Node * base_node = &(_nodes[0]); 00748 typename SearchTree<T>::Node * node = base_node; 00749 00750 int n = _nodes.size(); 00751 for(; node - base_node < n ; node++) { 00752 printf("%4d parent:%4d left:%4d right:%4d pred:%4d succ:%4d value:%10.6f\n",loc(node), loc(node->parent), loc(node->left), loc(node->right), loc(node->predecessor),loc(node->successor),node->value); 00753 } 00754 } 00755 00756 //---------------------------------------------------------------------- 00757 template<class T> typename SearchTree<T>::circulator SearchTree<T>::somewhere() { 00758 return circulator(_top_node); 00759 } 00760 00761 00762 //---------------------------------------------------------------------- 00763 template<class T> typename SearchTree<T>::const_circulator SearchTree<T>::somewhere() const { 00764 return const_circulator(_top_node); 00765 } 00766 00767 00768 FASTJET_END_NAMESPACE 00769 00770 #endif // __FASTJET_SEARCHTREE_HH__