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>>
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,
RangeSetfirst 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,
RangeSetfirst 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.
Limitation
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 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 adoublewithout the cost of creating aNumberinstance.getMinLong(int)andgetMaxLong(int)are equivalent to the above methods for thelongprimitive type, used mostly forDatevalues (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
- See Also:
-
Field Summary
FieldsModifier and TypeFieldDescriptionThe type of elements in the ranges.protected final booleantrueif the maximal values of ranges in this set are inclusive, orfalseif exclusive.protected final booleantrueif the minimal values of ranges in this set are inclusive, orfalseif exclusive. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionbooleanAdds a range of values to this set.booleanAdds a range to this set.voidclear()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.booleanReturnstrueif the given object is an instance ofRangecompatible with this set and contained inside one of the range elements of this set.booleanReturnstrueif this set contains the specified element.static <E extends Comparable<? super E>>
RangeSet<E> Constructs an initially empty set of ranges.booleanCompares 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.doublegetMaxDouble(int index) Returns a range maximum value as adouble.longgetMaxLong(int index) Returns a range maximum value as along.doublegetMinDouble(int index) Returns a range minimum value as adouble.longgetMinLong(int index) Returns a range minimum value as along.SortedSet<Range<E>> Returns a view of the portion of this sorted set whose elements are strictly less thanupper.intindexOfMax(E value) Returns the index of the range having a maximum value equal or greater than the specified value.intindexOfMin(E value) Returns the index of the range having a minimum value equal or lower than the specified value.intindexOfRange(E value) If the specified value is inside a range, returns the index of this range.SortedSet<Range<E>> Returns a view of the portion of this range set which is the intersection of thisRangeSetwith the given range.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 newRangeobject initialized with the given values.booleanRemoves a range of values to this set.booleanRemoves a range from this set.intsize()Returns the number of ranges in this set.SortedSet<Range<E>> Returns a view of the portion of this sorted set whose elements range fromlower, inclusive, toupper, exclusive.SortedSet<Range<E>> Returns a view of the portion of this sorted set whose elements are greater than or equal tolower.final voidTrims this set to the minimal amount of memory required for holding its data.Methods inherited from class AbstractSet
hashCode, removeAllMethods inherited from class AbstractCollection
addAll, containsAll, isEmpty, retainAll, toArray, toArray, toStringMethods inherited from interface Collection
parallelStream, removeIf, stream, toArrayMethods inherited from interface Set
addAll, containsAll, hashCode, isEmpty, removeAll, retainAll, toArray, toArrayMethods inherited from interface SortedSet
addFirst, addLast, getFirst, getLast, removeFirst, removeLast, reversed, spliterator
-
Field Details
-
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:
-
isMinIncluded
protected final boolean isMinIncludedtrueif the minimal values of ranges in this set are inclusive, orfalseif exclusive. This value is specified at construction time and enforced when ranges are added or removed.- See Also:
-
isMaxIncluded
protected final boolean isMaxIncludedtrueif the maximal values of ranges in this set are inclusive, orfalseif exclusive. This value is specified at construction time and enforced when ranges are added or removed.- See Also:
-
-
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-trueif the minimal values are inclusive, orfalseif exclusive.isMaxIncluded-trueif the maximal values are inclusive, orfalseif 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-trueif the minimal values are inclusive, orfalseif exclusive.isMaxIncluded-trueif the maximal values are inclusive, orfalseif 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:
getElementTypein interfaceCheckedContainer<E extends Comparable<? super E>>- Returns:
- the element type.
-
comparator
Returns the comparator associated with this sorted set.- Specified by:
comparatorin interfaceSortedSet<E extends Comparable<? super E>>
-
clear
public void clear()Removes all elements from this set of ranges.- Specified by:
clearin interfaceCollection<E extends Comparable<? super E>>- Specified by:
clearin interfaceSet<E extends Comparable<? super E>>- Overrides:
clearin classAbstractCollection<Range<E extends Comparable<? super E>>>
-
size
public int size()Returns the number of ranges in this set.- Specified by:
sizein interfaceCollection<E extends Comparable<? super E>>- Specified by:
sizein interfaceSet<E extends Comparable<? super E>>- Specified by:
sizein 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
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
isMinIncludedandisMaxIncludedmatch the ones given to the constructor of thisRangeSet, then delegates toadd(Comparable, Comparable).- Specified by:
addin interfaceCollection<E extends Comparable<? super E>>- Specified by:
addin interfaceSet<E extends Comparable<? super E>>- Overrides:
addin classAbstractCollection<Range<E extends Comparable<? super E>>>- Parameters:
range- the range to add.- Returns:
trueif this set changed as a result of this method call.- Throws:
IllegalArgumentException- if theisMinIncludedorisMaxIncludedproperty does not match the one given at thisRangeSetconstructor.
-
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:
trueif this set changed as a result of this method call.- Throws:
IllegalArgumentException- ifminValueis 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
isMinIncludedandisMaxIncludedproperties 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 theisMinIncludedandisMaxIncludedare consistent with the ones given to the constructor of thisRangeSet, then delegates toremove(Comparable, Comparable).- Specified by:
removein interfaceCollection<E extends Comparable<? super E>>- Specified by:
removein interfaceSet<E extends Comparable<? super E>>- Overrides:
removein classAbstractCollection<Range<E extends Comparable<? super E>>>- Parameters:
object- the range to remove.- Returns:
trueif this set changed as a result of this method call.- Throws:
IllegalArgumentException- if theisMinIncludedorisMaxIncludedproperty is not the complement of the one given at thisRangeSetconstructor.
-
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:
trueif this set changed as a result of this method call.- Throws:
IllegalArgumentException- ifminValueis greater thanmaxValue.
-
contains
Returnstrueif the given object is an instance ofRangecompatible 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:
containsin interfaceCollection<E extends Comparable<? super E>>- Specified by:
containsin interfaceSet<E extends Comparable<? super E>>- Overrides:
containsin classAbstractCollection<Range<E extends Comparable<? super E>>>- Parameters:
object- the object to check for inclusion in this set.- Returns:
trueif the given object is contained in this set.
- Invoking
-
contains
Returnstrueif this set contains the specified element.- If the
exactargument 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
exactargument isfalse, then this method behaves as documented in thecontains(Object)method.
- Parameters:
range- the range to check for inclusion in this set.exact-truefor searching for an exact match, orfalsefor searching for inclusion in any range.- Returns:
trueif the given object is contained in this set.
- If the
-
first
Returns the first (lowest) range currently in this sorted set.- Specified by:
firstin 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:
lastin 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 thisRangeSetwith the given range. Changes in thisRangeSetwill 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):return intersect(new Range<E>(elementType, lower.minValue, lower.isMinIncluded, upper.minValue, !upper.isMinIncluded));API note: This method takes the minimal value of theupperargument instead than the maximal value because the upper endpoint is exclusive.- Specified by:
subSetin 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:
headSetin 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:
tailSetin 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 areRangeobjects.- Specified by:
iteratorin interfaceCollection<E extends Comparable<? super E>>- Specified by:
iteratorin interfaceIterable<E extends Comparable<? super E>>- Specified by:
iteratorin interfaceSet<E extends Comparable<? super E>>- Specified by:
iteratorin 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.
-
indexOfMin
Returns the index of the range having a minimum value equal or lower than the specified value. If the given value is lower than the minimal value of all ranges in this set, then this method returns -1.- Parameters:
value- the minimum value to search, ignoring inclusiveness/exclusiveness.- Returns:
- index of the range having a minimum value equal or lower than the specified value. May be -1.
- Since:
- 1.4
-
indexOfMax
Returns the index of the range having a maximum value equal or greater than the specified value. If the given value is greater than the maximal value of all ranges in this set, then this method returnssize().- Parameters:
value- the maximum value to search, ignoring inclusiveness/exclusiveness.- Returns:
- index of the range having a maximum value equal or greater than the specified value.
May be
size(). - Since:
- 1.4
-
getMinLong
Returns a range minimum value as along. Theindexcan be any value from 0 inclusive to the setsizeexclusive. The returned values always increase withindex. Widening conversions are performed as needed.- Parameters:
index- the range index, from 0 inclusive tosizeexclusive.- Returns:
- the minimum value for the range at the specified index.
- Throws:
IndexOutOfBoundsException- ifindexis out of bounds.ClassCastException- if range elements are not convertible tolong.
-
getMinDouble
Returns a range minimum value as adouble. Theindexcan be any value from 0 inclusive to the setsizeexclusive. The returned values always increase withindex. Widening conversions are performed as needed.- Parameters:
index- the range index, from 0 inclusive tosizeexclusive.- Returns:
- the minimum value for the range at the specified index.
- Throws:
IndexOutOfBoundsException- ifindexis out of bounds.ClassCastException- if range elements are not convertible to numbers.- See Also:
-
getMaxLong
Returns a range maximum value as along. Theindexcan be any value from 0 inclusive to the setsizeexclusive. The returned values always increase withindex. Widening conversions are performed as needed.- Parameters:
index- the range index, from 0 inclusive tosizeexclusive.- Returns:
- the maximum value for the range at the specified index.
- Throws:
IndexOutOfBoundsException- ifindexis out of bounds.ClassCastException- if range elements are not convertible tolong.
-
getMaxDouble
Returns a range maximum value as adouble. Theindexcan be any value from 0 inclusive to the set'ssizeexclusive. The returned values always increase withindex. Widening conversions are performed as needed.- Parameters:
index- the range index, from 0 inclusive tosizeexclusive.- Returns:
- the maximum value for the range at the specified index.
- Throws:
IndexOutOfBoundsException- ifindexis out of bounds.ClassCastException- if range elements are not convertible to numbers.- See Also:
-
newRange
Returns a newRangeobject 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:
equalsin interfaceCollection<E extends Comparable<? super E>>- Specified by:
equalsin interfaceSet<E extends Comparable<? super E>>- Overrides:
equalsin classAbstractSet<Range<E extends Comparable<? super E>>>- Parameters:
object- the object to compare with this range.- Returns:
trueif the given object is equal to this range.
-
clone
Returns a clone of this range set.
-