SearchTree< T >

Collaboration diagram for SearchTree< T >:

Classes
class	circulator
class	const_circulator
class	Node

Public Member Functions
	SearchTree (const std::vector< T > &init)
	SearchTree (const std::vector< T > &init, unsigned int max_size)
void	remove (unsigned node_index)
void	remove (typename SearchTree::Node *node)
void	remove (typename SearchTree::circulator &circ)
circulator	insert (const T &value)
const Node &	operator[] (int i) const
unsigned int	size () const
void	verify_structure ()
void	verify_structure_linear () const
void	verify_structure_recursive (const Node *, const Node *, const Node *) const
void	print_elements ()
unsigned int	max_depth () const
int	loc (const Node *node) const
Node *	_find_predecessor (const Node *)
Node *	_find_successor (const Node *)
const Node &	operator[] (unsigned int i) const
const_circulator	somewhere () const
circulator	somewhere ()

Private Member Functions
void	_initialize (const std::vector< T > &init)
void	_do_initial_connections (unsigned int this_one, unsigned int scale, unsigned int left_edge, unsigned int right_edge, unsigned int depth)

Private Attributes
std::vector< Node >	_nodes
std::vector< Node * >	_available_nodes
Node *	_top_node
unsigned int	_n_removes

Constructor & Destructor Documentation

SearchTree() [1/2]

SearchTree

(

const std::vector< T > &

init

)

                                                                     :
  _nodes(init.size()), _available_nodes(0) {
  _available_nodes.reserve(init.size());
  _initialize(init);
}

SearchTree() [2/2]

SearchTree	(	const std::vector< T > &	init,
		unsigned int	max_size
	)

                                               :
  _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

_do_initial_connections()

void _do_initial_connections ( unsigned int  this_one, unsigned int  scale, unsigned int  left_edge, unsigned int  right_edge, unsigned int  depth  )

private

                       {
#ifdef __FJCORE_SEARCHTREE_TRACK_DEPTH
  _max_depth = max(depth, _max_depth);
#endif
  unsigned int ref_new_scale = (scale+1)/2;
  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 (left >= static_cast<int>(left_edge)
                    && _nodes[left].treelinks_null() ) {
      _nodes[left].parent = &(_nodes[this_one]);
      _nodes[this_one].left = &(_nodes[left]);
      _do_initial_connections(left, new_scale, left_edge, this_one, depth+1);
      did_child = true;
      break;
    }
    unsigned int old_new_scale = new_scale;
    new_scale = (old_new_scale + 1)/2;
    if (new_scale == old_new_scale) break;
  }
  if (!did_child) {_nodes[this_one].left = NULL;}
  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]);
      _do_initial_connections(right, new_scale, this_one+1,right_edge,depth+1);
      did_child = true;
      break;
    }
    unsigned int old_new_scale = new_scale;
    new_scale = (old_new_scale + 1)/2;
    if (new_scale == old_new_scale) break;
  }
  if (!did_child) {_nodes[this_one].right = NULL;}
}

_find_predecessor()

SearchTree< T >::Node * _find_predecessor

(

const Node *

)

                                                                                                                       {
  typename SearchTree<T>::Node * newnode;
  if (node->left != NULL) {
    newnode = node->left;
    while(newnode->right != NULL) {newnode = newnode->right;}
    return newnode;
  } else {
    const typename SearchTree<T>::Node * lastnode = node;
    newnode = node->parent;
    while(newnode != NULL) {
      if (newnode->right == lastnode) {return newnode;}
      lastnode = newnode;
      newnode = newnode->parent;
    }
    return newnode;
  }
}

_find_successor()

SearchTree< T >::Node * _find_successor

(

const Node *

)

                                                                                                                     {
  typename SearchTree<T>::Node * newnode;
  if (node->right != NULL) {
    newnode = node->right;
    while(newnode->left != NULL) {newnode = newnode->left;}
    return newnode;
  } else {
    const typename SearchTree<T>::Node * lastnode = node;
    newnode = node->parent;
    while(newnode != NULL) {
      if (newnode->left == lastnode) {return newnode;}
      lastnode = newnode;
      newnode = newnode->parent;
    }
    return newnode;
  }
}

_initialize()

void _initialize ( const std::vector< T > &  init )

