|
Algorithm Development Kit 1.0 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjava.util.AbstractCollection<E>
java.util.AbstractSet<IInterval>
algs.model.interval.SegmentTree<T>
T
- Type of the nodes for the tree. T must extend SegmentTreeNode
.public class SegmentTree<T extends SegmentTreeNode>
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.
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 |
---|
public SegmentTree(int left, int right)
Note that the tree represents the semi-closed range which includes value 'left', but does not include value 'right'.
left
- Left-most value allowed for a line segmentright
- Right-most value allowed for a line segment
java.lang.IllegalArgumentException
- if [left, right) is an invalid interval.public SegmentTree(int left, int right, IConstructor constructor)
left
- Left-most value allowed for a line segmentright
- Right-most value allowed for a line segmentconstructor
- Constructor to use when constructing nodes for this tree.
java.lang.IllegalArgumentException
- if [left, right) is an invalid interval.Method Detail |
---|
public IConstructor getConstructor()
public T getRoot()
public int size()
size
in interface java.util.Collection<IInterval>
size
in interface java.util.Set<IInterval>
size
in class java.util.AbstractCollection<IInterval>
public java.lang.String toString()
toString
in class java.util.AbstractCollection<IInterval>
public void checkInterval(IInterval interval)
interval
- proposed IInterval object to be validated.
java.lang.IllegalArgumentException
- if (interval.getLeft() >= interval.getRight())public boolean add(IInterval e)
add
in interface java.util.Collection<IInterval>
add
in interface java.util.Set<IInterval>
add
in class java.util.AbstractCollection<IInterval>
e
- Interval to add.
java.lang.IllegalArgumentException
- if interval is invalid.public boolean remove(java.lang.Object o)
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.
remove
in interface java.util.Collection<IInterval>
remove
in interface java.util.Set<IInterval>
remove
in class java.util.AbstractCollection<IInterval>
public java.util.Iterator<IInterval> iterator()
iterator
in interface java.lang.Iterable<IInterval>
iterator
in interface java.util.Collection<IInterval>
iterator
in interface java.util.Set<IInterval>
iterator
in class java.util.AbstractCollection<IInterval>
public boolean contains(java.lang.Object o)
contains
in interface java.util.Collection<IInterval>
contains
in interface java.util.Set<IInterval>
contains
in class java.util.AbstractCollection<IInterval>
java.lang.ClassCastException
- if o does not implement the IInterval interfaceAbstractCollection.contains(Object)
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |