Class RangeSet


  • public class RangeSet
    extends java.lang.Object
    Class for dealing with sets of integer ranges. Ranges are described by the first element and the one-past-last element. This code was inspired by Jan Kotek's "LongRangeSet" class, but has been completely reimplemented.
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static interface  RangeSet.ValueIterator
      Interface describing an iterator for going through all values in a RangeSet object.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected long[] r
      Sorted list of interval boundaries.
      protected int sz
      Current number of active entries.
    • Constructor Summary

      Constructors 
      Constructor Description
      RangeSet()
      Construct new object with initial space for 4 ranges.
      RangeSet​(int cap)
      Construct new object with initial capacity for a given number of ranges.
      RangeSet​(long[] data)
      Construct new object from an array of longs.
      RangeSet​(RangeSet other)
      Construct new object from another RangeSet
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods Deprecated Methods 
      Modifier and Type Method Description
      void add​(long a)
      After this operation, the RangeSet contains the union of itself and [a;a+1[.
      void add​(long a, long b)
      After this operation, the RangeSet contains the union of itself and [a;b[.
      void append​(long val)
      Append a single-value range to the object.
      void append​(long a, long b)
      Append a range to the object.
      void append​(RangeSet other)
      Append an entire range set to the object.
      void checkConsistency()
      Checks the object for internal consistency.
      void clear()
      Remove all entries in the set.
      boolean contains​(long a)
      Returns true if a is contained in the set, else false.
      boolean contains​(long a, long b)
      Returns true if all numbers [a;b[ are contained in the set, else false.
      boolean contains​(RangeSet other)
      Returns true if the set completely contains "other", else false.
      boolean containsAll​(long a, long b)
      Deprecated.
      boolean containsAll​(RangeSet other)
      Deprecated.
      boolean containsAny​(long a, long b)
      Deprecated.
      boolean containsAny​(RangeSet other)
      Deprecated.
      RangeSet difference​(RangeSet other)
      Return the difference of this RangeSet and other.
      void ensureCapacity​(int cap)
      Make sure the object can hold at least the given number of entries.
      boolean equals​(java.lang.Object obj)
      Returns true the object represents an identical set of ranges as obj.
      static RangeSet fromArray​(long[] v)  
      static RangeSet fromCompressed​(byte[] data)
      Returns a RangeSet obtained by decompressing a byte array which was originally generated by toCompressed().
      int hashCode()  
      void intersect​(long a, long b)
      After this operation, the RangeSet contains the intersection of itself and [a;b[.
      RangeSet intersection​(RangeSet other)
      Return the intersection of this RangeSet and other.
      boolean isEmpty()  
      long ivbegin​(int iv)  
      long ivend​(int iv)  
      int nranges()  
      long nval()  
      boolean overlaps​(long a, long b)
      Returns true if any of the numbers [a;b[ are contained in the set, else false.
      boolean overlaps​(RangeSet other)
      Returns true if there is overlap between the set and "other", else false.
      void remove​(long a)
      After this operation, the RangeSet contains the difference of itself and [a;a+1[.
      void remove​(long a, long b)
      After this operation, the RangeSet contains the difference of itself and [a;b[.
      long[] toArray()
      Creates an array containing all the numbers in the RangeSet.
      byte[] toCompressed()
      Returns a compressed representation of the RangeSet, using interpolative coding.
      java.lang.String toString()  
      void trimIfTooLarge()
      Shrinks the array for the entries to minimum size, if it is more than twice the minimum size
      void trimSize()
      Shrinks the array for the entries to minimum size.
      RangeSet union​(RangeSet other)
      Return the union of this RangeSet and other.
      RangeSet.ValueIterator valueIterator()
      Returns a ValueIterator, which iterates over all individual numbers in the RangeSet.
      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait
    • Field Detail

      • r

        protected long[] r
        Sorted list of interval boundaries.
      • sz

        protected int sz
        Current number of active entries.
    • Constructor Detail

      • RangeSet

        public RangeSet()
        Construct new object with initial space for 4 ranges.
      • RangeSet

        public RangeSet​(int cap)
        Construct new object with initial capacity for a given number of ranges.
        Parameters:
        cap - number of initially reserved ranges.
      • RangeSet

        public RangeSet​(long[] data)
        Construct new object from an array of longs.
        Parameters:
        data -
      • RangeSet

        public RangeSet​(RangeSet other)
        Construct new object from another RangeSet
        Parameters:
        other -
    • Method Detail

      • checkConsistency

        public void checkConsistency()
        Checks the object for internal consistency. If a problem is detected, an IllegalArgumentException is thrown.
      • ensureCapacity

        public void ensureCapacity​(int cap)
        Make sure the object can hold at least the given number of entries.
      • trimSize

        public void trimSize()
        Shrinks the array for the entries to minimum size.
      • trimIfTooLarge

        public void trimIfTooLarge()
        Shrinks the array for the entries to minimum size, if it is more than twice the minimum size
      • append

        public void append​(long val)
        Append a single-value range to the object.
        Parameters:
        val - value to append
      • append

        public void append​(long a,
                           long b)
        Append a range to the object.
        Parameters:
        a - first long in range
        b - one-after-last long in range
      • append

        public void append​(RangeSet other)
        Append an entire range set to the object.
      • nranges

        public int nranges()
        Returns:
        number of ranges in the set.
      • isEmpty

        public boolean isEmpty()
        Returns:
        true if no entries are stored, else false.
      • ivbegin

        public long ivbegin​(int iv)
        Returns:
        first number in range iv.
      • ivend

        public long ivend​(int iv)
        Returns:
        one-past-last number in range iv.
      • clear

        public void clear()
        Remove all entries in the set.
      • union

        public RangeSet union​(RangeSet other)
        Return the union of this RangeSet and other.
      • intersection

        public RangeSet intersection​(RangeSet other)
        Return the intersection of this RangeSet and other.
      • difference

        public RangeSet difference​(RangeSet other)
        Return the difference of this RangeSet and other.
      • contains

        public boolean contains​(long a)
        Returns true if a is contained in the set, else false.
      • contains

        public boolean contains​(long a,
                                long b)
        Returns true if all numbers [a;b[ are contained in the set, else false.
      • containsAll

        @Deprecated
        public boolean containsAll​(long a,
                                   long b)
        Deprecated.
      • overlaps

        public boolean overlaps​(long a,
                                long b)
        Returns true if any of the numbers [a;b[ are contained in the set, else false.
      • containsAny

        @Deprecated
        public boolean containsAny​(long a,
                                   long b)
        Deprecated.
      • contains

        public boolean contains​(RangeSet other)
        Returns true if the set completely contains "other", else false.
      • containsAll

        @Deprecated
        public boolean containsAll​(RangeSet other)
        Deprecated.
      • overlaps

        public boolean overlaps​(RangeSet other)
        Returns true if there is overlap between the set and "other", else false.
      • containsAny

        @Deprecated
        public boolean containsAny​(RangeSet other)
        Deprecated.
      • equals

        public boolean equals​(java.lang.Object obj)
        Returns true the object represents an identical set of ranges as obj.
        Overrides:
        equals in class java.lang.Object
      • hashCode

        public int hashCode()
        Overrides:
        hashCode in class java.lang.Object
      • nval

        public long nval()
        Returns:
        total number of values (not ranges) in the set.
      • intersect

        public void intersect​(long a,
                              long b)
        After this operation, the RangeSet contains the intersection of itself and [a;b[.
      • add

        public void add​(long a,
                        long b)
        After this operation, the RangeSet contains the union of itself and [a;b[.
      • add

        public void add​(long a)
        After this operation, the RangeSet contains the union of itself and [a;a+1[.
      • remove

        public void remove​(long a,
                           long b)
        After this operation, the RangeSet contains the difference of itself and [a;b[.
      • remove

        public void remove​(long a)
        After this operation, the RangeSet contains the difference of itself and [a;a+1[.
      • toArray

        public long[] toArray()
        Creates an array containing all the numbers in the RangeSet. Not recommended, because the arrays can become prohibitively large. It is preferrable to use a ValueIterator or explicit loops.
      • fromArray

        public static RangeSet fromArray​(long[] v)
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • valueIterator

        public RangeSet.ValueIterator valueIterator()
        Returns a ValueIterator, which iterates over all individual numbers in the RangeSet.
      • toCompressed

        public byte[] toCompressed()
                            throws java.lang.Exception
        Returns a compressed representation of the RangeSet, using interpolative coding.
        Throws:
        java.lang.Exception
      • fromCompressed

        public static RangeSet fromCompressed​(byte[] data)
                                       throws java.lang.Exception
        Returns a RangeSet obtained by decompressing a byte array which was originally generated by toCompressed().
        Throws:
        java.lang.Exception