Class IntIterableRangeSet

  • All Implemented Interfaces:
    Iterable<Integer>, ISet, IntIterableSet

    public class IntIterableRangeSet
    extends Object
    implements IntIterableSet
    Concrete implementation of IntIterableSet wherein values are stored in range set. A range is made of two ints, the lower bound and the upper bound of the range. A range can be a singleton, in that case, the lb and the ub are equal. If the upper bound of range A is equal to lower bound of range B, then the two ranges can be merged into a single one.

    Project: choco.

    Since:
    14/01/2016.
    Author:
    Charles Prud'homme
    • Field Detail

      • ELEMENTS

        protected int[] ELEMENTS
        Store elements
      • SIZE

        protected int SIZE
        Used size in ELEMENTS. To get the number of range simply divide by 2.
      • CARDINALITY

        protected int CARDINALITY
        Total number of elements in the set
    • Constructor Detail

      • IntIterableRangeSet

        public IntIterableRangeSet()
        Create an interval-based ordered set
      • IntIterableRangeSet

        public IntIterableRangeSet​(int a,
                                   int b)
        Create an interval-based ordered set initialized to [a,b]
        Parameters:
        a - lower bound of the interval
        b - upper bound of the interval
      • IntIterableRangeSet

        public IntIterableRangeSet​(int e)
        Create an interval-based ordered set initialized to singleton {e}
        Parameters:
        e - singleton value
      • IntIterableRangeSet

        public IntIterableRangeSet​(int[] values)
        Create an interval-based ordered set initialized to an array of values
        Parameters:
        values - some values
    • Method Detail

      • toSmartString

        public String toSmartString()
      • getNbRanges

        public int getNbRanges()
        Returns:
        number of ranges in this
      • cardinality

        public int cardinality()
      • minOfRange

        public int minOfRange​(int r)
      • maxOfRange

        public int maxOfRange​(int r)
      • min

        public int min()
        Specified by:
        min in interface ISet
        Returns:
        the smallest element in the set throws an exception if the set is empty Time complexity is linear for BIPARTITESET and LINKED_LIST (constant time otherwise)
      • max

        public int max()
        Specified by:
        max in interface ISet
        Returns:
        the largest element in the set throws an exception if the set is empty Time complexity is linear for BIPARTITESET and LINKED_LIST (constant time otherwise)
      • add

        public boolean add​(int e)
        Description copied from interface: ISet
        Add element to the set
        Specified by:
        add in interface ISet
        Parameters:
        e - element to add
        Returns:
        true iff element was not in the set and has been added
      • addAll

        public boolean addAll​(int... values)
        Description copied from interface: IntIterableSet
        Adds all of the elements in the array to this set.
        Specified by:
        addAll in interface IntIterableSet
        Parameters:
        values - array containing elements to be added to this set
        Returns:
        true if this set changed as a result of the call
      • addAll

        public boolean addAll​(IntIterableSet set)
        Description copied from interface: IntIterableSet
        Adds all of the elements in the specified set to this set.
        Specified by:
        addAll in interface IntIterableSet
        Parameters:
        set - set containing elements to be added to this set
        Returns:
        true if this set changed as a result of the call
      • retainAll

        public boolean retainAll​(IntIterableSet set)
        Description copied from interface: IntIterableSet
        Retains only the elements in this set that are contained in the specified set. In other words, removes from this set all of its elements that are not contained in the specified set.
        Specified by:
        retainAll in interface IntIterableSet
        Parameters:
        set - set containing elements to be retained in this set
        Returns:
        true if this set changed as a result of the call
      • remove

        public boolean remove​(int e)
        Description copied from interface: ISet
        Remove the first occurrence of element from the set
        Specified by:
        remove in interface ISet
        Parameters:
        e - element to add
        Returns:
        true iff element was in the set and has been removed
      • removeAll

        public boolean removeAll​(IntIterableSet set)
        Description copied from interface: IntIterableSet
        Removes all of this set's elements that are also contained in the specified set. After this call returns, this set will contain no elements in common with the specified set.
        Specified by:
        removeAll in interface IntIterableSet
        Parameters:
        set - set containing elements to be removed from this set
        Returns:
        true if this set changed as a result of the call
      • clear

        public void clear()
        Description copied from interface: ISet
        Remove all elements from the set
        Specified by:
        clear in interface ISet
      • getSetType

        public SetType getSetType()
        Specified by:
        getSetType in interface ISet
        Returns:
        the implementation type of this set
      • addBetween

        public boolean addBetween​(int a,
                                  int b)
      • removeBetween

        public boolean removeBetween​(int f,
                                     int t)
        Description copied from interface: IntIterableSet
        Removes all values between f (inclusive) and t (inclusive)
        Specified by:
        removeBetween in interface IntIterableSet
        Parameters:
        f - first value to remove
        t - last value to remove
        Returns:
        true if this set changed as a result of the call
      • retainBetween

        public boolean retainBetween​(int f,
                                     int t)
      • nextValueOut

        public int nextValueOut​(int e)
        Specified by:
        nextValueOut in interface IntIterableSet
        Parameters:
        e - (exclusive)
        Returns:
        the value outside thisn after 'aValue'
      • previousValueOut

        public int previousValueOut​(int e)
        Specified by:
        previousValueOut in interface IntIterableSet
        Parameters:
        e - (exclusive)
        Returns:
        the value outside this, before'aValue'
      • contains

        public boolean contains​(int o)
        Description copied from interface: ISet
        Test the existence of element in the set
        Specified by:
        contains in interface ISet
        Parameters:
        o - element to add
        Returns:
        true iff the set contains element
      • size

        public int size()
        Specified by:
        size in interface ISet
        Returns:
        the number of elements in the set
      • newIterator

        public ISetIterator newIterator()
        Description copied from interface: ISet
        Creates a new iterator object, for nested loops only.
        Specified by:
        newIterator in interface ISet
        Returns:
        a new iterator for this set
      • plus

        public void plus​(int x)
        add the value x to all integers stored in this set
        Specified by:
        plus in interface IntIterableSet
        Parameters:
        x - value to add
      • iterator

        public ISetIterator iterator()
        Description copied from interface: ISet
        Use the following loop to iterate over this set without autoboxing. // more readable but with autoboxing for(int value:set){ ... } // more verbose but without autoboxing ISetIterator iter = set.primitiveIterator(); while(iter.hasNext()){ int k = iter.next(); ... } Do not use this iterator to make nested loops over ISet (prefer ISet.newIterator())
        Specified by:
        iterator in interface ISet
        Specified by:
        iterator in interface Iterable<Integer>
        Returns:
        the default iterator (singleton) of this set
      • minus

        public void minus​(int x)
        subtract the value x to all integers stored in this set
        Specified by:
        minus in interface IntIterableSet
        Parameters:
        x - value to add
      • times

        public void times​(int x)
        multiply by x to all integers stored in this set
        Parameters:
        x - value to add
      • rangeOf

        public int rangeOf​(int x)
        By convention, range are numbered starting from 1 (not 0).
        Parameters:
        x - a value
        Returns:
        the range index if the value is in the set or -range point - 1 otherwise where range point corresponds to the range directly greater than the key
      • rangeOf

        protected int rangeOf​(int x,
                              int fromIndex,
                              int toIndex)
        By convention, range are numbered starting from 1 (not 0).
        Parameters:
        x - a value
        Returns:
        the range index if the value is in the set or -range point - 1 otherwise where range point corresponds to the range directly greater than the key
      • compact

        public void compact()
        Compact the array in memory
      • flip

        public IntIterableRangeSet flip()
        Turn this into the complement of this. calling :
        set.flip().flip()
        goes back to the original set.
        Returns:
        this turned into its complement, based on MIN and MAX
      • flip

        public IntIterableRangeSet flip​(int lb,
                                        int ub)
        Turn this into the complement of this. calling :
        set.flip().flip()
        goes back to the original set.
        Returns:
        this turned into its complement, based on lb, ub
      • forEachValueIn

        public void forEachValueIn​(IntConsumer c)
        Apply the operation c on each value in this set
        Parameters:
        c - an operation
      • forEachValueOut

        public void forEachValueOut​(IntConsumer c)
        Apply the operation c on each value in : ]min(), max()[ \ this set.
        Parameters:
        c - an operation
      • toArray

        public int[] toArray()
        Description copied from interface: ISet
        Copies the set in an array if integers
        Specified by:
        toArray in interface ISet
        Returns:
        an array containing all of the elements in this set in sorted sequence