Package org.apache.sis.util.collection

# 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. 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 `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 of `Range​.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 of `Range​.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.
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 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)` 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.

## 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 `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 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 final Class<E>`
  `elementType`
  The type of elements in the ranges.
  `protected final boolean`
  `isMaxIncluded`
  `true` if the maximal values of ranges in this set are inclusive, or `false` if exclusive.
  `protected final boolean`
  `isMinIncluded`
  `true` if the minimal values of ranges in this set are inclusive, or `false` if exclusive.

- ## Constructor Summary

  Constructors
  Modifier
  Constructor
  Description
  `protected`
  `RangeSet(Class<E> elementType, boolean isMinIncluded, boolean isMaxIncluded)`
  Constructs an initially empty set of ranges.

- ## Method Summary

  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)`
  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>>
  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.
  `final 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`.
  `final 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 class Object

  `finalize, getClass, notify, notifyAll, wait, wait, wait`

  ### Methods inherited from interface Collection

  `parallelStream, removeIf, stream, toArray`

  ### Methods inherited from interface Iterable

  `forEach`

  ### Methods inherited from interface Set

  `addAll, containsAll, hashCode, isEmpty, removeAll, retainAll, toArray, toArray`

  ### Methods inherited from interface SortedSet

  `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​.getElementType()`

  - ### 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​.isMinIncluded()`

  - ### 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​.isMaxIncluded()`

- ## 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:
      `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.

- ## 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, or `false` if exclusive.
      `isMaxIncluded` - `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:
      `getElementType` in interface `CheckedContainer<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 `SortedSet<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 `AbstractCollection<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 `AbstractCollection<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 `isMinIncluded` and `isMaxIncluded` match the ones given to the constructor of this `RangeSet`, 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 `AbstractCollection<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 the `isMinIncluded` or `isMaxIncluded` property does not match the one given at this `RangeSet` 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` - if `minValue` is greater than `maxValue`.

  - ### 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 `isMinIncluded` and `isMaxIncluded` properties of the given range shall be the complement of the ones given to the constructor of this `RangeSet`:

    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 `isMinIncluded` and `isMaxIncluded` are consistent with the ones given to the constructor of this `RangeSet`, 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 `AbstractCollection<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 the `isMinIncluded` or `isMaxIncluded` property is not the complement of the one given at this `RangeSet` 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` - if `minValue` is greater than `maxValue`.

  - ### 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 `AbstractCollection<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 `SortedSet<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 interface `SortedSet<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 this `RangeSet` with the given range. Changes in this `RangeSet` will be reflected in the returned view, and conversely.
    Parameters:
      `subRange` - the range to intersect with this `RangeSet`.
    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:
      `subSet` in interface `SortedSet<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 `subSet(Range, Range)` method, except that the lower endpoint is `null`.
    Specified by:
      `headSet` in interface `SortedSet<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 `subSet(Range, Range)` method, except that the upper endpoint is `null`.
    Specified by:
      `tailSet` in interface `SortedSet<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 `AbstractCollection<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 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, inclusive.
    Throws:
      `IndexOutOfBoundsException` - if `index` is out of bounds.
      `ClassCastException` - 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, inclusive.
    Throws:
      `IndexOutOfBoundsException` - if `index` 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 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, inclusive.
    Throws:
      `IndexOutOfBoundsException` - if `index` is out of bounds.
      `ClassCastException` - 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, exclusive.
    Throws:
      `IndexOutOfBoundsException` - if `index` 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 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 `AbstractSet<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.