net.cscott.jutil
Class IntervalTree

java.lang.Object
  net.cscott.jutil.BinaryTree
      net.cscott.jutil.RedBlackTree
          net.cscott.jutil.IntervalTree

public class IntervalTree
extends RedBlackTree

An IntervalTree is a mutable collection of IntervalTree.Intervals. IntervalTrees support efficient lookup of overlapping elements.

Every element in an IntervalTree must be an IntervalTree.Interval. Thus element lookup is done based upon IntervalTree.Intervals, not on the datum assocatied with each IntervalTree.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:

addInterval(java.lang.Object, int, int), "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.

Nested classes/interfaces inherited from class net.cscott.jutil.RedBlackTree

RedBlackTree.RBNode

Nested classes/interfaces inherited from class net.cscott.jutil.BinaryTree

BinaryTree.Node

Field Summary

Fields inherited from class net.cscott.jutil.BinaryTree

comp, NIL

Constructor Summary

IntervalTree()
Constructs a new empty IntervalTree.

Method Summary

IntervalTree.Interval	addInterval(Object datum, int low, int high) Constructs a new IntervalTree.Interval i and adds i to this.
Iterator	allOverlapping(IntervalTree.Interval i) Returns an Iterator over IntervalTree.Intervals that yields every interval in this that overlaps i.
static void	main(String[] args)
protected BinaryTree.Node	makeNode(Object o) requires: o is-a IntervalTree.Interval.
IntervalTree.Interval	searchOverlapping(IntervalTree.Interval i) Returns some IntervalTree.Interval in this which overlaps the bounds defined by the argument interval i, or null if no such interval exists.
protected BinaryTree.Node	setLeft(BinaryTree.Node p, BinaryTree.Node l) Sets the left child of p.
protected BinaryTree.Node	setParent(BinaryTree.Node c, BinaryTree.Node p) Sets the parent of p.
protected BinaryTree.Node	setRight(BinaryTree.Node p, BinaryTree.Node r) Sets the right child of p.

Methods inherited from class net.cscott.jutil.RedBlackTree

deleteNode, insertNode, leftRotate, rbDeleteFixup, rightRotate, swapPositions

Methods inherited from class net.cscott.jutil.BinaryTree

add, contains, dump, dump, maximum, maximum, minimum, minimum, remove, root, search, setRoot, successor, test

Methods inherited from class java.lang.Object

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

Constructor Detail

IntervalTree

public IntervalTree()

Constructs a new empty IntervalTree.

Method Detail

makeNode

protected BinaryTree.Node makeNode(Object o)

requires: o is-a IntervalTree.Interval.

Overrides:

makeNode in class RedBlackTree

setLeft

protected BinaryTree.Node setLeft(BinaryTree.Node p,
                                  BinaryTree.Node l)

Description copied from class: BinaryTree

Sets the left child of p. Modifies: this, p, l Effects: p.left_post = l. Returns: p.left_pre.

Overrides:

setLeft in class BinaryTree

setRight

protected BinaryTree.Node setRight(BinaryTree.Node p,
                                   BinaryTree.Node r)

Description copied from class: BinaryTree

Sets the right child of p. Modifies: this, p, r Effects: p.right_post = r. Returns: p.right_pre.

Overrides:

setRight in class BinaryTree

setParent

protected BinaryTree.Node setParent(BinaryTree.Node c,
                                    BinaryTree.Node p)

Description copied from class: BinaryTree

Sets the parent of p. Modifies: this, c, p Effects: c.parent_post = p. Returns: c.parent_pre.

Overrides:

setParent in class BinaryTree

searchOverlapping

public IntervalTree.Interval searchOverlapping(IntervalTree.Interval i)

Returns some IntervalTree.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"

allOverlapping

public Iterator allOverlapping(IntervalTree.Interval i)

Returns an Iterator over IntervalTree.Intervals that yields every interval in this that overlaps i.

addInterval

public IntervalTree.Interval addInterval(Object datum,
                                         int low,
                                         int high)

Constructs a new IntervalTree.Interval i and adds i to this. Convenience method. Requires: high > low. datum can be null.

main

public static void main(String[] args)