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

Type Parameters:
E - the type of range elements.
All Implemented Interfaces:
Serializable, Cloneable, Iterable<Range<E>>, Collection<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.
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 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.

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

Since:
0.3
See Also:

Defined in the sis-utility module

  • 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:
    • 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:
  • 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: 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:
    • 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:
    • 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:
    • 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.
    • 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:
      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, inclusive.
      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:
    • 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:
      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, exclusive.
      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:
    • 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.