Interval tree. More...

#include <interval_tree.h>

Public Member Functions
SimpleInterval< S > *	deleteNode (IntervalTreeNode< S > *node)
	Delete one node of the interval tree. More...

void	deleteNode (SimpleInterval< S > *ivl)
	delete node stored a given interval More...

IntervalTreeNode< S > *	getPredecessor (IntervalTreeNode< S > *node) const
	get the predecessor of a given node More...

IntervalTreeNode< S > *	getSuccessor (IntervalTreeNode< S > *node) const
	Get the successor of a given node. More...

IntervalTreeNode< S > *	insert (SimpleInterval< S > *new_interval)
	Insert one node of the interval tree. More...

	IntervalTree ()

void	print () const
	Print the whole interval tree. More...

std::deque< SimpleInterval< S > * >	query (S low, S high)
	Return result for a given query. More...

	~IntervalTree ()

Protected Member Functions
void	deleteFixup (IntervalTreeNode< S > *node)

void	fixupMaxHigh (IntervalTreeNode< S > *node)
	Travels up to the root fixing the max_high fields after an insertion or deletion. More...

void	leftRotate (IntervalTreeNode< S > *node)
	left rotation of tree node More...

void	recursiveInsert (IntervalTreeNode< S > *node)
	Inserts node into the tree as if it were a regular binary tree. More...

void	recursivePrint (IntervalTreeNode< S > *node) const
	recursively print a subtree More...

IntervalTreeNode< S > *	recursiveSearch (IntervalTreeNode< S > node, SimpleInterval< S > ivl) const
	recursively find the node corresponding to the interval More...

void	rightRotate (IntervalTreeNode< S > *node)
	right rotation of tree node More...

Protected Attributes
IntervalTreeNode< S > *	nil

IntervalTreeNode< S > *	root

Private Attributes
unsigned int	current_parent

it_recursion_node< S > *	recursion_node_stack

unsigned int	recursion_node_stack_size

unsigned int	recursion_node_stack_top

Detailed Description

template<typename S>
class fcl::detail::IntervalTree< S >

Interval tree.

Definition at line 72 of file interval_tree.h.

Constructor & Destructor Documentation

◆ IntervalTree()

template<typename S >

fcl::detail::IntervalTree< S >::IntervalTree

the following are used for the query function

Definition at line 54 of file interval_tree-inl.h.

◆ ~IntervalTree()

template<typename S >

fcl::detail::IntervalTree< S >::~IntervalTree

Definition at line 77 of file interval_tree-inl.h.

Member Function Documentation

◆ deleteFixup()

template<typename S >

void fcl::detail::IntervalTree< S >::deleteFixup ( IntervalTreeNode< S > * node )

protected

Definition at line 335 of file interval_tree-inl.h.

◆ deleteNode() [1/2]

template<typename S >

SimpleInterval< S > * fcl::detail::IntervalTree< S >::deleteNode ( IntervalTreeNode< S > * 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 437 of file interval_tree-inl.h.

◆ deleteNode() [2/2]

template<typename S >

void fcl::detail::IntervalTree< S >::deleteNode ( SimpleInterval< S > * ivl )

delete node stored a given interval

Definition at line 410 of file interval_tree-inl.h.

◆ fixupMaxHigh()

template<typename S >

void fcl::detail::IntervalTree< S >::fixupMaxHigh ( IntervalTreeNode< S > * node )

protected

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

Definition at line 190 of file interval_tree-inl.h.

◆ getPredecessor()

template<typename S >

IntervalTreeNode< S > * fcl::detail::IntervalTree< S >::getPredecessor ( IntervalTreeNode< S > * node ) const

get the predecessor of a given node

Definition at line 291 of file interval_tree-inl.h.

◆ getSuccessor()

template<typename S >

IntervalTreeNode< S > * fcl::detail::IntervalTree< S >::getSuccessor ( IntervalTreeNode< S > * node ) const

Get the successor of a given node.

Definition at line 266 of file interval_tree-inl.h.

◆ insert()

template<typename S >

IntervalTreeNode< S > * fcl::detail::IntervalTree< S >::insert ( SimpleInterval< S > * new_interval )

Insert one node of the interval tree.

use sentinel instead of checking for root

Definition at line 201 of file interval_tree-inl.h.

◆ leftRotate()

template<typename S >

void fcl::detail::IntervalTree< S >::leftRotate ( IntervalTreeNode< S > * node )

protected

left rotation of tree node

Definition at line 116 of file interval_tree-inl.h.

◆ print()

template<typename S >

void fcl::detail::IntervalTree< S >::print

Print the whole interval tree.

Definition at line 328 of file interval_tree-inl.h.

◆ query()

template<typename S >

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

Return result for a given query.

Definition at line 512 of file interval_tree-inl.h.

◆ recursiveInsert()

template<typename S >

void fcl::detail::IntervalTree< S >::recursiveInsert ( IntervalTreeNode< S > * node )

protected

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

Definition at line 165 of file interval_tree-inl.h.

◆ recursivePrint()

template<typename S >

void fcl::detail::IntervalTree< S >::recursivePrint ( IntervalTreeNode< S > * node ) const

protected

recursively print a subtree

Definition at line 316 of file interval_tree-inl.h.

◆ recursiveSearch()

template<typename S >

IntervalTreeNode< S > * fcl::detail::IntervalTree< S >::recursiveSearch	(	IntervalTreeNode< S > *	node,
		SimpleInterval< S > *	ivl
	)		const

protected

recursively find the node corresponding to the interval

Definition at line 419 of file interval_tree-inl.h.

◆ rightRotate()

template<typename S >

void fcl::detail::IntervalTree< S >::rightRotate ( IntervalTreeNode< S > * node )

protected

right rotation of tree node

Definition at line 141 of file interval_tree-inl.h.

Member Data Documentation

◆ current_parent

template<typename S >

unsigned int fcl::detail::IntervalTree< S >::current_parent

private

Definition at line 130 of file interval_tree.h.

◆ nil

template<typename S >

IntervalTreeNode<S>* fcl::detail::IntervalTree< S >::nil

protected

Definition at line 105 of file interval_tree.h.

◆ recursion_node_stack

template<typename S >

it_recursion_node<S>* fcl::detail::IntervalTree< S >::recursion_node_stack

private

Definition at line 129 of file interval_tree.h.

◆ recursion_node_stack_size

template<typename S >

unsigned int fcl::detail::IntervalTree< S >::recursion_node_stack_size

private

Definition at line 128 of file interval_tree.h.

◆ recursion_node_stack_top

template<typename S >

unsigned int fcl::detail::IntervalTree< S >::recursion_node_stack_top

private

Definition at line 131 of file interval_tree.h.

◆ root

template<typename S >

IntervalTreeNode<S>* fcl::detail::IntervalTree< S >::root

protected

Definition at line 103 of file 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

template<typename S> class fcl::detail::IntervalTree< S >

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

◆ nil

◆ recursion_node_stack

◆ recursion_node_stack_size

◆ recursion_node_stack_top

◆ root

template<typename S>
class fcl::detail::IntervalTree< S >