Gephi Toolkit Javadoc

org.gephi.data.attributes.type
Class IntervalTree<T>

java.lang.Object
  extended by org.gephi.data.attributes.type.IntervalTree<T>
Type Parameters:
T - type of data

public final class IntervalTree<T>
extends java.lang.Object

It is essentially a map from intervals to object which can be queried for Interval instances associated with a particular interval of time.

Insertion can be performed in O(lg n) time, where n is the number of nodes. All intervals in a tree that overlap some interval i can be listed in O(min(n, k lg n) time, where k is the number of intervals in the output list. Thus search and deletion can be performed in this time.

The space consumption is O(n).

Note that this implementation doesn't allow intervals to be duplicated.

References:

Author:
Cezary Bartosiak

Constructor Summary
IntervalTree()
          Constructs an empty IntervalTree.
IntervalTree(IntervalTree intervalTree)
          Constructs a copy of the given IntervalTree.
 
Method Summary
 void delete(Interval interval)
          Removes all intervals from this IntervalTree that overlap with the given interval.
 boolean equals(java.lang.Object obj)
          Compares this interval tree with the specified object for equality.
 double getHigh()
          Returns the rightmost point or Double.POSITIVE_INFINITY in case of no intervals.
 java.util.List<Interval<T>> getIntervals()
          Returns all intervals.
 double getLow()
          Returns the leftmost point or Double.NEGATIVE_INFINITY in case of no intervals.
 int hashCode()
          Returns a hashcode of this interval tree.
 void insert(Interval<T> interval)
          Inserts the interval into this IntervalTree.
 boolean isEmpty()
          Indicates if this IntervalTree contains 0 intervals.
 boolean isHighExcluded()
          Indicates if the rightmost point is excluded.
 boolean isLowExcluded()
          Indicates if the leftmost point is excluded.
 Interval<T> maximum()
          Returns the interval with the highest left endpoint.
 Interval<T> minimum()
          Returns the interval with the lowest left endpoint.
 boolean overlapsWith(Interval interval)
          Indicates if this IntervalTree overlaps with the given time interval.
 java.util.List<Interval<T>> search(double low, double high)
          Returns all intervals overlapping with an interval given by low and high.
 java.util.List<Interval<T>> search(Interval interval)
          Returns all intervals overlapping with a given Interval.
 java.lang.String toString()
          Returns a string representation of this interval tree in a format <[low, high, value], ..., [low, high, value]>.
 java.lang.String toString(boolean timesAsDoubles)
          Creates a string representation of all the intervals with their values.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

IntervalTree

public IntervalTree()
Constructs an empty IntervalTree.


IntervalTree

public IntervalTree(IntervalTree intervalTree)
Constructs a copy of the given IntervalTree.

Parameters:
intervalTree - a copied IntervalTree
Method Detail

insert

public void insert(Interval<T> interval)
Inserts the interval into this IntervalTree.

Parameters:
interval - an interval to be inserted
Throws:
java.lang.NullPointerException - if interval is null.

delete

public void delete(Interval interval)
Removes all intervals from this IntervalTree that overlap with the given interval.

Parameters:
interval - determines which intervals should be removed
Throws:
java.lang.NullPointerException - if interval is null.

minimum

public Interval<T> minimum()
Returns the interval with the lowest left endpoint.

Returns:
the interval with the lowest left endpoint or null if the tree is empty.

maximum

public Interval<T> maximum()
Returns the interval with the highest left endpoint.

Returns:
the interval with the highest left endpoint or null if the tree is empty.

getLow

public double getLow()
Returns the leftmost point or Double.NEGATIVE_INFINITY in case of no intervals.

Returns:
the leftmost point.

getHigh

public double getHigh()
Returns the rightmost point or Double.POSITIVE_INFINITY in case of no intervals.

Returns:
the rightmost point.

isLowExcluded

public boolean isLowExcluded()
Indicates if the leftmost point is excluded.

Returns:
true if the leftmost point is excluded, false otherwise.

isHighExcluded

public boolean isHighExcluded()
Indicates if the rightmost point is excluded.

Returns:
true if the rightmost point is excluded, false otherwise.

isEmpty

public boolean isEmpty()
Indicates if this IntervalTree contains 0 intervals.

Returns:
true if this IntervalTree is empty, false otherwise.

getIntervals

public java.util.List<Interval<T>> getIntervals()
Returns all intervals.

Returns:
all intervals

search

public java.util.List<Interval<T>> search(Interval interval)
Returns all intervals overlapping with a given Interval.

Parameters:
interval - an {#code Interval} to be searched for overlaps
Returns:
all intervals overlapping with a given Interval.
Throws:
java.lang.NullPointerException - if interval is null.

search

public java.util.List<Interval<T>> search(double low,
                                          double high)
Returns all intervals overlapping with an interval given by low and high. They are considered as included by default.

Parameters:
low - the left endpoint of an interval to be searched for overlaps
high - the right endpoint an interval to be searched for overlaps
Returns:
all intervals overlapping with an interval given by low and high.
Throws:
java.lang.IllegalArgumentException - if low > high.

overlapsWith

public boolean overlapsWith(Interval interval)
Indicates if this IntervalTree overlaps with the given time interval.

Parameters:
interval - a given time interval
Returns:
true if this IntervalTree overlaps with interval, false otherwise.

equals

public boolean equals(java.lang.Object obj)
Compares this interval tree with the specified object for equality.

Note that two interval trees are equal if they contain the same intervals.

Overrides:
equals in class java.lang.Object
Parameters:
obj - object to which this interval tree is to be compared
Returns:
true if and only if the specified Object is a IntervalTree which contain the same intervals as this IntervalTree's.
See Also:
hashCode()

hashCode

public int hashCode()
Returns a hashcode of this interval tree.

Overrides:
hashCode in class java.lang.Object
Returns:
a hashcode of this interval tree.

toString

public java.lang.String toString(boolean timesAsDoubles)
Creates a string representation of all the intervals with their values.

Parameters:
timesAsDoubles - indicates if times should be shown as doubles or dates
Returns:
a string representation with times as doubles or dates.

toString

public java.lang.String toString()
Returns a string representation of this interval tree in a format <[low, high, value], ..., [low, high, value]>. Nodes are visited in inorder.

Times are always shown as doubles.

Overrides:
toString in class java.lang.Object
Returns:
a string representation of this interval tree.

Gephi Toolkit Javadoc