# Class IntervalTree

java.lang.Object
htsjdk.tribble.index.interval.IntervalTree

public class IntervalTree extends Object
An implementation of an interval tree, following the explanation. from CLR. For efficiently finding all intervals which overlap a given interval or point.

References: http://en.wikipedia.org/wiki/Interval_tree

Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8

## Constructor Summary

Constructors
Constructor
Description
`IntervalTree()`

## Method Summary

Modifier and Type
Method
Description
`List<Interval>`
`findOverlapping(Interval interval)`
`List<Interval>`
`getIntervals()`
Return all intervals in tree.
`int`
`getSize()`
The estimated size of the tree.
`void`
`insert(Interval interval)`
`boolean`
`isValid()`
Test code: make sure that the tree has all the properties defined by Red Black trees and interval trees
`int`
`size()`
`String`
`toString()`

### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`

## Constructor Details

### IntervalTree

public IntervalTree()

## Method Details

### 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.