#include <interval_tree.h>
Public Member Functions | |
| IntervalTree () | |
| ~IntervalTree () | |
| void | print () const |
| Print the whole interval tree. | |
| SimpleInterval * | deleteNode (IntervalTreeNode *node) |
| Delete one node of the interval tree. | |
| void | deleteNode (SimpleInterval *ivl) |
| delete node stored a given interval | |
| IntervalTreeNode * | insert (SimpleInterval *new_interval) |
| Insert one node of the interval tree. | |
| IntervalTreeNode * | getPredecessor (IntervalTreeNode *node) const |
| get the predecessor of a given node | |
| IntervalTreeNode * | getSuccessor (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 | |
| IntervalTreeNode * | recursiveSearch (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 | |
| IntervalTreeNode * | root |
| IntervalTreeNode * | nil |
Definition at line 100 of file interval_tree.h.
| fcl::IntervalTree::IntervalTree | ( | ) |
Definition at line 70 of file interval_tree.cpp.
| 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.
