FastJet  3.1.0-beta.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
SearchTree.hh
1 //FJSTARTHEADER
2 // $Id: SearchTree.hh 3433 2014-07-23 08:17:03Z salam $
3 //
4 // Copyright (c) 2005-2014, Matteo Cacciari, Gavin P. Salam and Gregory Soyez
5 //
6 //----------------------------------------------------------------------
7 // This file is part of FastJet.
8 //
9 // FastJet is free software; you can redistribute it and/or modify
10 // it under the terms of the GNU General Public License as published by
11 // the Free Software Foundation; either version 2 of the License, or
12 // (at your option) any later version.
13 //
14 // The algorithms that underlie FastJet have required considerable
15 // development. They are described in the original FastJet paper,
16 // hep-ph/0512210 and in the manual, arXiv:1111.6097. If you use
17 // FastJet as part of work towards a scientific publication, please
18 // quote the version you use and include a citation to the manual and
19 // optionally also to hep-ph/0512210.
20 //
21 // FastJet is distributed in the hope that it will be useful,
22 // but WITHOUT ANY WARRANTY; without even the implied warranty of
23 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 // GNU General Public License for more details.
25 //
26 // You should have received a copy of the GNU General Public License
27 // along with FastJet. If not, see <http://www.gnu.org/licenses/>.
28 //----------------------------------------------------------------------
29 //FJENDHEADER
30 
31 
32 #ifndef __FASTJET_SEARCHTREE_HH__
33 #define __FASTJET_SEARCHTREE_HH__
34 
35 #include<vector>
36 #include<cassert>
37 #include<cstddef>
38 #include "fastjet/internal/base.hh"
39 
40 FASTJET_BEGIN_NAMESPACE // defined in fastjet/internal/base.hh
41 
42 
43 //======================================================================
44 /// \if internal_doc
45 /// @ingroup internal
46 /// \class SearchTree
47 /// Efficient class for a search tree
48 ///
49 /// This is the class for a search tree designed to be especially efficient
50 /// when looking for successors and predecessors (to be used in Chan's
51 /// CP algorithm). It has the requirement that the maximum size of the
52 /// search tree must be known in advance.
53 /// \endif
54 template<class T> class SearchTree {
55 public:
56 
57  class Node;
58  class circulator;
59  class const_circulator;
60 
61  /// constructor for a search tree from an ordered vector
62  SearchTree(const std::vector<T> & init);
63 
64  /// constructor for a search tree from an ordered vector allowing
65  /// for future growth beyond the current size, up to max_size
66  SearchTree(const std::vector<T> & init, unsigned int max_size);
67 
68  /// remove the node corresponding to node_index from the search tree
69  void remove(unsigned node_index);
70  void remove(typename SearchTree::Node * node);
71  void remove(typename SearchTree::circulator & circ);
72 
73  /// insert the supplied value into the tree and return a pointer to
74  /// the relevant SearchTreeNode.
75  //Node * insert(const T & value);
76  circulator insert(const T & value);
77 
78  const Node & operator[](int i) const {return _nodes[i];};
79 
80  /// return the number of elements currently in the search tree
81  unsigned int size() const {return _nodes.size() - _available_nodes.size();}
82 
83  /// check that the structure we've obtained makes sense...
84  void verify_structure();
85  void verify_structure_linear() const;
86  void verify_structure_recursive(const Node * , const Node * , const Node * ) const;
87 
88  /// print out all elements...
89  void print_elements();
90 
91  // tracking the depth may have some speed overhead -- so leave it
92  // out for the time being...
93 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
94  /// the max depth the tree has ever reached
95  inline unsigned int max_depth() const {return _max_depth;};
96 #else
97  inline unsigned int max_depth() const {return 0;};
98 #endif
99 
100  int loc(const Node * node) const ;
101 
102  /// return predecessor by walking through the tree
103  Node * _find_predecessor(const Node *);
104  /// return successor by walking through the tree
105  Node * _find_successor(const Node *);
106 
107  const Node & operator[](unsigned int i) const {return _nodes[i];};
108 
109  /// return a circulator to some place in the tree (with a circulator
110  /// you don't care where...)
111  const_circulator somewhere() const;
112  circulator somewhere();
113 
114 private:
115 
116  void _initialize(const std::vector<T> & init);
117 
118  std::vector<Node> _nodes;
119  std::vector<Node *> _available_nodes;
120  Node * _top_node;
121  unsigned int _n_removes;
122 
123 
124  /// recursive routine for doing the initial connections assuming things
125  /// are ordered. Assumes this_one's parent is labelled, and was
126  /// generated at a scale "scale" -- connections will be carried out
127  /// including left edge and excluding right edge
128  void _do_initial_connections(unsigned int this_one, unsigned int scale,
129  unsigned int left_edge, unsigned int right_edge,
130  unsigned int depth);
131 
132 
133 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
134  unsigned int _max_depth;
135 #endif
136 
137 };
138 
139 
140 //======================================================================
141 /// \if internal_doc
142 /// @ingroup internal
143 /// \class SearchTree::Node
144 /// A node in the search tree
145 /// \endif
146 template<class T> class SearchTree<T>::Node{
147 public:
148  Node() {}; /// default constructor
149 
150 
151  /// returns tree if all the tree-related links are set to null for this node
152  bool treelinks_null() const {
153  return ((parent==0) && (left==0) && (right==0));};
154 
155  /// set all the tree-related links are set to null for this node
156  inline void nullify_treelinks() {
157  parent = NULL;
158  left = NULL;
159  right = NULL;
160  };
161 
162  /// if my parent exists, determine whether I am it's left or right
163  /// node and set the relevant link equal to XX.
164  void reset_parents_link_to_me(Node * XX);
165 
166  T value;
167  Node * left;
168  Node * right;
169  Node * parent;
170  Node * successor;
171  Node * predecessor;
172 };
173 
174 //----------------------------------------------------------------------
175 template<class T> void SearchTree<T>::Node::reset_parents_link_to_me(typename SearchTree<T>::Node * XX) {
176  if (parent == NULL) {return;}
177  if (parent->right == this) {parent->right = XX;}
178  else {parent->left = XX;}
179 }
180 
181 
182 
183 //======================================================================
184 /// \if internal_doc
185 /// @ingroup internal
186 /// \class SearchTree::circulator
187 /// circulator for the search tree
188 /// \endif
189 template<class T> class SearchTree<T>::circulator{
190 public:
191 
192  // so that it can access our _node object;
193  // note: "class U" needed for clang (v1.1 branches/release_27) compilation
194  // 2014-07-22: as reported by Torbjorn Sjostrand,
195  // the next line was giving a warning with Apple LLVM version 5.1 (clang-503.0.40) (based on LLVM 3.4svn)
196  // (dependent nested name specifier 'SearchTree<U>::' for friend class declaration is not supported)
197  // Just commenting it out, things still seem to work; same with a template of type T
198  //template<class U> friend class SearchTree<U>::const_circulator;
199  friend class SearchTree<T>::const_circulator;
200  friend class SearchTree<T>;
201 
202  circulator() : _node(NULL) {}
203 
204  circulator(Node * node) : _node(node) {}
205 
206  const T * operator->() const {return &(_node->value);}
207  T * operator->() {return &(_node->value);}
208  const T & operator*() const {return _node->value;}
209  T & operator*() {return _node->value;}
210 
211  /// prefix increment (structure copied from stl_bvector.h)
212  circulator & operator++() {
213  _node = _node->successor;
214  return *this;}
215 
216  /// postfix increment ["int" argument tells compiler it's postfix]
217  /// (structure copied from stl_bvector.h)
218  circulator operator++(int) {
219  circulator tmp = *this;
220  _node = _node->successor;
221  return tmp;}
222 
223  /// prefix decrement (structure copied from stl_bvector.h)
224  circulator & operator--() {
225  _node = _node->predecessor;
226  return *this;}
227 
228  /// postfix decrement ["int" argument tells compiler it's postfix]
229  /// (structure copied from stl_bvector.h)
230  circulator operator--(int) {
231  circulator tmp = *this;
232  _node = _node->predecessor;
233  return tmp;}
234 
235  /// return a circulator referring to the next node
236  circulator next() const {
237  return circulator(_node->successor);}
238 
239  /// return a circulator referring to the previous node
240  circulator previous() const {
241  return circulator(_node->predecessor);}
242 
243  bool operator!=(const circulator & other) const {return other._node != _node;}
244  bool operator==(const circulator & other) const {return other._node == _node;}
245 
246 private:
247  Node * _node;
248 };
249 
250 
251 //======================================================================
252 /// \if internal_doc
253 /// @ingroup internal
254 /// \class SearchTree::const_circulator
255 /// A const_circulator for the search tree
256 /// \endif
257 template<class T> class SearchTree<T>::const_circulator{
258 public:
259 
260  const_circulator() : _node(NULL) {}
261 
262  const_circulator(const Node * node) : _node(node) {}
263  const_circulator(const circulator & circ) :_node(circ._node) {}
264 
265  const T * operator->() {return &(_node->value);}
266  const T & operator*() const {return _node->value;}
267 
268  /// prefix increment (structure copied from stl_bvector.h)
269  const_circulator & operator++() {
270  _node = _node->successor;
271  return *this;}
272 
273  /// postfix increment ["int" argument tells compiler it's postfix]
274  /// (structure copied from stl_bvector.h)
275  const_circulator operator++(int) {
276  const_circulator tmp = *this;
277  _node = _node->successor;
278  return tmp;}
279 
280 
281  /// prefix decrement (structure copied from stl_bvector.h)
282  const_circulator & operator--() {
283  _node = _node->predecessor;
284  return *this;}
285 
286  /// postfix decrement ["int" argument tells compiler it's postfix]
287  /// (structure copied from stl_bvector.h)
288  const_circulator operator--(int) {
289  const_circulator tmp = *this;
290  _node = _node->predecessor;
291  return tmp;}
292 
293  /// return a circulator referring to the next node
294  const_circulator next() const {
295  return const_circulator(_node->successor);}
296 
297  /// return a circulator referring to the previous node
298  const_circulator previous() const {
299  return const_circulator(_node->predecessor);}
300 
301 
302 
303  bool operator!=(const const_circulator & other) const {return other._node != _node;}
304  bool operator==(const const_circulator & other) const {return other._node == _node;}
305 
306 private:
307  const Node * _node;
308 };
309 
310 
311 
312 
313 //----------------------------------------------------------------------
314 /// initialise from a sorted initial array allowing for a larger
315 /// maximum size of the array...
316 template<class T> SearchTree<T>::SearchTree(const std::vector<T> & init,
317  unsigned int max_size) :
318  _nodes(max_size) {
319 
320  _available_nodes.reserve(max_size);
321  _available_nodes.resize(max_size - init.size());
322  for (unsigned int i = init.size(); i < max_size; i++) {
323  _available_nodes[i-init.size()] = &(_nodes[i]);
324  }
325 
326  _initialize(init);
327 }
328 
329 //----------------------------------------------------------------------
330 /// initialise from a sorted initial array
331 template<class T> SearchTree<T>::SearchTree(const std::vector<T> & init) :
332  _nodes(init.size()), _available_nodes(0) {
333 
334  // reserve space for the list of available nodes
335  _available_nodes.reserve(init.size());
336  _initialize(init);
337 }
338 
339 //----------------------------------------------------------------------
340 /// do the actual hard work of initialization
341 template<class T> void SearchTree<T>::_initialize(const std::vector<T> & init) {
342 
343  _n_removes = 0;
344  unsigned n = init.size();
345  assert(n>=1);
346 
347  // reserve space for the list of available nodes
348  //_available_nodes.reserve();
349 
350 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
351  _max_depth = 0;
352 #endif
353 
354 
355  // validate the input
356  for (unsigned int i = 1; i<n; i++) {
357  assert(!(init[i] < init[i-1]));
358  }
359 
360  // now initialise the vector; link neighbours in the sequence
361  for(unsigned int i = 0; i < n; i++) {
362  _nodes[i].value = init[i];
363  _nodes[i].predecessor = (& (_nodes[i])) - 1;
364  _nodes[i].successor = (& (_nodes[i])) + 1;
365  _nodes[i].nullify_treelinks();
366  }
367  // make a loop structure so that we can circulate...
368  _nodes[0].predecessor = (& (_nodes[n-1]));
369  _nodes[n-1].successor = (& (_nodes[0]));
370 
371  // now label the rest of the nodes
372  unsigned int scale = (n+1)/2;
373  unsigned int top = std::min(n-1,scale);
374  _nodes[top].parent = NULL;
375  _top_node = &(_nodes[top]);
376  _do_initial_connections(top, scale, 0, n, 0);
377 
378  // make sure things are sensible...
379  //verify_structure();
380 }
381 
382 
383 
384 //----------------------------------------------------------------------
385 template<class T> inline int SearchTree<T>::loc(const Node * node) const {return node == NULL?
386  -999 : node - &(_nodes[0]);}
387 
388 
389 //----------------------------------------------------------------------
390 /// Recursive creation of connections, assuming the _nodes vector is
391 /// completely filled and ordered
392 template<class T> void SearchTree<T>::_do_initial_connections(
393  unsigned int this_one,
394  unsigned int scale,
395  unsigned int left_edge,
396  unsigned int right_edge,
397  unsigned int depth
398  ) {
399 
400 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
401  // keep track of tree depth for checking things stay reasonable...
402  _max_depth = max(depth, _max_depth);
403 #endif
404 
405  //std::cout << this_one << " "<< scale<< std::endl;
406  unsigned int ref_new_scale = (scale+1)/2;
407 
408  // work through children to our left
409  unsigned new_scale = ref_new_scale;
410  bool did_child = false;
411  while(true) {
412  int left = this_one - new_scale; // be careful here to use signed int...
413  // if there is something unitialised to our left, link to it
414  if (left >= static_cast<int>(left_edge)
415  && _nodes[left].treelinks_null() ) {
416  _nodes[left].parent = &(_nodes[this_one]);
417  _nodes[this_one].left = &(_nodes[left]);
418  // create connections between left_edge and this_one
419  _do_initial_connections(left, new_scale, left_edge, this_one, depth+1);
420  did_child = true;
421  break;
422  }
423  // reduce the scale so as to try again
424  unsigned int old_new_scale = new_scale;
425  new_scale = (old_new_scale + 1)/2;
426  // unless we've reached end of tree
427  if (new_scale == old_new_scale) break;
428  }
429  if (!did_child) {_nodes[this_one].left = NULL;}
430 
431 
432  // work through children to our right
433  new_scale = ref_new_scale;
434  did_child = false;
435  while(true) {
436  unsigned int right = this_one + new_scale;
437  if (right < right_edge && _nodes[right].treelinks_null()) {
438  _nodes[right].parent = &(_nodes[this_one]);
439  _nodes[this_one].right = &(_nodes[right]);
440  // create connections between this_one+1 and right_edge
441  _do_initial_connections(right, new_scale, this_one+1,right_edge,depth+1);
442  did_child = true;
443  break;
444  }
445  // reduce the scale so as to try again
446  unsigned int old_new_scale = new_scale;
447  new_scale = (old_new_scale + 1)/2;
448  // unless we've reached end of tree
449  if (new_scale == old_new_scale) break;
450  }
451  if (!did_child) {_nodes[this_one].right = NULL;}
452 
453 }
454 
455 
456 
457 //----------------------------------------------------------------------
458 template<class T> void SearchTree<T>::remove(unsigned int node_index) {
459  remove(&(_nodes[node_index]));
460 }
461 
462 //----------------------------------------------------------------------
463 template<class T> void SearchTree<T>::remove(circulator & circ) {
464  remove(circ._node);
465 }
466 
467 //----------------------------------------------------------------------
468 // Useful reference for this:
469 // http://en.wikipedia.org/wiki/Binary_search_tree#Deletion
470 template<class T> void SearchTree<T>::remove(typename SearchTree<T>::Node * node) {
471 
472  // we don't remove things from the tree if we've reached the last
473  // elements... (is this wise?)
474  assert(size() > 1); // switch this to throw...?
475  assert(!node->treelinks_null());
476 
477  // deal with relinking predecessor and successor
478  node->predecessor->successor = node->successor;
479  node->successor->predecessor = node->predecessor;
480 
481  if (node->left == NULL && node->right == NULL) {
482  // node has no children, so remove it by nullifying the pointer
483  // from the parent
484  node->reset_parents_link_to_me(NULL);
485 
486  } else if (node->left != NULL && node->right == NULL){
487  // make parent point to my child
488  node->reset_parents_link_to_me(node->left);
489  // and child to parent
490  node->left->parent = node->parent;
491  // sort out the top node...
492  if (_top_node == node) {_top_node = node->left;}
493 
494  } else if (node->left == NULL && node->right != NULL){
495  // make parent point to my child
496  node->reset_parents_link_to_me(node->right);
497  // and child to parent
498  node->right->parent = node->parent;
499  // sort out the top node...
500  if (_top_node == node) {_top_node = node->right;}
501 
502  } else {
503  // we have two children; we will put a replacement in our place
504  Node * replacement;
505  //SearchTree<T>::Node * replacements_child;
506  // chose predecessor or successor (one, then other, then first, etc...)
507  bool use_predecessor = (_n_removes % 2 == 1);
508  if (use_predecessor) {
509  // Option 1: put predecessor in our place, and have its parent
510  // point to its left child (as a predecessor it has no right child)
511  replacement = node->predecessor;
512  assert(replacement->right == NULL); // guaranteed if it's our predecessor
513  // we have to be careful of replacing certain links when the
514  // replacement is this node's child
515  if (replacement != node->left) {
516  if (replacement->left != NULL) {
517  replacement->left->parent = replacement->parent;}
518  replacement->reset_parents_link_to_me(replacement->left);
519  replacement->left = node->left;
520  }
521  replacement->parent = node->parent;
522  replacement->right = node->right;
523  } else {
524  // Option 2: put successor in our place, and have its parent
525  // point to its right child (as a successor it has no left child)
526  replacement = node->successor;
527  assert(replacement->left == NULL); // guaranteed if it's our successor
528  if (replacement != node->right) {
529  if (replacement->right != NULL) {
530  replacement->right->parent = replacement->parent;}
531  replacement->reset_parents_link_to_me(replacement->right);
532  replacement->right = node->right;
533  }
534  replacement->parent = node->parent;
535  replacement->left = node->left;
536  }
537  node->reset_parents_link_to_me(replacement);
538 
539  // make sure node's original children now point to the replacement
540  if (node->left != replacement) {node->left->parent = replacement;}
541  if (node->right != replacement) {node->right->parent = replacement;}
542 
543  // sort out the top node...
544  if (_top_node == node) {_top_node = replacement;}
545  }
546 
547  // make sure we leave something nice and clean...
548  node->nullify_treelinks();
549  node->predecessor = NULL;
550  node->successor = NULL;
551 
552  // for bookkeeping (and choosing whether to use pred. or succ.)
553  _n_removes++;
554  // for when we next need access to a free node...
555  _available_nodes.push_back(node);
556 }
557 
558 
559 //----------------------------------------------------------------------
560 //template<class T> typename SearchTree<T>::Node * SearchTree<T>::insert(const T & value) {
561 
562 //----------------------------------------------------------------------
563 template<class T> typename SearchTree<T>::circulator SearchTree<T>::insert(const T & value) {
564  // make sure we don't exceed allowed number of nodes...
565  assert(_available_nodes.size() > 0);
566 
567  Node * node = _available_nodes.back();
568  _available_nodes.pop_back();
569  node->value = value;
570 
571  Node * location = _top_node;
572  Node * old_location = NULL;
573  bool on_left = true; // (init not needed -- but soothes g++4)
574  // work through tree until we reach its end
575 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
576  unsigned int depth = 0;
577 #endif
578  while(location != NULL) {
579 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
580  depth++;
581 #endif
582  old_location = location;
583  on_left = value < location->value;
584  if (on_left) {location = location->left;}
585  else {location = location->right;}
586  }
587 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
588  _max_depth = max(depth, _max_depth);
589 #endif
590  // now create tree links
591  node->parent = old_location;
592  if (on_left) {node->parent->left = node;}
593  else {node->parent->right = node;}
594  node->left = NULL;
595  node->right = NULL;
596  // and create predecessor / successor links
597  node->predecessor = _find_predecessor(node);
598  if (node->predecessor != NULL) {
599  // it exists, so make use of its info (will include a cyclic case,
600  // when successor is round the bend)
601  node->successor = node->predecessor->successor;
602  node->predecessor->successor = node;
603  node->successor->predecessor = node;
604  } else {
605  // deal with case when we are left-most edge of tree (then successor
606  // will exist...)
607  node->successor = _find_successor(node);
608  assert(node->successor != NULL); // can only happen if we're sole element
609  // (but not allowed, since tree size>=1)
610  node->predecessor = node->successor->predecessor;
611  node->successor->predecessor = node;
612  node->predecessor->successor = node;
613  }
614 
615  return circulator(node);
616 }
617 
618 
619 //----------------------------------------------------------------------
620 template<class T> void SearchTree<T>::verify_structure() {
621 
622  // do a check running through all elements
623  verify_structure_linear();
624 
625  // do a recursive check down tree from top
626 
627  // first establish the extremities
628  const Node * left_limit = _top_node;
629  while (left_limit->left != NULL) {left_limit = left_limit->left;}
630  const Node * right_limit = _top_node;
631  while (right_limit->right != NULL) {right_limit = right_limit->right;}
632 
633  // then actually do recursion
634  verify_structure_recursive(_top_node, left_limit, right_limit);
635 }
636 
637 
638 //----------------------------------------------------------------------
639 template<class T> void SearchTree<T>::verify_structure_recursive(
640  const typename SearchTree<T>::Node * element,
641  const typename SearchTree<T>::Node * left_limit,
642  const typename SearchTree<T>::Node * right_limit) const {
643 
644  assert(!(element->value < left_limit->value));
645  assert(!(right_limit->value < element->value));
646 
647  const Node * left = element->left;
648  if (left != NULL) {
649  assert(!(element->value < left->value));
650  if (left != left_limit) {
651  // recurse down the tree with this element as the right-hand limit
652  verify_structure_recursive(left, left_limit, element);}
653  }
654 
655  const Node * right = element->right;
656  if (right != NULL) {
657  assert(!(right->value < element->value));
658  if (right != right_limit) {
659  // recurse down the tree with this element as the left-hand limit
660  verify_structure_recursive(right, element, right_limit);}
661  }
662 }
663 
664 //----------------------------------------------------------------------
665 template<class T> void SearchTree<T>::verify_structure_linear() const {
666 
667  //print_elements();
668 
669  unsigned n_top = 0;
670  unsigned n_null = 0;
671  for(unsigned i = 0; i < _nodes.size(); i++) {
672  const typename SearchTree<T>::Node * node = &(_nodes[i]);
673  // make sure node is defined
674  if (node->treelinks_null()) {n_null++; continue;}
675 
676  // make sure of the number of "top" nodes
677  if (node->parent == NULL) {
678  n_top++;
679  //assert(node->left != NULL);
680  //assert(node->right != NULL);
681  } else {
682  // make sure that I am a child of my parent...
683  //assert((node->parent->left == node) || (node->parent->right == node));
684  assert((node->parent->left == node) ^ (node->parent->right == node));
685  }
686 
687  // when there is a left child make sure it's value is ordered
688  // (note use of !(b<a), to allow for a<=b while using just the <
689  // operator)
690  if (node->left != NULL) {
691  assert(!(node->value < node->left->value ));}
692 
693  // when there is a right child make sure it's value is ordered
694  if (node->right != NULL) {
695  assert(!(node->right->value < node->value ));}
696 
697  }
698  assert(n_top == 1 || (n_top == 0 && size() <= 1) );
699  assert(n_null == _available_nodes.size() ||
700  (n_null == _available_nodes.size() + 1 && size() == 1));
701 }
702 
703 
704 //----------------------------------------------------------------------
705 template<class T> typename SearchTree<T>::Node * SearchTree<T>::_find_predecessor(const typename SearchTree<T>::Node * node) {
706 
707  typename SearchTree<T>::Node * newnode;
708  if (node->left != NULL) {
709  // go down left, and then down right as far as possible.
710  newnode = node->left;
711  while(newnode->right != NULL) {newnode = newnode->right;}
712  return newnode;
713  } else {
714  const typename SearchTree<T>::Node * lastnode = node;
715  newnode = node->parent;
716  // go up the tree as long as we're going right (when we go left then
717  // we've found something smaller, so stop)
718  while(newnode != NULL) {
719  if (newnode->right == lastnode) {return newnode;}
720  lastnode = newnode;
721  newnode = newnode->parent;
722  }
723  return newnode;
724  }
725 }
726 
727 
728 //----------------------------------------------------------------------
729 template<class T> typename SearchTree<T>::Node * SearchTree<T>::_find_successor(const typename SearchTree<T>::Node * node) {
730 
731  typename SearchTree<T>::Node * newnode;
732  if (node->right != NULL) {
733  // go down right, and then down left as far as possible.
734  newnode = node->right;
735  while(newnode->left != NULL) {newnode = newnode->left;}
736  return newnode;
737  } else {
738  const typename SearchTree<T>::Node * lastnode = node;
739  newnode = node->parent;
740  // go up the tree as long as we're going left (when we go right then
741  // we've found something larger, so stop)
742  while(newnode != NULL) {
743  if (newnode->left == lastnode) {return newnode;}
744  lastnode = newnode;
745  newnode = newnode->parent;
746  }
747  return newnode;
748  }
749 }
750 
751 
752 //----------------------------------------------------------------------
753 // print out all the elements for visual checking...
754 template<class T> void SearchTree<T>::print_elements() {
755  typename SearchTree<T>::Node * base_node = &(_nodes[0]);
756  typename SearchTree<T>::Node * node = base_node;
757 
758  int n = _nodes.size();
759  for(; node - base_node < n ; node++) {
760  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);
761  }
762 }
763 
764 //----------------------------------------------------------------------
765 template<class T> typename SearchTree<T>::circulator SearchTree<T>::somewhere() {
766  return circulator(_top_node);
767 }
768 
769 
770 //----------------------------------------------------------------------
771 template<class T> typename SearchTree<T>::const_circulator SearchTree<T>::somewhere() const {
772  return const_circulator(_top_node);
773 }
774 
775 
776 FASTJET_END_NAMESPACE
777 
778 #endif // __FASTJET_SEARCHTREE_HH__