net.cscott.jutil
public class IntervalTree extends RedBlackTree
Every element in an IntervalTree must be an Interval. Thus element lookup is done based upon Intervals, not on the datum assocatied with each Interval.
The intervals maintained by this structure are considered to be closed intervals.
To make use of an IntervalTree cleaner, a
convenience method, addInterval
is provided.
See Also: IntervalTree "CLR section 15.3, (page 290)."
Nested Class Summary | |
---|---|
static class | IntervalTree.Interval Immutable record representing a closed interval
[ low ,high ] holding an object
obj . |
Constructor Summary | |
---|---|
IntervalTree() Constructs a new empty IntervalTree. |
Method Summary | |
---|---|
IntervalTree.Interval | addInterval(Object datum, int low, int high) Constructs a new Interval i and adds
i to this .
|
Iterator | allOverlapping(IntervalTree.Interval i) Returns an Iterator over Intervals that
yields every interval in this that overlaps i . |
static void | main(String[] args) |
protected Node | makeNode(Object o) requires: o is-a Interval. |
IntervalTree.Interval | searchOverlapping(IntervalTree.Interval i) Returns some Interval in this which
overlaps the bounds defined by the argument interval
i , or null if no such interval
exists.
|
protected Node | setLeft(Node p, Node l) |
protected Node | setParent(Node c, Node p) |
protected Node | setRight(Node p, Node r) |
this
.
Convenience method.
Requires: high > low.
datum
can be null.i
.this
which
overlaps the bounds defined by the argument interval
i
, or null
if no such interval
exists.
This operation is named "Interval-Search" in CLR
See Also: "CLR, pg 291"