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 IntervalTree
IntervalTree(@NonNull Collection<T> collection)	Instantiates a new IntervalTree with the given items

Method Summary

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

Methods inherited from interface java.lang.Iterable

forEach

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 interface Collection<T extends Span>

addAll

public boolean addAll(@NonNull
                      @NonNull Collection<? extends T> collection)

Specified by:

addAll in interface Collection<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 interface Collection<T extends Span>

contains

public boolean contains(Object o)

Specified by:

contains in interface Collection<T extends Span>

containsAll

public boolean containsAll(@NonNull
                           @NonNull Collection<?> collection)

Specified by:

containsAll in interface Collection<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 interface Collection<T extends Span>

iterator

public Iterator<T> iterator()

Specified by:

iterator in interface Collection<T extends Span>

Specified by:

iterator in interface Iterable<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 interface Collection<T extends Span>

removeAll

public boolean removeAll(@NonNull
                         @NonNull Collection<?> collection)

Specified by:

removeAll in interface Collection<T extends Span>

retainAll

public boolean retainAll(@NonNull
                         @NonNull Collection<?> collection)

Specified by:

retainAll in interface Collection<T extends Span>

size

public int size()

Specified by:

size in interface Collection<T extends Span>

toArray

public Object[] toArray()

Specified by:

toArray in interface Collection<T extends Span>

toArray

public <T1> T1[] toArray(T1[] t1s)

Specified by:

toArray in interface Collection<T extends Span>

toString

public String toString()

Overrides:

toString in class Object