Package net.cscott.jutil

Class IntervalTree

java.lang.Object

net.cscott.jutil.BinaryTree<IntervalTree.Interval>

net.cscott.jutil.RedBlackTree<IntervalTree.Interval>

net.cscott.jutil.IntervalTree

public class IntervalTree
extends RedBlackTree<IntervalTree.Interval>

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

Nested Classes

Modifier and Type	Class	Description
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

Constructors

Constructor	Description
IntervalTree()	Constructs a new empty IntervalTree.

Method Summary

Modifier and Type	Method	Description
IntervalTree.Interval	addInterval(Object datum, int low, int high)	Constructs a new IntervalTree.Interval i and adds i to this.
Iterator<IntervalTree.Interval>	allOverlapping(IntervalTree.Interval i)	Returns an Iterator over IntervalTree.Intervals that yields every interval in this that overlaps i.
protected void	deleteNode(BinaryTree<IntervalTree.Interval>.Node z)	Splices z out from this.
protected void	insertNode(BinaryTree<IntervalTree.Interval>.Node z)	Inserts z into some appropriate position in this.
protected BinaryTree<IntervalTree.Interval>.Node	makeNode(IntervalTree.Interval i)	Factory method for BinaryTree<K>.Node.
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<IntervalTree.Interval>.Node	setLeft(BinaryTree<IntervalTree.Interval>.Node p, BinaryTree<IntervalTree.Interval>.Node l)	Sets the left child of p.
protected BinaryTree<IntervalTree.Interval>.Node	setParent(BinaryTree<IntervalTree.Interval>.Node c, BinaryTree<IntervalTree.Interval>.Node p)	Sets the parent of p.
protected BinaryTree<IntervalTree.Interval>.Node	setRight(BinaryTree<IntervalTree.Interval>.Node p, BinaryTree<IntervalTree.Interval>.Node r)	Sets the right child of p.

Methods inherited from class net.cscott.jutil.RedBlackTree

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

Methods inherited from class java.lang.Object

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

Constructor Details

IntervalTree

public IntervalTree()

Constructs a new empty IntervalTree.

Method Details

makeNode

protected BinaryTree<IntervalTree.Interval>.Node makeNode(IntervalTree.Interval i)

Description copied from class: RedBlackTree

Factory method for BinaryTree<K>.Node. Every construction of a BinaryTree<K>.Node takes place through this method; thus subclasses of RedBlackTree can associate new data with their own nodes by extending the BinaryTree<K>.Node class and overriding this method.

Overrides:

makeNode in class RedBlackTree<IntervalTree.Interval>

setLeft

protected BinaryTree<IntervalTree.Interval>.Node setLeft(BinaryTree<IntervalTree.Interval>.Node p,
 BinaryTree<IntervalTree.Interval>.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<IntervalTree.Interval>

setRight

protected BinaryTree<IntervalTree.Interval>.Node setRight(BinaryTree<IntervalTree.Interval>.Node p,
 BinaryTree<IntervalTree.Interval>.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<IntervalTree.Interval>

setParent

protected BinaryTree<IntervalTree.Interval>.Node setParent(BinaryTree<IntervalTree.Interval>.Node c,
 BinaryTree<IntervalTree.Interval>.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<IntervalTree.Interval>

insertNode

protected void insertNode(BinaryTree<IntervalTree.Interval>.Node z)

Description copied from class: BinaryTree

Inserts z into some appropriate position in this. requires: (z.left == z.right == NIL) modifies: this, z From CLR, pg 251.

Overrides:

insertNode in class RedBlackTree<IntervalTree.Interval>

deleteNode

protected void deleteNode(BinaryTree<IntervalTree.Interval>.Node z)

Description copied from class: BinaryTree

Splices z out from this. Based on CLR, pg 253. modifies: this, z

Overrides:

deleteNode in class RedBlackTree<IntervalTree.Interval>

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<IntervalTree.Interval> 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.