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