public class IntervalTree<E extends java.lang.Comparable<E>,T extends HasInterval<E>>
extends java.util.AbstractCollection<T>
Modifier and Type | Class and Description |
---|---|
static class |
IntervalTree.TreeNode<E extends java.lang.Comparable<E>,T extends HasInterval<E>> |
Constructor and Description |
---|
IntervalTree() |
Modifier and Type | Method and Description |
---|---|
boolean |
add(IntervalTree.TreeNode<E,T> node,
T target) |
boolean |
add(IntervalTree.TreeNode<E,T> node,
T target,
double alpha) |
boolean |
add(T target) |
boolean |
addNonNested(T target) |
boolean |
addNonOverlapping(T target) |
void |
balance() |
IntervalTree.TreeNode<E,T> |
balance(IntervalTree.TreeNode<E,T> node) |
void |
check() |
void |
check(IntervalTree.TreeNode<E,T> treeNode) |
void |
clear() |
boolean |
contains(java.lang.Object o) |
boolean |
contains(T target) |
static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> |
containsInterval(IntervalTree<E,T> n,
E p,
boolean exact) |
static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> |
containsInterval(IntervalTree<E,T> node,
Interval<E> target,
boolean exact) |
boolean |
containsInterval(T target,
boolean exact) |
static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> |
containsValue(IntervalTree<E,T> node,
T target) |
IntervalTree.TreeNode<E,T> |
getLeftmostNode(IntervalTree.TreeNode<E,T> node) |
IntervalTree.TreeNode<E,T> |
getNode(IntervalTree.TreeNode<E,T> node,
int nodeIndex) |
static <T,E extends java.lang.Comparable<E>> |
getNonNested(java.util.List<? extends T> items,
java.util.function.Function<? super T,Interval<E>> toIntervalFunc,
java.util.Comparator<? super T> compareFunc) |
static <T extends HasInterval<E>,E extends java.lang.Comparable<E>> |
getNonOverlapping(java.util.List<? extends T> items) |
static <T extends HasInterval<E>,E extends java.lang.Comparable<E>> |
getNonOverlapping(java.util.List<? extends T> items,
java.util.Comparator<? super T> compareFunc) |
static <T,E extends java.lang.Comparable<E>> |
getNonOverlapping(java.util.List<? extends T> items,
java.util.function.Function<? super T,Interval<E>> toIntervalFunc) |
static <T,E extends java.lang.Comparable<E>> |
getNonOverlapping(java.util.List<? extends T> items,
java.util.function.Function<? super T,Interval<E>> toIntervalFunc,
java.util.Comparator<? super T> compareFunc) |
static <T,E extends java.lang.Comparable<E>> |
getNonOverlappingMaxScore(java.util.List<? extends T> items,
java.util.function.Function<? super T,Interval<E>> toIntervalFunc,
java.util.function.ToDoubleFunction<? super T> scoreFunc) |
static <T extends HasInterval<E>,E extends java.lang.Comparable<E>> |
getNonOverlappingMaxScore(java.util.List<? extends T> items,
java.util.function.ToDoubleFunction<? super T> scoreFunc) |
static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> |
getOverlapping(IntervalTree.TreeNode<E,T> n,
E p) |
static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> |
getOverlapping(IntervalTree.TreeNode<E,T> n,
E p,
java.util.List<T> result) |
static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> |
getOverlapping(IntervalTree.TreeNode<E,T> n,
Interval<E> target) |
static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> |
getOverlapping(IntervalTree.TreeNode<E,T> node,
Interval<E> target,
java.util.List<T> result) |
java.util.List<T> |
getOverlapping(T target) |
IntervalTree.TreeNode<E,T> |
getRightmostNode(IntervalTree.TreeNode<E,T> node) |
int |
height() |
int |
height(IntervalTree.TreeNode<E,T> node) |
boolean |
isAlphaBalanced(IntervalTree.TreeNode<E,T> node,
double alpha) |
boolean |
isEmpty() |
java.util.Iterator<T> |
iterator() |
IntervalTree.TreeNode<E,T> |
leftRotate(IntervalTree.TreeNode<E,T> oldRoot) |
static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> |
overlaps(IntervalTree.TreeNode<E,T> n,
E p) |
static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> |
overlaps(IntervalTree.TreeNode<E,T> node,
Interval<E> target) |
boolean |
overlaps(T target) |
boolean |
remove(IntervalTree.TreeNode<E,T> node,
T target) |
boolean |
remove(java.lang.Object o) |
boolean |
remove(T target) |
boolean |
removeAll(java.util.Collection<?> c) |
boolean |
retainAll(java.util.Collection<?> c) |
IntervalTree.TreeNode<E,T> |
rightRotate(IntervalTree.TreeNode<E,T> oldRoot) |
void |
rotateUp(IntervalTree.TreeNode<E,T> node,
IntervalTree.TreeNode<E,T> target) |
int |
size() |
java.lang.String |
toString() |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
public boolean isEmpty()
isEmpty
in interface java.util.Collection<T extends HasInterval<E>>
isEmpty
in class java.util.AbstractCollection<T extends HasInterval<E>>
public void clear()
clear
in interface java.util.Collection<T extends HasInterval<E>>
clear
in class java.util.AbstractCollection<T extends HasInterval<E>>
public java.lang.String toString()
toString
in class java.util.AbstractCollection<T extends HasInterval<E>>
public boolean add(T target)
add
in interface java.util.Collection<T extends HasInterval<E>>
add
in class java.util.AbstractCollection<T extends HasInterval<E>>
public boolean add(IntervalTree.TreeNode<E,T> node, T target)
public boolean add(IntervalTree.TreeNode<E,T> node, T target, double alpha)
public int size()
size
in interface java.util.Collection<T extends HasInterval<E>>
size
in class java.util.AbstractCollection<T extends HasInterval<E>>
public java.util.Iterator<T> iterator()
iterator
in interface java.lang.Iterable<T extends HasInterval<E>>
iterator
in interface java.util.Collection<T extends HasInterval<E>>
iterator
in class java.util.AbstractCollection<T extends HasInterval<E>>
public boolean removeAll(java.util.Collection<?> c)
removeAll
in interface java.util.Collection<T extends HasInterval<E>>
removeAll
in class java.util.AbstractCollection<T extends HasInterval<E>>
public boolean retainAll(java.util.Collection<?> c)
retainAll
in interface java.util.Collection<T extends HasInterval<E>>
retainAll
in class java.util.AbstractCollection<T extends HasInterval<E>>
public boolean contains(java.lang.Object o)
contains
in interface java.util.Collection<T extends HasInterval<E>>
contains
in class java.util.AbstractCollection<T extends HasInterval<E>>
public boolean remove(java.lang.Object o)
remove
in interface java.util.Collection<T extends HasInterval<E>>
remove
in class java.util.AbstractCollection<T extends HasInterval<E>>
public boolean remove(T target)
public boolean remove(IntervalTree.TreeNode<E,T> node, T target)
public void check()
public void check(IntervalTree.TreeNode<E,T> treeNode)
public boolean isAlphaBalanced(IntervalTree.TreeNode<E,T> node, double alpha)
public void balance()
public IntervalTree.TreeNode<E,T> balance(IntervalTree.TreeNode<E,T> node)
public void rotateUp(IntervalTree.TreeNode<E,T> node, IntervalTree.TreeNode<E,T> target)
public IntervalTree.TreeNode<E,T> rightRotate(IntervalTree.TreeNode<E,T> oldRoot)
public IntervalTree.TreeNode<E,T> leftRotate(IntervalTree.TreeNode<E,T> oldRoot)
public int height()
public int height(IntervalTree.TreeNode<E,T> node)
public IntervalTree.TreeNode<E,T> getLeftmostNode(IntervalTree.TreeNode<E,T> node)
public IntervalTree.TreeNode<E,T> getRightmostNode(IntervalTree.TreeNode<E,T> node)
public IntervalTree.TreeNode<E,T> getNode(IntervalTree.TreeNode<E,T> node, int nodeIndex)
public boolean addNonOverlapping(T target)
public boolean addNonNested(T target)
public boolean overlaps(T target)
public static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> java.util.List<T> getOverlapping(IntervalTree.TreeNode<E,T> n, E p)
public static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> java.util.List<T> getOverlapping(IntervalTree.TreeNode<E,T> n, Interval<E> target)
public static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> void getOverlapping(IntervalTree.TreeNode<E,T> n, E p, java.util.List<T> result)
public static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> void getOverlapping(IntervalTree.TreeNode<E,T> node, Interval<E> target, java.util.List<T> result)
public static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> boolean overlaps(IntervalTree.TreeNode<E,T> n, E p)
public static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> boolean overlaps(IntervalTree.TreeNode<E,T> node, Interval<E> target)
public boolean contains(T target)
public boolean containsInterval(T target, boolean exact)
public static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> boolean containsInterval(IntervalTree<E,T> n, E p, boolean exact)
public static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> boolean containsInterval(IntervalTree<E,T> node, Interval<E> target, boolean exact)
public static <E extends java.lang.Comparable<E>,T extends HasInterval<E>> boolean containsValue(IntervalTree<E,T> node, T target)
public static <T,E extends java.lang.Comparable<E>> java.util.List<T> getNonOverlapping(java.util.List<? extends T> items, java.util.function.Function<? super T,Interval<E>> toIntervalFunc)
public static <T,E extends java.lang.Comparable<E>> java.util.List<T> getNonOverlapping(java.util.List<? extends T> items, java.util.function.Function<? super T,Interval<E>> toIntervalFunc, java.util.Comparator<? super T> compareFunc)
public static <T extends HasInterval<E>,E extends java.lang.Comparable<E>> java.util.List<T> getNonOverlapping(java.util.List<? extends T> items, java.util.Comparator<? super T> compareFunc)
public static <T extends HasInterval<E>,E extends java.lang.Comparable<E>> java.util.List<T> getNonOverlapping(java.util.List<? extends T> items)
public static <T,E extends java.lang.Comparable<E>> java.util.List<T> getNonOverlappingMaxScore(java.util.List<? extends T> items, java.util.function.Function<? super T,Interval<E>> toIntervalFunc, java.util.function.ToDoubleFunction<? super T> scoreFunc)
public static <T extends HasInterval<E>,E extends java.lang.Comparable<E>> java.util.List<T> getNonOverlappingMaxScore(java.util.List<? extends T> items, java.util.function.ToDoubleFunction<? super T> scoreFunc)
public static <T,E extends java.lang.Comparable<E>> java.util.List<T> getNonNested(java.util.List<? extends T> items, java.util.function.Function<? super T,Interval<E>> toIntervalFunc, java.util.Comparator<? super T> compareFunc)