Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members

fastjet::SearchTree< T > Class Template Reference

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>

List of all members.

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


Detailed Description

template<class T>
class fastjet::SearchTree< T >

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.


Constructor & Destructor Documentation

template<class T>
fastjet::SearchTree< T >::SearchTree const std::vector< T > &  init  ) 
 

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 }

template<class T>
fastjet::SearchTree< T >::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.

..

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 }


Member Function Documentation

template<class T>
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
[private]
 

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 }

template<class T>
SearchTree< T >::Node * fastjet::SearchTree< T >::_find_predecessor const Node *   ) 
 

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 }

template<class T>
SearchTree< T >::Node * fastjet::SearchTree< T >::_find_successor const Node *   ) 
 

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 }

template<class T>
void fastjet::SearchTree< T >::_initialize const std::vector< T > &  init  )  [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, 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 }

template<class T>
SearchTree< T >::circulator fastjet::SearchTree< T >::insert const T &  value  ) 
 

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 }

template<class T>
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]);}

template<class T>
unsigned int fastjet::SearchTree< T >::max_depth  )  const [inline]
 

Definition at line 91 of file SearchTree.hh.

00091 {return 0;};

template<class T>
const Node& fastjet::SearchTree< T >::operator[] unsigned int  i  )  const [inline]
 

Definition at line 101 of file SearchTree.hh.

00101 {return _nodes[i];};

template<class T>
const Node& fastjet::SearchTree< T >::operator[] int  i  )  const [inline]
 

Definition at line 72 of file SearchTree.hh.

00072 {return _nodes[i];};

template<class T>
void fastjet::SearchTree< T >::print_elements  ) 
 

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 }

template<class T>
void fastjet::SearchTree< T >::remove SearchTree< T >::circulator &  circ  ) 
 

Definition at line 436 of file SearchTree.hh.

References fastjet::SearchTree< T >::remove().

00436                                                               {
00437   remove(circ._node);
00438 }

template<class T>
void fastjet::SearchTree< T >::remove SearchTree< T >::Node *  node  ) 
 

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 }

template<class T>
void fastjet::SearchTree< T >::remove unsigned  node_index  ) 
 

remove the node corresponding to node_index from the search tree

Referenced by fastjet::SearchTree< T >::remove().

template<class T>
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();}

template<class T>
SearchTree< T >::circulator fastjet::SearchTree< T >::somewhere  ) 
 

Definition at line 738 of file SearchTree.hh.

References fastjet::SearchTree< T >::_top_node.

00738                                                                             {
00739   return circulator(_top_node);
00740 }

template<class T>
SearchTree< T >::const_circulator fastjet::SearchTree< T >::somewhere  )  const
 

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 }

template<class T>
void fastjet::SearchTree< T >::verify_structure  ) 
 

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 }

template<class T>
void fastjet::SearchTree< T >::verify_structure_linear  )  const
 

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 }

template<class T>
void fastjet::SearchTree< T >::verify_structure_recursive const Node *  ,
const Node *  ,
const Node * 
const
 

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 }


Member Data Documentation

template<class T>
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().

template<class T>
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().

template<class T>
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().

template<class T>
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().


The documentation for this class was generated from the following file:
Generated on Mon Apr 2 20:58:23 2007 for fastjet by  doxygen 1.4.2