All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends

fcl::IntervalTree Class Reference

Interval tree. More...

#include <interval_tree.h>

List of all members.

Public Member Functions

 IntervalTree ()
 ~IntervalTree ()
void print () const
 Print the whole interval tree.
SimpleIntervaldeleteNode (IntervalTreeNode *node)
 Delete one node of the interval tree.
void deleteNode (SimpleInterval *ivl)
 delete node stored a given interval
IntervalTreeNodeinsert (SimpleInterval *new_interval)
 Insert one node of the interval tree.
IntervalTreeNodegetPredecessor (IntervalTreeNode *node) const
 get the predecessor of a given node
IntervalTreeNodegetSuccessor (IntervalTreeNode *node) const
 Get the successor of a given node.
std::deque< SimpleInterval * > query (double low, double high)
 Return result for a given query.

Protected Member Functions

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

Protected Attributes


Detailed Description

Interval tree.

Definition at line 100 of file interval_tree.h.

Constructor & Destructor Documentation

fcl::IntervalTree::IntervalTree (  ) 

Definition at line 70 of file interval_tree.cpp.

Member Function Documentation

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.

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.

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