Package it.unimi.dsi.sux4j.scratch
Class EliasFanoMonotoneLongBigListTables
java.lang.Object
java.util.AbstractCollection<Long>
it.unimi.dsi.fastutil.longs.AbstractLongCollection
it.unimi.dsi.fastutil.longs.AbstractLongBigList
it.unimi.dsi.sux4j.scratch.EliasFanoMonotoneLongBigListTables
- All Implemented Interfaces:
it.unimi.dsi.fastutil.BigList<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<Long>
,Serializable
,Comparable<it.unimi.dsi.fastutil.BigList<? extends Long>>
,Iterable<Long>
,Collection<Long>
public class EliasFanoMonotoneLongBigListTables
extends it.unimi.dsi.fastutil.longs.AbstractLongBigList
implements 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.
This implementation uses tables recording the position of one each 29 ones and zeroes.
- See Also:
-
Nested Class Summary
Nested classes/interfaces inherited from class it.unimi.dsi.fastutil.longs.AbstractLongBigList
it.unimi.dsi.fastutil.longs.AbstractLongBigList.LongRandomAccessSubList, it.unimi.dsi.fastutil.longs.AbstractLongBigList.LongSubList
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected final int
The number of lower bits.protected final long
The length of the sequence.static final int
protected final int
The base-2 logarithm ofquantum
.protected final long[]
The lower bits of each element, stored explicitly.protected final long
The mask for lower bits.protected final int
The indexing quantum.protected final long[]
The skips for ones (the k-th element contains the position of the (quantum
k)-th one).protected final long[]
The skips for zeroes (the k-th element contains the position of the (quantum
k)-th zero).protected final long[]
The upper bits. -
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
EliasFanoMonotoneLongBigListTables
(long[] a, it.unimi.dsi.fastutil.longs.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
EliasFanoMonotoneLongBigListTables
(long length, int l, long[] skipToOne, long[] skipToZero, long[] upperBits, long[] lowerBits) EliasFanoMonotoneLongBigListTables
(long n, long upperBound, it.unimi.dsi.fastutil.bytes.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.EliasFanoMonotoneLongBigListTables
(long n, long upperBound, it.unimi.dsi.fastutil.ints.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.EliasFanoMonotoneLongBigListTables
(long n, long upperBound, it.unimi.dsi.fastutil.longs.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.EliasFanoMonotoneLongBigListTables
(long n, long upperBound, it.unimi.dsi.fastutil.shorts.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.EliasFanoMonotoneLongBigListTables
(it.unimi.dsi.fastutil.bytes.ByteIterable list) Creates an Elias–Fano representation of the values returned by the given iterable object.EliasFanoMonotoneLongBigListTables
(it.unimi.dsi.fastutil.ints.IntIterable list) Creates an Elias–Fano representation of the values returned by the given iterable object.EliasFanoMonotoneLongBigListTables
(it.unimi.dsi.fastutil.longs.LongIterable list) Creates an Elias–Fano representation of the values returned by the given iterable object.EliasFanoMonotoneLongBigListTables
(it.unimi.dsi.fastutil.shorts.ShortIterable list) Creates an Elias–Fano representation of the values returned by the given iterable object. -
Method Summary
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
-
Field Details
-
LOG_2_QUANTUM
public static final int LOG_2_QUANTUM- See Also:
-
length
protected final long lengthThe length of the sequence. -
l
protected final int lThe number of lower bits. -
mask
protected final long maskThe mask for lower bits. -
lowerBits
protected final long[] lowerBitsThe lower bits of each element, stored explicitly. -
upperBits
protected final long[] upperBitsThe upper bits. -
skipToOne
protected final long[] skipToOneThe skips for ones (the k-th element contains the position of the (quantum
k)-th one). -
skipToZero
protected final long[] skipToZeroThe skips for zeroes (the k-th element contains the position of the (quantum
k)-th zero). -
quantum
protected final int quantumThe indexing quantum. -
log2Quantum
protected final int log2QuantumThe base-2 logarithm ofquantum
.
-
-
Constructor Details
-
EliasFanoMonotoneLongBigListTables
protected EliasFanoMonotoneLongBigListTables(long length, int l, long[] skipToOne, long[] skipToZero, long[] upperBits, long[] lowerBits) -
EliasFanoMonotoneLongBigListTables
public EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.ints.IntIterable list) Creates an Elias–Fano representation of the values returned by the given iterable object.- Parameters:
list
- an iterable object.
-
EliasFanoMonotoneLongBigListTables
public EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.shorts.ShortIterable list) Creates an Elias–Fano representation of the values returned by the given iterable object.- Parameters:
list
- an iterable object.
-
EliasFanoMonotoneLongBigListTables
public EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.bytes.ByteIterable list) Creates an Elias–Fano representation of the values returned by the given iterable object.- Parameters:
list
- an iterable object.
-
EliasFanoMonotoneLongBigListTables
public EliasFanoMonotoneLongBigListTables(it.unimi.dsi.fastutil.longs.LongIterable list) Creates an Elias–Fano representation of the values returned by the given iterable object.- Parameters:
list
- an iterable object.
-
EliasFanoMonotoneLongBigListTables
public EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.bytes.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 byiterator
.upperBound
- an upper bound to the values returned byiterator
(note that it used to be a strict upper bound).iterator
- an iterator returning nondecreasing elements.
-
EliasFanoMonotoneLongBigListTables
public EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.shorts.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 byiterator
.upperBound
- an upper bound to the values returned byiterator
(note that it used to be a strict upper bound).iterator
- an iterator returning nondecreasing elements.
-
EliasFanoMonotoneLongBigListTables
public EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.ints.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 byiterator
.upperBound
- an upper bound to the values returned byiterator
(note that it used to be a strict upper bound).iterator
- an iterator returning nondecreasing elements.
-
EliasFanoMonotoneLongBigListTables
public EliasFanoMonotoneLongBigListTables(long n, long upperBound, it.unimi.dsi.fastutil.longs.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 byiterator
.upperBound
- an upper bound to the values returned byiterator
(note that it used to be a strict upper bound).iterator
- an iterator returning nondecreasing elements.
-
EliasFanoMonotoneLongBigListTables
protected EliasFanoMonotoneLongBigListTables(long[] a, it.unimi.dsi.fastutil.longs.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 byiterator
and a (strict) upper bound to the values returned byiterator
.iterator
- an iterator returning nondecreasing elements.
-
-
Method Details
-
numBits
public long numBits() -
getLong
public long getLong(long index) - Specified by:
getLong
in interfaceit.unimi.dsi.fastutil.longs.LongBigList
-
size64
public long size64()- Specified by:
size64
in interfaceit.unimi.dsi.fastutil.Size64
-