E
- The type of range elements.public class RangeSet<E extends Comparable<? super E>> extends AbstractSet<Range<E>> implements CheckedContainer<Range<E>>, SortedSet<Range<E>>, Cloneable, Serializable
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:
RangeSet
first looks for existing
ranges overlapping the specified range. If overlapping ranges are found, then those ranges
are merged as of Range.union(Range)
. Consequently, adding ranges may in some
circumstances reduce the size of this set.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 of Range.subtract(Range)
. Consequently, removing
ranges may in some circumstances increase the size of this set.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.
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.
SortedSet
APISortedSet
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)
and getMaxDouble(int)
return the endpoint values
in the range at the given index as a double
without the cost of creating a
Number
instance.getMinLong(int)
and getMaxLong(int)
are equivalent to the above
methods for the long
primitive type, used mostly for Date
values (see implementation note below).intersect(Range)
provides a more convenient way than subSet(…)
,
headSet(…)
and tailSet(…)
for creating views over subsets of a
RangeSet
.trimToSize()
frees unused space.Range
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, is is more efficient to
use RangeSet<Long>
with millisecond values because RangeSet
will internally
use long[]
arrays in the later case.
Range
,
Serialized FormDefined in the sis-utility module
Modifier and Type | Field and 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, or false
if exclusive. |
protected boolean |
isMinIncluded
true if the minimal values of ranges in this set are inclusive, or false
if exclusive. |
Modifier | Constructor and Description |
---|---|
protected |
RangeSet(Class<E> elementType,
boolean isMinIncluded,
boolean isMaxIncluded)
Constructs an initially empty set of ranges.
|
Modifier and Type | Method and 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)
Returns
true if the given object is an instance of Range compatible
with this set and contained inside one of the range elements of this set. |
boolean |
contains(Range<E> range,
boolean exact)
Returns
true if this set contains the specified element. |
static <E extends Comparable<? super 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 always
Range . |
double |
getMaxDouble(int index)
Returns a range maximum value as a
double . |
long |
getMaxLong(int index)
Returns a range maximum value as a
long . |
double |
getMinDouble(int index)
Returns a range minimum value as a
double . |
long |
getMinLong(int index)
Returns a range minimum value as a
long . |
SortedSet<Range<E>> |
headSet(Range<E> upper)
Returns a view of the portion of this sorted set whose elements are
strictly less than
upper . |
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
this
RangeSet 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 new
Range 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
from
lower , inclusive, to upper , 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 to
lower . |
void |
trimToSize()
Trims this set to the minimal amount of memory required for holding its data.
|
hashCode, removeAll
addAll, containsAll, isEmpty, retainAll, toArray, toArray, toString
protected final Class<E extends Comparable<? super E>> elementType
Range.getElementType()
protected final boolean isMinIncluded
true
if the minimal values of ranges in this set are inclusive, or false
if exclusive. This value is specified at construction time and enforced when ranges are
added or removed.Range.isMinIncluded()
protected final boolean isMaxIncluded
true
if the maximal values of ranges in this set are inclusive, or false
if exclusive. This value is specified at construction time and enforced when ranges are
added or removed.Range.isMaxIncluded()
protected RangeSet(Class<E> elementType, boolean isMinIncluded, boolean isMaxIncluded)
create(Class, boolean, boolean)
method instead.elementType
- The type of the range elements.isMinIncluded
- true
if the minimal values are inclusive, or false
if exclusive.isMaxIncluded
- true
if the maximal values are inclusive, or false
if exclusive.public static <E extends Comparable<? super E>> RangeSet<E> create(Class<E> elementType, boolean isMinIncluded, boolean isMaxIncluded)
E
- The type of range elements.elementType
- The type of the range elements.isMinIncluded
- true
if the minimal values are inclusive, or false
if exclusive.isMaxIncluded
- true
if the maximal values are inclusive, or false
if exclusive.public final Class<Range<E>> getElementType()
Range
.
This is not the type of minimal and maximal values in range objects.getElementType
in interface CheckedContainer<Range<E extends Comparable<? super E>>>
public Comparator<Range<E>> comparator()
comparator
in interface SortedSet<Range<E extends Comparable<? super E>>>
public void clear()
clear
in interface Collection<Range<E extends Comparable<? super E>>>
clear
in interface Set<Range<E extends Comparable<? super E>>>
clear
in class AbstractCollection<Range<E extends Comparable<? super E>>>
public int size()
size
in interface Collection<Range<E extends Comparable<? super E>>>
size
in interface Set<Range<E extends Comparable<? super E>>>
size
in class AbstractCollection<Range<E extends Comparable<? super E>>>
public final void trimToSize()
public boolean add(Range<E> range) throws IllegalArgumentException
Range.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
and isMaxIncluded
match the ones given to the constructor of this RangeSet
, then delegates to
add(Comparable, Comparable)
.
add
in interface Collection<Range<E extends Comparable<? super E>>>
add
in interface Set<Range<E extends Comparable<? super E>>>
add
in class AbstractCollection<Range<E extends Comparable<? super E>>>
range
- The range to add.true
if this set changed as a result of this method call.IllegalArgumentException
- If the isMinIncluded
or isMaxIncluded
property doesn't match the one given at this RangeSet
constructor.public boolean add(E minValue, E maxValue) throws IllegalArgumentException
minValue
- The minimal value.maxValue
- The maximal value.true
if this set changed as a result of this method call.IllegalArgumentException
- if minValue
is greater than maxValue
.public boolean remove(Object object)
Range.subtract(Range)
.
In other words, invoking this method may increase the
size of this set.
The isMinIncluded
and isMaxIncluded
properties of the given range
shall be the complement of the ones given to the constructor of this RangeSet
:
add(…) values | remove(…) 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 of Range
, 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
the isMinIncluded
and isMaxIncluded
are consistent with the ones given to the
constructor of this RangeSet
, then delegates to remove(Comparable, Comparable)
.
remove
in interface Collection<Range<E extends Comparable<? super E>>>
remove
in interface Set<Range<E extends Comparable<? super E>>>
remove
in class AbstractCollection<Range<E extends Comparable<? super E>>>
object
- The range to remove.true
if this set changed as a result of this method call.IllegalArgumentException
- If the isMinIncluded
or isMaxIncluded
property is not the complement of the one given at this RangeSet
constructor.public boolean remove(E minValue, E maxValue) throws IllegalArgumentException
minValue
- The minimal value.maxValue
- The maximal value.true
if this set changed as a result of this method call.IllegalArgumentException
- if minValue
is greater than maxValue
.public boolean contains(Object object)
true
if the given object is an instance of Range
compatible
with this set and contained inside one of the range elements of this set.
If this method returns true
, then:
add(Range)
is guaranteed to have no effect.remove(Object)
is guaranteed to modify this set.false
, then:
add(Range)
is guaranteed to modify this set.remove(Object)
may or may not modify this set.
The consequence of invoking remove(…)
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)
.contains
in interface Collection<Range<E extends Comparable<? super E>>>
contains
in interface Set<Range<E extends Comparable<? super E>>>
contains
in class AbstractCollection<Range<E extends Comparable<? super E>>>
object
- The object to check for inclusion in this set.true
if the given object is contained in this set.public boolean contains(Range<E> range, boolean exact)
true
if this set contains the specified element.
exact
argument is true
, 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).exact
argument is false
, then this method
behaves as documented in the contains(Object)
method.range
- The range to check for inclusion in this set.exact
- true
for searching for an exact match,
or false
for searching for inclusion in any range.true
if the given object is contained in this set.public Range<E> first() throws NoSuchElementException
first
in interface SortedSet<Range<E extends Comparable<? super E>>>
NoSuchElementException
- if this set is empty.public Range<E> last() throws NoSuchElementException
last
in interface SortedSet<Range<E extends Comparable<? super E>>>
NoSuchElementException
- if the set is empty.public SortedSet<Range<E>> intersect(Range<E> subRange)
RangeSet
with the given range. Changes in this RangeSet
will be reflected in the returned view, and conversely.subRange
- The range to intersect with this RangeSet
.public SortedSet<Range<E>> subSet(Range<E> lower, Range<E> upper)
lower
, inclusive, to upper
, 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));
Note:
This method takes the minimal value of the upper
argument
rater than the maximal value because the upper endpoint is exclusive.
subSet
in interface SortedSet<Range<E extends Comparable<? super E>>>
lower
- Low endpoint (inclusive) of the sub set.upper
- High endpoint (exclusive) of the sub set.intersect(Range)
public SortedSet<Range<E>> headSet(Range<E> upper)
upper
.
The default implementation is equivalent to the same pseudo-code than the one
documented in the subSet(Range, Range)
method, except that the lower
endpoint is null
.headSet
in interface SortedSet<Range<E extends Comparable<? super E>>>
upper
- High endpoint (exclusive) of the headSet.intersect(Range)
public SortedSet<Range<E>> tailSet(Range<E> lower)
lower
.
The default implementation is equivalent to the same pseudo-code than the one
documented in the subSet(Range, Range)
method, except that the upper
endpoint is null
.tailSet
in interface SortedSet<Range<E extends Comparable<? super E>>>
lower
- Low endpoint (inclusive) of the tailSet.intersect(Range)
public Iterator<Range<E>> iterator()
Range
objects.iterator
in interface Iterable<Range<E extends Comparable<? super E>>>
iterator
in interface Collection<Range<E extends Comparable<? super E>>>
iterator
in interface Set<Range<E extends Comparable<? super E>>>
iterator
in class AbstractCollection<Range<E extends Comparable<? super E>>>
public int indexOfRange(E value)
-1
.value
- The value to search.public long getMinLong(int index) throws IndexOutOfBoundsException, ClassCastException
long
.
The index
can be any value from 0 inclusive to the set size
exclusive. The returned values always increase with index
.
Widening conversions are performed as needed.index
- The range index, from 0 inclusive to size
exclusive.IndexOutOfBoundsException
- if index
is out of bounds.ClassCastException
- if range elements are not convertible to long
.public double getMinDouble(int index) throws IndexOutOfBoundsException, ClassCastException
double
.
The index
can be any value from 0 inclusive to the set size
exclusive. The returned values always increase with index
.
Widening conversions are performed as needed.index
- The range index, from 0 inclusive to size
exclusive.IndexOutOfBoundsException
- if index
is out of bounds.ClassCastException
- if range elements are not convertible to numbers.NumberRange.getMinDouble()
public long getMaxLong(int index) throws IndexOutOfBoundsException, ClassCastException
long
.
The index
can be any value from 0 inclusive to the set size
exclusive. The returned values always increase with index
.
Widening conversions are performed as needed.index
- The range index, from 0 inclusive to size
exclusive.IndexOutOfBoundsException
- if index
is out of bounds.ClassCastException
- if range elements are not convertible to long
.public double getMaxDouble(int index) throws IndexOutOfBoundsException, ClassCastException
double
.
The index
can be any value from 0 inclusive to the set's size
exclusive. The returned values always increase with index
.
Widening conversions are performed as needed.index
- The range index, from 0 inclusive to size
exclusive.IndexOutOfBoundsException
- if index
is out of bounds.ClassCastException
- if range elements are not convertible to numbers.NumberRange.getMaxDouble()
protected Range<E> newRange(E lower, E upper)
Range
object initialized with the given values.lower
- The lower value, inclusive.upper
- The upper value, exclusive.public boolean equals(Object object)
equals
in interface Collection<Range<E extends Comparable<? super E>>>
equals
in interface Set<Range<E extends Comparable<? super E>>>
equals
in class AbstractSet<Range<E extends Comparable<? super E>>>
object
- The object to compare with this range.true
if the given object is equal to this range.Copyright © 2010–2013 The Apache Software Foundation. All rights reserved.