Class IntervalTree

• Defined in File interval_tree.h

Class Documentation

class IntervalTree

Interval tree.

Public 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(CoalScalar low, CoalScalar high)

Return result for a given query.

Protected Functions

void leftRotate(IntervalTreeNode *node)

left rotation of tree node

void rightRotate(IntervalTreeNode *node)

right rotation of tree node

void recursiveInsert(IntervalTreeNode *node)

Inserts node 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 *invalid_node