Package it.unimi.dsi.sux4j.scratch
Class EliasFanoMonotoneLongBigListTables
- 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.scratch.EliasFanoMonotoneLongBigListTables
-
- 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 EliasFanoMonotoneLongBigListTables extends it.unimi.dsi.fastutil.longs.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.This implementation uses tables recording the position of one each 29 ones and zeroes.
- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description protected int
l
The number of lower bits.protected long
length
The length of the sequence.static int
LOG_2_QUANTUM
protected int
log2Quantum
The base-2 logarithm ofquantum
.protected long[]
lowerBits
The lower bits of each element, stored explicitly.protected long
mask
The mask for lower bits.protected int
quantum
The indexing quantum.protected long[]
skipToOne
The skips for ones (the k-th element contains the position of the (quantum
k)-th one).protected long[]
skipToZero
The skips for zeroes (the k-th element contains the position of the (quantum
k)-th zero).protected long[]
upperBits
The upper bits.
-
Constructor Summary
Constructors Modifier Constructor Description 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.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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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
-
-
-
-
Field Detail
-
LOG_2_QUANTUM
public static final int LOG_2_QUANTUM
- See Also:
- Constant Field Values
-
length
protected final long length
The length of the sequence.
-
l
protected final int l
The number of lower bits.
-
mask
protected final long mask
The mask for lower bits.
-
lowerBits
protected final long[] lowerBits
The lower bits of each element, stored explicitly.
-
upperBits
protected final long[] upperBits
The upper bits.
-
skipToOne
protected final long[] skipToOne
The skips for ones (the k-th element contains the position of the (quantum
k)-th one).
-
skipToZero
protected final long[] skipToZero
The skips for zeroes (the k-th element contains the position of the (quantum
k)-th zero).
-
quantum
protected final int quantum
The indexing quantum.
-
log2Quantum
protected final int log2Quantum
The base-2 logarithm ofquantum
.
-
-
Constructor Detail
-
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.
-
-