coal::detail::IntervalTree Class Reference

Interval tree. More...

#include <coal/broadphase/detail/interval_tree.h>

Public Member Functions
	IntervalTree ()
	~IntervalTree ()
void	print () const
	Print the whole interval tree.
SimpleInterval *	deleteNode (IntervalTreeNode *node)
	Delete one node of the interval tree.
void	deleteNode (SimpleInterval *ivl)
	delete node stored a given interval
IntervalTreeNode *	insert (SimpleInterval *new_interval)
	Insert one node of the interval tree.
IntervalTreeNode *	getPredecessor (IntervalTreeNode *node) const
	get the predecessor of a given node
IntervalTreeNode *	getSuccessor (IntervalTreeNode *node) const
	Get the successor of a given node.
std::deque< SimpleInterval * >	query (CoalScalar low, CoalScalar high)
	Return result for a given query.

Protected Member Functions
void	leftRotate (IntervalTreeNode *node)
	left rotation of tree node
void	rightRotate (IntervalTreeNode *node)
	right rotation of tree node
void	recursiveInsert (IntervalTreeNode *node)
	Inserts node into the tree as if it were a regular binary tree.
void	recursivePrint (IntervalTreeNode *node) const
	recursively print a subtree
IntervalTreeNode *	recursiveSearch (IntervalTreeNode *node, SimpleInterval *ivl) const
	recursively find the node corresponding to the interval
void	fixupMaxHigh (IntervalTreeNode *node)
	Travels up to the root fixing the max_high fields after an insertion or deletion.
void	deleteFixup (IntervalTreeNode *node)

Protected Attributes
IntervalTreeNode *	root
IntervalTreeNode *	invalid_node

Detailed Description

Interval tree.

Constructor & Destructor Documentation

IntervalTree()

coal::detail::IntervalTree::IntervalTree

(

)

~IntervalTree()

coal::detail::IntervalTree::~IntervalTree

(

)

Member Function Documentation

deleteFixup()

void coal::detail::IntervalTree::deleteFixup ( IntervalTreeNode * node )

protected

deleteNode() [1/2]

SimpleInterval * coal::detail::IntervalTree::deleteNode

(

IntervalTreeNode *

node

)

Delete one node of the interval tree.

deleteNode() [2/2]

void coal::detail::IntervalTree::deleteNode

(

SimpleInterval *

ivl

)

delete node stored a given interval

fixupMaxHigh()

void coal::detail::IntervalTree::fixupMaxHigh ( IntervalTreeNode * node )

protected

Travels up to the root fixing the max_high fields after an insertion or deletion.

getPredecessor()

IntervalTreeNode * coal::detail::IntervalTree::getPredecessor

(

IntervalTreeNode *

node

)

const

get the predecessor of a given node

getSuccessor()

IntervalTreeNode * coal::detail::IntervalTree::getSuccessor

(

IntervalTreeNode *

node

)

const

Get the successor of a given node.

insert()

IntervalTreeNode * coal::detail::IntervalTree::insert

(

SimpleInterval *

new_interval

)

Insert one node of the interval tree.

leftRotate()

void coal::detail::IntervalTree::leftRotate ( IntervalTreeNode * node )

protected

left rotation of tree node

print()

void coal::detail::IntervalTree::print

(

)

const

Print the whole interval tree.

query()

std::deque< SimpleInterval * > coal::detail::IntervalTree::query	(	CoalScalar	low,
		CoalScalar	high )

Return result for a given query.

recursiveInsert()

void coal::detail::IntervalTree::recursiveInsert ( IntervalTreeNode * node )

protected

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

recursivePrint()

void coal::detail::IntervalTree::recursivePrint ( IntervalTreeNode * node ) const

protected

recursively print a subtree

recursiveSearch()

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

protected

recursively find the node corresponding to the interval

rightRotate()

void coal::detail::IntervalTree::rightRotate ( IntervalTreeNode * node )

protected

right rotation of tree node

Member Data Documentation

invalid_node

IntervalTreeNode* coal::detail::IntervalTree::invalid_node

protected

root

IntervalTreeNode* coal::detail::IntervalTree::root

protected

---

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

• include/coal/broadphase/detail/interval_tree.h