edu.usc.bg.validator
Class IntervalTree<Type>

java.lang.Object
  extended by edu.usc.bg.validator.IntervalTree<Type>
Type Parameters:
Type - The type of objects to associate.

public class IntervalTree<Type>
extends java.lang.Object

An Interval Tree is essentially a map from intervals to objects, which can be queried for all data associated with a particular interval of time.

Author:
Kevin Dolan

Constructor Summary
IntervalTree()
          Instantiate a new interval tree with no intervals.
IntervalTree(java.util.List<Interval<Type>> intervalList)
          Instantiate and build an interval tree with a preset list of intervals.
 
Method Summary
 void addInterval(Interval<Type> interval)
          Add an interval object to the interval tree's list.
 void addInterval(long begin, long end, Type data)
          Add an interval object to the interval tree's list.
 void build()
          Build the interval tree to reflect the list of intervals.
 int currentSize()
           
 java.util.List<Type> get(long time)
          Perform a stabbing query, returning the associated data.
 java.util.List<Type> get(long start, long end)
          Perform an interval query, returning the associated data.
 java.util.List<Interval<Type>> getIntervals(long time)
          Perform a stabbing query, returning the interval objects.
 java.util.List<Interval<Type>> getIntervals(long start, long end)
          Perform an interval query, returning the interval objects.
 boolean inSync()
          Determine whether this interval tree is currently a reflection of all intervals in the interval list.
 int listSize()
           
 java.lang.String toString()
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

IntervalTree

public IntervalTree()
Instantiate a new interval tree with no intervals.


IntervalTree

public IntervalTree(java.util.List<Interval<Type>> intervalList)
Instantiate and build an interval tree with a preset list of intervals.

Parameters:
intervalList - The list of intervals to use.
Method Detail

get

public java.util.List<Type> get(long time)
Perform a stabbing query, returning the associated data. Will rebuild the tree if out of sync.

Parameters:
time - The time to stab.
Returns:
the data associated with all intervals that contain time.

getIntervals

public java.util.List<Interval<Type>> getIntervals(long time)
Perform a stabbing query, returning the interval objects. Will rebuild the tree if out of sync.

Parameters:
time - the time to stab.
Returns:
all intervals that contain time.

get

public java.util.List<Type> get(long start,
                                long end)
Perform an interval query, returning the associated data. Will rebuild the tree if out of sync.

Parameters:
start - The start of the interval to check.
end - The end of the interval to check.
Returns:
The data associated with all intervals that intersect target.

getIntervals

public java.util.List<Interval<Type>> getIntervals(long start,
                                                   long end)
Perform an interval query, returning the interval objects. Will rebuild The tree if out of sync.

Parameters:
start - The start of the interval to check.
end - The end of the interval to check.
Returns:
All intervals that intersect target.

addInterval

public void addInterval(Interval<Type> interval)
Add an interval object to the interval tree's list. Will not rebuild the tree until the next query or call to build.

Parameters:
interval - The interval object to add.

addInterval

public void addInterval(long begin,
                        long end,
                        Type data)
Add an interval object to the interval tree's list. Will not rebuild the tree until the next query or call to build.

Parameters:
begin - The beginning of the interval.
end - The end of the interval.
data - The data to associate.

inSync

public boolean inSync()
Determine whether this interval tree is currently a reflection of all intervals in the interval list.

Returns:
true if no changes have been made since the last build.

build

public void build()
Build the interval tree to reflect the list of intervals. Will not run if this is currently in sync.


currentSize

public int currentSize()
Returns:
the number of entries in the currently built interval tree.

listSize

public int listSize()
Returns:
the number of entries in the interval list, equal to .size() if inSync().

toString

public java.lang.String toString()
Overrides:
toString in class java.lang.Object