Class EliasFanoIndexedMonotoneLongBigList

    • Constructor Summary

      Constructors 
      Constructor Description
      EliasFanoIndexedMonotoneLongBigList​(long n, long upperBound, it.unimi.dsi.fastutil.bytes.ByteIterator iterator)
      Creates an indexed Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.
      EliasFanoIndexedMonotoneLongBigList​(long n, long upperBound, it.unimi.dsi.fastutil.ints.IntIterator iterator)
      Creates an indexed Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.
      EliasFanoIndexedMonotoneLongBigList​(long n, long upperBound, it.unimi.dsi.fastutil.longs.LongIterator iterator)
      Creates an indexed Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.
      EliasFanoIndexedMonotoneLongBigList​(long n, long upperBound, it.unimi.dsi.fastutil.shorts.ShortIterator iterator)
      Creates an indexed Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.
      EliasFanoIndexedMonotoneLongBigList​(it.unimi.dsi.fastutil.bytes.ByteIterable list)
      Creates an indexed Elias–Fano representation of the values returned by the given iterable object.
      EliasFanoIndexedMonotoneLongBigList​(it.unimi.dsi.fastutil.ints.IntIterable list)
      Creates an indexed Elias–Fano representation of the values returned by the given iterable object.
      EliasFanoIndexedMonotoneLongBigList​(it.unimi.dsi.fastutil.longs.LongIterable list)
      Creates an indexed Elias–Fano representation of the values returned by the given iterable object.
      EliasFanoIndexedMonotoneLongBigList​(it.unimi.dsi.fastutil.shorts.ShortIterable list)
      Creates an indexed Elias–Fano representation of the values returned by the given iterable object.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean contains​(long x)
      Returns true if the sequence contains the specified element.
      long index()
      long indexOf​(long x)
      Returns the index of the first occurrence of the specified element in the sequence, or −1 if the element does not belong to the sequence.
      long indexOfUnsafe​(long x)
      Returns the index of the first occurrence of the specified element in the sequence, or −1 if the element does not belong to the sequence.
      EliasFanoIndexedMonotoneLongBigList.EliasFanoIndexedMonotoneLongBigListIterator iterator()
      Returns a list iterator over the values of this EliasFanoMonotoneLongBigList.
      EliasFanoIndexedMonotoneLongBigList.EliasFanoIndexedMonotoneLongBigListIterator listIterator()
      Returns a list iterator over the values of this EliasFanoMonotoneLongBigList.
      EliasFanoIndexedMonotoneLongBigList.EliasFanoIndexedMonotoneLongBigListIterator listIterator​(long from)
      Returns a list iterator over the values of this EliasFanoMonotoneLongBigList.
      long predecessor​(long upperBound)
      Returns the last element of the sequence that is less than the provided bound.
      long predecessorIndex​(long upperBound)
      Returns the index of the last element of the sequence that is less than the provided bound.
      long predecessorIndexUnsafe​(long upperBound)
      Returns the index of the last element of the sequence that is less than the provided bound.
      long predecessorUnsafe​(long upperBound)
      Returns the last element of the sequence that is less than the provided bound.
      long strictSuccessor​(long lowerBound)
      Returns the first element of the sequence that is greater than the provided bound.
      long strictSuccessorIndex​(long lowerBound)
      Returns the index of first element of the sequence that is greater than the provided bound.
      long strictSuccessorIndexUnsafe​(long lowerBound)
      Returns the index of first element of the sequence that is greater than the provided bound.
      long strictSuccessorUnsafe​(long lowerBound)
      Returns the first element of the sequence that is greater than the provided bound.
      long successor​(long lowerBound)
      Returns the first element of the sequence that is greater than or equal to the provided bound.
      long successorIndex​(long lowerBound)
      Returns the index of first element of the sequence that is greater than or equal to the provided bound.
      long successorIndexUnsafe​(long lowerBound)
      Returns the index of first element of the sequence that is greater than or equal to the provided bound.
      long successorUnsafe​(long lowerBound)
      Returns the first element of the sequence that is greater than or equal to the provided bound.
      long weakPredecessor​(long upperBound)
      Returns the last element of the sequence that is less than or equal to the provided bound.
      long weakPredecessorIndex​(long upperBound)
      Returns the index of the last element of the sequence that is less than or equal to the provided bound.
      long weakPredecessorIndexUnsafe​(long upperBound)
      Returns the index of the last element of the sequence that is less than or equal to the provided bound.
      long weakPredecessorUnsafe​(long upperBound)
      Returns the last element of the sequence that is less than or equal to the provided bound.
      • Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongBigList

        add, add, add, addAll, addAll, addAll, addAll, addElements, addElements, clear, compareTo, ensureIndex, ensureRestrictedIndex, equals, forEach, get, getElements, hashCode, indexOf, lastIndexOf, lastIndexOf, peek, peekLong, pop, popLong, push, push, rem, remove, removeElements, removeLong, set, set, setElements, size, size, subList, top, topLong, toString
      • Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongCollection

        add, contains, containsAll, containsAll, forEach, remove, removeAll, removeAll, removeIf, retainAll, retainAll, toArray, toLongArray, toLongArray
      • Methods inherited from class java.util.AbstractCollection

        isEmpty, toArray, toArray
      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Collection

        containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toArray
      • Methods inherited from interface it.unimi.dsi.fastutil.longs.LongBigList

        addAll, addAll, addAll, addAll, getElements, setElements, setElements, spliterator
      • Methods inherited from interface it.unimi.dsi.fastutil.longs.LongCollection

        add, contains, containsAll, longIterator, longParallelStream, longSpliterator, longStream, parallelStream, remove, removeAll, removeIf, removeIf, removeIf, retainAll, stream, toArray, toLongArray, toLongArray
      • Methods inherited from interface it.unimi.dsi.fastutil.longs.LongIterable

        forEach, forEach
      • Methods inherited from interface it.unimi.dsi.fastutil.Stack

        isEmpty
    • Field Detail

      • selectUpperZero

        protected final SimpleSelectZero selectUpperZero
        The select structure used to extract the upper bits.
    • Constructor Detail

      • EliasFanoIndexedMonotoneLongBigList

        public EliasFanoIndexedMonotoneLongBigList​(it.unimi.dsi.fastutil.ints.IntIterable list)
        Creates an indexed Elias–Fano representation of the values returned by the given iterable object.
        Parameters:
        list - an iterable object returning nondecreasing natural numbers.
      • EliasFanoIndexedMonotoneLongBigList

        public EliasFanoIndexedMonotoneLongBigList​(it.unimi.dsi.fastutil.shorts.ShortIterable list)
        Creates an indexed Elias–Fano representation of the values returned by the given iterable object.
        Parameters:
        list - an iterable object returning nondecreasing natural numbers.
      • EliasFanoIndexedMonotoneLongBigList

        public EliasFanoIndexedMonotoneLongBigList​(it.unimi.dsi.fastutil.bytes.ByteIterable list)
        Creates an indexed Elias–Fano representation of the values returned by the given iterable object.
        Parameters:
        list - an iterable object returning nondecreasing natural numbers.
      • EliasFanoIndexedMonotoneLongBigList

        public EliasFanoIndexedMonotoneLongBigList​(it.unimi.dsi.fastutil.longs.LongIterable list)
        Creates an indexed Elias–Fano representation of the values returned by the given iterable object.
        Parameters:
        list - an iterable object returning nondecreasing natural numbers.
      • EliasFanoIndexedMonotoneLongBigList

        public EliasFanoIndexedMonotoneLongBigList​(long n,
                                                   long upperBound,
                                                   it.unimi.dsi.fastutil.bytes.ByteIterator iterator)
        Creates an indexed Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.

        This constructor is particularly useful if the elements of the iterator are provided by some sequential source.

        Parameters:
        n - the number of elements returned by iterator.
        upperBound - an upper bound to the values returned by iterator.
        iterator - an iterator returning nondecreasing natural numbers.
      • EliasFanoIndexedMonotoneLongBigList

        public EliasFanoIndexedMonotoneLongBigList​(long n,
                                                   long upperBound,
                                                   it.unimi.dsi.fastutil.ints.IntIterator iterator)
        Creates an indexed Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.

        This constructor is particularly useful if the elements of the iterator are provided by some sequential source.

        Parameters:
        n - the number of elements returned by iterator.
        upperBound - an upper bound to the values returned by iterator.
        iterator - an iterator returning nondecreasing natural numbers.
      • EliasFanoIndexedMonotoneLongBigList

        public EliasFanoIndexedMonotoneLongBigList​(long n,
                                                   long upperBound,
                                                   it.unimi.dsi.fastutil.longs.LongIterator iterator)
        Creates an indexed Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.

        This constructor is particularly useful if the elements of the iterator are provided by some sequential source.

        Parameters:
        n - the number of elements returned by iterator.
        upperBound - an upper bound to the values returned by iterator.
        iterator - an iterator returning nondecreasing natural numbers.
      • EliasFanoIndexedMonotoneLongBigList

        public EliasFanoIndexedMonotoneLongBigList​(long n,
                                                   long upperBound,
                                                   it.unimi.dsi.fastutil.shorts.ShortIterator iterator)
        Creates an indexed Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.

        This constructor is particularly useful if the elements of the iterator are provided by some sequential source.

        Parameters:
        n - the number of elements returned by iterator.
        upperBound - an upper bound to the values returned by iterator.
        iterator - an iterator returning nondecreasing natural numbers.
    • Method Detail

      • successor

        public long successor​(long lowerBound)
        Returns the first element of the sequence that is greater than or equal to the provided bound. If such an element exists, its position in the sequence can be retrieved using index().
        Parameters:
        lowerBound - a lower bound on the returned value.
        Returns:
        the first element of the sequence that is greater than or equal to lowerBound, or Long.MAX_VALUE if no such element exists, in which case index() will return the list length.
        See Also:
        strictSuccessor(long), successorUnsafe(long)
      • successorUnsafe

        public long successorUnsafe​(long lowerBound)
        Returns the first element of the sequence that is greater than or equal to the provided bound. If such an element exists, its position in the sequence can be retrieved using index().

        This method is slightly faster than successor(long), but it has a restricted argument range and it does perform bound checks.

        Parameters:
        lowerBound - a nonnegative lower bound on the returned value; must be smaller than or equal to the upper bound provided at construction time.
        Returns:
        the first element of the sequence that is greater than or equal to lowerBound; if lowerBound is greater than the last element of the sequence, this method returns the upper bound provided at construction time and index() is set to the length of this list; if lowerBound is out of bounds, behavior is undefined.
        See Also:
        successor(long)
      • successorIndex

        public long successorIndex​(long lowerBound)
        Returns the index of first element of the sequence that is greater than or equal to the provided bound.

        This method is significantly faster than successor(long), as it does not have to compute the actual successor; moreover, it does not change the return value of index().

        Parameters:
        lowerBound - a lower bound on the returned value.
        Returns:
        the index of the first element of the sequence that is greater than or equal to lowerBound, or the length of this list if no such element exists.
        See Also:
        successor(long), successorIndexUnsafe(long)
      • successorIndexUnsafe

        public long successorIndexUnsafe​(long lowerBound)
        Returns the index of first element of the sequence that is greater than or equal to the provided bound.

        This method is slightly faster than successorIndexUnsafe(long), but it has a restricted argument range and it does perform bound checks.

        This method is significantly faster than successorUnsafe(long), as it does not have to compute the actual successor; moreover, it does not change the return value of index().

        Parameters:
        lowerBound - a nonnegative lower bound on the returned value; must be smaller than or equal to the upper bound provided at construction time.
        Returns:
        the index of the first element of the sequence that is greater than or equal to lowerBound; if lowerBound is greater than the last element of the sequence, this method the length of this list; if lowerBound is out of bounds, behavior is undefined.
        See Also:
        successorIndex(long)
      • strictSuccessor

        public long strictSuccessor​(long lowerBound)
        Returns the first element of the sequence that is greater than the provided bound. If such an element exists, its position in the sequence can be retrieved using index().

        If such an element exists, its position in the sequence can be retrieved using index().

        Parameters:
        lowerBound - a lower bound on the returned value.
        Returns:
        the first element of the sequence that is greater than lowerBound, or Long.MAX_VALUE if no such element exists, in which case index() will return the list length.
        See Also:
        successor(long), strictSuccessorUnsafe(long)
      • strictSuccessorUnsafe

        public long strictSuccessorUnsafe​(long lowerBound)
        Returns the first element of the sequence that is greater than the provided bound. If such an element exists, its position in the sequence can be retrieved using index().

        This method is slightly faster than strictSuccessor(long), but it has a restricted argument range and it does perform bound checks.

        Parameters:
        lowerBound - a nonnegative lower bound on the returned value; must be smaller than the upper bound provided at construction time.
        Returns:
        the first element of the sequence that is greater than lowerBound, or the upper bound provided at construction timeif no such element exists; in that case, index() is set to the length of the sequence; if lowerBound is out of bounds, behavior is undefined.
        See Also:
        strictSuccessor(long)
      • strictSuccessorIndex

        public long strictSuccessorIndex​(long lowerBound)
        Returns the index of first element of the sequence that is greater than the provided bound.

        This method is significantly faster than strictSuccessor(long), as it does not have to compute the actual strict successor; moreover, it does not change the return value of index().

        Parameters:
        lowerBound - a lower bound on the returned value.
        Returns:
        the index of the first element of the sequence that is greater than lowerBound, or the length of the sequence if no such element exists.
        See Also:
        strictSuccessor(long), strictSuccessorIndexUnsafe(long)
      • strictSuccessorIndexUnsafe

        public long strictSuccessorIndexUnsafe​(long lowerBound)
        Returns the index of first element of the sequence that is greater than the provided bound.

        This method is slightly faster than strictSuccessorIndex(long), but it has a restricted argument range and it does perform bound checks.

        This method is significantly faster than strictSuccessorUnsafe(long), as it does not have to compute the actual strict successor; moreover, it does not change the return value of index().

        Parameters:
        lowerBound - a nonnegative lower bound on the returned value; must be smaller than the upper bound provided at construction time.
        Returns:
        the index of first element of the sequence that is greater than lowerBound, or the length of the sequence if no such element exists; if lowerBound is out of bounds, behavior is undefined.
        See Also:
        strictSuccessorIndex(long)
      • predecessor

        public long predecessor​(long upperBound)
        Returns the last element of the sequence that is less than the provided bound. If such an element exists, its position in the sequence can be retrieved using index().
        Parameters:
        upperBound - a strict upper bound on the returned value.
        Returns:
        the last element of the sequence that is less than upperBound, or −1 if no such element exists, in which case index() will return −1.
        See Also:
        weakPredecessor(long), predecessorUnsafe(long)
      • predecessorUnsafe

        public long predecessorUnsafe​(long upperBound)
        Returns the last element of the sequence that is less than the provided bound. If such an element exists, its position in the sequence can be retrieved using index().

        This method is slightly faster than predecessor(long), but it has a restricted argument range and it does perform bound checks.

        Parameters:
        upperBound - a nonnegative strict upper bound on the returned value, greater than the first element of the sequence and smaller than or equal to the upper bound provided at construction time.
        Returns:
        the last element of the sequence that is less than upperBound; if upperBound is out of bounds, behavior is undefined.
        See Also:
        predecessor(long)
      • predecessorIndex

        public long predecessorIndex​(long upperBound)
        Returns the index of the last element of the sequence that is less than the provided bound.

        This method is significantly faster than predecessor(long), as it does not have to compute the actual predecessor; moreover, it does not change the return value of index().

        Parameters:
        upperBound - an upper bound on the returned value.
        Returns:
        the index of the last element of the sequence that is less than upperBound, or −1 if no such element exists.
        See Also:
        predecessor(long), predecessorIndexUnsafe(long)
      • predecessorIndexUnsafe

        public long predecessorIndexUnsafe​(long upperBound)
        Returns the index of the last element of the sequence that is less than the provided bound.

        This method is slightly faster than predecessorIndex(long), but it has a restricted argument range and it does perform bound checks.

        This method is significantly faster than predecessorUnsafe(long), as it does not have to compute the actual predecessor; moreover, it does not change the return value of index().

        Parameters:
        upperBound - a nonnegative strict upper bound on the returned value, greater than the first element of the sequence and smaller than or equal to the upper bound provided at construction time.
        Returns:
        the index of the last element of the sequence that is less than upperBound; if upperBound is out of bounds, behavior is undefined.
        See Also:
        predecessorIndex(long)
      • weakPredecessor

        public long weakPredecessor​(long upperBound)
        Returns the last element of the sequence that is less than or equal to the provided bound. If such an element exists, its position in the sequence can be retrieved using index().
        Parameters:
        upperBound - an upper bound on the returned value.
        Returns:
        the last element of the sequence that is less than or equal to upperBound, or Long.MIN_VALUE if no such element exists, in which case index() will return −1.
        See Also:
        predecessor(long), weakPredecessorUnsafe(long)
      • weakPredecessorUnsafe

        public long weakPredecessorUnsafe​(long upperBound)
        Returns the last element of the sequence that is less than or equal to the provided bound. If such an element exists, its position in the sequence can be retrieved using index().

        This method is slightly faster than weakPredecessor(long), but it has a restricted argument range and it does perform bound checks.

        Parameters:
        upperBound - a nonnegative strict upper bound on the returned value, greater than or equal to the first element of the sequence and smaller than the upper bound provided at construction time.
        Returns:
        the last element of the sequence that is less than or equal to upperBound; if upperBound is out of bounds, behavior is undefined.
        See Also:
        weakPredecessor(long)
      • weakPredecessorIndex

        public long weakPredecessorIndex​(long upperBound)
        Returns the index of the last element of the sequence that is less than or equal to the provided bound.

        This method is significantly faster than weakPredecessor(long), as it does not have to compute the actual weak predecessor; moreover, it does not change the return value of index().

        Parameters:
        upperBound - an upper bound on the returned value.
        Returns:
        the index of the last element of the sequence that is less than or equal to upperBound, or −1 if no such element exists, in which case index() will return −1.
        See Also:
        weakPredecessor(long), weakPredecessorIndexUnsafe(long)
      • weakPredecessorIndexUnsafe

        public long weakPredecessorIndexUnsafe​(long upperBound)
        Returns the index of the last element of the sequence that is less than or equal to the provided bound.

        This method is slightly faster than weakPredecessorIndex(long), but it has a restricted argument range and it does perform bound checks.

        This method is significantly faster than weakPredecessorUnsafe(long), as it does not have to compute the actual weak predecessor; moreover, it does not change the return value of index().

        Parameters:
        upperBound - a nonnegative strict upper bound on the returned value, greater than or equal to the first element of the sequence and smaller than the upper bound provided at construction time.
        Returns:
        the index of the last element of the sequence that is less than or equal to upperBound; if upperBound is out of bounds, behavior is undefined.
        See Also:
        weakPredecessorIndex(long)
      • indexOf

        public long indexOf​(long x)
        Returns the index of the first occurrence of the specified element in the sequence, or −1 if the element does not belong to the sequence.

        This method does not change the value returned by index().

        Specified by:
        indexOf in interface it.unimi.dsi.fastutil.longs.LongBigList
        Overrides:
        indexOf in class it.unimi.dsi.fastutil.longs.AbstractLongBigList
        Parameters:
        x - a long.
        Returns:
        the position of x in the sequence, or −1 if x does not belong to the sequence.
        See Also:
        indexOfUnsafe(long)
      • indexOfUnsafe

        public long indexOfUnsafe​(long x)
        Returns the index of the first occurrence of the specified element in the sequence, or −1 if the element does not belong to the sequence.

        This method is slightly faster than indexOf(long), but it has a restricted argument range and it does perform bound checks.

        Parameters:
        x - a nonnegative long smaller than the upper bound provided at construction time.
        Returns:
        the position of x in the sequence, or −1 if x does not belong to the sequence; if x is out of bounds, behavior is undefined.
        See Also:
        indexOf(long)
      • contains

        public boolean contains​(long x)
        Returns true if the sequence contains the specified element.

        This method does not change the value returned by index(). Use indexOf(long) if you need to retrieve the position of an element.

        Specified by:
        contains in interface it.unimi.dsi.fastutil.longs.LongCollection
        Overrides:
        contains in class it.unimi.dsi.fastutil.longs.AbstractLongBigList
        Parameters:
        x - a long.
        Returns:
        true if the sequence contains x.