Class EliasFanoMonotoneLongBigListTables

java.lang.Object
java.util.AbstractCollection<Long>
it.unimi.dsi.fastutil.longs.AbstractLongCollection
it.unimi.dsi.fastutil.longs.AbstractLongBigList
it.unimi.dsi.sux4j.scratch.EliasFanoMonotoneLongBigListTables
All Implemented Interfaces:
it.unimi.dsi.fastutil.BigList<Long>, it.unimi.dsi.fastutil.longs.LongBigList, it.unimi.dsi.fastutil.longs.LongCollection, it.unimi.dsi.fastutil.longs.LongIterable, it.unimi.dsi.fastutil.longs.LongStack, it.unimi.dsi.fastutil.Size64, it.unimi.dsi.fastutil.Stack<Long>, Serializable, Comparable<it.unimi.dsi.fastutil.BigList<? extends Long>>, Iterable<Long>, Collection<Long>

public class EliasFanoMonotoneLongBigListTables extends it.unimi.dsi.fastutil.longs.AbstractLongBigList implements Serializable
An implementation of Elias–Fano's representation of monotone sequences; an element occupies a number of bits bounded by two plus the logarithm of the average gap.

This implementation uses tables recording the position of one each 29 ones and zeroes.

See Also:
  • Nested Class Summary

    Nested classes/interfaces inherited from class it.unimi.dsi.fastutil.longs.AbstractLongBigList

    it.unimi.dsi.fastutil.longs.AbstractLongBigList.LongRandomAccessSubList, it.unimi.dsi.fastutil.longs.AbstractLongBigList.LongSubList
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected final int
    The number of lower bits.
    protected final long
    The length of the sequence.
    static final int
     
    protected final int
    The base-2 logarithm of quantum.
    protected final long[]
    The lower bits of each element, stored explicitly.
    protected final long
    The mask for lower bits.
    protected final int
    The indexing quantum.
    protected final long[]
    The skips for ones (the k-th element contains the position of the (quantumk)-th one).
    protected final long[]
    The skips for zeroes (the k-th element contains the position of the (quantumk)-th zero).
    protected final long[]
    The upper bits.
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    EliasFanoMonotoneLongBigListTables(long[] a, it.unimi.dsi.fastutil.longs.LongIterator iterator)
    Creates an Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.
    protected
    EliasFanoMonotoneLongBigListTables(long length, int l, long[] skipToOne, long[] skipToZero, long[] upperBits, long[] lowerBits)
     
     
    EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.bytes.ByteIterator iterator)
    Creates an Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.
     
    EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.ints.IntIterator iterator)
    Creates an Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.
     
    EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.longs.LongIterator iterator)
    Creates an Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.
     
    EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.shorts.ShortIterator iterator)
    Creates an Elias–Fano representation of the values returned by an iterator, given that the overall number of elements and an upper bound are provided, too.
     
    EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.bytes.ByteIterable list)
    Creates an Elias–Fano representation of the values returned by the given iterable object.
     
    EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.ints.IntIterable list)
    Creates an Elias–Fano representation of the values returned by the given iterable object.
     
    EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.longs.LongIterable list)
    Creates an Elias–Fano representation of the values returned by the given iterable object.
     
    EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.shorts.ShortIterable list)
    Creates an Elias–Fano representation of the values returned by the given iterable object.
  • Method Summary

    Modifier and Type
    Method
    Description
    long
    getLong(long index)
     
    long
     
    long
     

    Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongBigList

    add, add, add, addAll, addAll, addAll, addAll, addElements, addElements, clear, compareTo, contains, ensureIndex, ensureRestrictedIndex, equals, forEach, get, getElements, hashCode, indexOf, indexOf, iterator, lastIndexOf, lastIndexOf, listIterator, listIterator, 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 Details

    • LOG_2_QUANTUM

      public static final int LOG_2_QUANTUM
      See Also:
    • length

      protected final long length
      The length of the sequence.
    • l

      protected final int l
      The number of lower bits.
    • mask

      protected final long mask
      The mask for lower bits.
    • lowerBits

      protected final long[] lowerBits
      The lower bits of each element, stored explicitly.
    • upperBits

      protected final long[] upperBits
      The upper bits.
    • skipToOne

      protected final long[] skipToOne
      The skips for ones (the k-th element contains the position of the (quantumk)-th one).
    • skipToZero

      protected final long[] skipToZero
      The skips for zeroes (the k-th element contains the position of the (quantumk)-th zero).
    • quantum

      protected final int quantum
      The indexing quantum.
    • log2Quantum

      protected final int log2Quantum
      The base-2 logarithm of quantum.
  • Constructor Details

    • EliasFanoMonotoneLongBigListTables

      protected EliasFanoMonotoneLongBigListTables(long length, int l, long[] skipToOne, long[] skipToZero, long[] upperBits, long[] lowerBits)
    • EliasFanoMonotoneLongBigListTables

      public EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.ints.IntIterable list)
      Creates an Elias–Fano representation of the values returned by the given iterable object.
      Parameters:
      list - an iterable object.
    • EliasFanoMonotoneLongBigListTables

      public EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.shorts.ShortIterable list)
      Creates an Elias–Fano representation of the values returned by the given iterable object.
      Parameters:
      list - an iterable object.
    • EliasFanoMonotoneLongBigListTables

      public EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.bytes.ByteIterable list)
      Creates an Elias–Fano representation of the values returned by the given iterable object.
      Parameters:
      list - an iterable object.
    • EliasFanoMonotoneLongBigListTables

      public EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.longs.LongIterable list)
      Creates an Elias–Fano representation of the values returned by the given iterable object.
      Parameters:
      list - an iterable object.
    • EliasFanoMonotoneLongBigListTables

      public EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.bytes.ByteIterator iterator)
      Creates an 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 (note that it used to be a strict upper bound).
      iterator - an iterator returning nondecreasing elements.
    • EliasFanoMonotoneLongBigListTables

      public EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.shorts.ShortIterator iterator)
      Creates an 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 (note that it used to be a strict upper bound).
      iterator - an iterator returning nondecreasing elements.
    • EliasFanoMonotoneLongBigListTables

      public EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.ints.IntIterator iterator)
      Creates an 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 (note that it used to be a strict upper bound).
      iterator - an iterator returning nondecreasing elements.
    • EliasFanoMonotoneLongBigListTables

      public EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.longs.LongIterator iterator)
      Creates an 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 (note that it used to be a strict upper bound).
      iterator - an iterator returning nondecreasing elements.
    • EliasFanoMonotoneLongBigListTables

      protected EliasFanoMonotoneLongBigListTables(long[] a, it.unimi.dsi.fastutil.longs.LongIterator iterator)
      Creates an 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 used only internally, to work around the usual problems caused by the obligation to call this() before anything else.

      Parameters:
      a - an array containing the number of elements returned by iterator and a (strict) upper bound to the values returned by iterator.
      iterator - an iterator returning nondecreasing elements.
  • Method Details

    • numBits

      public long numBits()
    • getLong

      public long getLong(long index)
      Specified by:
      getLong in interface it.unimi.dsi.fastutil.longs.LongBigList
    • size64

      public long size64()
      Specified by:
      size64 in interface it.unimi.dsi.fastutil.Size64