Package it.unimi.dsi.sux4j.scratch

Class EliasFanoMonotoneLongBigListTables

  • All Implemented Interfaces:
    it.unimi.dsi.fastutil.BigList<java.lang.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<java.lang.Long>, java.io.Serializable, java.lang.Comparable<it.unimi.dsi.fastutil.BigList<? extends java.lang.Long>>, java.lang.Iterable<java.lang.Long>, java.util.Collection<java.lang.Long>
    public class EliasFanoMonotoneLongBigListTables
extends it.unimi.dsi.fastutil.longs.AbstractLongBigList
implements java.io.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:
    Serialized Form

    • 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 int l
      The number of lower bits.
      protected long length
      The length of the sequence.
      static int LOG_2_QUANTUM  
      protected int log2Quantum
      The base-2 logarithm of quantum.
      protected long[] lowerBits
      The lower bits of each element, stored explicitly.
      protected long mask
      The mask for lower bits.
      protected int quantum
      The indexing quantum.
      protected long[] skipToOne
      The skips for ones (the k-th element contains the position of the (quantumk)-th one).
      protected long[] skipToZero
      The skips for zeroes (the k-th element contains the position of the (quantumk)-th zero).
      protected long[] upperBits
      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

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      long getLong​(long index)  
      long numBits()  
      long size64()  

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

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

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

      • 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