collision_space_ccd::IntervalTree Class Reference

Interval tree. More...

#include <interval_tree.h>

List of all members.

Public Member Functions
Interval *	deleteNode (IntervalTreeNode *node)
	Delete 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.
IntervalTreeNode *	insert (Interval *new_interval)
	Insert one node of the interval tree.
	IntervalTree ()
void	print () const
	Print the whole interval tree.
std::deque< Interval * >	query (double low, double high)
	Return result for a given query.
	~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.
void	leftRotate (IntervalTreeNode *node)
	left rotation of tree node
void	recursiveInsert (IntervalTreeNode *node)
	recursively insert a node
void	recursivePrint (IntervalTreeNode *node) const
	recursively print a subtree
void	rightRotate (IntervalTreeNode *node)
	right rotation of tree node
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 111 of file interval_tree.h.

---

Constructor & Destructor Documentation

collision_space_ccd::IntervalTree::IntervalTree

(

)

Definition at line 56 of file interval_tree.cpp.

collision_space_ccd::IntervalTree::~IntervalTree

(

)

Definition at line 293 of file interval_tree.cpp.

---

Member Function Documentation

void collision_space_ccd::IntervalTree::deleteFixup

(

IntervalTreeNode *

node

)

[protected]

Definition at line 336 of file interval_tree.cpp.

Interval * collision_space_ccd::IntervalTree::deleteNode

(

IntervalTreeNode *

node

)

Delete one node of the interval tree.

Definition at line 409 of file interval_tree.cpp.

void collision_space_ccd::IntervalTree::fixupMaxHigh

(

IntervalTreeNode *

node

)

[protected]

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

Definition at line 151 of file interval_tree.cpp.

IntervalTreeNode * collision_space_ccd::IntervalTree::getPredecessor

(

IntervalTreeNode *

node

)

const

get the predecessor of a given node

Definition at line 247 of file interval_tree.cpp.

IntervalTreeNode * collision_space_ccd::IntervalTree::getSuccessor

(

IntervalTreeNode *

node

)

const

Get the successor of a given node.

Definition at line 223 of file interval_tree.cpp.

IntervalTreeNode * collision_space_ccd::IntervalTree::insert

(

Interval *

new_interval

)

Insert one node of the interval tree.

Definition at line 160 of file interval_tree.cpp.

void collision_space_ccd::IntervalTree::leftRotate

(

IntervalTreeNode *

node

)

[protected]

left rotation of tree node

Definition at line 78 of file interval_tree.cpp.

void collision_space_ccd::IntervalTree::print

(

)

const

Print the whole interval tree.

Definition at line 331 of file interval_tree.cpp.

std::deque< Interval * > collision_space_ccd::IntervalTree::query	(	double	low,
		double	high
	)

Return result for a given query.

Definition at line 480 of file interval_tree.cpp.

void collision_space_ccd::IntervalTree::recursiveInsert

(

IntervalTreeNode *

node

)

[protected]

recursively insert a node

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

Definition at line 127 of file interval_tree.cpp.

void collision_space_ccd::IntervalTree::recursivePrint

(

IntervalTreeNode *

node

)

const [protected]

recursively print a subtree

Definition at line 283 of file interval_tree.cpp.

void collision_space_ccd::IntervalTree::rightRotate

(

IntervalTreeNode *

node

)

[protected]

right rotation of tree node

Definition at line 102 of file interval_tree.cpp.

---

Member Data Documentation

unsigned int collision_space_ccd::IntervalTree::current_parent [private]

Definition at line 163 of file interval_tree.h.

IntervalTreeNode* collision_space_ccd::IntervalTree::nil [protected]

Definition at line 141 of file interval_tree.h.

it_recursion_node* collision_space_ccd::IntervalTree::recursion_node_stack [private]

Definition at line 162 of file interval_tree.h.

unsigned int collision_space_ccd::IntervalTree::recursion_node_stack_size [private]

Definition at line 161 of file interval_tree.h.

unsigned int collision_space_ccd::IntervalTree::recursion_node_stack_top [private]

Definition at line 164 of file interval_tree.h.

IntervalTreeNode* collision_space_ccd::IntervalTree::root [protected]

Definition at line 139 of file interval_tree.h.

---

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

• interval_tree.h
• interval_tree.cpp