FCL  0.6.0
Flexible Collision Library
Public Member Functions | Protected Member Functions | Protected Attributes | List of all members
fcl::detail::IntervalTree< S > Class Template Reference

Interval tree. More...

#include <interval_tree.h>

Public Member Functions

 IntervalTree ()
 
void print () const
 Print the whole interval tree.
 
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
 
IntervalTreeNode< S > * insert (SimpleInterval< S > *new_interval)
 Insert one node of the interval tree. More...
 
IntervalTreeNode< S > * getPredecessor (IntervalTreeNode< S > *node) const
 get the predecessor of a given node
 
IntervalTreeNode< S > * getSuccessor (IntervalTreeNode< S > *node) const
 Get the successor of a given node.
 
std::deque< SimpleInterval< S > * > query (S low, S high)
 Return result for a given query.
 

Protected Member Functions

void leftRotate (IntervalTreeNode< S > *node)
 left rotation of tree node
 
void rightRotate (IntervalTreeNode< S > *node)
 right rotation of tree node
 
void recursiveInsert (IntervalTreeNode< S > *node)
 Inserts node into the tree as if it were a regular binary tree.
 
void recursivePrint (IntervalTreeNode< S > *node) const
 recursively print a subtree
 
IntervalTreeNode< S > * recursiveSearch (IntervalTreeNode< S > *node, SimpleInterval< S > *ivl) const
 recursively find the node corresponding to the interval
 
void fixupMaxHigh (IntervalTreeNode< S > *node)
 Travels up to the root fixing the max_high fields after an insertion or deletion.
 
void deleteFixup (IntervalTreeNode< S > *node)
 

Protected Attributes

IntervalTreeNode< S > * root
 
IntervalTreeNode< S > * nil
 

Detailed Description

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

Interval tree.

Constructor & Destructor Documentation

template<typename S >
fcl::detail::IntervalTree< S >::IntervalTree ( )

the following are used for the query function

Member Function Documentation

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

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

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