fcl::IntervalTree Class Reference

Interval tree. More...

#include <interval_tree.h>

List of all members.

Public Member Functions
SimpleInterval *	deleteNode (IntervalTreeNode *node)
	Delete one node of the interval tree.
void	deleteNode (SimpleInterval *ivl)
	delete node stored a given interval
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 (SimpleInterval *new_interval)
	Insert one node of the interval tree.
	IntervalTree ()
void	print () const
	Print the whole interval tree.
std::deque< SimpleInterval * >	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
IntervalTreeNode *	recursiveSearch (IntervalTreeNode *node, SimpleInterval *ivl) const
	recursively find the node corresponding to the interval
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 100 of file interval_tree.h.

---

Constructor & Destructor Documentation

fcl::IntervalTree::IntervalTree

(

)

the following are used for the query function

Definition at line 70 of file interval_tree.cpp.

fcl::IntervalTree::~IntervalTree

(

)

Definition at line 91 of file interval_tree.cpp.

---

Member Function Documentation

void fcl::IntervalTree::deleteFixup

(

IntervalTreeNode *

node

)

[protected]

Definition at line 350 of file interval_tree.cpp.

SimpleInterval * fcl::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 446 of file interval_tree.cpp.

void fcl::IntervalTree::deleteNode

(

SimpleInterval *

ivl

)

delete node stored a given interval

Definition at line 423 of file interval_tree.cpp.

void fcl::IntervalTree::fixupMaxHigh

(

IntervalTreeNode *

node

)

[protected]

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

Definition at line 202 of file interval_tree.cpp.

IntervalTreeNode * fcl::IntervalTree::getPredecessor

(

IntervalTreeNode *

node

)

const

get the predecessor of a given node

Definition at line 298 of file interval_tree.cpp.

IntervalTreeNode * fcl::IntervalTree::getSuccessor

(

IntervalTreeNode *

node

)

const

Get the successor of a given node.

Definition at line 274 of file interval_tree.cpp.

IntervalTreeNode * fcl::IntervalTree::insert

(

SimpleInterval *

new_interval

)

Insert one node of the interval tree.

use sentinel instead of checking for root

Definition at line 211 of file interval_tree.cpp.

void fcl::IntervalTree::leftRotate

(

IntervalTreeNode *

node

)

[protected]

left rotation of tree node

Definition at line 129 of file interval_tree.cpp.

void fcl::IntervalTree::print

(

)

const

Print the whole interval tree.

Definition at line 345 of file interval_tree.cpp.

std::deque< SimpleInterval * > fcl::IntervalTree::query	(	double	low,
		double	high
	)

Return result for a given query.

Definition at line 517 of file interval_tree.cpp.

void fcl::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 178 of file interval_tree.cpp.

void fcl::IntervalTree::recursivePrint

(

IntervalTreeNode *

node

)

const [protected]

recursively print a subtree

Definition at line 334 of file interval_tree.cpp.

IntervalTreeNode * fcl::IntervalTree::recursiveSearch	(	IntervalTreeNode *	node,
		SimpleInterval *	ivl
	)		const [protected]

recursively find the node corresponding to the interval

Definition at line 430 of file interval_tree.cpp.

void fcl::IntervalTree::rightRotate

(

IntervalTreeNode *

node

)

[protected]

right rotation of tree node

Definition at line 153 of file interval_tree.cpp.

---

Member Data Documentation

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

Definition at line 158 of file interval_tree.h.

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

Definition at line 133 of file interval_tree.h.

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

Definition at line 157 of file interval_tree.h.

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

Definition at line 156 of file interval_tree.h.

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

Definition at line 159 of file interval_tree.h.

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

Definition at line 131 of file interval_tree.h.

---

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

• interval_tree.h
• interval_tree.cpp