Fork me on GitHub

source: git/external/fastjet/internal/SearchTree.hh@ e7cccc2

3.4.3pre05
Last change on this file since e7cccc2 was b7b836a, checked in by Pavel Demin <pavel-demin@…>, 7 years ago

update FastJet library to 3.3.1 and FastJet Contrib library to 1.036

  • Property mode set to 100644
File size: 26.0 KB
RevLine 
[35cdc46]1//FJSTARTHEADER
[b7b836a]2// $Id: SearchTree.hh 4354 2018-04-22 07:12:37Z salam $
[d7d2da3]3//
[b7b836a]4// Copyright (c) 2005-2018, Matteo Cacciari, Gavin P. Salam and Gregory Soyez
[d7d2da3]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
[35cdc46]15// development. They are described in the original FastJet paper,
16// hep-ph/0512210 and in the manual, arXiv:1111.6097. If you use
[d7d2da3]17// FastJet as part of work towards a scientific publication, please
[35cdc46]18// quote the version you use and include a citation to the manual and
19// optionally also to hep-ph/0512210.
[d7d2da3]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//----------------------------------------------------------------------
[35cdc46]29//FJENDHEADER
[d7d2da3]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
40FASTJET_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
54template<class T> class SearchTree {
55public:
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...
[d69dfe4]93#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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
114private:
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
[d69dfe4]133#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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
146template<class T> class SearchTree<T>::Node{
147public:
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//----------------------------------------------------------------------
175template<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
189template<class T> class SearchTree<T>::circulator{
190public:
191
[35cdc46]192 // so that it can access our _node object;
[d69dfe4]193 // note: "class U" needed for clang (v1.1 branches/release_27) compilation
[35cdc46]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;
[d7d2da3]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
246private:
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
257template<class T> class SearchTree<T>::const_circulator{
258public:
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
306private:
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...
316template<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
331template<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
341template<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
[d69dfe4]350#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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//----------------------------------------------------------------------
385template<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
392template<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
[d69dfe4]400#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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//----------------------------------------------------------------------
458template<class T> void SearchTree<T>::remove(unsigned int node_index) {
459 remove(&(_nodes[node_index]));
460}
461
462//----------------------------------------------------------------------
463template<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
470template<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//----------------------------------------------------------------------
563template<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
[d69dfe4]575#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]576 unsigned int depth = 0;
577#endif
578 while(location != NULL) {
[d69dfe4]579#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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 }
[d69dfe4]587#ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
[d7d2da3]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//----------------------------------------------------------------------
620template<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//----------------------------------------------------------------------
639template<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//----------------------------------------------------------------------
665template<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//----------------------------------------------------------------------
705template<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//----------------------------------------------------------------------
729template<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...
754template<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//----------------------------------------------------------------------
765template<class T> typename SearchTree<T>::circulator SearchTree<T>::somewhere() {
766 return circulator(_top_node);
767}
768
769
770//----------------------------------------------------------------------
771template<class T> typename SearchTree<T>::const_circulator SearchTree<T>::somewhere() const {
772 return const_circulator(_top_node);
773}
774
775
776FASTJET_END_NAMESPACE
777
778#endif // __FASTJET_SEARCHTREE_HH__
Note: See TracBrowser for help on using the repository browser.