public class IntervalTree<E extends Comparable<E>,T extends HasInterval<E>> extends AbstractCollection<T>
Modifier and Type | Class and Description |
---|---|
static class |
IntervalTree.TreeNode<E extends 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(Object o) |
boolean |
contains(T target) |
static <E extends Comparable<E>,T extends HasInterval<E>> |
containsInterval(IntervalTree<E,T> n,
E p,
boolean exact) |
static <E extends 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 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 Comparable<E>> |
getNonNested(List<? extends T> items,
Function<? super T,Interval<E>> toIntervalFunc,
Comparator<? super T> compareFunc) |
static <T extends HasInterval<E>,E extends Comparable<E>> |
getNonOverlapping(List<? extends T> items) |
static <T extends HasInterval<E>,E extends Comparable<E>> |
getNonOverlapping(List<? extends T> items,
Comparator<? super T> compareFunc) |
static <T,E extends Comparable<E>> |
getNonOverlapping(List<? extends T> items,
Function<? super T,Interval<E>> toIntervalFunc) |
static <T,E extends Comparable<E>> |
getNonOverlapping(List<? extends T> items,
Function<? super T,Interval<E>> toIntervalFunc,
Comparator<? super T> compareFunc) |
static <T,E extends Comparable<E>> |
getNonOverlappingMaxScore(List<? extends T> items,
Function<? super T,Interval<E>> toIntervalFunc,
ToDoubleFunction<? super T> scoreFunc) |
static <T extends HasInterval<E>,E extends Comparable<E>> |
getNonOverlappingMaxScore(List<? extends T> items,
ToDoubleFunction<? super T> scoreFunc) |
static <E extends Comparable<E>,T extends HasInterval<E>> |
getOverlapping(IntervalTree.TreeNode<E,T> n,
E p) |
static <E extends Comparable<E>,T extends HasInterval<E>> |
getOverlapping(IntervalTree.TreeNode<E,T> n,
E p,
List<T> result) |
static <E extends Comparable<E>,T extends HasInterval<E>> |
getOverlapping(IntervalTree.TreeNode<E,T> n,
Interval<E> target) |
static <E extends Comparable<E>,T extends HasInterval<E>> |
getOverlapping(IntervalTree.TreeNode<E,T> node,
Interval<E> target,
List<T> result) |
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() |
Iterator<T> |
iterator() |
IntervalTree.TreeNode<E,T> |
leftRotate(IntervalTree.TreeNode<E,T> oldRoot) |
static <E extends Comparable<E>,T extends HasInterval<E>> |
overlaps(IntervalTree.TreeNode<E,T> n,
E p) |
static <E extends 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(Object o) |
boolean |
remove(T target) |
boolean |
removeAll(Collection<?> c) |
boolean |
retainAll(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() |
String |
toString() |
addAll, containsAll, toArray, toArray
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
equals, hashCode, parallelStream, removeIf, spliterator, stream
public boolean isEmpty()
isEmpty
in interface Collection<T extends HasInterval<E>>
isEmpty
in class AbstractCollection<T extends HasInterval<E>>
public void clear()
clear
in interface Collection<T extends HasInterval<E>>
clear
in class AbstractCollection<T extends HasInterval<E>>
public String toString()
toString
in class AbstractCollection<T extends HasInterval<E>>
public boolean add(T target)
add
in interface Collection<T extends HasInterval<E>>
add
in class 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 Collection<T extends HasInterval<E>>
size
in class AbstractCollection<T extends HasInterval<E>>
public Iterator<T> iterator()
iterator
in interface Iterable<T extends HasInterval<E>>
iterator
in interface Collection<T extends HasInterval<E>>
iterator
in class AbstractCollection<T extends HasInterval<E>>
public boolean removeAll(Collection<?> c)
removeAll
in interface Collection<T extends HasInterval<E>>
removeAll
in class AbstractCollection<T extends HasInterval<E>>
public boolean retainAll(Collection<?> c)
retainAll
in interface Collection<T extends HasInterval<E>>
retainAll
in class AbstractCollection<T extends HasInterval<E>>
public boolean contains(Object o)
contains
in interface Collection<T extends HasInterval<E>>
contains
in class AbstractCollection<T extends HasInterval<E>>
public boolean remove(Object o)
remove
in interface Collection<T extends HasInterval<E>>
remove
in class 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 Comparable<E>,T extends HasInterval<E>> List<T> getOverlapping(IntervalTree.TreeNode<E,T> n, E p)
public static <E extends Comparable<E>,T extends HasInterval<E>> List<T> getOverlapping(IntervalTree.TreeNode<E,T> n, Interval<E> target)
public static <E extends Comparable<E>,T extends HasInterval<E>> void getOverlapping(IntervalTree.TreeNode<E,T> n, E p, List<T> result)
public static <E extends Comparable<E>,T extends HasInterval<E>> void getOverlapping(IntervalTree.TreeNode<E,T> node, Interval<E> target, List<T> result)
public static <E extends Comparable<E>,T extends HasInterval<E>> boolean overlaps(IntervalTree.TreeNode<E,T> n, E p)
public static <E extends 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 Comparable<E>,T extends HasInterval<E>> boolean containsInterval(IntervalTree<E,T> n, E p, boolean exact)
public static <E extends Comparable<E>,T extends HasInterval<E>> boolean containsInterval(IntervalTree<E,T> node, Interval<E> target, boolean exact)
public static <E extends Comparable<E>,T extends HasInterval<E>> boolean containsValue(IntervalTree<E,T> node, T target)
public static <T,E extends Comparable<E>> List<T> getNonOverlapping(List<? extends T> items, Function<? super T,Interval<E>> toIntervalFunc)
public static <T,E extends Comparable<E>> List<T> getNonOverlapping(List<? extends T> items, Function<? super T,Interval<E>> toIntervalFunc, Comparator<? super T> compareFunc)
public static <T extends HasInterval<E>,E extends Comparable<E>> List<T> getNonOverlapping(List<? extends T> items, Comparator<? super T> compareFunc)
public static <T extends HasInterval<E>,E extends Comparable<E>> List<T> getNonOverlapping(List<? extends T> items)
public static <T,E extends Comparable<E>> List<T> getNonOverlappingMaxScore(List<? extends T> items, Function<? super T,Interval<E>> toIntervalFunc, ToDoubleFunction<? super T> scoreFunc)
public static <T extends HasInterval<E>,E extends Comparable<E>> List<T> getNonOverlappingMaxScore(List<? extends T> items, ToDoubleFunction<? super T> scoreFunc)
public static <T,E extends Comparable<E>> List<T> getNonNested(List<? extends T> items, Function<? super T,Interval<E>> toIntervalFunc, Comparator<? super T> compareFunc)