Interval tree. More...
#include <interval_tree.h>
Public Member Functions | |
SimpleInterval * | deleteNode (IntervalTreeNode *node) |
Delete one node of the interval tree. More... | |
void | deleteNode (SimpleInterval *ivl) |
delete node stored a given interval More... | |
IntervalTreeNode * | getPredecessor (IntervalTreeNode *node) const |
get the predecessor of a given node More... | |
IntervalTreeNode * | getSuccessor (IntervalTreeNode *node) const |
Get the successor of a given node. More... | |
IntervalTreeNode * | insert (SimpleInterval *new_interval) |
Insert one node of the interval tree. More... | |
IntervalTree () | |
void | print () const |
Print the whole interval tree. More... | |
std::deque< SimpleInterval * > | query (FCL_REAL low, FCL_REAL high) |
Return result for a given query. More... | |
~IntervalTree () | |
Protected Member Functions | |
void | deleteFixup (IntervalTreeNode *node) |
void | fixupMaxHigh (IntervalTreeNode *node) |
Travels up to the root fixing the max_high fields after an insertion or deletion. More... | |
void | leftRotate (IntervalTreeNode *node) |
left rotation of tree node More... | |
void | recursiveInsert (IntervalTreeNode *node) |
Inserts node into the tree as if it were a regular binary tree. More... | |
void | recursivePrint (IntervalTreeNode *node) const |
recursively print a subtree More... | |
IntervalTreeNode * | recursiveSearch (IntervalTreeNode *node, SimpleInterval *ivl) const |
recursively find the node corresponding to the interval More... | |
void | rightRotate (IntervalTreeNode *node) |
right rotation of tree node More... | |
Protected Attributes | |
IntervalTreeNode * | nil |
IntervalTreeNode * | root |
Private Attributes | |
unsigned int | current_parent |
it_recursion_node * | recursion_node_stack |
unsigned int | recursion_node_stack_size |
unsigned int | recursion_node_stack_top |
Interval tree.
Definition at line 64 of file interval_tree.h.
hpp::fcl::detail::IntervalTree::IntervalTree | ( | ) |
the following are used for the query function
Definition at line 50 of file interval_tree.cpp.
hpp::fcl::detail::IntervalTree::~IntervalTree | ( | ) |
Definition at line 74 of file interval_tree.cpp.
|
protected |
Definition at line 282 of file interval_tree.cpp.
SimpleInterval * hpp::fcl::detail::IntervalTree::deleteNode | ( | IntervalTreeNode * | node | ) |
Delete one node of the interval tree.
y should not be nil in this case y is the node to splice out and x is its child
Definition at line 362 of file interval_tree.cpp.
void hpp::fcl::detail::IntervalTree::deleteNode | ( | SimpleInterval * | ivl | ) |
delete node stored a given interval
Definition at line 341 of file interval_tree.cpp.
|
protected |
Travels up to the root fixing the max_high fields after an insertion or deletion.
Definition at line 174 of file interval_tree.cpp.
IntervalTreeNode * hpp::fcl::detail::IntervalTree::getPredecessor | ( | IntervalTreeNode * | node | ) | const |
get the predecessor of a given node
Definition at line 252 of file interval_tree.cpp.
IntervalTreeNode * hpp::fcl::detail::IntervalTree::getSuccessor | ( | IntervalTreeNode * | node | ) | const |
Get the successor of a given node.
Definition at line 234 of file interval_tree.cpp.
IntervalTreeNode * hpp::fcl::detail::IntervalTree::insert | ( | SimpleInterval * | new_interval | ) |
Insert one node of the interval tree.
use sentinel instead of checking for root
Definition at line 183 of file interval_tree.cpp.
|
protected |
left rotation of tree node
Definition at line 105 of file interval_tree.cpp.
void hpp::fcl::detail::IntervalTree::print | ( | ) | const |
Print the whole interval tree.
Definition at line 279 of file interval_tree.cpp.
std::deque< SimpleInterval * > hpp::fcl::detail::IntervalTree::query | ( | FCL_REAL | low, |
FCL_REAL | high | ||
) |
Return result for a given query.
Definition at line 419 of file interval_tree.cpp.
|
protected |
Inserts node into the tree as if it were a regular binary tree.
Definition at line 152 of file interval_tree.cpp.
|
protected |
recursively print a subtree
Definition at line 270 of file interval_tree.cpp.
|
protected |
recursively find the node corresponding to the interval
Definition at line 347 of file interval_tree.cpp.
|
protected |
right rotation of tree node
Definition at line 129 of file interval_tree.cpp.
|
private |
Definition at line 121 of file interval_tree.h.
|
protected |
Definition at line 94 of file interval_tree.h.
|
private |
Definition at line 120 of file interval_tree.h.
|
private |
Definition at line 119 of file interval_tree.h.
|
private |
Definition at line 122 of file interval_tree.h.
|
protected |
Definition at line 92 of file interval_tree.h.