Fork me on GitHub

source: svn/trunk/Utilities/Fastjet/include/fastjet/internal/SearchTree.hh@ 1022

Last change on this file since 1022 was 11, checked in by severine ovyn, 16 years ago

Fastjet added; CDFCones directory has been changed

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