Class EliasFanoLongBigList
- java.lang.Object
-
- java.util.AbstractCollection<java.lang.Long>
-
- it.unimi.dsi.fastutil.longs.AbstractLongCollection
-
- it.unimi.dsi.fastutil.longs.AbstractLongBigList
-
- it.unimi.dsi.sux4j.util.EliasFanoLongBigList
-
- 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 EliasFanoLongBigList extends it.unimi.dsi.fastutil.longs.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.
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 Summary
Constructors Constructor Description EliasFanoLongBigList(it.unimi.dsi.fastutil.bytes.ByteIterable elements)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.bytes.ByteIterator iterator)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.bytes.ByteIterator iterator, byte lowerBound)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.ints.IntIterable elements)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.ints.IntIterator iterator)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.ints.IntIterator iterator, int lowerBound)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.longs.LongIterable elements)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.longs.LongIterator iterator)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.longs.LongIterator iterator, long lowerBound)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.longs.LongIterator iterator, long lowerBound, boolean offline)
Creates a new Elias–Fano long big list with low memory requirements.EliasFanoLongBigList(it.unimi.dsi.fastutil.shorts.ShortIterable elements)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.shorts.ShortIterator iterator)
Creates a new Elias–Fano long big list.EliasFanoLongBigList(it.unimi.dsi.fastutil.shorts.ShortIterator iterator, short lowerBound)
Creates a new Elias–Fano long big list.
-
Method Summary
All Methods Instance Methods Concrete Methods 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.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
-
-
-
-
Constructor Detail
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.longs.LongIterable elements)
Creates a new Elias–Fano long big list.- Parameters:
elements
- an iterable object.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.ints.IntIterable elements)
Creates a new Elias–Fano long big list.- Parameters:
elements
- an iterable object.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.shorts.ShortIterable elements)
Creates a new Elias–Fano long big list.- Parameters:
elements
- an iterable object.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.bytes.ByteIterable elements)
Creates a new Elias–Fano long big list.- Parameters:
elements
- an iterable object.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.longs.LongIterator iterator)
Creates a new Elias–Fano long big list.- Parameters:
iterator
- an iterator returning natural numbers.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.ints.IntIterator iterator)
Creates a new Elias–Fano long big list.- Parameters:
iterator
- an iterator returning natural numbers.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.shorts.ShortIterator iterator)
Creates a new Elias–Fano long big list.- Parameters:
iterator
- an iterator returning natural numbers.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.bytes.ByteIterator iterator)
Creates a new Elias–Fano long big list.- Parameters:
iterator
- an iterator returning natural numbers.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.ints.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 byiterator
.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.shorts.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 byiterator
.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.bytes.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 byiterator
.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.longs.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 byiterator
.
-
EliasFanoLongBigList
public EliasFanoLongBigList(it.unimi.dsi.fastutil.longs.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 byiterator
.offline
- if true, the construction uses offline memory.
-
-
Method Detail
-
getLong
public long getLong(long index)
- Specified by:
getLong
in interfaceit.unimi.dsi.fastutil.longs.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 withlength
consecutive entries starting at positionoffset
.offset
- the first position written indest
.length
- the number of elements written indest
starting atoffset
.- 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 interfaceit.unimi.dsi.fastutil.Size64
-
numBits
public long numBits()
-
-