private

                                                                           {
  _n_removes = 0;
  unsigned n = init.size();
  assert(n>=1);
#ifdef __FJCORE_SEARCHTREE_TRACK_DEPTH
  _max_depth     = 0;
#endif
  for (unsigned int i = 1; i<n; i++) {
    assert(!(init[i] < init[i-1]));
  }
  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();
  }
  _nodes[0].predecessor = (& (_nodes[n-1]));
  _nodes[n-1].successor = (& (_nodes[0]));
  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);
}

insert()

SearchTree< T >::circulator insert

(

const T &

value

)

                                                                                        {
  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)
#ifdef __FJCORE_SEARCHTREE_TRACK_DEPTH
  unsigned int depth = 0;
#endif
  while(location != NULL) {
#ifdef __FJCORE_SEARCHTREE_TRACK_DEPTH
    depth++;
#endif
    old_location = location;
    on_left = value < location->value;
    if (on_left) {location = location->left;}
    else {location = location->right;}
  }
#ifdef __FJCORE_SEARCHTREE_TRACK_DEPTH
  _max_depth = max(depth, _max_depth);
#endif
  node->parent = old_location;
  if (on_left) {node->parent->left = node;}
  else {node->parent->right = node;}
  node->left = NULL;
  node->right = NULL;
  node->predecessor = _find_predecessor(node);
  if (node->predecessor != NULL) {
    node->successor = node->predecessor->successor;
    node->predecessor->successor = node;
    node->successor->predecessor = node;
  } else {
    node->successor = _find_successor(node);
    assert(node->successor != NULL); // can only happen if we're sole element
    node->predecessor = node->successor->predecessor;
    node->successor->predecessor = node;
    node->predecessor->successor = node;
  }
  return circulator(node);
}

loc()

int loc ( const Node *  node ) const

inline

                                                                        {return node == NULL?
      -999 : node - &(_nodes[0]);}

max_depth()

unsigned int max_depth ( ) const

inline

{return 0;};

operator[]() [1/2]

const Node& operator[] ( int  i ) const

inline

{return _nodes[i];};

operator[]() [2/2]

const Node& operator[] ( unsigned int  i ) const

inline

{return _nodes[i];};

print_elements()

void print_elements

                                                     {
  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);
  }
}

remove() [1/3]

void remove

(

typename SearchTree< T >::circulator &

circ

)

                                                              {
  remove(circ._node);
}

remove() [2/3]

void remove

(

typename SearchTree< T >::Node *

node

)

remove() [3/3]

void remove

(

unsigned

node_index

)

size()

unsigned int size ( ) const

inline

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

somewhere() [1/2]

SearchTree< T >::circulator somewhere

                                                                            {
  return circulator(_top_node);
}

somewhere() [2/2]

SearchTree< T >::const_circulator somewhere

                                                                                        {
  return const_circulator(_top_node);
}

verify_structure()

void verify_structure

                                                       {
  verify_structure_linear();
  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;}
  verify_structure_recursive(_top_node, left_limit, right_limit);
}

verify_structure_linear()

void verify_structure_linear

                                                                    {
  unsigned n_top = 0;
  unsigned n_null = 0;
  for(unsigned i = 0; i < _nodes.size(); i++) {
    const typename SearchTree<T>::Node * node = &(_nodes[i]);
    if (node->treelinks_null()) {n_null++; continue;}
    if (node->parent == NULL) {
      n_top++;
    } else {
      assert((node->parent->left == node) ^ (node->parent->right == node));
    }
    if (node->left != NULL) {
      assert(!(node->value < node->left->value ));}
    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));
}

verify_structure_recursive()

void verify_structure_recursive	(	const Node *	,
		const Node *	,
		const Node *
	)		const

                                                                     {
  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) {
      verify_structure_recursive(left, left_limit, element);}
  }
  const Node * right = element->right;
  if (right != NULL) {
    assert(!(right->value < element->value));
    if (right != right_limit) {
      verify_structure_recursive(right, element, right_limit);}
  }
}

Member Data Documentation

_available_nodes

std::vector<Node *> _available_nodes

private

_n_removes

unsigned int _n_removes

private

_nodes

std::vector<Node> _nodes

private

_top_node

Node* _top_node

private

---

The documentation for this class was generated from the following file:

• /builds/cms-analysis/general/DasAnalysisSystem/Core/Installer/Core/JetObservables/src/fjcore.cc