|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.unimi.dsi.fastutil.longs.AbstractLongCollection
it.unimi.dsi.fastutil.longs.AbstractLongList
it.unimi.dsi.util.AbstractLongBigList
it.unimi.dsi.sux4j.util.EliasFanoLongBigList
public class EliasFanoLongBigList
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.
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).
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 |
---|
public EliasFanoLongBigList(LongIterable elements)
elements
- an iterable object.public EliasFanoLongBigList(IntIterable elements)
elements
- an iterable object.public EliasFanoLongBigList(ShortIterable elements)
elements
- an iterable object.public EliasFanoLongBigList(ByteIterable elements)
elements
- an iterable object.public EliasFanoLongBigList(LongIterator iterator)
iterator
- an iterator returning natural numbers.public EliasFanoLongBigList(IntIterator iterator)
iterator
- an iterator returning natural numbers.public EliasFanoLongBigList(ShortIterator iterator)
iterator
- an iterator returning natural numbers.public EliasFanoLongBigList(ByteIterator iterator)
iterator
- an iterator returning natural numbers.public EliasFanoLongBigList(IntIterator iterator, int lowerBound)
iterator
- an iterator returning natural numbers.lowerBound
- a (not necessarily strict) lower bound on the value returned by iterator
.public EliasFanoLongBigList(ShortIterator iterator, short lowerBound)
iterator
- an iterator returning natural numbers.lowerBound
- a (not necessarily strict) lower bound on the value returned by iterator
.public EliasFanoLongBigList(ByteIterator iterator, byte lowerBound)
iterator
- an iterator returning natural numbers.lowerBound
- a (not necessarily strict) lower bound on the value returned by iterator
.public EliasFanoLongBigList(LongIterator iterator, long lowerBound)
iterator
- an iterator returning natural numbers.lowerBound
- a (not necessarily strict) lower bound on the value returned by iterator
.Method Detail |
---|
public long getLong(long index)
getLong
in interface LongBigList
public long length()
length
in interface LongBigList
public long numBits()
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |