FastJet 3.0.6
SearchTree.hh
00001 //STARTHEADER
00002 // $Id: SearchTree.hh 3107 2013-05-03 15:47:47Z 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 __FASTJET_SEARCHTREE_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 __FASTJET_SEARCHTREE_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   // note: "class U" needed for clang (v1.1 branches/release_27) compilation
00192   template<class U> friend class SearchTree<U>::const_circulator;
00193   friend class SearchTree<T>;
00194 
00195   circulator() : _node(NULL) {}
00196 
00197   circulator(Node * node) : _node(node) {}
00198 
00199   const T * operator->() const {return &(_node->value);}
00200   T * operator->() {return &(_node->value);}
00201   const T & operator*() const {return _node->value;}
00202   T & operator*() {return _node->value;}
00203 
00204   /// prefix increment (structure copied from stl_bvector.h)
00205   circulator & operator++() {
00206     _node = _node->successor; 
00207     return *this;}
00208 
00209   /// postfix increment ["int" argument tells compiler it's postfix]
00210   /// (structure copied from stl_bvector.h)
00211   circulator operator++(int) {
00212     circulator tmp = *this;
00213     _node = _node->successor; 
00214     return tmp;}
00215 
00216   /// prefix decrement (structure copied from stl_bvector.h)
00217   circulator & operator--() {
00218     _node = _node->predecessor; 
00219     return *this;}
00220 
00221   /// postfix decrement ["int" argument tells compiler it's postfix]
00222   /// (structure copied from stl_bvector.h)
00223   circulator operator--(int) {
00224     circulator tmp = *this;
00225     _node = _node->predecessor; 
00226     return tmp;}
00227 
00228   /// return a circulator referring to the next node
00229   circulator next() const {
00230     return circulator(_node->successor);}
00231 
00232   /// return a circulator referring to the previous node
00233   circulator previous() const {
00234     return circulator(_node->predecessor);}
00235 
00236   bool operator!=(const circulator & other) const {return other._node != _node;}
00237   bool operator==(const circulator & other) const {return other._node == _node;}
00238 
00239 private:
00240   Node * _node;
00241 };
00242 
00243 
00244 //======================================================================
00245 /// \if internal_doc
00246 /// @ingroup internal
00247 /// \class SearchTree::const_circulator
00248 /// A const_circulator for the search tree
00249 /// \endif
00250 template<class T> class SearchTree<T>::const_circulator{
00251 public:
00252 
00253   const_circulator() : _node(NULL) {}
00254 
00255   const_circulator(const Node * node) : _node(node) {}
00256   const_circulator(const circulator & circ) :_node(circ._node) {}
00257 
00258   const T * operator->() {return &(_node->value);}
00259   const T & operator*() const {return _node->value;}
00260 
00261   /// prefix increment (structure copied from stl_bvector.h)
00262   const_circulator & operator++() {
00263     _node = _node->successor; 
00264     return *this;}
00265 
00266   /// postfix increment ["int" argument tells compiler it's postfix]
00267   /// (structure copied from stl_bvector.h)
00268   const_circulator operator++(int) {
00269     const_circulator tmp = *this;
00270     _node = _node->successor; 
00271     return tmp;}
00272 
00273 
00274   /// prefix decrement (structure copied from stl_bvector.h)
00275   const_circulator & operator--() {
00276     _node = _node->predecessor; 
00277     return *this;}
00278 
00279   /// postfix decrement ["int" argument tells compiler it's postfix]
00280   /// (structure copied from stl_bvector.h)
00281   const_circulator operator--(int) {
00282     const_circulator tmp = *this;
00283     _node = _node->predecessor; 
00284     return tmp;}
00285 
00286   /// return a circulator referring to the next node
00287   const_circulator next() const {
00288     return const_circulator(_node->successor);}
00289 
00290   /// return a circulator referring to the previous node
00291   const_circulator previous() const {
00292     return const_circulator(_node->predecessor);}
00293 
00294 
00295 
00296   bool operator!=(const const_circulator & other) const {return other._node != _node;}
00297   bool operator==(const const_circulator & other) const {return other._node == _node;}
00298 
00299 private:
00300   const Node * _node;
00301 };
00302 
00303 
00304 
00305 
00306 //----------------------------------------------------------------------
00307 /// initialise from a sorted initial array allowing for a larger
00308 /// maximum size of the array...
00309 template<class T> SearchTree<T>::SearchTree(const std::vector<T> & init,
00310                                             unsigned int max_size) :
00311   _nodes(max_size) {
00312 
00313   _available_nodes.reserve(max_size);
00314   _available_nodes.resize(max_size - init.size());
00315   for (unsigned int i = init.size(); i < max_size; i++) {
00316     _available_nodes[i-init.size()] = &(_nodes[i]);
00317   }
00318 
00319   _initialize(init);
00320 }
00321 
00322 //----------------------------------------------------------------------
00323 /// initialise from a sorted initial array
00324 template<class T> SearchTree<T>::SearchTree(const std::vector<T> & init) :
00325   _nodes(init.size()), _available_nodes(0) {
00326 
00327   // reserve space for the list of available nodes
00328   _available_nodes.reserve(init.size());
00329   _initialize(init);
00330 }
00331 
00332 //----------------------------------------------------------------------
00333 /// do the actual hard work of initialization
00334 template<class T> void SearchTree<T>::_initialize(const std::vector<T> & init) {
00335 
00336   _n_removes = 0;
00337   unsigned n = init.size();
00338   assert(n>=1);
00339 
00340   // reserve space for the list of available nodes
00341   //_available_nodes.reserve();
00342 
00343 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
00344   _max_depth     = 0;
00345 #endif
00346 
00347 
00348   // validate the input
00349   for (unsigned int i = 1; i<n; i++) {
00350     assert(!(init[i] < init[i-1]));
00351   }
00352   
00353   // now initialise the vector; link neighbours in the sequence
00354   for(unsigned int i = 0; i < n; i++) {
00355     _nodes[i].value = init[i];
00356     _nodes[i].predecessor = (& (_nodes[i])) - 1;
00357     _nodes[i].successor   = (& (_nodes[i])) + 1;
00358     _nodes[i].nullify_treelinks();
00359   }
00360   // make a loop structure so that we can circulate...
00361   _nodes[0].predecessor = (& (_nodes[n-1]));
00362   _nodes[n-1].successor = (& (_nodes[0]));
00363 
00364   // now label the rest of the nodes
00365   unsigned int scale = (n+1)/2;
00366   unsigned int top   = std::min(n-1,scale);
00367   _nodes[top].parent = NULL;
00368   _top_node = &(_nodes[top]);
00369   _do_initial_connections(top, scale, 0, n, 0);
00370 
00371   // make sure things are sensible...
00372   //verify_structure();
00373 }
00374 
00375 
00376 
00377 //----------------------------------------------------------------------
00378 template<class T> inline  int SearchTree<T>::loc(const Node * node) const {return node == NULL? 
00379       -999 : node - &(_nodes[0]);}
00380 
00381 
00382 //----------------------------------------------------------------------
00383 /// Recursive creation of connections, assuming the _nodes vector is
00384 /// completely filled and ordered
00385 template<class T> void SearchTree<T>::_do_initial_connections(
00386                                          unsigned int this_one, 
00387                                          unsigned int scale,
00388                                          unsigned int left_edge,
00389                                          unsigned int right_edge,
00390                                          unsigned int depth
00391                                          ) {
00392 
00393 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
00394   // keep track of tree depth for checking things stay reasonable...
00395   _max_depth = max(depth, _max_depth);
00396 #endif
00397 
00398   //std::cout << this_one << " "<< scale<< std::endl;
00399   unsigned int ref_new_scale = (scale+1)/2;
00400 
00401   // work through children to our left
00402   unsigned new_scale = ref_new_scale;
00403   bool     did_child  = false;
00404   while(true) {
00405     int left = this_one - new_scale; // be careful here to use signed int...
00406     // if there is something unitialised to our left, link to it
00407     if (left >= static_cast<int>(left_edge) 
00408                         && _nodes[left].treelinks_null() ) {
00409       _nodes[left].parent = &(_nodes[this_one]);
00410       _nodes[this_one].left = &(_nodes[left]);
00411       // create connections between left_edge and this_one
00412       _do_initial_connections(left, new_scale, left_edge, this_one, depth+1);
00413       did_child = true;
00414       break;
00415     }
00416     // reduce the scale so as to try again
00417     unsigned int old_new_scale = new_scale;
00418     new_scale = (old_new_scale + 1)/2;
00419     // unless we've reached end of tree
00420     if (new_scale == old_new_scale) break;
00421   }
00422   if (!did_child) {_nodes[this_one].left = NULL;}
00423 
00424 
00425   // work through children to our right
00426   new_scale = ref_new_scale;
00427   did_child  = false;
00428   while(true) {
00429     unsigned int right = this_one + new_scale;
00430     if (right < right_edge  && _nodes[right].treelinks_null()) {
00431       _nodes[right].parent = &(_nodes[this_one]);
00432       _nodes[this_one].right = &(_nodes[right]);
00433       // create connections between this_one+1 and right_edge
00434       _do_initial_connections(right, new_scale, this_one+1,right_edge,depth+1);
00435       did_child = true;
00436       break;
00437     }
00438     // reduce the scale so as to try again
00439     unsigned int old_new_scale = new_scale;
00440     new_scale = (old_new_scale + 1)/2;
00441     // unless we've reached end of tree
00442     if (new_scale == old_new_scale) break;
00443   }
00444   if (!did_child) {_nodes[this_one].right = NULL;}
00445 
00446 }
00447 
00448 
00449 
00450 //----------------------------------------------------------------------
00451 template<class T> void SearchTree<T>::remove(unsigned int node_index) {
00452   remove(&(_nodes[node_index]));
00453 }
00454 
00455 //----------------------------------------------------------------------
00456 template<class T> void SearchTree<T>::remove(circulator & circ) {
00457   remove(circ._node);
00458 }
00459 
00460 //----------------------------------------------------------------------
00461 // Useful reference for this:
00462 //   http://en.wikipedia.org/wiki/Binary_search_tree#Deletion
00463 template<class T> void SearchTree<T>::remove(typename SearchTree<T>::Node * node) {
00464 
00465   // we don't remove things from the tree if we've reached the last
00466   // elements... (is this wise?)
00467   assert(size() > 1); // switch this to throw...?
00468   assert(!node->treelinks_null());
00469 
00470   // deal with relinking predecessor and successor
00471   node->predecessor->successor = node->successor;
00472   node->successor->predecessor = node->predecessor;
00473 
00474   if (node->left == NULL && node->right == NULL) {
00475     // node has no children, so remove it by nullifying the pointer 
00476     // from the parent
00477     node->reset_parents_link_to_me(NULL); 
00478 
00479   } else if (node->left != NULL && node->right == NULL){
00480     // make parent point to my child
00481     node->reset_parents_link_to_me(node->left);
00482     // and child to parent
00483     node->left->parent = node->parent;         
00484     // sort out the top node...
00485     if (_top_node == node) {_top_node = node->left;}
00486 
00487   } else if (node->left == NULL && node->right != NULL){
00488     // make parent point to my child
00489     node->reset_parents_link_to_me(node->right);
00490     // and child to parent
00491     node->right->parent = node->parent;   
00492     // sort out the top node...
00493     if (_top_node == node) {_top_node = node->right;}
00494 
00495   } else {
00496     // we have two children; we will put a replacement in our place
00497     Node * replacement;
00498     //SearchTree<T>::Node * replacements_child;
00499     // chose predecessor or successor (one, then other, then first, etc...)
00500     bool use_predecessor = (_n_removes % 2 == 1);
00501     if (use_predecessor) {
00502       // Option 1: put predecessor in our place, and have its parent
00503       // point to its left child (as a predecessor it has no right child)
00504       replacement = node->predecessor;
00505       assert(replacement->right == NULL); // guaranteed if it's our predecessor
00506       // we have to be careful of replacing certain links when the 
00507       // replacement is this node's child
00508       if (replacement != node->left) {
00509         if (replacement->left != NULL) {
00510           replacement->left->parent = replacement->parent;}
00511         replacement->reset_parents_link_to_me(replacement->left);
00512         replacement->left   = node->left;
00513       }
00514       replacement->parent = node->parent;
00515       replacement->right  = node->right;
00516     } else {
00517       // Option 2: put successor in our place, and have its parent
00518       // point to its right child (as a successor it has no left child)
00519       replacement = node->successor;
00520       assert(replacement->left == NULL); // guaranteed if it's our successor
00521       if (replacement != node->right) {
00522         if (replacement->right != NULL) {
00523           replacement->right->parent = replacement->parent;}
00524         replacement->reset_parents_link_to_me(replacement->right);
00525         replacement->right  = node->right;
00526       }
00527       replacement->parent = node->parent;
00528       replacement->left   = node->left;
00529     }
00530     node->reset_parents_link_to_me(replacement);
00531 
00532     // make sure node's original children now point to the replacement
00533     if (node->left  != replacement) {node->left->parent  = replacement;}
00534     if (node->right != replacement) {node->right->parent = replacement;}
00535 
00536     // sort out the top node...
00537     if (_top_node == node) {_top_node = replacement;}
00538   }
00539 
00540   // make sure we leave something nice and clean...
00541   node->nullify_treelinks();
00542   node->predecessor = NULL;
00543   node->successor   = NULL;
00544 
00545   // for bookkeeping (and choosing whether to use pred. or succ.)
00546   _n_removes++;
00547   // for when we next need access to a free node...
00548   _available_nodes.push_back(node);
00549 }
00550 
00551 
00552 //----------------------------------------------------------------------
00553 //template<class T> typename SearchTree<T>::Node * SearchTree<T>::insert(const T & value) {
00554 
00555 //----------------------------------------------------------------------
00556 template<class T> typename SearchTree<T>::circulator SearchTree<T>::insert(const T & value) {
00557   // make sure we don't exceed allowed number of nodes...
00558   assert(_available_nodes.size() > 0);
00559 
00560   Node * node = _available_nodes.back();
00561   _available_nodes.pop_back();
00562   node->value = value;
00563 
00564   Node * location = _top_node;
00565   Node * old_location = NULL;
00566   bool             on_left = true; // (init not needed -- but soothes g++4)
00567   // work through tree until we reach its end
00568 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
00569   unsigned int depth = 0;
00570 #endif
00571   while(location != NULL) {
00572 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
00573     depth++;
00574 #endif
00575     old_location = location;
00576     on_left = value < location->value;
00577     if (on_left) {location = location->left;}
00578     else {location = location->right;}
00579   }
00580 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
00581   _max_depth = max(depth, _max_depth);
00582 #endif
00583   // now create tree links
00584   node->parent = old_location;
00585   if (on_left) {node->parent->left = node;} 
00586   else {node->parent->right = node;}
00587   node->left = NULL;
00588   node->right = NULL;
00589   // and create predecessor / successor links
00590   node->predecessor = _find_predecessor(node);
00591   if (node->predecessor != NULL) {
00592     // it exists, so make use of its info (will include a cyclic case,
00593     // when successor is round the bend)
00594     node->successor = node->predecessor->successor;
00595     node->predecessor->successor = node;
00596     node->successor->predecessor = node;
00597   } else {
00598     // deal with case when we are left-most edge of tree (then successor
00599     // will exist...)
00600     node->successor = _find_successor(node);
00601     assert(node->successor != NULL); // can only happen if we're sole element 
00602                                      // (but not allowed, since tree size>=1)
00603     node->predecessor = node->successor->predecessor;
00604     node->successor->predecessor = node;
00605     node->predecessor->successor = node;
00606   }
00607 
00608   return circulator(node);
00609 }
00610 
00611 
00612 //----------------------------------------------------------------------
00613 template<class T> void SearchTree<T>::verify_structure() {
00614   
00615   // do a check running through all elements
00616   verify_structure_linear();
00617 
00618   // do a recursive check down tree from top
00619 
00620   // first establish the extremities
00621   const Node * left_limit = _top_node;
00622   while (left_limit->left != NULL) {left_limit = left_limit->left;}
00623   const Node * right_limit = _top_node;
00624   while (right_limit->right != NULL) {right_limit = right_limit->right;}
00625 
00626   // then actually do recursion
00627   verify_structure_recursive(_top_node, left_limit, right_limit);
00628 }
00629 
00630 
00631 //----------------------------------------------------------------------
00632 template<class T> void SearchTree<T>::verify_structure_recursive(
00633                       const typename SearchTree<T>::Node * element, 
00634                       const typename SearchTree<T>::Node * left_limit,
00635                       const typename SearchTree<T>::Node * right_limit)  const {
00636 
00637   assert(!(element->value < left_limit->value));
00638   assert(!(right_limit->value < element->value));
00639 
00640   const Node * left = element->left;
00641   if (left != NULL) {
00642     assert(!(element->value < left->value));
00643     if (left != left_limit) {
00644       // recurse down the tree with this element as the right-hand limit
00645       verify_structure_recursive(left, left_limit, element);}
00646   }
00647   
00648   const Node * right = element->right;
00649   if (right != NULL) {
00650     assert(!(right->value < element->value));
00651     if (right != right_limit) {
00652       // recurse down the tree with this element as the left-hand limit
00653       verify_structure_recursive(right, element, right_limit);}
00654   }
00655 }
00656 
00657 //----------------------------------------------------------------------
00658 template<class T> void SearchTree<T>::verify_structure_linear() const {
00659 
00660   //print_elements();
00661 
00662   unsigned n_top = 0;
00663   unsigned n_null = 0;
00664   for(unsigned i = 0; i < _nodes.size(); i++) {
00665     const typename SearchTree<T>::Node * node = &(_nodes[i]);
00666     // make sure node is defined
00667     if (node->treelinks_null()) {n_null++; continue;}
00668 
00669     // make sure of the number of "top" nodes 
00670     if (node->parent == NULL) {
00671       n_top++;
00672       //assert(node->left != NULL);
00673       //assert(node->right != NULL);
00674     } else {
00675       // make sure that I am a child of my parent...
00676       //assert((node->parent->left == node) || (node->parent->right == node));
00677       assert((node->parent->left == node) ^ (node->parent->right == node));
00678     }
00679 
00680     // when there is a left child make sure it's value is ordered
00681     // (note use of !(b<a), to allow for a<=b while using just the <
00682     // operator)
00683     if (node->left != NULL) {
00684       assert(!(node->value < node->left->value ));}
00685 
00686     // when there is a right child make sure it's value is ordered
00687     if (node->right != NULL) {
00688       assert(!(node->right->value < node->value ));}
00689 
00690   }
00691   assert(n_top == 1 || (n_top == 0 && size() <= 1) );
00692   assert(n_null == _available_nodes.size() ||
00693          (n_null == _available_nodes.size() + 1 && size() == 1));
00694 }
00695 
00696 
00697 //----------------------------------------------------------------------
00698 template<class T> typename SearchTree<T>::Node * SearchTree<T>::_find_predecessor(const typename SearchTree<T>::Node * node) {
00699 
00700   typename SearchTree<T>::Node * newnode;
00701   if (node->left != NULL) {
00702     // go down left, and then down right as far as possible.
00703     newnode = node->left;
00704     while(newnode->right != NULL) {newnode = newnode->right;}
00705     return newnode;
00706   } else {
00707     const typename SearchTree<T>::Node * lastnode = node;
00708     newnode = node->parent;
00709     // go up the tree as long as we're going right (when we go left then
00710     // we've found something smaller, so stop)
00711     while(newnode != NULL) {
00712       if (newnode->right == lastnode) {return newnode;}
00713       lastnode = newnode;
00714       newnode = newnode->parent;
00715     }
00716     return newnode;
00717   }
00718 }
00719 
00720 
00721 //----------------------------------------------------------------------
00722 template<class T> typename SearchTree<T>::Node * SearchTree<T>::_find_successor(const typename SearchTree<T>::Node * node) {
00723 
00724   typename SearchTree<T>::Node * newnode;
00725   if (node->right != NULL) {
00726     // go down right, and then down left as far as possible.
00727     newnode = node->right;
00728     while(newnode->left != NULL) {newnode = newnode->left;}
00729     return newnode;
00730   } else {
00731     const typename SearchTree<T>::Node * lastnode = node;
00732     newnode = node->parent;
00733     // go up the tree as long as we're going left (when we go right then
00734     // we've found something larger, so stop)
00735     while(newnode != NULL) {
00736       if (newnode->left == lastnode) {return newnode;}
00737       lastnode = newnode;
00738       newnode = newnode->parent;
00739     }
00740     return newnode;
00741   }
00742 }
00743 
00744 
00745 //----------------------------------------------------------------------
00746 // print out all the elements for visual checking...
00747 template<class T> void SearchTree<T>::print_elements() {
00748   typename SearchTree<T>::Node * base_node = &(_nodes[0]);
00749   typename SearchTree<T>::Node * node = base_node;
00750   
00751   int n = _nodes.size();
00752   for(; node - base_node < n ; node++) {
00753     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);
00754   }
00755 }
00756 
00757 //----------------------------------------------------------------------
00758 template<class T> typename SearchTree<T>::circulator SearchTree<T>::somewhere() {
00759   return circulator(_top_node);
00760 }
00761 
00762 
00763 //----------------------------------------------------------------------
00764 template<class T> typename SearchTree<T>::const_circulator SearchTree<T>::somewhere() const {
00765   return const_circulator(_top_node);
00766 }
00767 
00768 
00769 FASTJET_END_NAMESPACE
00770 
00771 #endif // __FASTJET_SEARCHTREE_HH__
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends