Module org.apache.sis.util

Package org.apache.sis.util.collection

Class RangeSet<E extends Comparable<? super E>>

Object

AbstractCollection<Range<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>>, Sequenced­Collection<Range<E>>, Sequenced­Set<Range<E>>, Set<Range<E>>, Sorted­Set<Range<E>>, Checked­Container<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. All 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 Range­Set are always disjoint. More specifically:

• When a range is added, Range­Set 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.
• Conversely, when a range is removed, Range­Set 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.

Inclusive or exclusive endpoints

Range­Set requires that Range.is­Min­Included() and Range.is­Max­Included() 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 Range­Set class and override the add(Range), remove(Object) and new­Range(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 Sorted­Set API

This class contains some methods not found in standard Sorted­Set 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.

• index­Of­Range(Comparable) returns the index of the range containing the given value (if any).
• get­Min­Double(int) and get­Max­Double(int) return the endpoint values in the range at the given index as a double without the cost of creating a Number instance.
• get­Min­Long(int) and get­Max­Long(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 sub­Set(…), head­Set(…) and tail­Set(…) for creating views over subsets of a Range­Set.
• trim­To­Size() frees unused space.

Implementation note

For efficiency reasons, this set stores the range values in a Java array of primitive type if possible. The 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 new­Range(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 Range­Set<Date> instances, it is more efficient to use Range­Set<Long> with millisecond values because Range­Set will internally use long[] arrays in the latter case.

Since:

0.3

See Also:

• Range
• Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
protected final Class<E>	element­Type	The type of elements in the ranges.
protected final boolean	is­Max­Included	true if the maximal values of ranges in this set are inclusive, or false if exclusive.
protected final boolean	is­Min­Included	true if the minimal values of ranges in this set are inclusive, or false if exclusive.

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	Range­Set(Class<E> element­Type, boolean is­Min­Included, boolean is­Max­Included)	Constructs an initially empty set of ranges.

Method Summary

Modifier and Type	Method	Description
boolean	add(E min­Value, E max­Value)	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.
Range­Set<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>> Range­Set<E>	create(Class<E> element­Type, boolean is­Min­Included, boolean is­Max­Included)	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.
final Class<Range<E>>	get­Element­Type()	Returns the type of elements in this collection, which is always Range.
double	get­Max­Double(int index)	Returns a range maximum value as a double.
long	get­Max­Long(int index)	Returns a range maximum value as a long.
double	get­Min­Double(int index)	Returns a range minimum value as a double.
long	get­Min­Long(int index)	Returns a range minimum value as a long.
Sorted­Set<Range<E>>	head­Set(Range<E> upper)	Returns a view of the portion of this sorted set whose elements are strictly less than upper.
int	index­Of­Max(E value)	Returns the index of the range having a maximum value equal or greater than the specified value.
int	index­Of­Min(E value)	Returns the index of the range having a minimum value equal or lower than the specified value.
int	index­Of­Range(E value)	If the specified value is inside a range, returns the index of this range.
Sorted­Set<Range<E>>	intersect(Range<E> sub­Range)	Returns a view of the portion of this range set which is the intersection of this Range­Set 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>	new­Range(E lower, E upper)	Returns a new Range object initialized with the given values.
boolean	remove(E min­Value, E max­Value)	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.
Sorted­Set<Range<E>>	sub­Set(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.
Sorted­Set<Range<E>>	tail­Set(Range<E> lower)	Returns a view of the portion of this sorted set whose elements are greater than or equal to lower.
final void	trim­To­Size()	Trims this set to the minimal amount of memory required for holding its data.

Methods inherited from class AbstractSet

hash­Code, remove­All

Methods inherited from class AbstractCollection

add­All, contains­All, is­Empty, retain­All, to­Array, to­Array, to­String

Methods inherited from class Object

finalize, get­Class, notify, notify­All, wait, wait, wait

Methods inherited from interface Collection

parallel­Stream, remove­If, stream, to­Array

Methods inherited from interface Iterable

for­Each

Methods inherited from interface Set

add­All, contains­All, hash­Code, is­Empty, remove­All, retain­All, to­Array, to­Array

Methods inherited from interface SortedSet

add­First, add­Last, get­First, get­Last, remove­First, remove­Last, reversed, spliterator

Field Details

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.get­Element­Type()

isMinIncluded

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.

See Also:

• Range.is­Min­Included()

isMaxIncluded

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.

See Also:

• Range.is­Max­Included()

Constructor Details

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 static create(Class, boolean, boolean) method instead.

Parameters:

element­Type - the type of the range elements.

is­Min­Included - true if the minimal values are inclusive, or false if exclusive.

is­Max­Included - true if the maximal values are inclusive, or false 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:

element­Type - the type of the range elements.

is­Min­Included - true if the minimal values are inclusive, or false if exclusive.

is­Max­Included - true if the maximal values are inclusive, or false 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 always Range. This is not the type of minimal and maximal values in range objects.

Specified by:

get­Element­Type in interface Checked­Container<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 interface Sorted­Set<E extends Comparable<? super E>>

clear

public void clear()

Removes all elements from this set of ranges.

Specified by:

clear in interface Collection<E extends Comparable<? super E>>

Specified by:

clear in interface Set<E extends Comparable<? super E>>

Overrides:

clear in class Abstract­Collection<Range<E extends Comparable<? super E>>>

size

public int size()

Returns the number of ranges in this set.

Specified by:

size in interface Collection<E extends Comparable<? super E>>

Specified by:

size in interface Set<E extends Comparable<? super E>>

Specified by:

size in class Abstract­Collection<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 of 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 is­Min­Included and is­Max­Included match the ones given to the constructor of this Range­Set, then delegates to add(Comparable, Comparable).

Specified by:

add in interface Collection<E extends Comparable<? super E>>

Specified by:

add in interface Set<E extends Comparable<? super E>>

Overrides:

add in class Abstract­Collection<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:

Illegal­Argument­Exception - if the is­Min­Included or is­Max­Included property does not match the one given at this Range­Set 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:

min­Value - the minimal value.

max­Value - the maximal value.

Returns:

true if this set changed as a result of this method call.

Throws:

Illegal­Argument­Exception - if min­Value is greater than max­Value.

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 of Range.subtract(Range). In other words, invoking this method may increase the size of this set.

The is­Min­Included and is­Max­Included properties of the given range shall be the complement of the ones given to the constructor of this Range­Set:

Expected bounds inclusion

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 is­Min­Included and is­Max­Included are consistent with the ones given to the constructor of this Range­Set, then delegates to remove(Comparable, Comparable).

Specified by:

remove in interface Collection<E extends Comparable<? super E>>

Specified by:

remove in interface Set<E extends Comparable<? super E>>

Overrides:

remove in class Abstract­Collection<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:

Illegal­Argument­Exception - if the is­Min­Included or is­Max­Included property is not the complement of the one given at this Range­Set 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:

min­Value - the minimal value.

max­Value - the maximal value.

Returns:

true if this set changed as a result of this method call.

Throws:

Illegal­Argument­Exception - if min­Value is greater than max­Value.

contains

public 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. If this method returns true, then:

• Invoking add(Range) is guaranteed to have no effect.
• Invoking remove(Object) is guaranteed to modify this set.

Conversely, if this method returns false, then:

• Invoking add(Range) is guaranteed to modify this set.
• Invoking 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.

The default implementation checks the type of the given object, then delegates to contains(object, false).

Specified by:

contains in interface Collection<E extends Comparable<? super E>>

Specified by:

contains in interface Set<E extends Comparable<? super E>>

Overrides:

contains in class Abstract­Collection<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.

contains

public boolean contains(Range<E> range,
 boolean exact)

Returns true if this set contains the specified element.

• If the 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).
• If the exact argument is false, then this method behaves as documented in the contains(Object) method.

Parameters:

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.

Returns:

true if the given object is contained in this set.

first

public Range<E> first()
               throws NoSuchElementException

Returns the first (lowest) range currently in this sorted set.

Specified by:

first in interface Sorted­Set<E extends Comparable<? super E>>

Throws:

No­Such­Element­Exception - 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 interface Sorted­Set<E extends Comparable<? super E>>

Throws:

No­Such­Element­Exception - 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 this Range­Set with the given range. Changes in this Range­Set will be reflected in the returned view, and conversely.

Parameters:

sub­Range - the range to intersect with this Range­Set.

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 from 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));

API note: This method takes the minimal value of the upper argument instead than the maximal value because the upper endpoint is exclusive.

Specified by:

sub­Set in interface Sorted­Set<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 than upper. The default implementation is equivalent to the same pseudo-code than the one documented in the sub­Set(Range, Range) method, except that the lower endpoint is null.

Specified by:

head­Set in interface Sorted­Set<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 to lower. The default implementation is equivalent to the same pseudo-code than the one documented in the sub­Set(Range, Range) method, except that the upper endpoint is null.

Specified by:

tail­Set in interface Sorted­Set<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 are Range objects.

Specified by:

iterator in interface Collection<E extends Comparable<? super E>>

Specified by:

iterator in interface Iterable<E extends Comparable<? super E>>

Specified by:

iterator in interface Set<E extends Comparable<? super E>>

Specified by:

iterator in class Abstract­Collection<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.

indexOfMin

public int indexOfMin(E value)

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

public int indexOfMax(E value)

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 returns size().

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

public long getMinLong(int index)
                throws IndexOutOfBoundsException,
ClassCastException

Returns a range minimum value as a 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.

Parameters:

index - the range index, from 0 inclusive to size exclusive.

Returns:

the minimum value for the range at the specified index.

Throws:

Index­Out­Of­Bounds­Exception - if index is out of bounds.

Class­Cast­Exception - if range elements are not convertible to long.

getMinDouble

public double getMinDouble(int index)
                    throws IndexOutOfBoundsException,
ClassCastException

Returns a range minimum value as a 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.

Parameters:

index - the range index, from 0 inclusive to size exclusive.

Returns:

the minimum value for the range at the specified index.

Throws:

Index­Out­Of­Bounds­Exception - if index is out of bounds.

Class­Cast­Exception - if range elements are not convertible to numbers.

See Also:

• Number­Range.get­Min­Double()

getMaxLong

public long getMaxLong(int index)
                throws IndexOutOfBoundsException,
ClassCastException

Returns a range maximum value as a 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.

Parameters:

index - the range index, from 0 inclusive to size exclusive.

Returns:

the maximum value for the range at the specified index.

Throws:

Index­Out­Of­Bounds­Exception - if index is out of bounds.

Class­Cast­Exception - if range elements are not convertible to long.

getMaxDouble

public double getMaxDouble(int index)
                    throws IndexOutOfBoundsException,
ClassCastException

Returns a range maximum value as a 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.

Parameters:

index - the range index, from 0 inclusive to size exclusive.

Returns:

the maximum value for the range at the specified index.

Throws:

Index­Out­Of­Bounds­Exception - if index is out of bounds.

Class­Cast­Exception - if range elements are not convertible to numbers.

See Also:

• Number­Range.get­Max­Double()

newRange

protected Range<E> newRange(E lower,
 E upper)

Returns a new Range 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 interface Collection<E extends Comparable<? super E>>

Specified by:

equals in interface Set<E extends Comparable<? super E>>

Overrides:

equals in class Abstract­Set<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

public RangeSet<E> clone()

Returns a clone of this range set.

Overrides:

clone in class Object

Returns:

a clone of this range set.