Package it.unimi.dsi.sux4j.util

Class EliasFanoIndexedMonotoneLongBigList

java.lang.Object
java.util.AbstractCollection<Long>
it.unimi.dsi.fastutil.longs.AbstractLongCollection
it.unimi.dsi.fastutil.longs.AbstractLongBigList
it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
it.unimi.dsi.sux4j.util.EliasFanoIndexedMonotoneLongBigList
All Implemented Interfaces:
BigList<Long>, LongBigList, LongCollection, LongIterable, LongStack, Size64, Stack<Long>, Serializable, Comparable<BigList<? extends Long>>, Iterable<Long>, Collection<Long>
public class EliasFanoIndexedMonotoneLongBigList extends EliasFanoMonotoneLongBigList implements Serializable
An extension of EliasFanoMonotoneLongBigList providing indexing (i.e., content-based addressing).

This implementation uses a SimpleSelectZero structure to support zero-selection inside the upper-bits array, which makes it possible to implement fast content-addressed based access methods such as successor(long), strictSuccessor(long), predecessor(long), weakPredecessor(long), contains(long) and indexOf(long).

Beside standard interface methods, additional unsafe methods such as successorUnsafe(long) have restricted argument ranges and skip bounds check for maximum performance. Bounds checks are performed even for these methods, however, when assertions are enabled.

This class is thread safe as long as you do not use index(), as its value depend on an internal variable that caches the result of successor(long), successorUnsafe(long), strictSuccessor(long), strictSuccessorUnsafe(long), predecessor(long), predecessorUnsafe(long), weakPredecessor(long), and weakPredecessorUnsafe(long). Usually it is possible to work around the issue using the alternative methods successorIndex(long), successorIndexUnsafe(long), strictSuccessorIndex(long), strictSuccessorIndexUnsafe(long), predecessorIndex(long), predecessorIndexUnsafe(long), weakPredecessorIndex(long), and weakPredecessorIndexUnsafe(long).

See Also:

  • Field Details

    • selectUpperZero

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

  • Constructor Details

    • EliasFanoIndexedMonotoneLongBigList

      public EliasFanoIndexedMonotoneLongBigList(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(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(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(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, 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, 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, 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, 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 Details

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    • 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 LongBigList
      Overrides:
      indexOf in class 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

      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:

    • 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 LongCollection
      Overrides:
      contains in class AbstractLongBigList
      Parameters:
      x - a long.
      Returns:
      true if the sequence contains x.

    • index

      public long index()
      Returns the index realizing the last value returned by successor(long), successorUnsafe(long), strictSuccessor(long), strictSuccessorUnsafe(long), predecessor(long), predecessorUnsafe(long), weakPredecessor(long), and weakPredecessorUnsafe(long).

      Usage of this method makes instances of this class not thread safe, as the return value is cached internally.

      Returns:
      the index of the element realizing the last value returned by successor(long), successorUnsafe(long), strictSuccessor(long), strictSuccessorUnsafe(long), predecessor(long), predecessorUnsafe(long), weakPredecessor(long), and weakPredecessorUnsafe(long), or −1 if no such method has ever been called.

    • listIterator

      public EliasFanoIndexedMonotoneLongBigList.EliasFanoIndexedMonotoneLongBigListIterator listIterator(long from)
      Description copied from class: EliasFanoMonotoneLongBigList
      Returns a list iterator over the values of this EliasFanoMonotoneLongBigList.

      Forward iteration will be faster than iterated calls to getLong(). Backward iteration is available, but it will perform similarly to getLong().

      Specified by:
      listIterator in interface BigList<Long>
      Specified by:
      listIterator in interface LongBigList
      Overrides:
      listIterator in class EliasFanoMonotoneLongBigList
      Parameters:
      from - the starting position in the sequence.
      Returns:
      a list iterator over the values of this EliasFanoMonotoneLongBigList.
      See Also:

    • listIterator

      public EliasFanoIndexedMonotoneLongBigList.EliasFanoIndexedMonotoneLongBigListIterator listIterator()
      Description copied from class: EliasFanoMonotoneLongBigList
      Returns a list iterator over the values of this EliasFanoMonotoneLongBigList.

      Forward iteration will be faster than iterated calls to getLong(). Backward iteration is available, but it will perform similarly to getLong().

      Specified by:
      listIterator in interface BigList<Long>
      Specified by:
      listIterator in interface LongBigList
      Overrides:
      listIterator in class EliasFanoMonotoneLongBigList
      Returns:
      a list iterator over the values of this EliasFanoMonotoneLongBigList.
      See Also:

    • iterator

      public EliasFanoIndexedMonotoneLongBigList.EliasFanoIndexedMonotoneLongBigListIterator iterator()
      Description copied from class: EliasFanoMonotoneLongBigList
      Returns a list iterator over the values of this EliasFanoMonotoneLongBigList.

      Forward iteration will be faster than iterated calls to getLong(). Backward iteration is available, but it will perform similarly to getLong().

      Specified by:
      iterator in interface Collection<Long>
      Specified by:
      iterator in interface Iterable<Long>
      Specified by:
      iterator in interface LongBigList
      Specified by:
      iterator in interface LongCollection
      Specified by:
      iterator in interface LongIterable
      Overrides:
      iterator in class EliasFanoMonotoneLongBigList
      Returns:
      a list iterator over the values of this EliasFanoMonotoneLongBigList.
      See Also: