K - the type of interval ends used by this treeV - values to be associated with the intervalspublic class IntervalST<K extends Comparable<K>,V> extends Object implements Iterable<IntervalST.Node<K,V>>
Interval1D as keys. If you want to
store multiple values associated with an interval, just store a List in the tree.
Implementation is an adaptation of IntervalST class (http://algs4.cs.princeton.edu/93intersection/IntervalST.java.html)
provided with Algorithms 4 book by Robert Sedgewick and Kevin Wayne.
Unlike the original, it allows insertion of Intervals which have the same left ends
and is fully generic.| Modifier and Type | Class and Description |
|---|---|
static class |
IntervalST.Node<U extends Comparable<U>,W>
BST helper node data type.
|
| Constructor and Description |
|---|
IntervalST() |
| Modifier and Type | Method and Description |
|---|---|
boolean |
check()
Check integrity of subtree count fields.
|
boolean |
contains(Interval1D<K> interval)
Check if the tree contains this exact interval.
|
IntervalST.Node<K,V> |
get(Interval1D<K> interval)
Get the value associated with the given key (Interval).
|
int |
height() |
Iterator<IntervalST.Node<K,V>> |
iterator() |
static void |
main(String[] args)
test client
|
void |
prettyPrint()
Print out the current tree from left to right.
|
void |
put(Interval1D<K> interval,
V value)
Insert a new node in the tree.
|
IntervalST.Node<K,V> |
remove(Interval1D<K> interval)
Remove and return value associated with given interval.
|
Interval1D<K> |
search(Interval1D<K> interval)
Return an interval in data structure that intersects the given interval;
Return null if no such interval exists.
|
List<IntervalST.Node<K,V>> |
searchAll(Interval1D<K> interval)
Return ALL intervals in data structure that intersect the given interval.
|
int |
size()
Return number of nodes in tree.
|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitforEach, spliteratorpublic void prettyPrint()
public Iterator<IntervalST.Node<K,V>> iterator()
iterator in interface Iterable<IntervalST.Node<K extends Comparable<K>,V>>public boolean contains(Interval1D<K> interval)
get(Interval1D) and compare it's return value to null.
This way you won't need to query the tree twice.interval - public IntervalST.Node<K,V> get(Interval1D<K> interval)
interval - public void put(Interval1D<K> interval, V value)
interval - value - public IntervalST.Node<K,V> remove(Interval1D<K> interval)
interval - public Interval1D<K> search(Interval1D<K> interval)
interval - public List<IntervalST.Node<K,V>> searchAll(Interval1D<K> interval)
interval - the interval to search forpublic int size()
public int height()
public boolean check()
public static void main(String[] args)
Copyright © 2017. All rights reserved.