net.cscott.jutil
public class IntervalTree extends RedBlackTree
IntervalTree is a mutable collection
of Intervals. IntervalTrees support
efficient lookup of overlapping elements.
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) |
IntervalTree.Interval i and adds
i to this.
Convenience method.
Requires: high > low.
datum can be null.Iterator over Intervals that
yields every interval in this that overlaps i.Interval.Interval in 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"