Class RangeSet<E extends Comparable<? super E>>
- Object
-
- AbstractCollection<E>
-
- AbstractSet<Range<E>>
-
- RangeSet<E>
-
- Type Parameters:
E
- the type of range elements.
- All Implemented Interfaces:
Serializable
,Cloneable
,Iterable<Range<E>>
,Collection<Range<E>>
,Set<Range<E>>
,SortedSet<Range<E>>
,CheckedContainer<Range<E>>
public class RangeSet<E extends Comparable<? super E>> extends AbstractSet<Range<E>> implements CheckedContainer<Range<E>>, SortedSet<Range<E>>, Cloneable, Serializable
An ordered set of disjoint ranges where overlapping ranges are merged. Alladd
andremove
operations defined in this class interact with the existing ranges, merging or splitting previously added ranges in order to ensure that every ranges in aRangeSet
are always disjoint. More specifically:- When a range is added,
RangeSet
first looks for existing ranges overlapping the specified range. If overlapping ranges are found, then those ranges are merged as ofRange.union(Range)
. Consequently, adding ranges may in some circumstances reduce the size of this set. - Conversely, when a range is removed,
RangeSet
first looks if that range is in the middle of an existing range. If such range is found, then the enclosing range is splitted as ofRange.subtract(Range)
. Consequently, removing ranges may in some circumstances increase the size of this set.
Inclusive or exclusive endpointsRangeSet
requires thatRange.isMinIncluded()
andRange.isMaxIncluded()
return the same values for all instances added to this set. Those values need to be specified at construction time. If a user needs to store mixed kind of ranges, then he needs to subclass thisRangeSet
class and override theadd(Range)
,remove(Object)
andnewRange(Comparable, Comparable)
methods.Note: Current implementation does not yet support open intervals. The ranges shall be either closed intervals, or half-open. This limitation exists because supporting open intervals implies that the internal array shall support duplicated values.Extensions toThis class contains some methods not found in standardSortedSet
APISortedSet
API. Some of those methods look likeList
API, in that they work with the index of aRange
instance in the sequence of ranges returned by the iterator.indexOfRange(Comparable)
returns the index of the range containing the given value (if any).getMinDouble(int)
andgetMaxDouble(int)
return the endpoint values in the range at the given index as adouble
without the cost of creating aNumber
instance.getMinLong(int)
andgetMaxLong(int)
are equivalent to the above methods for thelong
primitive type, used mostly forDate
values (see implementation note below).intersect(Range)
provides a more convenient way thansubSet(…)
,headSet(…)
andtailSet(…)
for creating views over subsets of aRangeSet
.trimToSize()
frees unused space.
Implementation noteFor efficiency reasons, this set stores the range values in a Java array of primitive type if possible. TheRange
instances given in argument to theadd(Range)
method are not retained by this class. Ranges are recreated during iterations by calls to thenewRange(Comparable, Comparable)
method. Subclasses can override that method if they need to customize the range objects to be created.While it is possible to create
RangeSet<Date>
instances, it is more efficient to useRangeSet<Long>
with millisecond values becauseRangeSet
will internally uselong[]
arrays in the later case.- Since:
- 0.3
- See Also:
Range
, Serialized Form
Defined in the
sis-utility
module
-
-
Field Summary
Fields Modifier and Type Field Description protected Class<E>
elementType
The type of elements in the ranges.protected boolean
isMaxIncluded
true
if the maximal values of ranges in this set are inclusive, orfalse
if exclusive.protected boolean
isMinIncluded
true
if the minimal values of ranges in this set are inclusive, orfalse
if exclusive.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(E minValue, E maxValue)
Adds a range of values to this set.boolean
add(Range<E> range)
Adds a range to this set.void
clear()
Removes all elements from this set of ranges.RangeSet<E>
clone()
Returns a clone of this range set.Comparator<Range<E>>
comparator()
Returns the comparator associated with this sorted set.boolean
contains(Object object)
Returnstrue
if the given object is an instance ofRange
compatible with this set and contained inside one of the range elements of this set.boolean
contains(Range<E> range, boolean exact)
Returnstrue
if this set contains the specified element.static <E extends Comparable<? super E>>
RangeSet<E>create(Class<E> elementType, boolean isMinIncluded, boolean isMaxIncluded)
Constructs an initially empty set of ranges.boolean
equals(Object object)
Compares the specified object with this set of ranges for equality.Range<E>
first()
Returns the first (lowest) range currently in this sorted set.Class<Range<E>>
getElementType()
Returns the type of elements in this collection, which is alwaysRange
.double
getMaxDouble(int index)
Returns a range maximum value as adouble
.long
getMaxLong(int index)
Returns a range maximum value as along
.double
getMinDouble(int index)
Returns a range minimum value as adouble
.long
getMinLong(int index)
Returns a range minimum value as along
.SortedSet<Range<E>>
headSet(Range<E> upper)
Returns a view of the portion of this sorted set whose elements are strictly less thanupper
.int
indexOfRange(E value)
If the specified value is inside a range, returns the index of this range.SortedSet<Range<E>>
intersect(Range<E> subRange)
Returns a view of the portion of this range set which is the intersection of thisRangeSet
with the given range.Iterator<Range<E>>
iterator()
Returns an iterator over the elements in this set of ranges.Range<E>
last()
Returns the last (highest) range currently in this sorted set.protected Range<E>
newRange(E lower, E upper)
Returns a newRange
object initialized with the given values.boolean
remove(E minValue, E maxValue)
Removes a range of values to this set.boolean
remove(Object object)
Removes a range from this set.int
size()
Returns the number of ranges in this set.SortedSet<Range<E>>
subSet(Range<E> lower, Range<E> upper)
Returns a view of the portion of this sorted set whose elements range fromlower
, inclusive, toupper
, exclusive.SortedSet<Range<E>>
tailSet(Range<E> lower)
Returns a view of the portion of this sorted set whose elements are greater than or equal tolower
.void
trimToSize()
Trims this set to the minimal amount of memory required for holding its data.-
Methods inherited from class AbstractSet
hashCode, removeAll
-
Methods inherited from class AbstractCollection
addAll, containsAll, isEmpty, retainAll, toArray, toArray, toString
-
Methods inherited from interface Collection
parallelStream, removeIf, stream, toArray
-
Methods inherited from interface Set
addAll, containsAll, hashCode, isEmpty, removeAll, retainAll, toArray, toArray
-
Methods inherited from interface SortedSet
spliterator
-
-
-
-
Field Detail
-
elementType
protected final Class<E extends Comparable<? super E>> elementType
The type of elements in the ranges. If the element are numbers, then the value is the wrapper type (not the primitive type).- See Also:
Range.getElementType()
-
isMinIncluded
protected final boolean isMinIncluded
true
if the minimal values of ranges in this set are inclusive, orfalse
if exclusive. This value is specified at construction time and enforced when ranges are added or removed.- See Also:
Range.isMinIncluded()
-
isMaxIncluded
protected final boolean isMaxIncluded
true
if the maximal values of ranges in this set are inclusive, orfalse
if exclusive. This value is specified at construction time and enforced when ranges are added or removed.- See Also:
Range.isMaxIncluded()
-
-
Constructor Detail
-
RangeSet
protected RangeSet(Class<E> elementType, boolean isMinIncluded, boolean isMaxIncluded)
Constructs an initially empty set of ranges. This constructor is provided for sub-classing only. Client code should use the staticcreate(Class, boolean, boolean)
method instead.- Parameters:
elementType
- the type of the range elements.isMinIncluded
-true
if the minimal values are inclusive, orfalse
if exclusive.isMaxIncluded
-true
if the maximal values are inclusive, orfalse
if exclusive.
-
-
Method Detail
-
create
public static <E extends Comparable<? super E>> RangeSet<E> create(Class<E> elementType, boolean isMinIncluded, boolean isMaxIncluded)
Constructs an initially empty set of ranges.- Type Parameters:
E
- the type of range elements.- Parameters:
elementType
- the type of the range elements.isMinIncluded
-true
if the minimal values are inclusive, orfalse
if exclusive.isMaxIncluded
-true
if the maximal values are inclusive, orfalse
if exclusive.- Returns:
- a new range set for range elements of the given type.
-
getElementType
public final Class<Range<E>> getElementType()
Returns the type of elements in this collection, which is alwaysRange
. This is not the type of minimal and maximal values in range objects.- Specified by:
getElementType
in interfaceCheckedContainer<E extends Comparable<? super E>>
- Returns:
- the element type.
-
comparator
public Comparator<Range<E>> comparator()
Returns the comparator associated with this sorted set.- Specified by:
comparator
in interfaceSortedSet<E extends Comparable<? super E>>
-
clear
public void clear()
Removes all elements from this set of ranges.- Specified by:
clear
in interfaceCollection<E extends Comparable<? super E>>
- Specified by:
clear
in interfaceSet<E extends Comparable<? super E>>
- Overrides:
clear
in classAbstractCollection<Range<E extends Comparable<? super E>>>
-
size
public int size()
Returns the number of ranges in this set.- Specified by:
size
in interfaceCollection<E extends Comparable<? super E>>
- Specified by:
size
in interfaceSet<E extends Comparable<? super E>>
- Specified by:
size
in classAbstractCollection<Range<E extends Comparable<? super E>>>
-
trimToSize
public final void trimToSize()
Trims this set to the minimal amount of memory required for holding its data. This method may be invoked after all elements have been added in order to free unused memory.
-
add
public boolean add(Range<E> range) throws IllegalArgumentException
Adds a range to this set. If the specified range overlaps existing ranges, then the existing ranges will be merged as ofRange.union(Range)
. In other words, invoking this method may reduce the size of this set.The default implementation does nothing if the given range is empty. Otherwise this method ensures that the
isMinIncluded
andisMaxIncluded
match the ones given to the constructor of thisRangeSet
, then delegates toadd(Comparable, Comparable)
.- Specified by:
add
in interfaceCollection<E extends Comparable<? super E>>
- Specified by:
add
in interfaceSet<E extends Comparable<? super E>>
- Overrides:
add
in classAbstractCollection<Range<E extends Comparable<? super E>>>
- Parameters:
range
- the range to add.- Returns:
true
if this set changed as a result of this method call.- Throws:
IllegalArgumentException
- if theisMinIncluded
orisMaxIncluded
property does not match the one given at thisRangeSet
constructor.
-
add
public boolean add(E minValue, E maxValue) throws IllegalArgumentException
Adds a range of values to this set. If the specified range overlaps existing ranges, then the existing ranges will be merged. This may result in smaller size of this set.- Parameters:
minValue
- the minimal value.maxValue
- the maximal value.- Returns:
true
if this set changed as a result of this method call.- Throws:
IllegalArgumentException
- ifminValue
is greater thanmaxValue
.
-
remove
public boolean remove(Object object)
Removes a range from this set. If the specified range is inside an existing range, then the existing range may be splitted in two smaller ranges as ofRange.subtract(Range)
. In other words, invoking this method may increase the size of this set.The
isMinIncluded
andisMaxIncluded
properties of the given range shall be the complement of the ones given to the constructor of thisRangeSet
:Expected bounds inclusion add(…)
valuesremove(…)
values[min … max]
(min … max)
(min … max)
[min … max]
[min … max)
(min … max]
(min … max]
[min … max)
The default implementation does nothing if the given object is
null
, or is not an instance ofRange
, or is empty, or its element type is not equals to the element type of the ranges of this set. Otherwise this method ensures that theisMinIncluded
andisMaxIncluded
are consistent with the ones given to the constructor of thisRangeSet
, then delegates toremove(Comparable, Comparable)
.- Specified by:
remove
in interfaceCollection<E extends Comparable<? super E>>
- Specified by:
remove
in interfaceSet<E extends Comparable<? super E>>
- Overrides:
remove
in classAbstractCollection<Range<E extends Comparable<? super E>>>
- Parameters:
object
- the range to remove.- Returns:
true
if this set changed as a result of this method call.- Throws:
IllegalArgumentException
- if theisMinIncluded
orisMaxIncluded
property is not the complement of the one given at thisRangeSet
constructor.
-
remove
public boolean remove(E minValue, E maxValue) throws IllegalArgumentException
Removes a range of values to this set. If the specified range in inside an existing ranges, then the existing range may be splitted in two smaller ranges. This may result in greater size of this set.- Parameters:
minValue
- the minimal value.maxValue
- the maximal value.- Returns:
true
if this set changed as a result of this method call.- Throws:
IllegalArgumentException
- ifminValue
is greater thanmaxValue
.
-
contains
public boolean contains(Object object)
Returnstrue
if the given object is an instance ofRange
compatible with this set and contained inside one of the range elements of this set. If this method returnstrue
, then:- Invoking
add(Range)
is guaranteed to have no effect. - Invoking
remove(Object)
is guaranteed to modify this set.
false
, then:- Invoking
add(Range)
is guaranteed to modify this set. - Invoking
remove(Object)
may or may not modify this set. The consequence of invokingremove(…)
is undetermined because it depends on whether the given range is outside every ranges in this set, or if it overlaps with at least one range.
contains(object, false)
.- Specified by:
contains
in interfaceCollection<E extends Comparable<? super E>>
- Specified by:
contains
in interfaceSet<E extends Comparable<? super E>>
- Overrides:
contains
in classAbstractCollection<Range<E extends Comparable<? super E>>>
- Parameters:
object
- the object to check for inclusion in this set.- Returns:
true
if the given object is contained in this set.
- Invoking
-
contains
public boolean contains(Range<E> range, boolean exact)
Returnstrue
if this set contains the specified element.- If the
exact
argument istrue
, then this method searches for an exact match (i.e. this method doesn't check if the given range is contained in a larger range). - If the
exact
argument isfalse
, then this method behaves as documented in thecontains(Object)
method.
- Parameters:
range
- the range to check for inclusion in this set.exact
-true
for searching for an exact match, orfalse
for searching for inclusion in any range.- Returns:
true
if the given object is contained in this set.
- If the
-
first
public Range<E> first() throws NoSuchElementException
Returns the first (lowest) range currently in this sorted set.- Specified by:
first
in interfaceSortedSet<E extends Comparable<? super E>>
- Throws:
NoSuchElementException
- if this set is empty.
-
last
public Range<E> last() throws NoSuchElementException
Returns the last (highest) range currently in this sorted set.- Specified by:
last
in interfaceSortedSet<E extends Comparable<? super E>>
- Throws:
NoSuchElementException
- if the set is empty.
-
intersect
public SortedSet<Range<E>> intersect(Range<E> subRange)
Returns a view of the portion of this range set which is the intersection of thisRangeSet
with the given range. Changes in thisRangeSet
will be reflected in the returned view, and conversely.- Parameters:
subRange
- the range to intersect with thisRangeSet
.- Returns:
- a view of the specified range within this range set.
-
subSet
public SortedSet<Range<E>> subSet(Range<E> lower, Range<E> upper)
Returns a view of the portion of this sorted set whose elements range fromlower
, inclusive, toupper
, exclusive. The default implementation is equivalent to the following pseudo-code (omitting argument checks):return intersect(new Range<E>(elementType, lower.minValue, lower.isMinIncluded, upper.minValue, !upper.isMinIncluded));
API note: This method takes the minimal value of theupper
argument instead than the maximal value because the upper endpoint is exclusive.- Specified by:
subSet
in interfaceSortedSet<E extends Comparable<? super E>>
- Parameters:
lower
- low endpoint (inclusive) of the sub set.upper
- high endpoint (exclusive) of the sub set.- Returns:
- a view of the specified range within this sorted set.
- See Also:
intersect(Range)
-
headSet
public SortedSet<Range<E>> headSet(Range<E> upper)
Returns a view of the portion of this sorted set whose elements are strictly less thanupper
. The default implementation is equivalent to the same pseudo-code than the one documented in thesubSet(Range, Range)
method, except that the lower endpoint isnull
.- Specified by:
headSet
in interfaceSortedSet<E extends Comparable<? super E>>
- Parameters:
upper
- high endpoint (exclusive) of the headSet.- Returns:
- a view of the specified initial range of this sorted set.
- See Also:
intersect(Range)
-
tailSet
public SortedSet<Range<E>> tailSet(Range<E> lower)
Returns a view of the portion of this sorted set whose elements are greater than or equal tolower
. The default implementation is equivalent to the same pseudo-code than the one documented in thesubSet(Range, Range)
method, except that the upper endpoint isnull
.- Specified by:
tailSet
in interfaceSortedSet<E extends Comparable<? super E>>
- Parameters:
lower
- low endpoint (inclusive) of the tailSet.- Returns:
- a view of the specified final range of this sorted set.
- See Also:
intersect(Range)
-
iterator
public Iterator<Range<E>> iterator()
Returns an iterator over the elements in this set of ranges. All elements areRange
objects.- Specified by:
iterator
in interfaceCollection<E extends Comparable<? super E>>
- Specified by:
iterator
in interfaceIterable<E extends Comparable<? super E>>
- Specified by:
iterator
in interfaceSet<E extends Comparable<? super E>>
- Specified by:
iterator
in classAbstractCollection<Range<E extends Comparable<? super E>>>
-
indexOfRange
public int indexOfRange(E value)
If the specified value is inside a range, returns the index of this range. Otherwise, returns-1
.- Parameters:
value
- the value to search.- Returns:
- the index of the range which contains this value, or -1 if there is no such range.
-
getMinLong
public long getMinLong(int index) throws IndexOutOfBoundsException, ClassCastException
Returns a range minimum value as along
. Theindex
can be any value from 0 inclusive to the setsize
exclusive. The returned values always increase withindex
. Widening conversions are performed as needed.- Parameters:
index
- the range index, from 0 inclusive tosize
exclusive.- Returns:
- the minimum value for the range at the specified index, inclusive.
- Throws:
IndexOutOfBoundsException
- ifindex
is out of bounds.ClassCastException
- if range elements are not convertible tolong
.
-
getMinDouble
public double getMinDouble(int index) throws IndexOutOfBoundsException, ClassCastException
Returns a range minimum value as adouble
. Theindex
can be any value from 0 inclusive to the setsize
exclusive. The returned values always increase withindex
. Widening conversions are performed as needed.- Parameters:
index
- the range index, from 0 inclusive tosize
exclusive.- Returns:
- the minimum value for the range at the specified index, inclusive.
- Throws:
IndexOutOfBoundsException
- ifindex
is out of bounds.ClassCastException
- if range elements are not convertible to numbers.- See Also:
NumberRange.getMinDouble()
-
getMaxLong
public long getMaxLong(int index) throws IndexOutOfBoundsException, ClassCastException
Returns a range maximum value as along
. Theindex
can be any value from 0 inclusive to the setsize
exclusive. The returned values always increase withindex
. Widening conversions are performed as needed.- Parameters:
index
- the range index, from 0 inclusive tosize
exclusive.- Returns:
- the maximum value for the range at the specified index, inclusive.
- Throws:
IndexOutOfBoundsException
- ifindex
is out of bounds.ClassCastException
- if range elements are not convertible tolong
.
-
getMaxDouble
public double getMaxDouble(int index) throws IndexOutOfBoundsException, ClassCastException
Returns a range maximum value as adouble
. Theindex
can be any value from 0 inclusive to the set'ssize
exclusive. The returned values always increase withindex
. Widening conversions are performed as needed.- Parameters:
index
- the range index, from 0 inclusive tosize
exclusive.- Returns:
- the maximum value for the range at the specified index, exclusive.
- Throws:
IndexOutOfBoundsException
- ifindex
is out of bounds.ClassCastException
- if range elements are not convertible to numbers.- See Also:
NumberRange.getMaxDouble()
-
newRange
protected Range<E> newRange(E lower, E upper)
Returns a newRange
object initialized with the given values.- Parameters:
lower
- the lower value, inclusive.upper
- the upper value, exclusive.- Returns:
- the new range for the given values.
-
equals
public boolean equals(Object object)
Compares the specified object with this set of ranges for equality.- Specified by:
equals
in interfaceCollection<E extends Comparable<? super E>>
- Specified by:
equals
in interfaceSet<E extends Comparable<? super E>>
- Overrides:
equals
in classAbstractSet<Range<E extends Comparable<? super E>>>
- Parameters:
object
- the object to compare with this range.- Returns:
true
if the given object is equal to this range.
-
-