Class EliasFanoLongBigList

All Implemented Interfaces:
BigList<Long>, LongBigList, LongCollection, LongIterable, LongStack, Size64, Stack<Long>, Serializable, Comparable<BigList<? extends Long>>, Iterable<Long>, Collection<Long>

public class EliasFanoLongBigList
extends AbstractLongBigList
implements Serializable
A compressed big list of longs; each element occupies a number of bits bounded by one plus its bit length plus the logarithm of the average bit length of an element.

Instances of this class store in a highly compacted form a list of longs. Values are provided either through an iterable object, or through an iterator, but in the latter case the user must also provide a (not necessarily strict) lower bound (0 by default) on the returned values. The compression is particularly high if the distribution of the values of the list is skewed towards the smallest values.

An additional bulk method makes it possible to extract several consecutive entries at high speed.

Implementation details

Instances of this class store values by offsetting them so that they are strictly positive. Then, the bits of each element, excluding the most significant one, are concatenated in a bit array, and the positions of the initial bit of each element are stored using the Elias–Fano representation. If the distribution of the elements is skewed towards small values, this method achieves very a good compression (and, in any case, w.r.t. exact binary length it will not lose more than one bit per element, plus lower-order terms).

During the construction, the list of borders (i.e., bit positions where each stored element starts) must be temporarily stored. For very large lists, it might be useful to use a constructor that provides offline storage for borders.

See Also:
Serialized Form
  • Constructor Details

    • EliasFanoLongBigList

      public EliasFanoLongBigList​(LongIterable elements)
      Creates a new Elias–Fano long big list.
      Parameters:
      elements - an iterable object.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(IntIterable elements)
      Creates a new Elias–Fano long big list.
      Parameters:
      elements - an iterable object.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(ShortIterable elements)
      Creates a new Elias–Fano long big list.
      Parameters:
      elements - an iterable object.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(ByteIterable elements)
      Creates a new Elias–Fano long big list.
      Parameters:
      elements - an iterable object.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(LongIterator iterator)
      Creates a new Elias–Fano long big list.
      Parameters:
      iterator - an iterator returning natural numbers.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(IntIterator iterator)
      Creates a new Elias–Fano long big list.
      Parameters:
      iterator - an iterator returning natural numbers.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(ShortIterator iterator)
      Creates a new Elias–Fano long big list.
      Parameters:
      iterator - an iterator returning natural numbers.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(ByteIterator iterator)
      Creates a new Elias–Fano long big list.
      Parameters:
      iterator - an iterator returning natural numbers.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(IntIterator iterator, int lowerBound)
      Creates a new Elias–Fano long big list.
      Parameters:
      iterator - an iterator returning natural numbers.
      lowerBound - a (not necessarily strict) lower bound on the values returned by iterator.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(ShortIterator iterator, short lowerBound)
      Creates a new Elias–Fano long big list.
      Parameters:
      iterator - an iterator returning natural numbers.
      lowerBound - a (not necessarily strict) lower bound on the values returned by iterator.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(ByteIterator iterator, byte lowerBound)
      Creates a new Elias–Fano long big list.
      Parameters:
      iterator - an iterator returning natural numbers.
      lowerBound - a (not necessarily strict) lower bound on the values returned by iterator.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(LongIterator iterator, long lowerBound)
      Creates a new Elias–Fano long big list.

      This constructor does not use offline space.

      Parameters:
      iterator - an iterator returning natural numbers.
      lowerBound - a (not necessarily strict) lower bound on the values returned by iterator.
    • EliasFanoLongBigList

      public EliasFanoLongBigList​(LongIterator iterator, long lowerBound, boolean offline)
      Creates a new Elias–Fano long big list with low memory requirements.

      This constructor will use a temporary file to store the border array if offline is true.

      Parameters:
      iterator - an iterator returning natural numbers.
      lowerBound - a (not necessarily strict) lower bound on the values returned by iterator.
      offline - if true, the construction uses offline memory.
  • Method Details

    • getLong

      public long getLong​(long index)
      Specified by:
      getLong in interface LongBigList
    • get

      public long[] get​(long index, long[] dest, int offset, int length)
      Extracts a number of consecutive entries into a given array fragment.
      Parameters:
      index - the index of the first entry returned.
      dest - the destination array; it will be filled with length consecutive entries starting at position offset.
      offset - the first position written in dest.
      length - the number of elements written in dest starting at offset.
      Returns:
      dest
      See Also:
      get(long, long[])
    • get

      public long[] get​(long index, long[] dest)
      Extracts a number of consecutive entries into a given array.
      Parameters:
      index - the index of the first entry returned.
      dest - the destination array; it will be filled with consecutive entries.
      Returns:
      dest
      See Also:
      get(long, long[], int, int)
    • size64

      public long size64()
      Specified by:
      size64 in interface Size64
    • numBits

      public long numBits()