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 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.

  - ### Constructor Summary

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

  - ### Method Summary

    All Methods Static Methods Instance Methods Concrete Methods
    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.
    `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.

    - ### 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 Detail

    - #### 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 Detail

    - #### 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 Detail

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