30 #ifndef __FASTJET_SEARCHTREE_HH__
31 #define __FASTJET_SEARCHTREE_HH__
36 #include "fastjet/internal/base.hh"
38 FASTJET_BEGIN_NAMESPACE
52 template<
class T>
class SearchTree {
57 class const_circulator;
60 SearchTree(
const std::vector<T> & init);
64 SearchTree(
const std::vector<T> & init,
unsigned int max_size);
67 void remove(
unsigned node_index);
68 void remove(
typename SearchTree::Node * node);
69 void remove(
typename SearchTree::circulator & circ);
74 circulator insert(
const T & value);
76 const Node & operator[](
int i)
const {
return _nodes[i];};
79 unsigned int size()
const {
return _nodes.size() - _available_nodes.size();}
82 void verify_structure();
83 void verify_structure_linear()
const;
84 void verify_structure_recursive(
const Node * ,
const Node * ,
const Node * )
const;
87 void print_elements();
91 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
93 inline unsigned int max_depth()
const {
return _max_depth;};
95 inline unsigned int max_depth()
const {
return 0;};
98 int loc(
const Node * node)
const ;
101 Node * _find_predecessor(
const Node *);
103 Node * _find_successor(
const Node *);
105 const Node & operator[](
unsigned int i)
const {
return _nodes[i];};
109 const_circulator somewhere()
const;
110 circulator somewhere();
114 void _initialize(
const std::vector<T> & init);
116 std::vector<Node> _nodes;
117 std::vector<Node *> _available_nodes;
119 unsigned int _n_removes;
126 void _do_initial_connections(
unsigned int this_one,
unsigned int scale,
127 unsigned int left_edge,
unsigned int right_edge,
131 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
132 unsigned int _max_depth;
144 template<
class T>
class SearchTree<T>::Node{
150 bool treelinks_null()
const {
151 return ((parent==0) && (left==0) && (right==0));};
154 inline void nullify_treelinks() {
162 void reset_parents_link_to_me(Node * XX);
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;}
187 template<
class T>
class SearchTree<T>::circulator{
192 template<
class U>
friend class SearchTree<U>::const_circulator;
193 friend class SearchTree<T>;
195 circulator() : _node(NULL) {}
197 circulator(Node * node) : _node(node) {}
199 const T * operator->()
const {
return &(_node->value);}
200 T * operator->() {
return &(_node->value);}
201 const T &
operator*()
const {
return _node->value;}
205 circulator & operator++() {
206 _node = _node->successor;
211 circulator operator++(
int) {
212 circulator tmp = *
this;
213 _node = _node->successor;
217 circulator & operator--() {
218 _node = _node->predecessor;
223 circulator operator--(
int) {
224 circulator tmp = *
this;
225 _node = _node->predecessor;
229 circulator next()
const {
230 return circulator(_node->successor);}
233 circulator previous()
const {
234 return circulator(_node->predecessor);}
236 bool operator!=(
const circulator & other)
const {
return other._node != _node;}
237 bool operator==(
const circulator & other)
const {
return other._node == _node;}
250 template<
class T>
class SearchTree<T>::const_circulator{
253 const_circulator() : _node(NULL) {}
255 const_circulator(
const Node * node) : _node(node) {}
256 const_circulator(
const circulator & circ) :_node(circ._node) {}
258 const T * operator->() {
return &(_node->value);}
259 const T &
operator*()
const {
return _node->value;}
262 const_circulator & operator++() {
263 _node = _node->successor;
268 const_circulator operator++(
int) {
269 const_circulator tmp = *
this;
270 _node = _node->successor;
275 const_circulator & operator--() {
276 _node = _node->predecessor;
281 const_circulator operator--(
int) {
282 const_circulator tmp = *
this;
283 _node = _node->predecessor;
287 const_circulator next()
const {
288 return const_circulator(_node->successor);}
291 const_circulator previous()
const {
292 return const_circulator(_node->predecessor);}
296 bool operator!=(
const const_circulator & other)
const {
return other._node != _node;}
297 bool operator==(
const const_circulator & other)
const {
return other._node == _node;}
309 template<
class T> SearchTree<T>::SearchTree(
const std::vector<T> & init,
310 unsigned int max_size) :
313 _available_nodes.reserve(max_size);
314 _available_nodes.resize(max_size - init.size());
315 for (
unsigned int i = init.size(); i < max_size; i++) {
316 _available_nodes[i-init.size()] = &(_nodes[i]);
324 template<
class T> SearchTree<T>::SearchTree(
const std::vector<T> & init) :
325 _nodes(init.size()), _available_nodes(0) {
328 _available_nodes.reserve(init.size());
334 template<
class T>
void SearchTree<T>::_initialize(
const std::vector<T> & init) {
337 unsigned n = init.size();
343 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
349 for (
unsigned int i = 1; i<n; i++) {
350 assert(!(init[i] < init[i-1]));
354 for(
unsigned int i = 0; i < n; i++) {
355 _nodes[i].value = init[i];
356 _nodes[i].predecessor = (& (_nodes[i])) - 1;
357 _nodes[i].successor = (& (_nodes[i])) + 1;
358 _nodes[i].nullify_treelinks();
361 _nodes[0].predecessor = (& (_nodes[n-1]));
362 _nodes[n-1].successor = (& (_nodes[0]));
365 unsigned int scale = (n+1)/2;
366 unsigned int top = std::min(n-1,scale);
367 _nodes[top].parent = NULL;
368 _top_node = &(_nodes[top]);
369 _do_initial_connections(top, scale, 0, n, 0);
378 template<
class T>
inline int SearchTree<T>::loc(
const Node * node)
const {
return node == NULL?
379 -999 : node - &(_nodes[0]);}
385 template<
class T>
void SearchTree<T>::_do_initial_connections(
386 unsigned int this_one,
388 unsigned int left_edge,
389 unsigned int right_edge,
393 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
395 _max_depth = max(depth, _max_depth);
399 unsigned int ref_new_scale = (scale+1)/2;
402 unsigned new_scale = ref_new_scale;
403 bool did_child =
false;
405 int left = this_one - new_scale;
407 if (left >=
static_cast<int>(left_edge)
408 && _nodes[left].treelinks_null() ) {
409 _nodes[left].parent = &(_nodes[this_one]);
410 _nodes[this_one].left = &(_nodes[left]);
412 _do_initial_connections(left, new_scale, left_edge, this_one, depth+1);
417 unsigned int old_new_scale = new_scale;
418 new_scale = (old_new_scale + 1)/2;
420 if (new_scale == old_new_scale)
break;
422 if (!did_child) {_nodes[this_one].left = NULL;}
426 new_scale = ref_new_scale;
429 unsigned int right = this_one + new_scale;
430 if (right < right_edge && _nodes[right].treelinks_null()) {
431 _nodes[right].parent = &(_nodes[this_one]);
432 _nodes[this_one].right = &(_nodes[right]);
434 _do_initial_connections(right, new_scale, this_one+1,right_edge,depth+1);
439 unsigned int old_new_scale = new_scale;
440 new_scale = (old_new_scale + 1)/2;
442 if (new_scale == old_new_scale)
break;
444 if (!did_child) {_nodes[this_one].right = NULL;}
451 template<
class T>
void SearchTree<T>::remove(
unsigned int node_index) {
452 remove(&(_nodes[node_index]));
456 template<
class T>
void SearchTree<T>::remove(circulator & circ) {
463 template<
class T>
void SearchTree<T>::remove(
typename SearchTree<T>::Node * node) {
468 assert(!node->treelinks_null());
471 node->predecessor->successor = node->successor;
472 node->successor->predecessor = node->predecessor;
474 if (node->left == NULL && node->right == NULL) {
477 node->reset_parents_link_to_me(NULL);
479 }
else if (node->left != NULL && node->right == NULL){
481 node->reset_parents_link_to_me(node->left);
483 node->left->parent = node->parent;
485 if (_top_node == node) {_top_node = node->left;}
487 }
else if (node->left == NULL && node->right != NULL){
489 node->reset_parents_link_to_me(node->right);
491 node->right->parent = node->parent;
493 if (_top_node == node) {_top_node = node->right;}
500 bool use_predecessor = (_n_removes % 2 == 1);
501 if (use_predecessor) {
504 replacement = node->predecessor;
505 assert(replacement->right == NULL);
508 if (replacement != node->left) {
509 if (replacement->left != NULL) {
510 replacement->left->parent = replacement->parent;}
511 replacement->reset_parents_link_to_me(replacement->left);
512 replacement->left = node->left;
514 replacement->parent = node->parent;
515 replacement->right = node->right;
519 replacement = node->successor;
520 assert(replacement->left == NULL);
521 if (replacement != node->right) {
522 if (replacement->right != NULL) {
523 replacement->right->parent = replacement->parent;}
524 replacement->reset_parents_link_to_me(replacement->right);
525 replacement->right = node->right;
527 replacement->parent = node->parent;
528 replacement->left = node->left;
530 node->reset_parents_link_to_me(replacement);
533 if (node->left != replacement) {node->left->parent = replacement;}
534 if (node->right != replacement) {node->right->parent = replacement;}
537 if (_top_node == node) {_top_node = replacement;}
541 node->nullify_treelinks();
542 node->predecessor = NULL;
543 node->successor = NULL;
548 _available_nodes.push_back(node);
556 template<
class T>
typename SearchTree<T>::circulator SearchTree<T>::insert(
const T & value) {
558 assert(_available_nodes.size() > 0);
560 Node * node = _available_nodes.back();
561 _available_nodes.pop_back();
564 Node * location = _top_node;
565 Node * old_location = NULL;
568 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
569 unsigned int depth = 0;
571 while(location != NULL) {
572 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
575 old_location = location;
576 on_left = value < location->value;
577 if (on_left) {location = location->left;}
578 else {location = location->right;}
580 #ifdef __FASTJET_SEARCHTREE_TRACK_DEPTH
581 _max_depth = max(depth, _max_depth);
584 node->parent = old_location;
585 if (on_left) {node->parent->left = node;}
586 else {node->parent->right = node;}
590 node->predecessor = _find_predecessor(node);
591 if (node->predecessor != NULL) {
594 node->successor = node->predecessor->successor;
595 node->predecessor->successor = node;
596 node->successor->predecessor = node;
600 node->successor = _find_successor(node);
601 assert(node->successor != NULL);
603 node->predecessor = node->successor->predecessor;
604 node->successor->predecessor = node;
605 node->predecessor->successor = node;
608 return circulator(node);
613 template<
class T>
void SearchTree<T>::verify_structure() {
616 verify_structure_linear();
621 const Node * left_limit = _top_node;
622 while (left_limit->left != NULL) {left_limit = left_limit->left;}
623 const Node * right_limit = _top_node;
624 while (right_limit->right != NULL) {right_limit = right_limit->right;}
627 verify_structure_recursive(_top_node, left_limit, right_limit);
632 template<
class T>
void SearchTree<T>::verify_structure_recursive(
633 const typename SearchTree<T>::Node * element,
634 const typename SearchTree<T>::Node * left_limit,
635 const typename SearchTree<T>::Node * right_limit)
const {
637 assert(!(element->value < left_limit->value));
638 assert(!(right_limit->value < element->value));
640 const Node * left = element->left;
642 assert(!(element->value < left->value));
643 if (left != left_limit) {
645 verify_structure_recursive(left, left_limit, element);}
648 const Node * right = element->right;
650 assert(!(right->value < element->value));
651 if (right != right_limit) {
653 verify_structure_recursive(right, element, right_limit);}
658 template<
class T>
void SearchTree<T>::verify_structure_linear()
const {
664 for(
unsigned i = 0; i < _nodes.size(); i++) {
665 const typename SearchTree<T>::Node * node = &(_nodes[i]);
667 if (node->treelinks_null()) {n_null++;
continue;}
670 if (node->parent == NULL) {
677 assert((node->parent->left == node) ^ (node->parent->right == node));
683 if (node->left != NULL) {
684 assert(!(node->value < node->left->value ));}
687 if (node->right != NULL) {
688 assert(!(node->right->value < node->value ));}
691 assert(n_top == 1 || (n_top == 0 && size() <= 1) );
692 assert(n_null == _available_nodes.size() ||
693 (n_null == _available_nodes.size() + 1 && size() == 1));
698 template<
class T>
typename SearchTree<T>::Node * SearchTree<T>::_find_predecessor(
const typename SearchTree<T>::Node * node) {
700 typename SearchTree<T>::Node * newnode;
701 if (node->left != NULL) {
703 newnode = node->left;
704 while(newnode->right != NULL) {newnode = newnode->right;}
707 const typename SearchTree<T>::Node * lastnode = node;
708 newnode = node->parent;
711 while(newnode != NULL) {
712 if (newnode->right == lastnode) {
return newnode;}
714 newnode = newnode->parent;
722 template<
class T>
typename SearchTree<T>::Node * SearchTree<T>::_find_successor(
const typename SearchTree<T>::Node * node) {
724 typename SearchTree<T>::Node * newnode;
725 if (node->right != NULL) {
727 newnode = node->right;
728 while(newnode->left != NULL) {newnode = newnode->left;}
731 const typename SearchTree<T>::Node * lastnode = node;
732 newnode = node->parent;
735 while(newnode != NULL) {
736 if (newnode->left == lastnode) {
return newnode;}
738 newnode = newnode->parent;
747 template<
class T>
void SearchTree<T>::print_elements() {
748 typename SearchTree<T>::Node * base_node = &(_nodes[0]);
749 typename SearchTree<T>::Node * node = base_node;
751 int n = _nodes.size();
752 for(; node - base_node < n ; node++) {
753 printf(
"%4d parent:%4d left:%4d right:%4d pred:%4d succ:%4d value:%10.6f\n",loc(node), loc(node->parent), loc(node->left), loc(node->right), loc(node->predecessor),loc(node->successor),node->value);
758 template<
class T>
typename SearchTree<T>::circulator SearchTree<T>::somewhere() {
759 return circulator(_top_node);
764 template<
class T>
typename SearchTree<T>::const_circulator SearchTree<T>::somewhere()
const {
765 return const_circulator(_top_node);
769 FASTJET_END_NAMESPACE
771 #endif // __FASTJET_SEARCHTREE_HH__