Package org.apache.sis.util.collection

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

java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<Range<E>>
org.apache.sis.util.collection.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>>
Direct Known Subclasses:
RangeSet.Numeric
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.

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

Since:
0.3
Version:
0.5
See Also:

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      Serial number for inter-operability with different versions.
      See Also:

    • 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:

    • elementCode

      private final byte elementCode
      The primitive type, as one of DOUBLE, FLOAT, LONG, INTEGER, SHORT, BYTE, CHARACTER enumeration. If the elementType is not the wrapper of a primitive type, then this field value is OTHER.

    • 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:

    • 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:

    • array

      private Object array
      The array of ranges. It may be either an array of Java primitive type like int[] or float[], or an array of Comparable elements. All elements at even indices are minimal values, and all elements at odd indices are maximal values. Elements in this array must be strictly increasing without duplicated values.
      Note: The restriction against duplicated values will need to be removed in a future version if we want to support open intervals. All binary searches in this class will need to take in account the possibility for duplicated values.

    • length

      private transient int length
      The length of valid elements in the array. Since the array contains both the minimum and maximum values, its length is twice the number of ranges in this set.
      See Also:

    • modCount

      private transient int modCount
      The amount of modifications applied on the range array. Used for checking concurrent modifications.

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

    • reallocate

      private void reallocate()
      Unconditionally copies the internal array in a new array having just the required length.

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

    • insertAt

      private void insertAt(int lower, E minValue, E maxValue)
      Inserts two values at the given index. The underlying array shall be non-null before this method is invoked. This method increases the array size as needed.
      Parameters:
      lower - the index where to insert the values.
      minValue - the first value to insert.
      maxValue - the second value to insert.

    • removeAt

      private void removeAt(int lower, int upper)
      Removes the values in the given range. The underlying array shall be non-null before this method is invoked.
      Parameters:
      lower - first value to remove, inclusive.
      upper - last value to remove, exclusive.

    • isSorted

      private boolean isSorted()
      Returns true if the element in the array are sorted. This method is used for assertions only. The array shall be trimmed to size before this method is invoked.

    • binarySearch

      final int binarySearch(E value, int lower, int upper)
      Returns the index of value in array. This method delegates to one of Arrays.binarySearch methods, depending on element primary type.
      Parameters:
      value - the value to search.
      lower - index of the first value to examine.
      upper - index after the last value to examine.

    • ensureOrdered

      private static <E extends Comparable<? super E>> void ensureOrdered(E minValue, E maxValue)
      Ensures that the given minimum value is not greater than the maximum value. This method is used for argument checks.

    • 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: 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):
      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:

    • 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:

    • 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:

    • 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:

    • 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:

    • getValue

      final E getValue(int index)
      Returns the value at the specified index. Even index are lower endpoints, while odd index are upper endpoints. The index validity must have been checked before this method is invoked.

    • getRange

      final Range<E> getRange(int index)
      Returns the range at the given array index. The given index is relative to the interval array, which is twice the index of range elements.
      Parameters:
      index - the range index, from 0 inclusive to length exclusive.

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

    • writeObject

      private void writeObject(ObjectOutputStream out) throws IOException
      Invoked before serialization. Trims the internal array to the minimal size in order to reduce the size of the object to be serialized.
      Parameters:
      out - the output stream where to serialize this range set.
      Throws:
      IOException - if an I/O error occurred while writing.

    • readObject

      private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException
      Invoked after deserialization. Initializes the transient fields.
      Parameters:
      in - the input stream from which to deserialize a range set.
      Throws:
      IOException - if an I/O error occurred while reading or if the stream contains invalid data.
      ClassNotFoundException - if the class serialized on the stream is not on the classpath.