T - The type for the start and end point of the intervalpublic class IntervalTree<T extends Comparable<? super T>> extends AbstractSet<Interval<T>>
The tree functions as a set, meaning that it will not store an interval more than
once. More formally, for any two distinct intervals x and y within the tree, it is
guaranteed that x.equals(y) will evaluate to false. If you try to add an interval to the tree,
which is already in it, the tree will reject it. See the documentation of
the add method for more information. The tree will also not accept
null or empty intervals, meaning intervals whose Interval.isEmpty()
method evaluates to true.
The iterator() method of the tree returns a fail-fast iterator, which will
throw a ConcurrentModificationException, if the tree is modified in any form
during the iteration, other than by using the iterator's own remove method. However,
this is done in a best-effort manner, since it is generally hard to guarantee this behaviour
while using non-atomic and not synchronized methods.
The tree relies on the usage of a subclass of the Interval class to represent the
intervals. The majority of the interval methods are already implemented within the
Interval class and don't have to be implemented by the extending class. Comparisons
between the intervals are also pre-implemented in the Interval class and use the
start and endpoints to create a total order of all stored intervals. However, if the tree
needs to store intervals that have the same start and end points but represent different
logical entities, you need a subclass that overwrites the equals, hashCode
and compareTo methods. See the documentation of Interval for more information.
| Constructor and Description |
|---|
IntervalTree() |
| Modifier and Type | Method and Description |
|---|---|
boolean |
add(Interval<T> interval)
Adds an interval to the tree.
|
void |
clear()
Removes all intervals from the tree.
|
boolean |
contains(Object o)
Checks if a given object is stored in the tree.
|
Iterator<Interval<T>> |
iterator() |
Set<Interval<T>> |
query(Interval<T> interval)
Searches for and returns all intervals stored in the tree, that intersect a given
query interval.
|
Set<Interval<T>> |
query(T point)
Searches for and returns all intervals stored in the tree, that contain a given
query point.
|
boolean |
remove(Interval<T> interval)
Removes an interval from the tree, if it was stored in it.
|
int |
size()
Returns the size of the tree.
|
equals, hashCode, removeAlladdAll, containsAll, isEmpty, remove, retainAll, toArray, toArray, toStringclone, finalize, getClass, notify, notifyAll, wait, wait, waitaddAll, containsAll, isEmpty, remove, retainAll, spliterator, toArray, toArrayparallelStream, removeIf, streampublic boolean add(Interval<T> interval)
assimilated.
This is why this operation may run in O(n) worst-case time, even though
on average it should run in O(logn) due to the nature binary trees.add in interface Collection<Interval<T extends Comparable<? super T>>>add in interface Set<Interval<T extends Comparable<? super T>>>add in class AbstractCollection<Interval<T extends Comparable<? super T>>>interval - The interval to be added to the tree.true, if the tree has been modified as a result of the operation,
or false otherwise.public Set<Interval<T>> query(T point)
O(logn + k), where
n is the size of the tree and k is the size of the returned set,
provided that the time complexity of iterating over the intervals stored in each
visited node is amortized O(1). This assumption is met for the current
implementation of TreeNode, where TreeSets are used.point - The query point.public Set<Interval<T>> query(Interval<T> interval)
O(logn + k), where
n is the size of the tree and k is the size of the returned set,
provided that the time complexity of iterating over the intervals stored in each
visited node is amortized O(1). This assumption is met for the current
implementation of TreeNode, where TreeSets are used.interval - The query interval.public boolean remove(Interval<T> interval)
deletion of a node, which in turn may cause
rebalancing of the tree and the assimilation
of intervals from one node to another. This is why this operation may run in O(n)
worst-case time, even though on average it should run in O(logn) due to the
nature binary trees.interval - public Iterator<Interval<T>> iterator()
iterator in interface Iterable<Interval<T extends Comparable<? super T>>>iterator in interface Collection<Interval<T extends Comparable<? super T>>>iterator in interface Set<Interval<T extends Comparable<? super T>>>iterator in class AbstractCollection<Interval<T extends Comparable<? super T>>>public int size()
size in interface Collection<Interval<T extends Comparable<? super T>>>size in interface Set<Interval<T extends Comparable<? super T>>>size in class AbstractCollection<Interval<T extends Comparable<? super T>>>public void clear()
O(1) worst-case
time operation.clear in interface Collection<Interval<T extends Comparable<? super T>>>clear in interface Set<Interval<T extends Comparable<? super T>>>clear in class AbstractCollection<Interval<T extends Comparable<? super T>>>public boolean contains(Object o)
O(logn) worst-case time.contains in interface Collection<Interval<T extends Comparable<? super T>>>contains in interface Set<Interval<T extends Comparable<? super T>>>contains in class AbstractCollection<Interval<T extends Comparable<? super T>>>o - The query object.true, if the object is stored in the tree, or false
otherwise.Copyright © 2016. All rights reserved.