Algorithm
Development Kit 1.0

algs.model.interval
Class SegmentTree<T extends SegmentTreeNode>

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by java.util.AbstractSet<IInterval>
          extended by algs.model.interval.SegmentTree<T>
Type Parameters:
T - Type of the nodes for the tree. T must extend SegmentTreeNode.
All Implemented Interfaces:
java.lang.Iterable<IInterval>, java.util.Collection<IInterval>, java.util.Set<IInterval>

public class SegmentTree<T extends SegmentTreeNode>
extends java.util.AbstractSet<IInterval>
implements java.util.Set<IInterval>

Given a fixed set of [1..N] values, the segment tree is a rooted binary tree that manages intervals [begin,end] on a line, where left <= begin < end < right.

The initial tree is constructed from an initial domain [left,right) which completely defines the domain from which all segments are drawn.

In this base implementation, the SegmentTreeNode only maintains a count with each node. The class is extensible by subclasses of SegmentTreeNode.

Note that the remove operation is not capable of removing "parts" of segments from the SegmentTree. That is, if the Tree only contains the segment [2,10) and a request is made to remove segment [4,8), you will not get a tree with segments [2,4) and [8, 10).

Note that the constructor to be used is drawn right from the parameterized class, since T extends SegmentTreeNode. If an extended type is used, it MUST provide its own constructor.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Constructor Summary
SegmentTree(int left, int right)
          Construct the rooted tree to manage segments drawn from the [left, right) domain.
SegmentTree(int left, int right, IConstructor constructor)
          Construct the rooted tree to manage segments drawn from the [left, right) domain.
 
Method Summary
 boolean add(IInterval e)
          Add the given interval to the tree.
 void checkInterval(IInterval interval)
          Used to validate IInterval before being incorporated into this data structure.
 boolean contains(java.lang.Object o)
          This method must be rewritten because it is used to determine if the given IInterval is stored within the Segment tree.
 IConstructor getConstructor()
          For those SegmentTrees that demand different class of nodes as the base element of the Tree, this method tells us the constructor being used.
 T getRoot()
          Return the root of the tree.
 java.util.Iterator<IInterval> iterator()
          Use in-order traversal over the tree.
 boolean remove(java.lang.Object o)
          Removes a single instance of the specified element from this collection, if it is present (optional operation).
 int size()
          Returns the count of elements in the tree.
 java.lang.String toString()
          Create string representation of the Tree.
 
Methods inherited from class java.util.AbstractSet
equals, hashCode, removeAll
 
Methods inherited from class java.util.AbstractCollection
addAll, clear, containsAll, isEmpty, retainAll, toArray, toArray
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Set
addAll, clear, containsAll, equals, hashCode, isEmpty, removeAll, retainAll, toArray, toArray
 

Constructor Detail

SegmentTree

public SegmentTree(int left,
                   int right)
Construct the rooted tree to manage segments drawn from the [left, right) domain.

Note that the tree represents the semi-closed range which includes value 'left', but does not include value 'right'.

Parameters:
left - Left-most value allowed for a line segment
right - Right-most value allowed for a line segment
Throws:
java.lang.IllegalArgumentException - if [left, right) is an invalid interval.

SegmentTree

public SegmentTree(int left,
                   int right,
                   IConstructor constructor)
Construct the rooted tree to manage segments drawn from the [left, right) domain. Note that the tree represents the semi-closed range which includes value 'left', but does not include value 'right'.

Parameters:
left - Left-most value allowed for a line segment
right - Right-most value allowed for a line segment
constructor - Constructor to use when constructing nodes for this tree.
Throws:
java.lang.IllegalArgumentException - if [left, right) is an invalid interval.
Method Detail

getConstructor

public IConstructor getConstructor()
For those SegmentTrees that demand different class of nodes as the base element of the Tree, this method tells us the constructor being used.


getRoot

public T getRoot()
Return the root of the tree.


size

public int size()
Returns the count of elements in the tree.

Specified by:
size in interface java.util.Collection<IInterval>
Specified by:
size in interface java.util.Set<IInterval>
Specified by:
size in class java.util.AbstractCollection<IInterval>

toString

public java.lang.String toString()
Create string representation of the Tree.

Overrides:
toString in class java.util.AbstractCollection<IInterval>

checkInterval

public void checkInterval(IInterval interval)
Used to validate IInterval before being incorporated into this data structure. Note that IInterval may contain invalid (or potentially malicious) methods that do not satisfy their specifications. At this time, it is not possible to validate the entire behavior of IInterval. This method is only focused on the structure of the [left, right) range.

Parameters:
interval - proposed IInterval object to be validated.
Throws:
java.lang.IllegalArgumentException - if (interval.getLeft() >= interval.getRight())

add

public boolean add(IInterval e)
Add the given interval to the tree.

Specified by:
add in interface java.util.Collection<IInterval>
Specified by:
add in interface java.util.Set<IInterval>
Overrides:
add in class java.util.AbstractCollection<IInterval>
Parameters:
e - Interval to add.
Returns:
true on successful addition, false otherwise.
Throws:
java.lang.IllegalArgumentException - if interval is invalid.

remove

public boolean remove(java.lang.Object o)
Removes a single instance of the specified element from this collection, if it is present (optional operation). More formally, removes an element e such that (o==null ? e==null : o.equals(e)), if the collection contains one or more such elements. Returns true if the collection contained the specified element (or equivalently, if the collection changed as a result of the call).

We override this method to improve the efficiency of the implementation. You can remove it to witness the extra performance costs from using the iterator (which for a binary tree is inorder traversal) to remove individual intervals from the tree. Note the object is not checked for whether it is a valid IInterval.

Specified by:
remove in interface java.util.Collection<IInterval>
Specified by:
remove in interface java.util.Set<IInterval>
Overrides:
remove in class java.util.AbstractCollection<IInterval>

iterator

public java.util.Iterator<IInterval> iterator()
Use in-order traversal over the tree.

Specified by:
iterator in interface java.lang.Iterable<IInterval>
Specified by:
iterator in interface java.util.Collection<IInterval>
Specified by:
iterator in interface java.util.Set<IInterval>
Specified by:
iterator in class java.util.AbstractCollection<IInterval>

contains

public boolean contains(java.lang.Object o)
This method must be rewritten because it is used to determine if the given IInterval is stored within the Segment tree. Note that if we didn't overwrite this method, the comparison would be against the internal nodes of the segment tree, not the value(s) being contained by those nodes. Subclasses can override this 'contains' to actually peek into the extra information that is going to be stored by the appropriate nodes. Note the object is not checked for whether it is a valid IInterval.

Specified by:
contains in interface java.util.Collection<IInterval>
Specified by:
contains in interface java.util.Set<IInterval>
Overrides:
contains in class java.util.AbstractCollection<IInterval>
Throws:
java.lang.ClassCastException - if o does not implement the IInterval interface
See Also:
AbstractCollection.contains(Object)

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.