Package com.gengoai.collection.tree
Class IntervalTree<T extends Span>
- java.lang.Object
-
- com.gengoai.collection.tree.IntervalTree<T>
-
- Type Parameters:
T
- the element type parameter
- All Implemented Interfaces:
Serializable
,Iterable<T>
,Collection<T>
public class IntervalTree<T extends Span> extends Object implements Collection<T>, Serializable
An Tree structure with fast lookups for elements falling within a given interval.
- Author:
- David B. Bracewell
- See Also:
- Serialized Form
-
-
Constructor Summary
Constructors Constructor Description IntervalTree()
Instantiates a new IntervalTreeIntervalTree(@NonNull Collection<T> collection)
Instantiates a new IntervalTree with the given items
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(T item)
boolean
addAll(@NonNull Collection<? extends T> collection)
Iterable<T>
ceiling(T span)
Returns the least elements in this set greater than or equal to the given element, or an empty Iterable if there is no such element.Iterator<T>
ceilingIterator(T start)
Returns an iterator of items in the tree starting at the least element in the set greater than or equal to the given element or an empty iterator if there is no such element.void
clear()
boolean
contains(Object o)
boolean
containsAll(@NonNull Collection<?> collection)
boolean
containsOverlappingSpans(@NonNull Span span)
Iterable<T>
floor(T span)
Returns the greatest elements in this set less than or equal to the given element, or an empty iterable if there is no such element.Iterator<T>
floorIterator(T start)
Returns an iterator of items in the tree starting at the greatest element in the set less than or equal to the given element or an empty iterator if there is no such element.Iterable<T>
higher(T span)
Returns the least elements in this set greater than the given element, or an empty Iterable if there is no such element.Iterator<T>
higherIterator(T start)
Returns an iterator of items in the tree starting at the least element in the set greater than the given element or an empty iterator if there is no such element.boolean
isEmpty()
Iterator<T>
iterator()
Iterable<T>
lower(T span)
Returns the greatest elements in this set less than the given element, or an empty iterable if there is no such element.Iterator<T>
lowerIterator(T start)
Returns an iterator of items in the tree starting at the greatest element in the set less than the given element or an empty iterator if there is no such element.Iterable<T>
overlapping(@NonNull Span span)
Returns the collection of elements in this set overlapping with the given span including.boolean
remove(Object o)
boolean
removeAll(@NonNull Collection<?> collection)
boolean
retainAll(@NonNull Collection<?> collection)
int
size()
Object[]
toArray()
<T1> T1[]
toArray(T1[] t1s)
String
toString()
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface java.util.Collection
equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray
-
-
-
-
Constructor Detail
-
IntervalTree
public IntervalTree()
Instantiates a new IntervalTree
-
IntervalTree
public IntervalTree(@NonNull @NonNull Collection<T> collection)
Instantiates a new IntervalTree with the given items- Parameters:
collection
- the collection of items to initialize the IntervalTree with
-
-
Method Detail
-
add
public boolean add(@NonNull T item)
- Specified by:
add
in interfaceCollection<T extends Span>
-
addAll
public boolean addAll(@NonNull @NonNull Collection<? extends T> collection)
- Specified by:
addAll
in interfaceCollection<T extends Span>
-
ceiling
public Iterable<T> ceiling(@NonNull T span)
Returns the least elements in this set greater than or equal to the given element, or an empty Iterable if there is no such element.- Parameters:
span
- the span to match- Returns:
- the iterable of least elements greater than or equal to span, or an empty Iterable if there is no such element
-
ceilingIterator
public Iterator<T> ceilingIterator(@NonNull T start)
Returns an iterator of items in the tree starting at the least element in the set greater than or equal to the given element or an empty iterator if there is no such element.- Parameters:
start
- the span to match for the starting point of iteration- Returns:
- the iterator of items in the tree starting at the least element in the set greater than or equal to the given element or an empty iterator if there is no such element.
-
clear
public void clear()
- Specified by:
clear
in interfaceCollection<T extends Span>
-
contains
public boolean contains(Object o)
- Specified by:
contains
in interfaceCollection<T extends Span>
-
containsAll
public boolean containsAll(@NonNull @NonNull Collection<?> collection)
- Specified by:
containsAll
in interfaceCollection<T extends Span>
-
containsOverlappingSpans
public boolean containsOverlappingSpans(@NonNull @NonNull Span span)
-
floor
public Iterable<T> floor(@NonNull T span)
Returns the greatest elements in this set less than or equal to the given element, or an empty iterable if there is no such element.- Parameters:
span
- the span to match- Returns:
- the iterable of the the greatest elements in this set less than or equal to the given element, or an empty iterable if there is no such element.
-
floorIterator
public Iterator<T> floorIterator(@NonNull T start)
Returns an iterator of items in the tree starting at the greatest element in the set less than or equal to the given element or an empty iterator if there is no such element.- Parameters:
start
- the span to match for the starting point of iteration- Returns:
- the iterator of items in the tree starting at the greatest element in the set less than or equal to the given element or an empty iterator if there is no such element.
-
higher
public Iterable<T> higher(@NonNull T span)
Returns the least elements in this set greater than the given element, or an empty Iterable if there is no such element.- Parameters:
span
- the span to match- Returns:
- the iterable of least elements greater than span, or an empty Iterable if there is no such element
-
higherIterator
public Iterator<T> higherIterator(@NonNull T start)
Returns an iterator of items in the tree starting at the least element in the set greater than the given element or an empty iterator if there is no such element.- Parameters:
start
- the span to match for the starting point of iteration- Returns:
- the iterator of items in the tree starting at the least element in the set greater than the given element or an empty iterator if there is no such element.
-
isEmpty
public boolean isEmpty()
- Specified by:
isEmpty
in interfaceCollection<T extends Span>
-
lower
public Iterable<T> lower(@NonNull T span)
Returns the greatest elements in this set less than the given element, or an empty iterable if there is no such element.- Parameters:
span
- the span to match- Returns:
- the iterable of the the greatest elements in this set less than the given element, or an empty iterable if there is no such element.
-
lowerIterator
public Iterator<T> lowerIterator(@NonNull T start)
Returns an iterator of items in the tree starting at the greatest element in the set less than the given element or an empty iterator if there is no such element.- Parameters:
start
- the span to match for the starting point of iteration- Returns:
- the iterator of items in the tree starting at the greatest element in the set less than the given element or an empty iterator if there is no such element.
-
overlapping
public Iterable<T> overlapping(@NonNull @NonNull Span span)
Returns the collection of elements in this set overlapping with the given span including.- Parameters:
span
- the span to match- Returns:
- the list of elements overlapping in this set overlapping with the given span
-
remove
public boolean remove(Object o)
- Specified by:
remove
in interfaceCollection<T extends Span>
-
removeAll
public boolean removeAll(@NonNull @NonNull Collection<?> collection)
- Specified by:
removeAll
in interfaceCollection<T extends Span>
-
retainAll
public boolean retainAll(@NonNull @NonNull Collection<?> collection)
- Specified by:
retainAll
in interfaceCollection<T extends Span>
-
size
public int size()
- Specified by:
size
in interfaceCollection<T extends Span>
-
toArray
public Object[] toArray()
- Specified by:
toArray
in interfaceCollection<T extends Span>
-
toArray
public <T1> T1[] toArray(T1[] t1s)
- Specified by:
toArray
in interfaceCollection<T extends Span>
-
-