hpp::fcl::detail::IntervalTree Class Reference

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

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:

• interval_tree.h
• interval_tree.cpp