it.unimi.dsi.sux4j.util
Class EliasFanoLongBigList

java.lang.Object
  extended by it.unimi.dsi.fastutil.longs.AbstractLongCollection
      extended by it.unimi.dsi.fastutil.longs.AbstractLongList
          extended by it.unimi.dsi.util.AbstractLongBigList
              extended by it.unimi.dsi.sux4j.util.EliasFanoLongBigList
All Implemented Interfaces:
LongCollection, LongIterable, LongList, LongStack, Stack<java.lang.Long>, LongBigList, java.io.Serializable, java.lang.Comparable<java.util.List<? extends java.lang.Long>>, java.lang.Iterable<java.lang.Long>, java.util.Collection<java.lang.Long>, java.util.List<java.lang.Long>

public class EliasFanoLongBigList
extends AbstractLongBigList
implements java.io.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.

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).

See Also:
Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from class it.unimi.dsi.util.AbstractLongBigList
AbstractLongBigList.LongSubBigList
 
Nested classes/interfaces inherited from class it.unimi.dsi.fastutil.longs.AbstractLongList
AbstractLongList.LongSubList
 
Constructor Summary
EliasFanoLongBigList(ByteIterable elements)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(ByteIterator iterator)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(ByteIterator iterator, byte lowerBound)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(IntIterable elements)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(IntIterator iterator)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(IntIterator iterator, int lowerBound)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(LongIterable elements)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(LongIterator iterator)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(LongIterator iterator, long lowerBound)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(ShortIterable elements)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(ShortIterator iterator)
          Creates a new Elias–Fano long big list.
EliasFanoLongBigList(ShortIterator iterator, short lowerBound)
          Creates a new Elias–Fano long big list.
 
Method Summary
 long getLong(long index)
           
 long length()
           
 long numBits()
           
 
Methods inherited from class it.unimi.dsi.util.AbstractLongBigList
add, ensureIndex, ensureRestrictedIndex, getLong, length, removeLong, set, size, subList
 
Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongList
add, add, add, addAll, addAll, addAll, addAll, addAll, addAll, addElements, addElements, compareTo, contains, ensureIndex, ensureRestrictedIndex, equals, get, getElements, hashCode, indexOf, indexOf, iterator, lastIndexOf, lastIndexOf, listIterator, listIterator, longListIterator, longListIterator, longSubList, peek, peekLong, pop, popLong, push, push, rem, remove, remove, removeElements, removeLong, set, set, size, subList, top, topLong, toString
 
Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongCollection
add, clear, contains, containsAll, containsAll, isEmpty, longIterator, rem, removeAll, removeAll, retainAll, retainAll, toArray, toArray, toArray, toLongArray, toLongArray
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface it.unimi.dsi.fastutil.longs.LongList
add, addAll, addAll, addAll, addElements, addElements, getElements, indexOf, iterator, lastIndexOf, listIterator, listIterator, longListIterator, longListIterator, longSubList, removeElements, removeLong, set, size, subList
 
Methods inherited from interface java.util.List
add, add, addAll, addAll, clear, contains, containsAll, equals, get, hashCode, indexOf, isEmpty, lastIndexOf, remove, remove, removeAll, retainAll, set, toArray, toArray
 
Methods inherited from interface java.lang.Comparable
compareTo
 
Methods inherited from interface it.unimi.dsi.fastutil.longs.LongCollection
add, addAll, contains, containsAll, longIterator, rem, removeAll, retainAll, toArray, toArray, toLongArray, toLongArray
 
Methods inherited from interface it.unimi.dsi.fastutil.Stack
isEmpty
 

Constructor Detail

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 value 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 value 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 value returned by iterator.

EliasFanoLongBigList

public EliasFanoLongBigList(LongIterator iterator,
                            long 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 value returned by iterator.
Method Detail

getLong

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

length

public long length()
Specified by:
length in interface LongBigList

numBits

public long numBits()