|
fastjet 2.4.5
|
|
fastjet 2.4.5
|
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) |
| 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 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 |
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.
| fastjet::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 305 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); }
| fastjet::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 290 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); }
| 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 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 366 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 * fastjet::SearchTree< T >::_find_predecessor | ( | const Node * | ) |
return predecessor by walking through the tree
Definition at line 679 of file SearchTree.hh.
References fastjet::SearchTree< T >::Node::left, fastjet::SearchTree< T >::Node::parent, and fastjet::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 * fastjet::SearchTree< T >::_find_successor | ( | const Node * | ) |
return successor by walking through the tree
Definition at line 703 of file SearchTree.hh.
References fastjet::SearchTree< T >::Node::left, fastjet::SearchTree< T >::Node::parent, and fastjet::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 fastjet::SearchTree< T >::_initialize | ( | const std::vector< T > & | init | ) | [private] |
do the actual hard work of initialization
Definition at line 315 of file SearchTree.hh.
References fastjet::d0::inline_maths::min().
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();
}
| 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 537 of file SearchTree.hh.
References 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.
{
// 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 fastjet::SearchTree< T >::loc | ( | const Node * | node | ) | const [inline] |
Definition at line 359 of file SearchTree.hh.
{return node == NULL?
-999 : node - &(_nodes[0]);}
| unsigned int fastjet::SearchTree< T >::max_depth | ( | ) | const [inline] |
Definition at line 91 of file SearchTree.hh.
{return 0;};
| const Node& fastjet::SearchTree< T >::operator[] | ( | int | i | ) | const [inline] |
Definition at line 72 of file SearchTree.hh.
{return _nodes[i];};
| const Node& fastjet::SearchTree< T >::operator[] | ( | unsigned int | i | ) | const [inline] |
Definition at line 101 of file SearchTree.hh.
{return _nodes[i];};
| void fastjet::SearchTree< T >::print_elements | ( | ) |
print out all elements...
Definition at line 728 of file SearchTree.hh.
References fastjet::SearchTree< T >::Node::left, fastjet::SearchTree< T >::Node::parent, fastjet::SearchTree< T >::Node::predecessor, fastjet::SearchTree< T >::Node::right, fastjet::SearchTree< T >::Node::successor, and fastjet::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 fastjet::SearchTree< T >::remove | ( | typename SearchTree< T >::Node * | node | ) |
| void fastjet::SearchTree< T >::remove | ( | unsigned | node_index | ) |
remove the node corresponding to node_index from the search tree
| void fastjet::SearchTree< T >::remove | ( | typename SearchTree< T >::circulator & | circ | ) |
Definition at line 437 of file SearchTree.hh.
References fastjet::SearchTree< T >::circulator::_node.
{
remove(circ._node);
}
| 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.
{return _nodes.size() - _available_nodes.size();}
| SearchTree< T >::circulator fastjet::SearchTree< T >::somewhere | ( | ) |
Definition at line 739 of file SearchTree.hh.
{
return circulator(_top_node);
}
| 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 745 of file SearchTree.hh.
{
return const_circulator(_top_node);
}
| void fastjet::SearchTree< T >::verify_structure | ( | ) |
check that the structure we've obtained makes sense...
Definition at line 594 of file SearchTree.hh.
References fastjet::SearchTree< T >::Node::left, and fastjet::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 fastjet::SearchTree< T >::verify_structure_linear | ( | ) | const |
Definition at line 639 of file SearchTree.hh.
References fastjet::SearchTree< T >::Node::left, fastjet::SearchTree< T >::Node::parent, fastjet::SearchTree< T >::Node::right, fastjet::SearchTree< T >::Node::treelinks_null(), and fastjet::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 fastjet::SearchTree< T >::verify_structure_recursive | ( | const Node * | , |
| const Node * | , | ||
| const Node * | |||
| ) | const |
Definition at line 613 of file SearchTree.hh.
References fastjet::SearchTree< T >::Node::left, fastjet::SearchTree< T >::Node::right, and fastjet::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);}
}
}
std::vector<Node *> fastjet::SearchTree< T >::_available_nodes [private] |
Definition at line 113 of file SearchTree.hh.
Referenced by fastjet::SearchTree< T >::SearchTree().
unsigned int fastjet::SearchTree< T >::_n_removes [private] |
Definition at line 115 of file SearchTree.hh.
std::vector<Node> fastjet::SearchTree< T >::_nodes [private] |
Definition at line 112 of file SearchTree.hh.
Referenced by fastjet::SearchTree< T >::SearchTree().
Node* fastjet::SearchTree< T >::_top_node [private] |
Definition at line 114 of file SearchTree.hh.
1.7.4