it.unimi.dsi.sux4j.util
Class EliasFanoMonotoneLongBigList

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.EliasFanoMonotoneLongBigList
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>
Direct Known Subclasses:
EliasFanoPrefixSumLongBigList, SparseSelect

public class EliasFanoMonotoneLongBigList
extends 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.

Instances of this class represent in a highly compacted form a nondecreasing sequence of natural numbers. Instances are built by providing either an iterator returning the (nondecreasing) sequence, or an iterable object that provides such an iterator. In the first case, you must also provide in advance the number of elements that will be returned and an upper bound to their values (see below), and at the end of the construction the iterator will be exhausted.

Implementation details

Given a (nondecreasing) monotone sequence x0, x1,… , xn − 1 of natural numbers smaller than u, the Elias–Fano representation makes it possible to store it using at most 2 + log(u/n) bits per element, which is very close to the information-theoretical lower bound ≈ log e + log(u/n). A typical example is a list of pointer into records of a large file: instead of using, for each pointer, a number of bit sufficient to express the length of the file, the Elias–Fano representation makes it possible to use, for each pointer, a number of bits roughly equal to the logarithm of the average length of a record. The representation was introduced in Peter Elias, “Efficient storage and retrieval by content and address of static files”, J. Assoc. Comput. Mach., 21(2):246−260, 1974, and also independently by Robert Fano, “On the number of bits required to implement an associative memory”, Memorandum 61, Computer Structures Group, Project MAC, MIT, Cambridge, Mass., n.d., 1971.

The elements of the sequence are recorded by storing separately the lower s = ⌊log(u/n)⌋ bits and the remaining upper bits. The lower bits are stored contiguously, whereas the upper bits are stored in an array of n + xn − 1 / 2s bits by setting, for each 0 ≤ i < n, the bit of index xi / 2s + i; the value can then be recovered by selecting the i-th bit of the resulting bit array and subtracting i (note that this will work because the upper bits are nondecreasing).

This implementation uses SimpleSelect to support selection inside the upper-bits array.

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
 
Field Summary
protected  int l
          The number of lower bits.
protected  long length
          The length of the sequence.
protected  LongBigList lowerBits
          The list of lower bits of each element, stored explicitly.
protected  SimpleSelect selectUpper
          The select structure used to extract the upper bits.
 
Constructor Summary
  EliasFanoMonotoneLongBigList(ByteIterable list)
          Creates an Elias–Fano representation of the values returned by the given iterable object.
  EliasFanoMonotoneLongBigList(IntIterable list)
          Creates an Elias–Fano representation of the values returned by the given iterable object.
protected EliasFanoMonotoneLongBigList(long[] a, 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 EliasFanoMonotoneLongBigList(long length, int l, LongBigList lowerBits, SimpleSelect selectUpper)
           
  EliasFanoMonotoneLongBigList(LongIterable list)
          Creates an Elias–Fano representation of the values returned by the given iterable object.
  EliasFanoMonotoneLongBigList(long n, long upperBound, 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.
  EliasFanoMonotoneLongBigList(long n, long upperBound, 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.
  EliasFanoMonotoneLongBigList(long n, long upperBound, 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.
  EliasFanoMonotoneLongBigList(long n, long upperBound, 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.
  EliasFanoMonotoneLongBigList(ShortIterable list)
          Creates an Elias–Fano representation of the values returned by the given iterable object.
 
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
 

Field Detail

length

protected final long length
The length of the sequence.


l

protected final int l
The number of lower bits.


lowerBits

protected final LongBigList lowerBits
The list of lower bits of each element, stored explicitly.


selectUpper

protected final SimpleSelect selectUpper
The select structure used to extract the upper bits.

Constructor Detail

EliasFanoMonotoneLongBigList

protected EliasFanoMonotoneLongBigList(long length,
                                       int l,
                                       LongBigList lowerBits,
                                       SimpleSelect selectUpper)

EliasFanoMonotoneLongBigList

public EliasFanoMonotoneLongBigList(IntIterable list)
Creates an Elias–Fano representation of the values returned by the given iterable object.

Parameters:
list - an iterable object.

EliasFanoMonotoneLongBigList

public EliasFanoMonotoneLongBigList(ShortIterable list)
Creates an Elias–Fano representation of the values returned by the given iterable object.

Parameters:
list - an iterable object.

EliasFanoMonotoneLongBigList

public EliasFanoMonotoneLongBigList(ByteIterable list)
Creates an Elias–Fano representation of the values returned by the given iterable object.

Parameters:
list - an iterable object.

EliasFanoMonotoneLongBigList

public EliasFanoMonotoneLongBigList(LongIterable list)
Creates an Elias–Fano representation of the values returned by the given iterable object.

Parameters:
list - an iterable object.

EliasFanoMonotoneLongBigList

public EliasFanoMonotoneLongBigList(long n,
                                    long upperBound,
                                    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 - a (strict) upper bound to the values returned by iterator.
iterator - an iterator returning nondecreasing elements.

EliasFanoMonotoneLongBigList

public EliasFanoMonotoneLongBigList(long n,
                                    long upperBound,
                                    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 - a (strict) upper bound to the values returned by iterator.
iterator - an iterator returning nondecreasing elements.

EliasFanoMonotoneLongBigList

public EliasFanoMonotoneLongBigList(long n,
                                    long upperBound,
                                    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 - a (strict) upper bound to the values returned by iterator.
iterator - an iterator returning nondecreasing elements.

EliasFanoMonotoneLongBigList

public EliasFanoMonotoneLongBigList(long n,
                                    long upperBound,
                                    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 - a (strict) upper bound to the values returned by iterator.
iterator - an iterator returning nondecreasing elements.

EliasFanoMonotoneLongBigList

protected EliasFanoMonotoneLongBigList(long[] a,
                                       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 LongBigList

length

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