Public Member Functions | Protected Member Functions | Protected Attributes | Private Attributes | List of all members
fcl::detail::IntervalTree< S > Class Template Reference

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 ( low,
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:


fcl
Author(s):
autogenerated on Tue Jun 22 2021 07:27:56