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

Interval tree. More...

#include <hpp/fcl/broadphase/detail/interval_tree.h>

Collaboration diagram for hpp::fcl::detail::IntervalTree:

Public Member Functions
	IntervalTree ()
	~IntervalTree ()
void	print () const
	Print the whole interval tree. More...
SimpleInterval *	deleteNode (IntervalTreeNode *node)
	Delete one node of the interval tree. More...
void	deleteNode (SimpleInterval *ivl)
	delete node stored a given interval More...
IntervalTreeNode *	insert (SimpleInterval *new_interval)
	Insert one node of the interval tree. 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...
std::deque< SimpleInterval * >	query (FCL_REAL low, FCL_REAL high)
	Return result for a given query. More...

Protected Member Functions
void	leftRotate (IntervalTreeNode *node)
	left rotation of tree node More...
void	rightRotate (IntervalTreeNode *node)
	right 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	fixupMaxHigh (IntervalTreeNode *node)
	Travels up to the root fixing the max_high fields after an insertion or deletion. More...
void	deleteFixup (IntervalTreeNode *node)

Protected Attributes
IntervalTreeNode *	root
IntervalTreeNode *	invalid_node

Detailed Description

Interval tree.

Constructor & Destructor Documentation

IntervalTree()

hpp::fcl::detail::IntervalTree::IntervalTree

(

)

~IntervalTree()

hpp::fcl::detail::IntervalTree::~IntervalTree

(

)

Member Function Documentation

deleteFixup()

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

protected

deleteNode() [1/2]

SimpleInterval* hpp::fcl::detail::IntervalTree::deleteNode

(

IntervalTreeNode *

node

)

Delete one node of the interval tree.

deleteNode() [2/2]

void hpp::fcl::detail::IntervalTree::deleteNode

(

SimpleInterval *

ivl

)

delete node stored a given interval

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.

getPredecessor()

IntervalTreeNode* hpp::fcl::detail::IntervalTree::getPredecessor

(

IntervalTreeNode *

node

)

const

get the predecessor of a given node

getSuccessor()

IntervalTreeNode* hpp::fcl::detail::IntervalTree::getSuccessor

(

IntervalTreeNode *

node

)

const

Get the successor of a given node.

insert()

IntervalTreeNode* hpp::fcl::detail::IntervalTree::insert

(

SimpleInterval *

new_interval

)

Insert one node of the interval tree.

leftRotate()

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

protected

left rotation of tree node

print()

void hpp::fcl::detail::IntervalTree::print

(

)

const

Print the whole interval tree.

query()

std::deque<SimpleInterval*> hpp::fcl::detail::IntervalTree::query	(	FCL_REAL	low,
		FCL_REAL	high
	)

Return result for a given query.

recursiveInsert()

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

protected

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

recursivePrint()

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

protected

recursively print a subtree

recursiveSearch()

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

protected

recursively find the node corresponding to the interval

rightRotate()

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

protected

right rotation of tree node

Member Data Documentation

invalid_node

IntervalTreeNode* hpp::fcl::detail::IntervalTree::invalid_node

protected

root

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

protected

---

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

• include/hpp/fcl/broadphase/detail/interval_tree.h