#include <SearchTree.hh>
Public Member Functions | |
SearchTree (const std::vector< T > &init) | |
initialise from a sorted initial array | |
SearchTree (const std::vector< T > &init, unsigned int max_size) | |
initialise from a sorted initial array allowing for a larger maximum size of the array. | |
void | remove (unsigned node_index) |
remove the node corresponding to node_index from the search tree | |
void | remove (SearchTree::Node *node) |
void | remove (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 creation of connections, assuming the _nodes vector is completely filled and ordered. | |
Private Attributes | |
std::vector< Node > | _nodes |
std::vector< Node * > | _available_nodes |
Node * | _top_node |
unsigned int | _n_removes |
Classes | |
class | circulator |
class | const_circulator |
class | Node |
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.
|
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 }
|
|
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 }
|
|
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 }
|
|
return predecessor by walking through the tree
Definition at line 678 of file SearchTree.hh. Referenced by fastjet::SearchTree< T >::insert(). 00678 { 00679 00680 typename SearchTree<T>::Node * newnode; 00681 if (node->left != NULL) { 00682 // go down left, and then down right as far as possible. 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 // go up the tree as long as we're going right (when we go left then 00690 // we've found something smaller, so stop) 00691 while(newnode != NULL) { 00692 if (newnode->right == lastnode) {return newnode;} 00693 lastnode = newnode; 00694 newnode = newnode->parent; 00695 } 00696 return newnode; 00697 } 00698 }
|
|
return successor by walking through the tree
Definition at line 702 of file SearchTree.hh. Referenced by fastjet::SearchTree< T >::insert(). 00702 { 00703 00704 typename SearchTree<T>::Node * newnode; 00705 if (node->right != NULL) { 00706 // go down right, and then down left as far as possible. 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 // go up the tree as long as we're going left (when we go right then 00714 // we've found something larger, so stop) 00715 while(newnode != NULL) { 00716 if (newnode->left == lastnode) {return newnode;} 00717 lastnode = newnode; 00718 newnode = newnode->parent; 00719 } 00720 return newnode; 00721 } 00722 }
|
|
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, and fastjet::SearchTree< T >::_top_node. 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 }
|
|
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(), and fastjet::SearchTree< T >::_top_node. 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 }
|
|
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]);}
|
|
Definition at line 91 of file SearchTree.hh. 00091 {return 0;};
|
|
Definition at line 101 of file SearchTree.hh. 00101 {return _nodes[i];};
|
|
Definition at line 72 of file SearchTree.hh. 00072 {return _nodes[i];};
|
|
print out all elements...
Definition at line 727 of file SearchTree.hh. References fastjet::SearchTree< T >::_nodes, and fastjet::SearchTree< T >::loc(). 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 }
|
|
Definition at line 436 of file SearchTree.hh. References fastjet::SearchTree< T >::remove(). 00436 { 00437 remove(circ._node); 00438 }
|
|
Definition at line 443 of file SearchTree.hh. References fastjet::SearchTree< T >::_available_nodes, fastjet::SearchTree< T >::_n_removes, fastjet::SearchTree< T >::_top_node, and fastjet::SearchTree< T >::size(). 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 }
|
|
remove the node corresponding to node_index from the search tree
Referenced by fastjet::SearchTree< T >::remove(). |
|
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();}
|
|
Definition at line 738 of file SearchTree.hh. References fastjet::SearchTree< T >::_top_node. 00738 { 00739 return circulator(_top_node); 00740 }
|
|
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 }
|
|
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 >::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 }
|
|
Definition at line 638 of file SearchTree.hh. References fastjet::SearchTree< T >::_available_nodes, fastjet::SearchTree< T >::_nodes, and fastjet::SearchTree< T >::size(). 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 }
|
|
Definition at line 612 of file SearchTree.hh. Referenced by fastjet::SearchTree< T >::verify_structure(). 00615 { 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 // recurse down the tree with this element as the right-hand limit 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 // recurse down the tree with this element as the left-hand limit 00633 verify_structure_recursive(right, element, right_limit);} 00634 } 00635 }
|
|
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(). |
|
Definition at line 115 of file SearchTree.hh. Referenced by fastjet::SearchTree< T >::_initialize(), and fastjet::SearchTree< T >::remove(). |
|
|
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(). |