Class RangeSet<E extends Comparable<? super E>>
- Type Parameters:
E
- the type of range elements.
- All Implemented Interfaces:
Serializable
,Cloneable
,Iterable<Range<E>>
,Collection<Range<E>>
,SequencedCollection<Range<E>>
,SequencedSet<Range<E>>
,Set<Range<E>>
,SortedSet<Range<E>>
,CheckedContainer<Range<E>>
- Direct Known Subclasses:
RangeSet.Numeric
add
and remove
operations defined in this class interact with the existing
ranges, merging or splitting previously added ranges in order to ensure that every ranges in a
RangeSet
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 endpoints
RangeSet
requires that Range.isMinIncluded()
and Range.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
this RangeSet
class and override the add(Range)
, remove(Object)
and
newRange(Comparable, Comparable)
methods.
Extensions to SortedSet
API
This class contains some methods not found in standard SortedSet
API.
Some of those methods look like List
API, in that they work
with the index of a Range
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 note
For efficiency reasons, this set stores the range values in a Java array of primitive type if possible. TheRange
instances given in argument to the add(Range)
method are
not retained by this class. Ranges are recreated during iterations by calls to the
newRange(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
use RangeSet<Long>
with millisecond values because RangeSet
will internally
use long[]
arrays in the latter case.
- Since:
- 0.3
- Version:
- 0.5
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static final class
RangeSet.Compare<E extends Comparable<? super E>>
The range comparator returned bycomparator()
.private class
The iterator returned byiterator()
.private static final class
RangeSet.Numeric<E extends Number & Comparable<? super E>>
ARangeSet
implementation forNumberRange
elements.private final class
The iterator returned byRangeSet.SubSet.iterator()
.private final class
A view over a subset ofRangeSet
. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate Object
The array of ranges.private final byte
The primitive type, as one ofDOUBLE
,FLOAT
,LONG
,INTEGER
,SHORT
,BYTE
,CHARACTER
enumeration.The type of elements in the ranges.protected final boolean
true
if the maximal values of ranges in this set are inclusive, orfalse
if exclusive.protected final boolean
true
if the minimal values of ranges in this set are inclusive, orfalse
if exclusive.private int
The length of valid elements in the array.private int
The amount of modifications applied on the range array.private static final long
Serial number for inter-operability with different versions. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionboolean
Adds a range of values to this set.boolean
Adds a range to this set.(package private) final int
binarySearch
(E value, int lower, int upper) Returns the index ofvalue
inarray
.void
clear()
Removes all elements from this set of ranges.clone()
Returns a clone of this range set.Comparator
<Range<E>> Returns the comparator associated with this sorted set.boolean
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
Returnstrue
if this set contains the specified element.static <E extends Comparable<? super E>>
RangeSet<E> Constructs an initially empty set of ranges.private static <E extends Comparable<? super E>>
voidensureOrdered
(E minValue, E maxValue) Ensures that the given minimum value is not greater than the maximum value.boolean
Compares the specified object with this set of ranges for equality.first()
Returns the first (lowest) range currently in this sorted set.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
.getRange
(int index) Returns the range at the given array index.(package private) final E
getValue
(int index) Returns the value at the specified index.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.private void
Inserts two values at the given index.Returns a view of the portion of this range set which is the intersection of thisRangeSet
with the given range.private boolean
isSorted()
Returnstrue
if the element in the array are sorted.iterator()
Returns an iterator over the elements in this set of ranges.last()
Returns the last (highest) range currently in this sorted set.Returns a newRange
object initialized with the given values.private void
Invoked after deserialization.private void
Unconditionally copies the internal array in a new array having just the required length.boolean
Removes a range of values to this set.boolean
Removes a range from this set.private void
removeAt
(int lower, int upper) Removes the values in the given range.int
size()
Returns the number of ranges in this set.Returns a view of the portion of this sorted set whose elements range fromlower
, inclusive, toupper
, exclusive.Returns a view of the portion of this sorted set whose elements are greater than or equal tolower
.final void
Trims this set to the minimal amount of memory required for holding its data.private void
Invoked before serialization.Methods inherited from class java.util.AbstractSet
hashCode, removeAll
Methods inherited from class java.util.AbstractCollection
addAll, containsAll, isEmpty, retainAll, toArray, toArray, toString
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Collection
parallelStream, removeIf, stream, toArray
Methods inherited from interface java.util.Set
addAll, containsAll, hashCode, isEmpty, removeAll, retainAll, toArray, toArray
Methods inherited from interface java.util.SortedSet
addFirst, addLast, getFirst, getLast, removeFirst, removeLast, reversed, spliterator
-
Field Details
-
serialVersionUID
private static final long serialVersionUIDSerial number for inter-operability with different versions.- See Also:
-
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:
-
elementCode
private final byte elementCodeThe primitive type, as one ofDOUBLE
,FLOAT
,LONG
,INTEGER
,SHORT
,BYTE
,CHARACTER
enumeration. If theelementType
is not the wrapper of a primitive type, then this field value isOTHER
. -
isMinIncluded
protected final boolean isMinIncludedtrue
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:
-
isMaxIncluded
protected final boolean isMaxIncludedtrue
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:
-
array
The array of ranges. It may be either an array of Java primitive type likeint[]
orfloat[]
, or an array ofComparable
elements. All elements at even indices are minimal values, and all elements at odd indices are maximal values. Elements in this array must be strictly increasing without duplicated values.Note: The restriction against duplicated values will need to be removed in a future version if we want to support open intervals. All binary searches in this class will need to take in account the possibility for duplicated values. -
length
private transient int lengthThe length of valid elements in the array. Since the array contains both the minimum and maximum values, its length is twice the number of ranges in this set.- See Also:
-
modCount
private transient int modCountThe amount of modifications applied on the range array. Used for checking concurrent modifications.
-
-
Constructor Details
-
RangeSet
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 Details
-
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
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
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>>>
-
reallocate
private void reallocate()Unconditionally copies the internal array in a new array having just the required length. -
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. -
insertAt
Inserts two values at the given index. The underlying array shall be non-null before this method is invoked. This method increases the array size as needed.- Parameters:
lower
- the index where to insert the values.minValue
- the first value to insert.maxValue
- the second value to insert.
-
removeAt
private void removeAt(int lower, int upper) Removes the values in the given range. The underlying array shall be non-null before this method is invoked.- Parameters:
lower
- first value to remove, inclusive.upper
- last value to remove, exclusive.
-
isSorted
private boolean isSorted()Returnstrue
if the element in the array are sorted. This method is used for assertions only. The array shall be trimmed to size before this method is invoked. -
binarySearch
Returns the index ofvalue
inarray
. This method delegates to one ofArrays.binarySearch
methods, depending on element primary type.- Parameters:
value
- the value to search.lower
- index of the first value to examine.upper
- index after the last value to examine.
-
ensureOrdered
Ensures that the given minimum value is not greater than the maximum value. This method is used for argument checks. -
add
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
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
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
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
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
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
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
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
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
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):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:
-
headSet
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:
-
tailSet
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:
-
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
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
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
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:
-
getMaxLong
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
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:
-
getValue
Returns the value at the specified index. Even index are lower endpoints, while odd index are upper endpoints. The index validity must have been checked before this method is invoked. -
getRange
Returns the range at the given array index. The given index is relative to the intervalarray
, which is twice the index of range elements.- Parameters:
index
- the range index, from 0 inclusive tolength
exclusive.
-
newRange
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
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.
-
clone
Returns a clone of this range set. -
writeObject
Invoked before serialization. Trims the internal array to the minimal size in order to reduce the size of the object to be serialized.- Parameters:
out
- the output stream where to serialize this range set.- Throws:
IOException
- if an I/O error occurred while writing.
-
readObject
Invoked after deserialization. Initializes the transient fields.- Parameters:
in
- the input stream from which to deserialize a range set.- Throws:
IOException
- if an I/O error occurred while reading or if the stream contains invalid data.ClassNotFoundException
- if the class serialized on the stream is not on the classpath.
-