00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032 #ifndef __FASTJET_SEARCHTREE_HH__
00033 #define __FASTJET_SEARCHTREE_HH__
00034
00035 #include<vector>
00036 #include<cassert>
00037 #include<cstddef>
00038 #include "fastjet/internal/base.hh"
00039
00040 FASTJET_BEGIN_NAMESPACE
00041
00042
00043
00048 template<class T> class SearchTree {
00049 public:
00050
00051 class Node;
00052 class circulator;
00053 class const_circulator;
00054
00056 SearchTree(const std::vector<T> & init);
00057
00060 SearchTree(const std::vector<T> & init, unsigned int max_size);
00061
00063 void remove(unsigned node_index);
00064 void remove(SearchTree::Node * node);
00065 void remove(SearchTree::circulator & circ);
00066
00069
00070 circulator insert(const T & value);
00071
00072 const Node & operator[](int i) const {return _nodes[i];};
00073
00075 unsigned int size() const {return _nodes.size() - _available_nodes.size();}
00076
00078 void verify_structure();
00079 void verify_structure_linear() const;
00080 void verify_structure_recursive(const Node * , const Node * , const Node * ) const;
00081
00083 void print_elements();
00084
00085
00086
00087 #ifdef TRACK_DEPTH
00089 inline unsigned int max_depth() const {return _max_depth;};
00090 #else
00091 inline unsigned int max_depth() const {return 0;};
00092 #endif
00093
00094 int loc(const Node * node) const ;
00095
00097 Node * _find_predecessor(const Node *);
00099 Node * _find_successor(const Node *);
00100
00101 const Node & operator[](unsigned int i) const {return _nodes[i];};
00102
00105 const_circulator somewhere() const;
00106 circulator somewhere();
00107
00108 private:
00109
00110 void _initialize(const std::vector<T> & init);
00111
00112 std::vector<Node> _nodes;
00113 std::vector<Node *> _available_nodes;
00114 Node * _top_node;
00115 unsigned int _n_removes;
00116
00117
00122 void _do_initial_connections(unsigned int this_one, unsigned int scale,
00123 unsigned int left_edge, unsigned int right_edge,
00124 unsigned int depth);
00125
00126
00127 #ifdef TRACK_DEPTH
00128 unsigned int _max_depth;
00129 #endif
00130
00131 };
00132
00133
00134
00135 template<class T> class SearchTree<T>::Node{
00136 public:
00137 Node() {};
00138
00139
00141 bool treelinks_null() const {
00142 return ((parent==0) && (left==0) && (right==0));};
00143
00145 inline void nullify_treelinks() {
00146 parent = NULL;
00147 left = NULL;
00148 right = NULL;
00149 };
00150
00153 void reset_parents_link_to_me(Node * XX);
00154
00155 T value;
00156 Node * left;
00157 Node * right;
00158 Node * parent;
00159 Node * successor;
00160 Node * predecessor;
00161 };
00162
00163
00164 template<class T> void SearchTree<T>::Node::reset_parents_link_to_me(SearchTree<T>::Node * XX) {
00165 if (parent == NULL) {return;}
00166 if (parent->right == this) {parent->right = XX;}
00167 else {parent->left = XX;}
00168 }
00169
00170
00171
00172
00173 template<class T> class SearchTree<T>::circulator{
00174 public:
00175
00176
00177 friend class SearchTree<T>::const_circulator;
00178 friend class SearchTree<T>;
00179
00180 circulator() : _node(NULL) {}
00181
00182 circulator(Node * node) : _node(node) {}
00183
00184 const T * operator->() const {return &(_node->value);}
00185 T * operator->() {return &(_node->value);}
00186 const T & operator*() const {return _node->value;}
00187 T & operator*() {return _node->value;}
00188
00190 circulator & operator++() {
00191 _node = _node->successor;
00192 return *this;}
00193
00196 circulator operator++(int) {
00197 circulator tmp = *this;
00198 _node = _node->successor;
00199 return tmp;}
00200
00202 circulator & operator--() {
00203 _node = _node->predecessor;
00204 return *this;}
00205
00208 circulator operator--(int) {
00209 circulator tmp = *this;
00210 _node = _node->predecessor;
00211 return tmp;}
00212
00214 circulator next() const {
00215 return circulator(_node->successor);}
00216
00218 circulator previous() const {
00219 return circulator(_node->predecessor);}
00220
00221 bool operator!=(const circulator & other) const {return other._node != _node;}
00222 bool operator==(const circulator & other) const {return other._node == _node;}
00223
00224 private:
00225 Node * _node;
00226 };
00227
00228
00229
00230 template<class T> class SearchTree<T>::const_circulator{
00231 public:
00232
00233 const_circulator() : _node(NULL) {}
00234
00235 const_circulator(const Node * node) : _node(node) {}
00236 const_circulator(const circulator & circ) :_node(circ._node) {}
00237
00238 const T * operator->() {return &(_node->value);}
00239 const T & operator*() const {return _node->value;}
00240
00242 const_circulator & operator++() {
00243 _node = _node->successor;
00244 return *this;}
00245
00248 const_circulator operator++(int) {
00249 const_circulator tmp = *this;
00250 _node = _node->successor;
00251 return tmp;}
00252
00253
00255 const_circulator & operator--() {
00256 _node = _node->predecessor;
00257 return *this;}
00258
00261 const_circulator operator--(int) {
00262 const_circulator tmp = *this;
00263 _node = _node->predecessor;
00264 return tmp;}
00265
00267 const_circulator next() const {
00268 return const_circulator(_node->successor);}
00269
00271 const_circulator previous() const {
00272 return const_circulator(_node->predecessor);}
00273
00274
00275
00276 bool operator!=(const const_circulator & other) const {return other._node != _node;}
00277 bool operator==(const const_circulator & other) const {return other._node == _node;}
00278
00279 private:
00280 const Node * _node;
00281 };
00282
00283
00284
00285
00286
00289 template<class T> SearchTree<T>::SearchTree(const std::vector<T> & init,
00290 unsigned int max_size) :
00291 _nodes(max_size) {
00292
00293 _available_nodes.reserve(max_size);
00294 _available_nodes.resize(max_size - init.size());
00295 for (unsigned int i = init.size(); i < max_size; i++) {
00296 _available_nodes[i-init.size()] = &(_nodes[i]);
00297 }
00298
00299 _initialize(init);
00300 }
00301
00302
00304 template<class T> SearchTree<T>::SearchTree(const std::vector<T> & init) :
00305 _nodes(init.size()), _available_nodes(0) {
00306
00307
00308 _available_nodes.reserve(init.size());
00309 _initialize(init);
00310 }
00311
00312
00314 template<class T> void SearchTree<T>::_initialize(const std::vector<T> & init) {
00315
00316 _n_removes = 0;
00317 unsigned n = init.size();
00318 assert(n>=1);
00319
00320
00321
00322
00323 #ifdef TRACK_DEPTH
00324 _max_depth = 0;
00325 #endif
00326
00327
00328
00329 for (unsigned int i = 1; i<n; i++) {
00330 assert(!(init[i] < init[i-1]));
00331 }
00332
00333
00334 for(unsigned int i = 0; i < n; i++) {
00335 _nodes[i].value = init[i];
00336 _nodes[i].predecessor = (& (_nodes[i])) - 1;
00337 _nodes[i].successor = (& (_nodes[i])) + 1;
00338 _nodes[i].nullify_treelinks();
00339 }
00340
00341 _nodes[0].predecessor = (& (_nodes[n-1]));
00342 _nodes[n-1].successor = (& (_nodes[0]));
00343
00344
00345 unsigned int scale = (n+1)/2;
00346 unsigned int top = std::min(n-1,scale);
00347 _nodes[top].parent = NULL;
00348 _top_node = &(_nodes[top]);
00349 _do_initial_connections(top, scale, 0, n, 0);
00350
00351
00352
00353 }
00354
00355
00356
00357
00358 template<class T> inline int SearchTree<T>::loc(const Node * node) const {return node == NULL?
00359 -999 : node - &(_nodes[0]);}
00360
00361
00362
00365 template<class T> void SearchTree<T>::_do_initial_connections(
00366 unsigned int this_one,
00367 unsigned int scale,
00368 unsigned int left_edge,
00369 unsigned int right_edge,
00370 unsigned int depth
00371 ) {
00372
00373 #ifdef TRACK_DEPTH
00374
00375 _max_depth = max(depth, _max_depth);
00376 #endif
00377
00378
00379 unsigned int ref_new_scale = (scale+1)/2;
00380
00381
00382 unsigned new_scale = ref_new_scale;
00383 bool did_child = false;
00384 while(true) {
00385 int left = this_one - new_scale;
00386
00387 if (left >= static_cast<int>(left_edge)
00388 && _nodes[left].treelinks_null() ) {
00389 _nodes[left].parent = &(_nodes[this_one]);
00390 _nodes[this_one].left = &(_nodes[left]);
00391
00392 _do_initial_connections(left, new_scale, left_edge, this_one, depth+1);
00393 did_child = true;
00394 break;
00395 }
00396
00397 unsigned int old_new_scale = new_scale;
00398 new_scale = (old_new_scale + 1)/2;
00399
00400 if (new_scale == old_new_scale) break;
00401 }
00402 if (!did_child) {_nodes[this_one].left = NULL;}
00403
00404
00405
00406 new_scale = ref_new_scale;
00407 did_child = false;
00408 while(true) {
00409 unsigned int right = this_one + new_scale;
00410 if (right < right_edge && _nodes[right].treelinks_null()) {
00411 _nodes[right].parent = &(_nodes[this_one]);
00412 _nodes[this_one].right = &(_nodes[right]);
00413
00414 _do_initial_connections(right, new_scale, this_one+1,right_edge,depth+1);
00415 did_child = true;
00416 break;
00417 }
00418
00419 unsigned int old_new_scale = new_scale;
00420 new_scale = (old_new_scale + 1)/2;
00421
00422 if (new_scale == old_new_scale) break;
00423 }
00424 if (!did_child) {_nodes[this_one].right = NULL;}
00425
00426 }
00427
00428
00429
00430
00431 template<class T> void SearchTree<T>::remove(unsigned int node_index) {
00432 remove(&(_nodes[node_index]));
00433 }
00434
00435
00436 template<class T> void SearchTree<T>::remove(circulator & circ) {
00437 remove(circ._node);
00438 }
00439
00440
00441
00442
00443 template<class T> void SearchTree<T>::remove(SearchTree<T>::Node * node) {
00444
00445
00446
00447 assert(size() > 1);
00448 assert(!node->treelinks_null());
00449
00450
00451 node->predecessor->successor = node->successor;
00452 node->successor->predecessor = node->predecessor;
00453
00454 if (node->left == NULL && node->right == NULL) {
00455
00456
00457 node->reset_parents_link_to_me(NULL);
00458
00459 } else if (node->left != NULL && node->right == NULL){
00460
00461 node->reset_parents_link_to_me(node->left);
00462
00463 node->left->parent = node->parent;
00464
00465 if (_top_node == node) {_top_node = node->left;}
00466
00467 } else if (node->left == NULL && node->right != NULL){
00468
00469 node->reset_parents_link_to_me(node->right);
00470
00471 node->right->parent = node->parent;
00472
00473 if (_top_node == node) {_top_node = node->right;}
00474
00475 } else {
00476
00477 Node * replacement;
00478
00479
00480 bool use_predecessor = (_n_removes % 2 == 1);
00481 if (use_predecessor) {
00482
00483
00484 replacement = node->predecessor;
00485 assert(replacement->right == NULL);
00486
00487
00488 if (replacement != node->left) {
00489 if (replacement->left != NULL) {
00490 replacement->left->parent = replacement->parent;}
00491 replacement->reset_parents_link_to_me(replacement->left);
00492 replacement->left = node->left;
00493 }
00494 replacement->parent = node->parent;
00495 replacement->right = node->right;
00496 } else {
00497
00498
00499 replacement = node->successor;
00500 assert(replacement->left == NULL);
00501 if (replacement != node->right) {
00502 if (replacement->right != NULL) {
00503 replacement->right->parent = replacement->parent;}
00504 replacement->reset_parents_link_to_me(replacement->right);
00505 replacement->right = node->right;
00506 }
00507 replacement->parent = node->parent;
00508 replacement->left = node->left;
00509 }
00510 node->reset_parents_link_to_me(replacement);
00511
00512
00513 if (node->left != replacement) {node->left->parent = replacement;}
00514 if (node->right != replacement) {node->right->parent = replacement;}
00515
00516
00517 if (_top_node == node) {_top_node = replacement;}
00518 }
00519
00520
00521 node->nullify_treelinks();
00522 node->predecessor = NULL;
00523 node->successor = NULL;
00524
00525
00526 _n_removes++;
00527
00528 _available_nodes.push_back(node);
00529 }
00530
00531
00532
00533
00534
00535
00536 template<class T> typename SearchTree<T>::circulator SearchTree<T>::insert(const T & value) {
00537
00538 assert(_available_nodes.size() > 0);
00539
00540 Node * node = _available_nodes.back();
00541 _available_nodes.pop_back();
00542 node->value = value;
00543
00544 Node * location = _top_node;
00545 Node * old_location = NULL;
00546 bool on_left = true;
00547
00548 #ifdef TRACK_DEPTH
00549 unsigned int depth = 0;
00550 #endif
00551 while(location != NULL) {
00552 #ifdef TRACK_DEPTH
00553 depth++;
00554 #endif
00555 old_location = location;
00556 on_left = value < location->value;
00557 if (on_left) {location = location->left;}
00558 else {location = location->right;}
00559 }
00560 #ifdef TRACK_DEPTH
00561 _max_depth = max(depth, _max_depth);
00562 #endif
00563
00564 node->parent = old_location;
00565 if (on_left) {node->parent->left = node;}
00566 else {node->parent->right = node;}
00567 node->left = NULL;
00568 node->right = NULL;
00569
00570 node->predecessor = _find_predecessor(node);
00571 if (node->predecessor != NULL) {
00572
00573
00574 node->successor = node->predecessor->successor;
00575 node->predecessor->successor = node;
00576 node->successor->predecessor = node;
00577 } else {
00578
00579
00580 node->successor = _find_successor(node);
00581 assert(node->successor != NULL);
00582
00583 node->predecessor = node->successor->predecessor;
00584 node->successor->predecessor = node;
00585 node->predecessor->successor = node;
00586 }
00587
00588 return circulator(node);
00589 }
00590
00591
00592
00593 template<class T> void SearchTree<T>::verify_structure() {
00594
00595
00596 verify_structure_linear();
00597
00598
00599
00600
00601 const Node * left_limit = _top_node;
00602 while (left_limit->left != NULL) {left_limit = left_limit->left;}
00603 const Node * right_limit = _top_node;
00604 while (right_limit->right != NULL) {right_limit = right_limit->right;}
00605
00606
00607 verify_structure_recursive(_top_node, left_limit, right_limit);
00608 }
00609
00610
00611
00612 template<class T> void SearchTree<T>::verify_structure_recursive(
00613 const SearchTree<T>::Node * element,
00614 const SearchTree<T>::Node * left_limit,
00615 const SearchTree<T>::Node * right_limit) const {
00616
00617 assert(!(element->value < left_limit->value));
00618 assert(!(right_limit->value < element->value));
00619
00620 const Node * left = element->left;
00621 if (left != NULL) {
00622 assert(!(element->value < left->value));
00623 if (left != left_limit) {
00624
00625 verify_structure_recursive(left, left_limit, element);}
00626 }
00627
00628 const Node * right = element->right;
00629 if (right != NULL) {
00630 assert(!(right->value < element->value));
00631 if (right != right_limit) {
00632
00633 verify_structure_recursive(right, element, right_limit);}
00634 }
00635 }
00636
00637
00638 template<class T> void SearchTree<T>::verify_structure_linear() const {
00639
00640
00641
00642 unsigned n_top = 0;
00643 unsigned n_null = 0;
00644 for(unsigned i = 0; i < _nodes.size(); i++) {
00645 const typename SearchTree<T>::Node * node = &(_nodes[i]);
00646
00647 if (node->treelinks_null()) {n_null++; continue;}
00648
00649
00650 if (node->parent == NULL) {
00651 n_top++;
00652
00653
00654 } else {
00655
00656
00657 assert((node->parent->left == node) ^ (node->parent->right == node));
00658 }
00659
00660
00661
00662
00663 if (node->left != NULL) {
00664 assert(!(node->value < node->left->value ));}
00665
00666
00667 if (node->right != NULL) {
00668 assert(!(node->right->value < node->value ));}
00669
00670 }
00671 assert(n_top == 1 || (n_top == 0 && size() <= 1) );
00672 assert(n_null == _available_nodes.size() ||
00673 (n_null == _available_nodes.size() + 1 && size() == 1));
00674 }
00675
00676
00677
00678 template<class T> typename SearchTree<T>::Node * SearchTree<T>::_find_predecessor(const SearchTree<T>::Node * node) {
00679
00680 typename SearchTree<T>::Node * newnode;
00681 if (node->left != NULL) {
00682
00683 newnode = node->left;
00684 while(newnode->right != NULL) {newnode = newnode->right;}
00685 return newnode;
00686 } else {
00687 const typename SearchTree<T>::Node * lastnode = node;
00688 newnode = node->parent;
00689
00690
00691 while(newnode != NULL) {
00692 if (newnode->right == lastnode) {return newnode;}
00693 lastnode = newnode;
00694 newnode = newnode->parent;
00695 }
00696 return newnode;
00697 }
00698 }
00699
00700
00701
00702 template<class T> typename SearchTree<T>::Node * SearchTree<T>::_find_successor(const SearchTree<T>::Node * node) {
00703
00704 typename SearchTree<T>::Node * newnode;
00705 if (node->right != NULL) {
00706
00707 newnode = node->right;
00708 while(newnode->left != NULL) {newnode = newnode->left;}
00709 return newnode;
00710 } else {
00711 const typename SearchTree<T>::Node * lastnode = node;
00712 newnode = node->parent;
00713
00714
00715 while(newnode != NULL) {
00716 if (newnode->left == lastnode) {return newnode;}
00717 lastnode = newnode;
00718 newnode = newnode->parent;
00719 }
00720 return newnode;
00721 }
00722 }
00723
00724
00725
00726
00727 template<class T> void SearchTree<T>::print_elements() {
00728 typename SearchTree<T>::Node * base_node = &(_nodes[0]);
00729 typename SearchTree<T>::Node * node = base_node;
00730
00731 int n = _nodes.size();
00732 for(; node - base_node < n ; node++) {
00733 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);
00734 }
00735 }
00736
00737
00738 template<class T> typename SearchTree<T>::circulator SearchTree<T>::somewhere() {
00739 return circulator(_top_node);
00740 }
00741
00742
00743
00744 template<class T> typename SearchTree<T>::const_circulator SearchTree<T>::somewhere() const {
00745 return const_circulator(_top_node);
00746 }
00747
00748
00749 FASTJET_END_NAMESPACE
00750
00751 #endif // __FASTJET_SEARCHTREE_HH__