1 | //STARTHEADER |
---|
2 | // $Id: SearchTree.hh 2577 2011-09-13 15:11:38Z 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 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 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 | friend class SearchTree<T>::const_circulator; |
---|
192 | friend class SearchTree<T>; |
---|
193 | |
---|
194 | circulator() : _node(NULL) {} |
---|
195 | |
---|
196 | circulator(Node * node) : _node(node) {} |
---|
197 | |
---|
198 | const T * operator->() const {return &(_node->value);} |
---|
199 | T * operator->() {return &(_node->value);} |
---|
200 | const T & operator*() const {return _node->value;} |
---|
201 | T & operator*() {return _node->value;} |
---|
202 | |
---|
203 | /// prefix increment (structure copied from stl_bvector.h) |
---|
204 | circulator & operator++() { |
---|
205 | _node = _node->successor; |
---|
206 | return *this;} |
---|
207 | |
---|
208 | /// postfix increment ["int" argument tells compiler it's postfix] |
---|
209 | /// (structure copied from stl_bvector.h) |
---|
210 | circulator operator++(int) { |
---|
211 | circulator tmp = *this; |
---|
212 | _node = _node->successor; |
---|
213 | return tmp;} |
---|
214 | |
---|
215 | /// prefix decrement (structure copied from stl_bvector.h) |
---|
216 | circulator & operator--() { |
---|
217 | _node = _node->predecessor; |
---|
218 | return *this;} |
---|
219 | |
---|
220 | /// postfix decrement ["int" argument tells compiler it's postfix] |
---|
221 | /// (structure copied from stl_bvector.h) |
---|
222 | circulator operator--(int) { |
---|
223 | circulator tmp = *this; |
---|
224 | _node = _node->predecessor; |
---|
225 | return tmp;} |
---|
226 | |
---|
227 | /// return a circulator referring to the next node |
---|
228 | circulator next() const { |
---|
229 | return circulator(_node->successor);} |
---|
230 | |
---|
231 | /// return a circulator referring to the previous node |
---|
232 | circulator previous() const { |
---|
233 | return circulator(_node->predecessor);} |
---|
234 | |
---|
235 | bool operator!=(const circulator & other) const {return other._node != _node;} |
---|
236 | bool operator==(const circulator & other) const {return other._node == _node;} |
---|
237 | |
---|
238 | private: |
---|
239 | Node * _node; |
---|
240 | }; |
---|
241 | |
---|
242 | |
---|
243 | //====================================================================== |
---|
244 | /// \if internal_doc |
---|
245 | /// @ingroup internal |
---|
246 | /// \class SearchTree::const_circulator |
---|
247 | /// A const_circulator for the search tree |
---|
248 | /// \endif |
---|
249 | template<class T> class SearchTree<T>::const_circulator{ |
---|
250 | public: |
---|
251 | |
---|
252 | const_circulator() : _node(NULL) {} |
---|
253 | |
---|
254 | const_circulator(const Node * node) : _node(node) {} |
---|
255 | const_circulator(const circulator & circ) :_node(circ._node) {} |
---|
256 | |
---|
257 | const T * operator->() {return &(_node->value);} |
---|
258 | const T & operator*() const {return _node->value;} |
---|
259 | |
---|
260 | /// prefix increment (structure copied from stl_bvector.h) |
---|
261 | const_circulator & operator++() { |
---|
262 | _node = _node->successor; |
---|
263 | return *this;} |
---|
264 | |
---|
265 | /// postfix increment ["int" argument tells compiler it's postfix] |
---|
266 | /// (structure copied from stl_bvector.h) |
---|
267 | const_circulator operator++(int) { |
---|
268 | const_circulator tmp = *this; |
---|
269 | _node = _node->successor; |
---|
270 | return tmp;} |
---|
271 | |
---|
272 | |
---|
273 | /// prefix decrement (structure copied from stl_bvector.h) |
---|
274 | const_circulator & operator--() { |
---|
275 | _node = _node->predecessor; |
---|
276 | return *this;} |
---|
277 | |
---|
278 | /// postfix decrement ["int" argument tells compiler it's postfix] |
---|
279 | /// (structure copied from stl_bvector.h) |
---|
280 | const_circulator operator--(int) { |
---|
281 | const_circulator tmp = *this; |
---|
282 | _node = _node->predecessor; |
---|
283 | return tmp;} |
---|
284 | |
---|
285 | /// return a circulator referring to the next node |
---|
286 | const_circulator next() const { |
---|
287 | return const_circulator(_node->successor);} |
---|
288 | |
---|
289 | /// return a circulator referring to the previous node |
---|
290 | const_circulator previous() const { |
---|
291 | return const_circulator(_node->predecessor);} |
---|
292 | |
---|
293 | |
---|
294 | |
---|
295 | bool operator!=(const const_circulator & other) const {return other._node != _node;} |
---|
296 | bool operator==(const const_circulator & other) const {return other._node == _node;} |
---|
297 | |
---|
298 | private: |
---|
299 | const Node * _node; |
---|
300 | }; |
---|
301 | |
---|
302 | |
---|
303 | |
---|
304 | |
---|
305 | //---------------------------------------------------------------------- |
---|
306 | /// initialise from a sorted initial array allowing for a larger |
---|
307 | /// maximum size of the array... |
---|
308 | template<class T> SearchTree<T>::SearchTree(const std::vector<T> & init, |
---|
309 | unsigned int max_size) : |
---|
310 | _nodes(max_size) { |
---|
311 | |
---|
312 | _available_nodes.reserve(max_size); |
---|
313 | _available_nodes.resize(max_size - init.size()); |
---|
314 | for (unsigned int i = init.size(); i < max_size; i++) { |
---|
315 | _available_nodes[i-init.size()] = &(_nodes[i]); |
---|
316 | } |
---|
317 | |
---|
318 | _initialize(init); |
---|
319 | } |
---|
320 | |
---|
321 | //---------------------------------------------------------------------- |
---|
322 | /// initialise from a sorted initial array |
---|
323 | template<class T> SearchTree<T>::SearchTree(const std::vector<T> & init) : |
---|
324 | _nodes(init.size()), _available_nodes(0) { |
---|
325 | |
---|
326 | // reserve space for the list of available nodes |
---|
327 | _available_nodes.reserve(init.size()); |
---|
328 | _initialize(init); |
---|
329 | } |
---|
330 | |
---|
331 | //---------------------------------------------------------------------- |
---|
332 | /// do the actual hard work of initialization |
---|
333 | template<class T> void SearchTree<T>::_initialize(const std::vector<T> & init) { |
---|
334 | |
---|
335 | _n_removes = 0; |
---|
336 | unsigned n = init.size(); |
---|
337 | assert(n>=1); |
---|
338 | |
---|
339 | // reserve space for the list of available nodes |
---|
340 | //_available_nodes.reserve(); |
---|
341 | |
---|
342 | #ifdef TRACK_DEPTH |
---|
343 | _max_depth = 0; |
---|
344 | #endif |
---|
345 | |
---|
346 | |
---|
347 | // validate the input |
---|
348 | for (unsigned int i = 1; i<n; i++) { |
---|
349 | assert(!(init[i] < init[i-1])); |
---|
350 | } |
---|
351 | |
---|
352 | // now initialise the vector; link neighbours in the sequence |
---|
353 | for(unsigned int i = 0; i < n; i++) { |
---|
354 | _nodes[i].value = init[i]; |
---|
355 | _nodes[i].predecessor = (& (_nodes[i])) - 1; |
---|
356 | _nodes[i].successor = (& (_nodes[i])) + 1; |
---|
357 | _nodes[i].nullify_treelinks(); |
---|
358 | } |
---|
359 | // make a loop structure so that we can circulate... |
---|
360 | _nodes[0].predecessor = (& (_nodes[n-1])); |
---|
361 | _nodes[n-1].successor = (& (_nodes[0])); |
---|
362 | |
---|
363 | // now label the rest of the nodes |
---|
364 | unsigned int scale = (n+1)/2; |
---|
365 | unsigned int top = std::min(n-1,scale); |
---|
366 | _nodes[top].parent = NULL; |
---|
367 | _top_node = &(_nodes[top]); |
---|
368 | _do_initial_connections(top, scale, 0, n, 0); |
---|
369 | |
---|
370 | // make sure things are sensible... |
---|
371 | //verify_structure(); |
---|
372 | } |
---|
373 | |
---|
374 | |
---|
375 | |
---|
376 | //---------------------------------------------------------------------- |
---|
377 | template<class T> inline int SearchTree<T>::loc(const Node * node) const {return node == NULL? |
---|
378 | -999 : node - &(_nodes[0]);} |
---|
379 | |
---|
380 | |
---|
381 | //---------------------------------------------------------------------- |
---|
382 | /// Recursive creation of connections, assuming the _nodes vector is |
---|
383 | /// completely filled and ordered |
---|
384 | template<class T> void SearchTree<T>::_do_initial_connections( |
---|
385 | unsigned int this_one, |
---|
386 | unsigned int scale, |
---|
387 | unsigned int left_edge, |
---|
388 | unsigned int right_edge, |
---|
389 | unsigned int depth |
---|
390 | ) { |
---|
391 | |
---|
392 | #ifdef TRACK_DEPTH |
---|
393 | // keep track of tree depth for checking things stay reasonable... |
---|
394 | _max_depth = max(depth, _max_depth); |
---|
395 | #endif |
---|
396 | |
---|
397 | //std::cout << this_one << " "<< scale<< std::endl; |
---|
398 | unsigned int ref_new_scale = (scale+1)/2; |
---|
399 | |
---|
400 | // work through children to our left |
---|
401 | unsigned new_scale = ref_new_scale; |
---|
402 | bool did_child = false; |
---|
403 | while(true) { |
---|
404 | int left = this_one - new_scale; // be careful here to use signed int... |
---|
405 | // if there is something unitialised to our left, link to it |
---|
406 | if (left >= static_cast<int>(left_edge) |
---|
407 | && _nodes[left].treelinks_null() ) { |
---|
408 | _nodes[left].parent = &(_nodes[this_one]); |
---|
409 | _nodes[this_one].left = &(_nodes[left]); |
---|
410 | // create connections between left_edge and this_one |
---|
411 | _do_initial_connections(left, new_scale, left_edge, this_one, depth+1); |
---|
412 | did_child = true; |
---|
413 | break; |
---|
414 | } |
---|
415 | // reduce the scale so as to try again |
---|
416 | unsigned int old_new_scale = new_scale; |
---|
417 | new_scale = (old_new_scale + 1)/2; |
---|
418 | // unless we've reached end of tree |
---|
419 | if (new_scale == old_new_scale) break; |
---|
420 | } |
---|
421 | if (!did_child) {_nodes[this_one].left = NULL;} |
---|
422 | |
---|
423 | |
---|
424 | // work through children to our right |
---|
425 | new_scale = ref_new_scale; |
---|
426 | did_child = false; |
---|
427 | while(true) { |
---|
428 | unsigned int right = this_one + new_scale; |
---|
429 | if (right < right_edge && _nodes[right].treelinks_null()) { |
---|
430 | _nodes[right].parent = &(_nodes[this_one]); |
---|
431 | _nodes[this_one].right = &(_nodes[right]); |
---|
432 | // create connections between this_one+1 and right_edge |
---|
433 | _do_initial_connections(right, new_scale, this_one+1,right_edge,depth+1); |
---|
434 | did_child = true; |
---|
435 | break; |
---|
436 | } |
---|
437 | // reduce the scale so as to try again |
---|
438 | unsigned int old_new_scale = new_scale; |
---|
439 | new_scale = (old_new_scale + 1)/2; |
---|
440 | // unless we've reached end of tree |
---|
441 | if (new_scale == old_new_scale) break; |
---|
442 | } |
---|
443 | if (!did_child) {_nodes[this_one].right = NULL;} |
---|
444 | |
---|
445 | } |
---|
446 | |
---|
447 | |
---|
448 | |
---|
449 | //---------------------------------------------------------------------- |
---|
450 | template<class T> void SearchTree<T>::remove(unsigned int node_index) { |
---|
451 | remove(&(_nodes[node_index])); |
---|
452 | } |
---|
453 | |
---|
454 | //---------------------------------------------------------------------- |
---|
455 | template<class T> void SearchTree<T>::remove(circulator & circ) { |
---|
456 | remove(circ._node); |
---|
457 | } |
---|
458 | |
---|
459 | //---------------------------------------------------------------------- |
---|
460 | // Useful reference for this: |
---|
461 | // http://en.wikipedia.org/wiki/Binary_search_tree#Deletion |
---|
462 | template<class T> void SearchTree<T>::remove(typename SearchTree<T>::Node * node) { |
---|
463 | |
---|
464 | // we don't remove things from the tree if we've reached the last |
---|
465 | // elements... (is this wise?) |
---|
466 | assert(size() > 1); // switch this to throw...? |
---|
467 | assert(!node->treelinks_null()); |
---|
468 | |
---|
469 | // deal with relinking predecessor and successor |
---|
470 | node->predecessor->successor = node->successor; |
---|
471 | node->successor->predecessor = node->predecessor; |
---|
472 | |
---|
473 | if (node->left == NULL && node->right == NULL) { |
---|
474 | // node has no children, so remove it by nullifying the pointer |
---|
475 | // from the parent |
---|
476 | node->reset_parents_link_to_me(NULL); |
---|
477 | |
---|
478 | } else if (node->left != NULL && node->right == NULL){ |
---|
479 | // make parent point to my child |
---|
480 | node->reset_parents_link_to_me(node->left); |
---|
481 | // and child to parent |
---|
482 | node->left->parent = node->parent; |
---|
483 | // sort out the top node... |
---|
484 | if (_top_node == node) {_top_node = node->left;} |
---|
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->right); |
---|
489 | // and child to parent |
---|
490 | node->right->parent = node->parent; |
---|
491 | // sort out the top node... |
---|
492 | if (_top_node == node) {_top_node = node->right;} |
---|
493 | |
---|
494 | } else { |
---|
495 | // we have two children; we will put a replacement in our place |
---|
496 | Node * replacement; |
---|
497 | //SearchTree<T>::Node * replacements_child; |
---|
498 | // chose predecessor or successor (one, then other, then first, etc...) |
---|
499 | bool use_predecessor = (_n_removes % 2 == 1); |
---|
500 | if (use_predecessor) { |
---|
501 | // Option 1: put predecessor in our place, and have its parent |
---|
502 | // point to its left child (as a predecessor it has no right child) |
---|
503 | replacement = node->predecessor; |
---|
504 | assert(replacement->right == NULL); // guaranteed if it's our predecessor |
---|
505 | // we have to be careful of replacing certain links when the |
---|
506 | // replacement is this node's child |
---|
507 | if (replacement != node->left) { |
---|
508 | if (replacement->left != NULL) { |
---|
509 | replacement->left->parent = replacement->parent;} |
---|
510 | replacement->reset_parents_link_to_me(replacement->left); |
---|
511 | replacement->left = node->left; |
---|
512 | } |
---|
513 | replacement->parent = node->parent; |
---|
514 | replacement->right = node->right; |
---|
515 | } else { |
---|
516 | // Option 2: put successor in our place, and have its parent |
---|
517 | // point to its right child (as a successor it has no left child) |
---|
518 | replacement = node->successor; |
---|
519 | assert(replacement->left == NULL); // guaranteed if it's our successor |
---|
520 | if (replacement != node->right) { |
---|
521 | if (replacement->right != NULL) { |
---|
522 | replacement->right->parent = replacement->parent;} |
---|
523 | replacement->reset_parents_link_to_me(replacement->right); |
---|
524 | replacement->right = node->right; |
---|
525 | } |
---|
526 | replacement->parent = node->parent; |
---|
527 | replacement->left = node->left; |
---|
528 | } |
---|
529 | node->reset_parents_link_to_me(replacement); |
---|
530 | |
---|
531 | // make sure node's original children now point to the replacement |
---|
532 | if (node->left != replacement) {node->left->parent = replacement;} |
---|
533 | if (node->right != replacement) {node->right->parent = replacement;} |
---|
534 | |
---|
535 | // sort out the top node... |
---|
536 | if (_top_node == node) {_top_node = replacement;} |
---|
537 | } |
---|
538 | |
---|
539 | // make sure we leave something nice and clean... |
---|
540 | node->nullify_treelinks(); |
---|
541 | node->predecessor = NULL; |
---|
542 | node->successor = NULL; |
---|
543 | |
---|
544 | // for bookkeeping (and choosing whether to use pred. or succ.) |
---|
545 | _n_removes++; |
---|
546 | // for when we next need access to a free node... |
---|
547 | _available_nodes.push_back(node); |
---|
548 | } |
---|
549 | |
---|
550 | |
---|
551 | //---------------------------------------------------------------------- |
---|
552 | //template<class T> typename SearchTree<T>::Node * SearchTree<T>::insert(const T & value) { |
---|
553 | |
---|
554 | //---------------------------------------------------------------------- |
---|
555 | template<class T> typename SearchTree<T>::circulator SearchTree<T>::insert(const T & value) { |
---|
556 | // make sure we don't exceed allowed number of nodes... |
---|
557 | assert(_available_nodes.size() > 0); |
---|
558 | |
---|
559 | Node * node = _available_nodes.back(); |
---|
560 | _available_nodes.pop_back(); |
---|
561 | node->value = value; |
---|
562 | |
---|
563 | Node * location = _top_node; |
---|
564 | Node * old_location = NULL; |
---|
565 | bool on_left = true; // (init not needed -- but soothes g++4) |
---|
566 | // work through tree until we reach its end |
---|
567 | #ifdef TRACK_DEPTH |
---|
568 | unsigned int depth = 0; |
---|
569 | #endif |
---|
570 | while(location != NULL) { |
---|
571 | #ifdef TRACK_DEPTH |
---|
572 | depth++; |
---|
573 | #endif |
---|
574 | old_location = location; |
---|
575 | on_left = value < location->value; |
---|
576 | if (on_left) {location = location->left;} |
---|
577 | else {location = location->right;} |
---|
578 | } |
---|
579 | #ifdef TRACK_DEPTH |
---|
580 | _max_depth = max(depth, _max_depth); |
---|
581 | #endif |
---|
582 | // now create tree links |
---|
583 | node->parent = old_location; |
---|
584 | if (on_left) {node->parent->left = node;} |
---|
585 | else {node->parent->right = node;} |
---|
586 | node->left = NULL; |
---|
587 | node->right = NULL; |
---|
588 | // and create predecessor / successor links |
---|
589 | node->predecessor = _find_predecessor(node); |
---|
590 | if (node->predecessor != NULL) { |
---|
591 | // it exists, so make use of its info (will include a cyclic case, |
---|
592 | // when successor is round the bend) |
---|
593 | node->successor = node->predecessor->successor; |
---|
594 | node->predecessor->successor = node; |
---|
595 | node->successor->predecessor = node; |
---|
596 | } else { |
---|
597 | // deal with case when we are left-most edge of tree (then successor |
---|
598 | // will exist...) |
---|
599 | node->successor = _find_successor(node); |
---|
600 | assert(node->successor != NULL); // can only happen if we're sole element |
---|
601 | // (but not allowed, since tree size>=1) |
---|
602 | node->predecessor = node->successor->predecessor; |
---|
603 | node->successor->predecessor = node; |
---|
604 | node->predecessor->successor = node; |
---|
605 | } |
---|
606 | |
---|
607 | return circulator(node); |
---|
608 | } |
---|
609 | |
---|
610 | |
---|
611 | //---------------------------------------------------------------------- |
---|
612 | template<class T> void SearchTree<T>::verify_structure() { |
---|
613 | |
---|
614 | // do a check running through all elements |
---|
615 | verify_structure_linear(); |
---|
616 | |
---|
617 | // do a recursive check down tree from top |
---|
618 | |
---|
619 | // first establish the extremities |
---|
620 | const Node * left_limit = _top_node; |
---|
621 | while (left_limit->left != NULL) {left_limit = left_limit->left;} |
---|
622 | const Node * right_limit = _top_node; |
---|
623 | while (right_limit->right != NULL) {right_limit = right_limit->right;} |
---|
624 | |
---|
625 | // then actually do recursion |
---|
626 | verify_structure_recursive(_top_node, left_limit, right_limit); |
---|
627 | } |
---|
628 | |
---|
629 | |
---|
630 | //---------------------------------------------------------------------- |
---|
631 | template<class T> void SearchTree<T>::verify_structure_recursive( |
---|
632 | const typename SearchTree<T>::Node * element, |
---|
633 | const typename SearchTree<T>::Node * left_limit, |
---|
634 | const typename SearchTree<T>::Node * right_limit) const { |
---|
635 | |
---|
636 | assert(!(element->value < left_limit->value)); |
---|
637 | assert(!(right_limit->value < element->value)); |
---|
638 | |
---|
639 | const Node * left = element->left; |
---|
640 | if (left != NULL) { |
---|
641 | assert(!(element->value < left->value)); |
---|
642 | if (left != left_limit) { |
---|
643 | // recurse down the tree with this element as the right-hand limit |
---|
644 | verify_structure_recursive(left, left_limit, element);} |
---|
645 | } |
---|
646 | |
---|
647 | const Node * right = element->right; |
---|
648 | if (right != NULL) { |
---|
649 | assert(!(right->value < element->value)); |
---|
650 | if (right != right_limit) { |
---|
651 | // recurse down the tree with this element as the left-hand limit |
---|
652 | verify_structure_recursive(right, element, right_limit);} |
---|
653 | } |
---|
654 | } |
---|
655 | |
---|
656 | //---------------------------------------------------------------------- |
---|
657 | template<class T> void SearchTree<T>::verify_structure_linear() const { |
---|
658 | |
---|
659 | //print_elements(); |
---|
660 | |
---|
661 | unsigned n_top = 0; |
---|
662 | unsigned n_null = 0; |
---|
663 | for(unsigned i = 0; i < _nodes.size(); i++) { |
---|
664 | const typename SearchTree<T>::Node * node = &(_nodes[i]); |
---|
665 | // make sure node is defined |
---|
666 | if (node->treelinks_null()) {n_null++; continue;} |
---|
667 | |
---|
668 | // make sure of the number of "top" nodes |
---|
669 | if (node->parent == NULL) { |
---|
670 | n_top++; |
---|
671 | //assert(node->left != NULL); |
---|
672 | //assert(node->right != NULL); |
---|
673 | } else { |
---|
674 | // make sure that I am a child of my parent... |
---|
675 | //assert((node->parent->left == node) || (node->parent->right == node)); |
---|
676 | assert((node->parent->left == node) ^ (node->parent->right == node)); |
---|
677 | } |
---|
678 | |
---|
679 | // when there is a left child make sure it's value is ordered |
---|
680 | // (note use of !(b<a), to allow for a<=b while using just the < |
---|
681 | // operator) |
---|
682 | if (node->left != NULL) { |
---|
683 | assert(!(node->value < node->left->value ));} |
---|
684 | |
---|
685 | // when there is a right child make sure it's value is ordered |
---|
686 | if (node->right != NULL) { |
---|
687 | assert(!(node->right->value < node->value ));} |
---|
688 | |
---|
689 | } |
---|
690 | assert(n_top == 1 || (n_top == 0 && size() <= 1) ); |
---|
691 | assert(n_null == _available_nodes.size() || |
---|
692 | (n_null == _available_nodes.size() + 1 && size() == 1)); |
---|
693 | } |
---|
694 | |
---|
695 | |
---|
696 | //---------------------------------------------------------------------- |
---|
697 | template<class T> typename SearchTree<T>::Node * SearchTree<T>::_find_predecessor(const typename SearchTree<T>::Node * node) { |
---|
698 | |
---|
699 | typename SearchTree<T>::Node * newnode; |
---|
700 | if (node->left != NULL) { |
---|
701 | // go down left, and then down right as far as possible. |
---|
702 | newnode = node->left; |
---|
703 | while(newnode->right != NULL) {newnode = newnode->right;} |
---|
704 | return newnode; |
---|
705 | } else { |
---|
706 | const typename SearchTree<T>::Node * lastnode = node; |
---|
707 | newnode = node->parent; |
---|
708 | // go up the tree as long as we're going right (when we go left then |
---|
709 | // we've found something smaller, so stop) |
---|
710 | while(newnode != NULL) { |
---|
711 | if (newnode->right == lastnode) {return newnode;} |
---|
712 | lastnode = newnode; |
---|
713 | newnode = newnode->parent; |
---|
714 | } |
---|
715 | return newnode; |
---|
716 | } |
---|
717 | } |
---|
718 | |
---|
719 | |
---|
720 | //---------------------------------------------------------------------- |
---|
721 | template<class T> typename SearchTree<T>::Node * SearchTree<T>::_find_successor(const typename SearchTree<T>::Node * node) { |
---|
722 | |
---|
723 | typename SearchTree<T>::Node * newnode; |
---|
724 | if (node->right != NULL) { |
---|
725 | // go down right, and then down left as far as possible. |
---|
726 | newnode = node->right; |
---|
727 | while(newnode->left != NULL) {newnode = newnode->left;} |
---|
728 | return newnode; |
---|
729 | } else { |
---|
730 | const typename SearchTree<T>::Node * lastnode = node; |
---|
731 | newnode = node->parent; |
---|
732 | // go up the tree as long as we're going left (when we go right then |
---|
733 | // we've found something larger, so stop) |
---|
734 | while(newnode != NULL) { |
---|
735 | if (newnode->left == lastnode) {return newnode;} |
---|
736 | lastnode = newnode; |
---|
737 | newnode = newnode->parent; |
---|
738 | } |
---|
739 | return newnode; |
---|
740 | } |
---|
741 | } |
---|
742 | |
---|
743 | |
---|
744 | //---------------------------------------------------------------------- |
---|
745 | // print out all the elements for visual checking... |
---|
746 | template<class T> void SearchTree<T>::print_elements() { |
---|
747 | typename SearchTree<T>::Node * base_node = &(_nodes[0]); |
---|
748 | typename SearchTree<T>::Node * node = base_node; |
---|
749 | |
---|
750 | int n = _nodes.size(); |
---|
751 | for(; node - base_node < n ; node++) { |
---|
752 | 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); |
---|
753 | } |
---|
754 | } |
---|
755 | |
---|
756 | //---------------------------------------------------------------------- |
---|
757 | template<class T> typename SearchTree<T>::circulator SearchTree<T>::somewhere() { |
---|
758 | return circulator(_top_node); |
---|
759 | } |
---|
760 | |
---|
761 | |
---|
762 | //---------------------------------------------------------------------- |
---|
763 | template<class T> typename SearchTree<T>::const_circulator SearchTree<T>::somewhere() const { |
---|
764 | return const_circulator(_top_node); |
---|
765 | } |
---|
766 | |
---|
767 | |
---|
768 | FASTJET_END_NAMESPACE |
---|
769 | |
---|
770 | #endif // __FASTJET_SEARCHTREE_HH__ |
---|