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>

Collaboration diagram for fastjet::SearchTree< T >:

Collaboration graph
fastjet::SearchTree\< T \>::Node
[legend]
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 Nodeoperator[] (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 Nodeoperator[] (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  )  [inline]

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 
) [inline]

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 >::remove ( unsigned  node_index  ) 

remove the node corresponding to node_index from the search tree

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

template<class T>
void fastjet::SearchTree< T >::remove ( SearchTree< T >::circulator circ  )  [inline]

Definition at line 436 of file SearchTree.hh.

References fastjet::SearchTree< T >::circulator::_node.

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

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

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>
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 >::verify_structure_linear().

00075 {return _nodes.size() - _available_nodes.size();}

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

template<class T>
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, 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

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

template<class T>
void fastjet::SearchTree< T >::print_elements (  )  [inline]

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>
unsigned int fastjet::SearchTree< T >::max_depth (  )  const [inline]

Definition at line 91 of file SearchTree.hh.

00091 {return 0;};

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>
Node* fastjet::SearchTree< T >::_find_predecessor ( const Node  ) 

return predecessor by walking through the tree

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

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

return successor by walking through the tree

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

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>
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 }

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

template<class T>
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, 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>
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 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 }


Member Data Documentation

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>
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 >::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 >::somewhere(), and fastjet::SearchTree< T >::verify_structure().

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().


The documentation for this class was generated from the following file:
Generated on Tue Dec 18 17:05:55 2007 for fastjet by  doxygen 1.5.2