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 (CoalScalar low, CoalScalar 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 *	invalid_node

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 63 of file coal/broadphase/detail/interval_tree.h.

Constructor & Destructor Documentation

◆ IntervalTree()

coal::detail::IntervalTree::IntervalTree ( )

the following are used for the query function

Definition at line 49 of file interval_tree.cpp.

◆ ~IntervalTree()

coal::detail::IntervalTree::~IntervalTree ( )

Definition at line 74 of file interval_tree.cpp.

Member Function Documentation

◆ deleteFixup()

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

protected

Definition at line 282 of file interval_tree.cpp.

◆ deleteNode() [1/2]

SimpleInterval * coal::detail::IntervalTree::deleteNode ( IntervalTreeNode * node )

Delete one node of the interval tree.

y should not be invalid_node 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 coal::detail::IntervalTree::deleteNode ( SimpleInterval * ivl )

delete node stored a given interval

Definition at line 341 of file interval_tree.cpp.

◆ fixupMaxHigh()

void coal::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 * coal::detail::IntervalTree::getPredecessor ( IntervalTreeNode * node ) const

get the predecessor of a given node

Definition at line 252 of file interval_tree.cpp.

◆ getSuccessor()

IntervalTreeNode * coal::detail::IntervalTree::getSuccessor ( IntervalTreeNode * node ) const

Get the successor of a given node.

Definition at line 234 of file interval_tree.cpp.

◆ insert()

IntervalTreeNode * coal::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 coal::detail::IntervalTree::leftRotate ( IntervalTreeNode * node )

protected

left rotation of tree node

Definition at line 105 of file interval_tree.cpp.

◆ print()

void coal::detail::IntervalTree::print ( ) const

Print the whole interval tree.

Definition at line 279 of file interval_tree.cpp.

◆ query()

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

Return result for a given query.

Definition at line 421 of file interval_tree.cpp.

◆ recursiveInsert()

void coal::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 coal::detail::IntervalTree::recursivePrint ( IntervalTreeNode * node ) const

protected

recursively print a subtree

Definition at line 270 of file interval_tree.cpp.

◆ recursiveSearch()

IntervalTreeNode * coal::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 coal::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 coal::detail::IntervalTree::current_parent

private

Definition at line 120 of file coal/broadphase/detail/interval_tree.h.

◆ invalid_node

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

protected

Definition at line 93 of file coal/broadphase/detail/interval_tree.h.

◆ recursion_node_stack

it_recursion_node* coal::detail::IntervalTree::recursion_node_stack

private

Definition at line 119 of file coal/broadphase/detail/interval_tree.h.

◆ recursion_node_stack_size

unsigned int coal::detail::IntervalTree::recursion_node_stack_size

private

Definition at line 118 of file coal/broadphase/detail/interval_tree.h.

◆ recursion_node_stack_top

unsigned int coal::detail::IntervalTree::recursion_node_stack_top

private

Definition at line 121 of file coal/broadphase/detail/interval_tree.h.

◆ root

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

protected

Definition at line 91 of file coal/broadphase/detail/interval_tree.h.

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

Public Member Functions

Protected Member Functions

Protected Attributes

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ IntervalTree()

◆ ~IntervalTree()

Member Function Documentation

◆ deleteFixup()

◆ deleteNode() [1/2]

◆ deleteNode() [2/2]

◆ fixupMaxHigh()

◆ getPredecessor()

◆ getSuccessor()

◆ insert()

◆ leftRotate()

◆ print()

◆ query()

◆ recursiveInsert()

◆ recursivePrint()

◆ recursiveSearch()

◆ rightRotate()

Member Data Documentation

◆ current_parent

◆ invalid_node

◆ recursion_node_stack

◆ recursion_node_stack_size

◆ recursion_node_stack_top

◆ root