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(). : _nodes(init.size()), _available_nodes(0) { // reserve space for the list of available nodes _available_nodes.reserve(init.size()); _initialize(init); }

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. : _nodes(max_size) { _available_nodes.reserve(max_size); _available_nodes.resize(max_size - init.size()); for (unsigned int i = init.size(); i < max_size; i++) { _available_nodes[i-init.size()] = &(_nodes[i]); } _initialize(init); }

---

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(). { #ifdef TRACK_DEPTH // keep track of tree depth for checking things stay reasonable... _max_depth = max(depth, _max_depth); #endif //std::cout << this_one << " "<< scale<< std::endl; unsigned int ref_new_scale = (scale+1)/2; // work through children to our left unsigned new_scale = ref_new_scale; bool did_child = false; while(true) { int left = this_one - new_scale; // be careful here to use signed int... // if there is something unitialised to our left, link to it if (left >= static_cast<int>(left_edge) && _nodes[left].treelinks_null() ) { _nodes[left].parent = &(_nodes[this_one]); _nodes[this_one].left = &(_nodes[left]); // create connections between left_edge and this_one _do_initial_connections(left, new_scale, left_edge, this_one, depth+1); did_child = true; break; } // reduce the scale so as to try again unsigned int old_new_scale = new_scale; new_scale = (old_new_scale + 1)/2; // unless we've reached end of tree if (new_scale == old_new_scale) break; } if (!did_child) {_nodes[this_one].left = NULL;} // work through children to our right new_scale = ref_new_scale; did_child = false; while(true) { unsigned int right = this_one + new_scale; if (right < right_edge && _nodes[right].treelinks_null()) { _nodes[right].parent = &(_nodes[this_one]); _nodes[this_one].right = &(_nodes[right]); // create connections between this_one+1 and right_edge _do_initial_connections(right, new_scale, this_one+1,right_edge,depth+1); did_child = true; break; } // reduce the scale so as to try again unsigned int old_new_scale = new_scale; new_scale = (old_new_scale + 1)/2; // unless we've reached end of tree if (new_scale == old_new_scale) break; } if (!did_child) {_nodes[this_one].right = NULL;} }

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(). { typename SearchTree<T>::Node * newnode; if (node->left != NULL) { // go down left, and then down right as far as possible. newnode = node->left; while(newnode->right != NULL) {newnode = newnode->right;} return newnode; } else { const typename SearchTree<T>::Node * lastnode = node; newnode = node->parent; // go up the tree as long as we're going right (when we go left then // we've found something smaller, so stop) while(newnode != NULL) { if (newnode->right == lastnode) {return newnode;} lastnode = newnode; newnode = newnode->parent; } return newnode; } }

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(). { typename SearchTree<T>::Node * newnode; if (node->right != NULL) { // go down right, and then down left as far as possible. newnode = node->right; while(newnode->left != NULL) {newnode = newnode->left;} return newnode; } else { const typename SearchTree<T>::Node * lastnode = node; newnode = node->parent; // go up the tree as long as we're going left (when we go right then // we've found something larger, so stop) while(newnode != NULL) { if (newnode->left == lastnode) {return newnode;} lastnode = newnode; newnode = newnode->parent; } return newnode; } }

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(). { _n_removes = 0; unsigned n = init.size(); assert(n>=1); // reserve space for the list of available nodes //_available_nodes.reserve(); #ifdef TRACK_DEPTH _max_depth = 0; #endif // validate the input for (unsigned int i = 1; i<n; i++) { assert(!(init[i] < init[i-1])); } // now initialise the vector; link neighbours in the sequence for(unsigned int i = 0; i < n; i++) { _nodes[i].value = init[i]; _nodes[i].predecessor = (& (_nodes[i])) - 1; _nodes[i].successor = (& (_nodes[i])) + 1; _nodes[i].nullify_treelinks(); } // make a loop structure so that we can circulate... _nodes[0].predecessor = (& (_nodes[n-1])); _nodes[n-1].successor = (& (_nodes[0])); // now label the rest of the nodes unsigned int scale = (n+1)/2; unsigned int top = std::min(n-1,scale); _nodes[top].parent = NULL; _top_node = &(_nodes[top]); _do_initial_connections(top, scale, 0, n, 0); // make sure things are sensible... //verify_structure(); }

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. { // make sure we don't exceed allowed number of nodes... assert(_available_nodes.size() > 0); Node * node = _available_nodes.back(); _available_nodes.pop_back(); node->value = value; Node * location = _top_node; Node * old_location = NULL; bool on_left = true; // (init not needed -- but soothes g++4) // work through tree until we reach its end #ifdef TRACK_DEPTH unsigned int depth = 0; #endif while(location != NULL) { #ifdef TRACK_DEPTH depth++; #endif old_location = location; on_left = value < location->value; if (on_left) {location = location->left;} else {location = location->right;} } #ifdef TRACK_DEPTH _max_depth = max(depth, _max_depth); #endif // now create tree links node->parent = old_location; if (on_left) {node->parent->left = node;} else {node->parent->right = node;} node->left = NULL; node->right = NULL; // and create predecessor / successor links node->predecessor = _find_predecessor(node); if (node->predecessor != NULL) { // it exists, so make use of its info (will include a cyclic case, // when successor is round the bend) node->successor = node->predecessor->successor; node->predecessor->successor = node; node->successor->predecessor = node; } else { // deal with case when we are left-most edge of tree (then successor // will exist...) node->successor = _find_successor(node); assert(node->successor != NULL); // can only happen if we're sole element // (but not allowed, since tree size>=1) node->predecessor = node->successor->predecessor; node->successor->predecessor = node; node->predecessor->successor = node; } return circulator(node); }

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(). {return node == NULL? -999 : node - &(_nodes[0]);}

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

Definition at line 91 of file SearchTree.hh. {return 0;};

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

Definition at line 101 of file SearchTree.hh. {return _nodes[i];};

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

Definition at line 72 of file SearchTree.hh. {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(). { typename SearchTree<T>::Node * base_node = &(_nodes[0]); typename SearchTree<T>::Node * node = base_node; int n = _nodes.size(); for(; node - base_node < n ; node++) { 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); } }

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(). { remove(circ._node); }

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(). { // we don't remove things from the tree if we've reached the last // elements... (is this wise?) assert(size() > 1); // switch this to throw...? assert(!node->treelinks_null()); // deal with relinking predecessor and successor node->predecessor->successor = node->successor; node->successor->predecessor = node->predecessor; if (node->left == NULL && node->right == NULL) { // node has no children, so remove it by nullifying the pointer // from the parent node->reset_parents_link_to_me(NULL); } else if (node->left != NULL && node->right == NULL){ // make parent point to my child node->reset_parents_link_to_me(node->left); // and child to parent node->left->parent = node->parent; // sort out the top node... if (_top_node == node) {_top_node = node->left;} } else if (node->left == NULL && node->right != NULL){ // make parent point to my child node->reset_parents_link_to_me(node->right); // and child to parent node->right->parent = node->parent; // sort out the top node... if (_top_node == node) {_top_node = node->right;} } else { // we have two children; we will put a replacement in our place Node * replacement; //SearchTree<T>::Node * replacements_child; // chose predecessor or successor (one, then other, then first, etc...) bool use_predecessor = (_n_removes % 2 == 1); if (use_predecessor) { // Option 1: put predecessor in our place, and have its parent // point to its left child (as a predecessor it has no right child) replacement = node->predecessor; assert(replacement->right == NULL); // guaranteed if it's our predecessor // we have to be careful of replacing certain links when the // replacement is this node's child if (replacement != node->left) { if (replacement->left != NULL) { replacement->left->parent = replacement->parent;} replacement->reset_parents_link_to_me(replacement->left); replacement->left = node->left; } replacement->parent = node->parent; replacement->right = node->right; } else { // Option 2: put successor in our place, and have its parent // point to its right child (as a successor it has no left child) replacement = node->successor; assert(replacement->left == NULL); // guaranteed if it's our successor if (replacement != node->right) { if (replacement->right != NULL) { replacement->right->parent = replacement->parent;} replacement->reset_parents_link_to_me(replacement->right); replacement->right = node->right; } replacement->parent = node->parent; replacement->left = node->left; } node->reset_parents_link_to_me(replacement); // make sure node's original children now point to the replacement if (node->left != replacement) {node->left->parent = replacement;} if (node->right != replacement) {node->right->parent = replacement;} // sort out the top node... if (_top_node == node) {_top_node = replacement;} } // make sure we leave something nice and clean... node->nullify_treelinks(); node->predecessor = NULL; node->successor = NULL; // for bookkeeping (and choosing whether to use pred. or succ.) _n_removes++; // for when we next need access to a free node... _available_nodes.push_back(node); }

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(). {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. { return circulator(_top_node); }

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. { return const_circulator(_top_node); }

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(). { // do a check running through all elements verify_structure_linear(); // do a recursive check down tree from top // first establish the extremities const Node * left_limit = _top_node; while (left_limit->left != NULL) {left_limit = left_limit->left;} const Node * right_limit = _top_node; while (right_limit->right != NULL) {right_limit = right_limit->right;} // then actually do recursion verify_structure_recursive(_top_node, left_limit, right_limit); }

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(). { //print_elements(); unsigned n_top = 0; unsigned n_null = 0; for(unsigned i = 0; i < _nodes.size(); i++) { const typename SearchTree<T>::Node * node = &(_nodes[i]); // make sure node is defined if (node->treelinks_null()) {n_null++; continue;} // make sure of the number of "top" nodes if (node->parent == NULL) { n_top++; //assert(node->left != NULL); //assert(node->right != NULL); } else { // make sure that I am a child of my parent... //assert((node->parent->left == node) || (node->parent->right == node)); assert((node->parent->left == node) ^ (node->parent->right == node)); } // when there is a left child make sure it's value is ordered // (note use of !(b<a), to allow for a<=b while using just the < // operator) if (node->left != NULL) { assert(!(node->value < node->left->value ));} // when there is a right child make sure it's value is ordered if (node->right != NULL) { assert(!(node->right->value < node->value ));} } assert(n_top == 1 || (n_top == 0 && size() <= 1) ); assert(n_null == _available_nodes.size() || (n_null == _available_nodes.size() + 1 && size() == 1)); }

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(). { assert(!(element->value < left_limit->value)); assert(!(right_limit->value < element->value)); const Node * left = element->left; if (left != NULL) { assert(!(element->value < left->value)); if (left != left_limit) { // recurse down the tree with this element as the right-hand limit verify_structure_recursive(left, left_limit, element);} } const Node * right = element->right; if (right != NULL) { assert(!(right->value < element->value)); if (right != right_limit) { // recurse down the tree with this element as the left-hand limit verify_structure_recursive(right, element, right_limit);} } }

---

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:

• include/fastjet/internal/SearchTree.hh

---