Package it.unimi.dsi.sux4j.util

Class EliasFanoLongBigList

java.lang.Object

java.util.AbstractCollection<Long>

it.unimi.dsi.fastutil.longs.AbstractLongCollection

it.unimi.dsi.fastutil.longs.AbstractLongBigList

it.unimi.dsi.sux4j.util.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

Nested Class Summary

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

AbstractLongBigList.LongRandomAccessSubList, AbstractLongBigList.LongSubList

Constructor Summary

Constructors

Constructor	Description
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(LongIterator iterator, long lowerBound, boolean offline)	Creates a new Elias–Fano long big list with low memory requirements.
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

Modifier and Type	Method	Description
long[]	get(long index, long[] dest)	Extracts a number of consecutive entries into a given array.
long[]	get(long index, long[] dest, int offset, int length)	Extracts a number of consecutive entries into a given array fragment.
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

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