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) |
| sets the detailed parameters for the ghosts (which may not be quite the same as those requested -- this is in order for things to fit in nicely into 2pi etc... | |
| 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 |
Detailed Description
template<class T>
class 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
| SearchTree< T >::SearchTree | ( | const std::vector< T > & | init | ) |
constructor for a search tree from an ordered vector
initialise from a sorted initial array
Definition at line 304 of file SearchTree.hh.
References SearchTree< T >::_available_nodes, and SearchTree< T >::_initialize().
: _nodes(init.size()), _available_nodes(0) { // reserve space for the list of available nodes _available_nodes.reserve(init.size()); _initialize(init); }
| SearchTree< T >::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
initialise from a sorted initial array allowing for a larger maximum size of the array...
Definition at line 289 of file SearchTree.hh.
References SearchTree< T >::_available_nodes, SearchTree< T >::_initialize(), and 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
| void 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 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.
{
#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;}
}
| SearchTree< T >::Node * SearchTree< T >::_find_predecessor | ( | const Node * | ) |
return predecessor by walking through the tree
Definition at line 678 of file SearchTree.hh.
References SearchTree< T >::Node::left, SearchTree< T >::Node::parent, and SearchTree< T >::Node::right.
{
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;
}
}
| SearchTree< T >::Node * SearchTree< T >::_find_successor | ( | const Node * | ) |
return successor by walking through the tree
Definition at line 702 of file SearchTree.hh.
References SearchTree< T >::Node::left, SearchTree< T >::Node::parent, and SearchTree< T >::Node::right.
{
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;
}
}
| void SearchTree< T >::_initialize | ( | const std::vector< T > & | init | ) | [private] |
sets the detailed parameters for the ghosts (which may not be quite the same as those requested -- this is in order for things to fit in nicely into 2pi etc...
do the actual hard work of initialization
Definition at line 45 of file GhostedAreaSpec.cc.
References twopi.
Referenced by SearchTree< T >::SearchTree().
{
// add on area-measuring dummy particles
_drap = sqrt(_ghost_area);
_dphi = _drap;
_nphi = int(ceil(twopi/_dphi)); _dphi = twopi/_nphi;
_nrap = int(ceil(_ghost_maxrap/_drap)); _drap = _ghost_maxrap / _nrap;
_actual_ghost_area = _dphi * _drap;
_n_ghosts = (2*_nrap+1)*_nphi;
// checkpoint the status of the random number generator.
checkpoint_random();
//_random_generator.info(cerr);
}
| SearchTree< T >::circulator 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 SearchTree< T >::Node::left, SearchTree< T >::Node::parent, SearchTree< T >::Node::predecessor, SearchTree< T >::Node::right, and SearchTree< T >::Node::value.
{
// 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);
}
| int SearchTree< T >::loc | ( | const Node * | node | ) | const [inline] |
Definition at line 358 of file SearchTree.hh.
{return node == NULL?
-999 : node - &(_nodes[0]);}
| unsigned int SearchTree< T >::max_depth | ( | ) | const [inline] |
Definition at line 91 of file SearchTree.hh.
{return 0;};
| const Node& SearchTree< T >::operator[] | ( | int | i | ) | const [inline] |
Definition at line 72 of file SearchTree.hh.
References SearchTree< T >::_nodes.
{return _nodes[i];};
| const Node& SearchTree< T >::operator[] | ( | unsigned int | i | ) | const [inline] |
Definition at line 101 of file SearchTree.hh.
References SearchTree< T >::_nodes.
{return _nodes[i];};
| void SearchTree< T >::print_elements | ( | ) |
print out all elements...
Definition at line 727 of file SearchTree.hh.
References SearchTree< T >::Node::left, SearchTree< T >::Node::parent, SearchTree< T >::Node::predecessor, SearchTree< T >::Node::right, SearchTree< T >::Node::successor, and SearchTree< T >::Node::value.
{
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);
}
}
| void SearchTree< T >::remove | ( | typename SearchTree< T >::Node * | node | ) |
| void SearchTree< T >::remove | ( | unsigned | node_index | ) |
remove the node corresponding to node_index from the search tree
| void SearchTree< T >::remove | ( | typename SearchTree< T >::circulator & | circ | ) |
Definition at line 436 of file SearchTree.hh.
References SearchTree< T >::circulator::_node.
{
remove(circ._node);
}
| unsigned int SearchTree< T >::size | ( | ) | const [inline] |
return the number of elements currently in the search tree
Definition at line 75 of file SearchTree.hh.
References SearchTree< T >::_available_nodes, and SearchTree< T >::_nodes.
{return _nodes.size() - _available_nodes.size();}
| SearchTree< T >::circulator SearchTree< T >::somewhere | ( | ) |
Definition at line 738 of file SearchTree.hh.
{
return circulator(_top_node);
}
| SearchTree< T >::const_circulator 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.
{
return const_circulator(_top_node);
}
| void SearchTree< T >::verify_structure | ( | ) |
check that the structure we've obtained makes sense...
Definition at line 593 of file SearchTree.hh.
References SearchTree< T >::Node::left, and SearchTree< T >::Node::right.
{
// 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);
}
| void SearchTree< T >::verify_structure_linear | ( | ) | const |
Definition at line 638 of file SearchTree.hh.
References SearchTree< T >::Node::left, SearchTree< T >::Node::parent, SearchTree< T >::Node::right, SearchTree< T >::Node::treelinks_null(), and SearchTree< T >::Node::value.
{
//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));
}
| void SearchTree< T >::verify_structure_recursive | ( | const Node * | , |
| const Node * | , | ||
| const Node * | |||
| ) | const |
Definition at line 612 of file SearchTree.hh.
References SearchTree< T >::Node::left, SearchTree< T >::Node::right, and SearchTree< T >::Node::value.
{
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
std::vector<Node *> SearchTree< T >::_available_nodes [private] |
Definition at line 113 of file SearchTree.hh.
Referenced by SearchTree< T >::SearchTree(), and SearchTree< T >::size().
unsigned int SearchTree< T >::_n_removes [private] |
Definition at line 115 of file SearchTree.hh.
std::vector<Node> SearchTree< T >::_nodes [private] |
Definition at line 112 of file SearchTree.hh.
Referenced by SearchTree< T >::operator[](), SearchTree< T >::SearchTree(), and SearchTree< T >::size().
Node* SearchTree< T >::_top_node [private] |
Definition at line 114 of file SearchTree.hh.
The documentation for this class was generated from the following files:
- include/fastjet/internal/SearchTree.hh
- src/GhostedAreaSpec.cc
