SearchTree.hh

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

Generated on Tue Dec 18 17:05:02 2007 for fastjet by  doxygen 1.5.2