This is the class for a search tree designed to be especially efficient when looking for successors and predecessors (to be used in Chan's CP algorithm). More...
#include <SearchTree.hh>
Classes | |
class | circulator |
class | const_circulator |
class | Node |
Public Member Functions | |
SearchTree (const std::vector< T > &init) | |
constructor for a search tree from an ordered vector | |
SearchTree (const std::vector< T > &init, unsigned int max_size) | |
constructor for a search tree from an ordered vector allowing for future growth beyond the current size, up to max_size | |
void | remove (unsigned node_index) |
remove the node corresponding to node_index from the search tree | |
void | remove (typename SearchTree::Node *node) |
void | remove (typename SearchTree::circulator &circ) |
circulator | insert (const T &value) |
insert the supplied value into the tree and return a pointer to the relevant SearchTreeNode. | |
const Node & | operator[] (int i) const |
unsigned int | size () const |
return the number of elements currently in the search tree | |
void | verify_structure () |
check that the structure we've obtained makes sense... | |
void | verify_structure_linear () const |
void | verify_structure_recursive (const Node *, const Node *, const Node *) const |
void | print_elements () |
print out all elements... | |
unsigned int | max_depth () const |
int | loc (const Node *node) const |
Node * | _find_predecessor (const Node *) |
return predecessor by walking through the tree | |
Node * | _find_successor (const Node *) |
return successor by walking through the tree | |
const Node & | operator[] (unsigned int i) const |
const_circulator | somewhere () const |
return a circulator to some place in the tree (with a circulator you don't care where. | |
circulator | somewhere () |
Private Member Functions | |
void | _initialize (const std::vector< T > &init) |
do the actual hard work of initialization | |
void | _do_initial_connections (unsigned int this_one, unsigned int scale, unsigned int left_edge, unsigned int right_edge, unsigned int depth) |
recursive routine for doing the initial connections assuming things are ordered. | |
Private Attributes | |
std::vector< Node > | _nodes |
std::vector< Node * > | _available_nodes |
Node * | _top_node |
unsigned int | _n_removes |
This is the class for a search tree designed to be especially efficient when looking for successors and predecessors (to be used in Chan's CP algorithm).
It has the requirement that the maximum size of the search tree must be known in advance.
Definition at line 48 of file SearchTree.hh.
fastjet::SearchTree< T >::SearchTree | ( | const std::vector< T > & | init | ) | [inline] |
constructor for a search tree from an ordered vector
initialise from a sorted initial array
Definition at line 304 of file SearchTree.hh.
References fastjet::SearchTree< T >::_available_nodes, and fastjet::SearchTree< T >::_initialize().
00304 : 00305 _nodes(init.size()), _available_nodes(0) { 00306 00307 // reserve space for the list of available nodes 00308 _available_nodes.reserve(init.size()); 00309 _initialize(init); 00310 }
fastjet::SearchTree< T >::SearchTree | ( | const std::vector< T > & | init, | |
unsigned int | max_size | |||
) | [inline] |
constructor for a search tree from an ordered vector allowing for future growth beyond the current size, up to max_size
initialise from a sorted initial array allowing for a larger maximum size of the array.
..
Definition at line 289 of file SearchTree.hh.
References fastjet::SearchTree< T >::_available_nodes, fastjet::SearchTree< T >::_initialize(), and fastjet::SearchTree< T >::_nodes.
00290 : 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 }
void fastjet::SearchTree< T >::_do_initial_connections | ( | unsigned int | this_one, | |
unsigned int | scale, | |||
unsigned int | left_edge, | |||
unsigned int | right_edge, | |||
unsigned int | depth | |||
) | [inline, private] |
recursive routine for doing the initial connections assuming things are ordered.
Recursive creation of connections, assuming the _nodes vector is completely filled and ordered.
Assumes this_one's parent is labelled, and was generated at a scale "scale" -- connections will be carried out including left edge and excluding right edge
Definition at line 365 of file SearchTree.hh.
References fastjet::SearchTree< T >::_nodes.
Referenced by fastjet::SearchTree< T >::_initialize().
00371 { 00372 00373 #ifdef TRACK_DEPTH 00374 // keep track of tree depth for checking things stay reasonable... 00375 _max_depth = max(depth, _max_depth); 00376 #endif 00377 00378 //std::cout << this_one << " "<< scale<< std::endl; 00379 unsigned int ref_new_scale = (scale+1)/2; 00380 00381 // work through children to our left 00382 unsigned new_scale = ref_new_scale; 00383 bool did_child = false; 00384 while(true) { 00385 int left = this_one - new_scale; // be careful here to use signed int... 00386 // if there is something unitialised to our left, link to it 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 // create connections between left_edge and this_one 00392 _do_initial_connections(left, new_scale, left_edge, this_one, depth+1); 00393 did_child = true; 00394 break; 00395 } 00396 // reduce the scale so as to try again 00397 unsigned int old_new_scale = new_scale; 00398 new_scale = (old_new_scale + 1)/2; 00399 // unless we've reached end of tree 00400 if (new_scale == old_new_scale) break; 00401 } 00402 if (!did_child) {_nodes[this_one].left = NULL;} 00403 00404 00405 // work through children to our right 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 // create connections between this_one+1 and right_edge 00414 _do_initial_connections(right, new_scale, this_one+1,right_edge,depth+1); 00415 did_child = true; 00416 break; 00417 } 00418 // reduce the scale so as to try again 00419 unsigned int old_new_scale = new_scale; 00420 new_scale = (old_new_scale + 1)/2; 00421 // unless we've reached end of tree 00422 if (new_scale == old_new_scale) break; 00423 } 00424 if (!did_child) {_nodes[this_one].right = NULL;} 00425 00426 }
Node* fastjet::SearchTree< T >::_find_predecessor | ( | const Node * | ) |
return predecessor by walking through the tree
Referenced by fastjet::SearchTree< T >::insert().
Node* fastjet::SearchTree< T >::_find_successor | ( | const Node * | ) |
return successor by walking through the tree
Referenced by fastjet::SearchTree< T >::insert().
void fastjet::SearchTree< T >::_initialize | ( | const std::vector< T > & | init | ) | [inline, private] |
do the actual hard work of initialization
Definition at line 314 of file SearchTree.hh.
References fastjet::SearchTree< T >::_do_initial_connections(), fastjet::SearchTree< T >::_n_removes, fastjet::SearchTree< T >::_nodes, fastjet::SearchTree< T >::_top_node, and fastjet::d0::inline_maths::min().
Referenced by fastjet::SearchTree< T >::SearchTree().
00314 { 00315 00316 _n_removes = 0; 00317 unsigned n = init.size(); 00318 assert(n>=1); 00319 00320 // reserve space for the list of available nodes 00321 //_available_nodes.reserve(); 00322 00323 #ifdef TRACK_DEPTH 00324 _max_depth = 0; 00325 #endif 00326 00327 00328 // validate the input 00329 for (unsigned int i = 1; i<n; i++) { 00330 assert(!(init[i] < init[i-1])); 00331 } 00332 00333 // now initialise the vector; link neighbours in the sequence 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 // make a loop structure so that we can circulate... 00341 _nodes[0].predecessor = (& (_nodes[n-1])); 00342 _nodes[n-1].successor = (& (_nodes[0])); 00343 00344 // now label the rest of the nodes 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 // make sure things are sensible... 00352 //verify_structure(); 00353 }
SearchTree< T >::circulator fastjet::SearchTree< T >::insert | ( | const T & | value | ) | [inline] |
insert the supplied value into the tree and return a pointer to the relevant SearchTreeNode.
Definition at line 536 of file SearchTree.hh.
References fastjet::SearchTree< T >::_available_nodes, fastjet::SearchTree< T >::_find_predecessor(), fastjet::SearchTree< T >::_find_successor(), fastjet::SearchTree< T >::_top_node, fastjet::SearchTree< T >::Node::left, fastjet::SearchTree< T >::Node::parent, fastjet::SearchTree< T >::Node::predecessor, fastjet::SearchTree< T >::Node::right, and fastjet::SearchTree< T >::Node::value.
00536 { 00537 // make sure we don't exceed allowed number of nodes... 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; // (init not needed -- but soothes g++4) 00547 // work through tree until we reach its end 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 // now create tree links 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 // and create predecessor / successor links 00570 node->predecessor = _find_predecessor(node); 00571 if (node->predecessor != NULL) { 00572 // it exists, so make use of its info (will include a cyclic case, 00573 // when successor is round the bend) 00574 node->successor = node->predecessor->successor; 00575 node->predecessor->successor = node; 00576 node->successor->predecessor = node; 00577 } else { 00578 // deal with case when we are left-most edge of tree (then successor 00579 // will exist...) 00580 node->successor = _find_successor(node); 00581 assert(node->successor != NULL); // can only happen if we're sole element 00582 // (but not allowed, since tree size>=1) 00583 node->predecessor = node->successor->predecessor; 00584 node->successor->predecessor = node; 00585 node->predecessor->successor = node; 00586 } 00587 00588 return circulator(node); 00589 }
int fastjet::SearchTree< T >::loc | ( | const Node * | node | ) | const [inline] |
Definition at line 358 of file SearchTree.hh.
References fastjet::SearchTree< T >::_nodes.
Referenced by fastjet::SearchTree< T >::print_elements().
00358 {return node == NULL? 00359 -999 : node - &(_nodes[0]);}
unsigned int fastjet::SearchTree< T >::max_depth | ( | ) | const [inline] |
Definition at line 91 of file SearchTree.hh.
const Node& fastjet::SearchTree< T >::operator[] | ( | unsigned int | i | ) | const [inline] |
Definition at line 101 of file SearchTree.hh.
00101 {return _nodes[i];};
const Node& fastjet::SearchTree< T >::operator[] | ( | int | i | ) | const [inline] |
Definition at line 72 of file SearchTree.hh.
00072 {return _nodes[i];};
void fastjet::SearchTree< T >::print_elements | ( | ) | [inline] |
print out all elements...
Definition at line 727 of file SearchTree.hh.
References fastjet::SearchTree< T >::_nodes, fastjet::SearchTree< T >::Node::left, fastjet::SearchTree< T >::loc(), fastjet::SearchTree< T >::Node::parent, fastjet::SearchTree< T >::Node::predecessor, fastjet::SearchTree< T >::Node::right, fastjet::SearchTree< T >::Node::successor, and fastjet::SearchTree< T >::Node::value.
00727 { 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 }
void fastjet::SearchTree< T >::remove | ( | typename SearchTree< T >::circulator & | circ | ) | [inline] |
Definition at line 436 of file SearchTree.hh.
References fastjet::SearchTree< T >::circulator::_node.
void fastjet::SearchTree< T >::remove | ( | typename SearchTree< T >::Node * | node | ) | [inline] |
Definition at line 443 of file SearchTree.hh.
References fastjet::SearchTree< T >::_available_nodes, fastjet::SearchTree< T >::_n_removes, fastjet::SearchTree< T >::_top_node, fastjet::SearchTree< T >::Node::left, fastjet::SearchTree< T >::Node::nullify_treelinks(), fastjet::SearchTree< T >::Node::parent, fastjet::SearchTree< T >::Node::predecessor, fastjet::SearchTree< T >::Node::reset_parents_link_to_me(), fastjet::SearchTree< T >::Node::right, fastjet::SearchTree< T >::size(), fastjet::SearchTree< T >::Node::successor, and fastjet::SearchTree< T >::Node::treelinks_null().
00443 { 00444 00445 // we don't remove things from the tree if we've reached the last 00446 // elements... (is this wise?) 00447 assert(size() > 1); // switch this to throw...? 00448 assert(!node->treelinks_null()); 00449 00450 // deal with relinking predecessor and successor 00451 node->predecessor->successor = node->successor; 00452 node->successor->predecessor = node->predecessor; 00453 00454 if (node->left == NULL && node->right == NULL) { 00455 // node has no children, so remove it by nullifying the pointer 00456 // from the parent 00457 node->reset_parents_link_to_me(NULL); 00458 00459 } else if (node->left != NULL && node->right == NULL){ 00460 // make parent point to my child 00461 node->reset_parents_link_to_me(node->left); 00462 // and child to parent 00463 node->left->parent = node->parent; 00464 // sort out the top node... 00465 if (_top_node == node) {_top_node = node->left;} 00466 00467 } else if (node->left == NULL && node->right != NULL){ 00468 // make parent point to my child 00469 node->reset_parents_link_to_me(node->right); 00470 // and child to parent 00471 node->right->parent = node->parent; 00472 // sort out the top node... 00473 if (_top_node == node) {_top_node = node->right;} 00474 00475 } else { 00476 // we have two children; we will put a replacement in our place 00477 Node * replacement; 00478 //SearchTree<T>::Node * replacements_child; 00479 // chose predecessor or successor (one, then other, then first, etc...) 00480 bool use_predecessor = (_n_removes % 2 == 1); 00481 if (use_predecessor) { 00482 // Option 1: put predecessor in our place, and have its parent 00483 // point to its left child (as a predecessor it has no right child) 00484 replacement = node->predecessor; 00485 assert(replacement->right == NULL); // guaranteed if it's our predecessor 00486 // we have to be careful of replacing certain links when the 00487 // replacement is this node's child 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 // Option 2: put successor in our place, and have its parent 00498 // point to its right child (as a successor it has no left child) 00499 replacement = node->successor; 00500 assert(replacement->left == NULL); // guaranteed if it's our successor 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 // make sure node's original children now point to the replacement 00513 if (node->left != replacement) {node->left->parent = replacement;} 00514 if (node->right != replacement) {node->right->parent = replacement;} 00515 00516 // sort out the top node... 00517 if (_top_node == node) {_top_node = replacement;} 00518 } 00519 00520 // make sure we leave something nice and clean... 00521 node->nullify_treelinks(); 00522 node->predecessor = NULL; 00523 node->successor = NULL; 00524 00525 // for bookkeeping (and choosing whether to use pred. or succ.) 00526 _n_removes++; 00527 // for when we next need access to a free node... 00528 _available_nodes.push_back(node); 00529 }
void fastjet::SearchTree< T >::remove | ( | unsigned | node_index | ) |
remove the node corresponding to node_index from the search tree
unsigned int fastjet::SearchTree< T >::size | ( | ) | const [inline] |
return the number of elements currently in the search tree
Definition at line 75 of file SearchTree.hh.
Referenced by fastjet::SearchTree< T >::remove(), and fastjet::SearchTree< T >::verify_structure_linear().
00075 {return _nodes.size() - _available_nodes.size();}
SearchTree< T >::circulator fastjet::SearchTree< T >::somewhere | ( | ) | [inline] |
Definition at line 738 of file SearchTree.hh.
References fastjet::SearchTree< T >::_top_node.
00738 { 00739 return circulator(_top_node); 00740 }
SearchTree< T >::const_circulator fastjet::SearchTree< T >::somewhere | ( | ) | const [inline] |
return a circulator to some place in the tree (with a circulator you don't care where.
..)
Definition at line 744 of file SearchTree.hh.
References fastjet::SearchTree< T >::_top_node.
00744 { 00745 return const_circulator(_top_node); 00746 }
void fastjet::SearchTree< T >::verify_structure | ( | ) | [inline] |
check that the structure we've obtained makes sense...
Definition at line 593 of file SearchTree.hh.
References fastjet::SearchTree< T >::_top_node, fastjet::SearchTree< T >::Node::left, fastjet::SearchTree< T >::Node::right, fastjet::SearchTree< T >::verify_structure_linear(), and fastjet::SearchTree< T >::verify_structure_recursive().
00593 { 00594 00595 // do a check running through all elements 00596 verify_structure_linear(); 00597 00598 // do a recursive check down tree from top 00599 00600 // first establish the extremities 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 // then actually do recursion 00607 verify_structure_recursive(_top_node, left_limit, right_limit); 00608 }
void fastjet::SearchTree< T >::verify_structure_linear | ( | ) | const [inline] |
Definition at line 638 of file SearchTree.hh.
References fastjet::SearchTree< T >::_available_nodes, fastjet::SearchTree< T >::_nodes, fastjet::SearchTree< T >::Node::left, fastjet::SearchTree< T >::Node::parent, fastjet::SearchTree< T >::Node::right, fastjet::SearchTree< T >::size(), fastjet::SearchTree< T >::Node::treelinks_null(), and fastjet::SearchTree< T >::Node::value.
Referenced by fastjet::SearchTree< T >::verify_structure().
00638 { 00639 00640 //print_elements(); 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 // make sure node is defined 00647 if (node->treelinks_null()) {n_null++; continue;} 00648 00649 // make sure of the number of "top" nodes 00650 if (node->parent == NULL) { 00651 n_top++; 00652 //assert(node->left != NULL); 00653 //assert(node->right != NULL); 00654 } else { 00655 // make sure that I am a child of my parent... 00656 //assert((node->parent->left == node) || (node->parent->right == node)); 00657 assert((node->parent->left == node) ^ (node->parent->right == node)); 00658 } 00659 00660 // when there is a left child make sure it's value is ordered 00661 // (note use of !(b<a), to allow for a<=b while using just the < 00662 // operator) 00663 if (node->left != NULL) { 00664 assert(!(node->value < node->left->value ));} 00665 00666 // when there is a right child make sure it's value is ordered 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 }
void fastjet::SearchTree< T >::verify_structure_recursive | ( | const Node * | , | |
const Node * | , | |||
const Node * | ||||
) | const |
Referenced by fastjet::SearchTree< T >::verify_structure().
std::vector<Node *> fastjet::SearchTree< T >::_available_nodes [private] |
Definition at line 113 of file SearchTree.hh.
Referenced by fastjet::SearchTree< T >::insert(), fastjet::SearchTree< T >::remove(), fastjet::SearchTree< T >::SearchTree(), and fastjet::SearchTree< T >::verify_structure_linear().
unsigned int fastjet::SearchTree< T >::_n_removes [private] |
Definition at line 115 of file SearchTree.hh.
Referenced by fastjet::SearchTree< T >::_initialize(), and fastjet::SearchTree< T >::remove().
std::vector<Node> fastjet::SearchTree< T >::_nodes [private] |
Definition at line 112 of file SearchTree.hh.
Referenced by fastjet::SearchTree< T >::_do_initial_connections(), fastjet::SearchTree< T >::_initialize(), fastjet::SearchTree< T >::loc(), fastjet::SearchTree< T >::print_elements(), fastjet::SearchTree< T >::SearchTree(), and fastjet::SearchTree< T >::verify_structure_linear().
Node* fastjet::SearchTree< T >::_top_node [private] |
Definition at line 114 of file SearchTree.hh.
Referenced by fastjet::SearchTree< T >::_initialize(), fastjet::SearchTree< T >::insert(), fastjet::SearchTree< T >::remove(), fastjet::SearchTree< T >::somewhere(), and fastjet::SearchTree< T >::verify_structure().