htsjdk.tribble.index.interval

Class IntervalTree

java.lang.Object

htsjdk.tribble.index.interval.IntervalTree

public class IntervalTree
extends java.lang.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 and Description
IntervalTree()

Method Summary

Modifier and Type	Method and Description
java.util.List<Interval>	findOverlapping(Interval interval)
java.util.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 o.
int	size()
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

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 java.util.List<Interval> findOverlapping(Interval interval)

Parameters:

interval -

Returns:

all matches as a list of Intervals

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

getIntervals

public java.util.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.