Constructor Detail

• IntervalTree

  public IntervalTree()

Method Detail

• insert

  public void insert​(Interval interval)

• getSize

  public int getSize()

  The estimated size of the tree. We keep a running count on each insert, this getter returns that count.

  Returns:

  See Also:

  size()

• findOverlapping

  public List<Interval> findOverlapping​(Interval interval)

  Parameters:

  interval -

  Returns:

  all matches as a list of Intervals

• toString

  public String toString()

  Overrides:

  toString in class Object

• getIntervals

  public List<Interval> getIntervals()

  Return all intervals in tree. TODO: an iterator would be more effecient.

  Returns:

• size

  public int size()

  Returns:

  Returns the number of nodes in the tree. Recalculated each call

  See Also:

  getSize()

• isValid

  public boolean isValid()

  Test code: make sure that the tree has all the properties defined by Red Black trees and interval trees

  o. Root is black.

  o. NIL is black.

  o. Red nodes have black children.

  o. Every path from root to leaves contains the same number of black nodes.

  o. getMax(node) is the maximum of any interval rooted at that node..

  This code is expensive, and only meant to be used for assertions and testing.