Public Member Functions | Protected Member Functions | Protected Attributes | Private Attributes | List of all members
hpp::fcl::detail::IntervalTree Class Reference

Interval tree. More...

#include <interval_tree.h>

Public Member Functions

SimpleIntervaldeleteNode (IntervalTreeNode *node)
 Delete one node of the interval tree. More...
 
void deleteNode (SimpleInterval *ivl)
 delete node stored a given interval More...
 
IntervalTreeNodegetPredecessor (IntervalTreeNode *node) const
 get the predecessor of a given node More...
 
IntervalTreeNodegetSuccessor (IntervalTreeNode *node) const
 Get the successor of a given node. More...
 
IntervalTreeNodeinsert (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...
 
IntervalTreeNoderecursiveSearch (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

IntervalTreeNodenil
 
IntervalTreeNoderoot
 

Private Attributes

unsigned int current_parent
 
it_recursion_noderecursion_node_stack
 
unsigned int recursion_node_stack_size
 
unsigned int recursion_node_stack_top
 

Detailed Description

Interval tree.

Definition at line 64 of file interval_tree.h.

Constructor & Destructor Documentation

◆ IntervalTree()

hpp::fcl::detail::IntervalTree::IntervalTree ( )

the following are used for the query function

Definition at line 50 of file interval_tree.cpp.

◆ ~IntervalTree()

hpp::fcl::detail::IntervalTree::~IntervalTree ( )

Definition at line 74 of file interval_tree.cpp.

Member Function Documentation

◆ deleteFixup()

void hpp::fcl::detail::IntervalTree::deleteFixup ( IntervalTreeNode node)
protected

Definition at line 282 of file interval_tree.cpp.

◆ deleteNode() [1/2]

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.

◆ deleteNode() [2/2]

void hpp::fcl::detail::IntervalTree::deleteNode ( SimpleInterval ivl)

delete node stored a given interval

Definition at line 341 of file interval_tree.cpp.

◆ fixupMaxHigh()

void hpp::fcl::detail::IntervalTree::fixupMaxHigh ( IntervalTreeNode node)
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.

◆ getPredecessor()

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.

◆ getSuccessor()

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.

◆ insert()

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.

◆ leftRotate()

void hpp::fcl::detail::IntervalTree::leftRotate ( IntervalTreeNode node)
protected

left rotation of tree node

Definition at line 105 of file interval_tree.cpp.

◆ print()

void hpp::fcl::detail::IntervalTree::print ( ) const

Print the whole interval tree.

Definition at line 279 of file interval_tree.cpp.

◆ query()

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.

◆ recursiveInsert()

void hpp::fcl::detail::IntervalTree::recursiveInsert ( IntervalTreeNode node)
protected

Inserts node into the tree as if it were a regular binary tree.

Definition at line 152 of file interval_tree.cpp.

◆ recursivePrint()

void hpp::fcl::detail::IntervalTree::recursivePrint ( IntervalTreeNode node) const
protected

recursively print a subtree

Definition at line 270 of file interval_tree.cpp.

◆ recursiveSearch()

IntervalTreeNode * hpp::fcl::detail::IntervalTree::recursiveSearch ( IntervalTreeNode node,
SimpleInterval ivl 
) const
protected

recursively find the node corresponding to the interval

Definition at line 347 of file interval_tree.cpp.

◆ rightRotate()

void hpp::fcl::detail::IntervalTree::rightRotate ( IntervalTreeNode node)
protected

right rotation of tree node

Definition at line 129 of file interval_tree.cpp.

Member Data Documentation

◆ current_parent

unsigned int hpp::fcl::detail::IntervalTree::current_parent
private

Definition at line 121 of file interval_tree.h.

◆ nil

IntervalTreeNode* hpp::fcl::detail::IntervalTree::nil
protected

Definition at line 94 of file interval_tree.h.

◆ recursion_node_stack

it_recursion_node* hpp::fcl::detail::IntervalTree::recursion_node_stack
private

Definition at line 120 of file interval_tree.h.

◆ recursion_node_stack_size

unsigned int hpp::fcl::detail::IntervalTree::recursion_node_stack_size
private

Definition at line 119 of file interval_tree.h.

◆ recursion_node_stack_top

unsigned int hpp::fcl::detail::IntervalTree::recursion_node_stack_top
private

Definition at line 122 of file interval_tree.h.

◆ root

IntervalTreeNode* hpp::fcl::detail::IntervalTree::root
protected

Definition at line 92 of file interval_tree.h.


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


hpp-fcl
Author(s):
autogenerated on Fri Jun 2 2023 02:39:03