Fork me on GitHub

source: git/external/fastjet/internal/SearchTree.hh@ 5babc8b

ImprovedOutputFile Timing dual_readout llp
Last change on this file since 5babc8b was d69dfe4, checked in by pavel <pavel@…>, 11 years ago

upgrade fastjet to 3.0.6

  • Property mode set to 100644
File size: 25.4 KB
RevLine 
[d7d2da3]1//STARTHEADER
[d69dfe4]2// $Id: SearchTree.hh 3107 2013-05-03 15:47:47Z salam $
[d7d2da3]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
38FASTJET_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
52template<class T> class SearchTree {
53public:
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...
[d69dfe4]91#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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
112private:
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
[d69dfe4]131#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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
144template<class T> class SearchTree<T>::Node{
145public:
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//----------------------------------------------------------------------
173template<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
187template<class T> class SearchTree<T>::circulator{
188public:
189
190 // so that it can access out _node object;
[d69dfe4]191 // note: "class U" needed for clang (v1.1 branches/release_27) compilation
192 template<class U> friend class SearchTree<U>::const_circulator;
[d7d2da3]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
239private:
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
250template<class T> class SearchTree<T>::const_circulator{
251public:
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
299private:
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...
309template<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
324template<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
334template<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
[d69dfe4]343#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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//----------------------------------------------------------------------
378template<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
385template<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
[d69dfe4]393#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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//----------------------------------------------------------------------
451template<class T> void SearchTree<T>::remove(unsigned int node_index) {
452 remove(&(_nodes[node_index]));
453}
454
455//----------------------------------------------------------------------
456template<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
463template<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//----------------------------------------------------------------------
556template<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
[d69dfe4]568#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]569 unsigned int depth = 0;
570#endif
571 while(location != NULL) {
[d69dfe4]572#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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 }
[d69dfe4]580#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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//----------------------------------------------------------------------
613template<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//----------------------------------------------------------------------
632template<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//----------------------------------------------------------------------
658template<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//----------------------------------------------------------------------
698template<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//----------------------------------------------------------------------
722template<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...
747template<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//----------------------------------------------------------------------
758template<class T> typename SearchTree<T>::circulator SearchTree<T>::somewhere() {
759 return circulator(_top_node);
760}
761
762
763//----------------------------------------------------------------------
764template<class T> typename SearchTree<T>::const_circulator SearchTree<T>::somewhere() const {
765 return const_circulator(_top_node);
766}
767
768
769FASTJET_END_NAMESPACE
770
771#endif // __FASTJET_SEARCHTREE_HH__
Note: See TracBrowser for help on using the repository browser.