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 2⁹ ones and zeroes.

See Also:

• Serialized Form

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

Fields

Modifier and Type	Field	Description
protected final int	l	The number of lower bits.
protected final long	length	The length of the sequence.
static final int	LOG_2_QUANTUM
protected final int	log2Quantum	The base-2 logarithm of quantum.
protected final long[]	lowerBits	The lower bits of each element, stored explicitly.
protected final long	mask	The mask for lower bits.
protected final int	quantum	The indexing quantum.
protected final long[]	skipToOne	The skips for ones (the k-th element contains the position of the (quantumk)-th one).
protected final long[]	skipToZero	The skips for zeroes (the k-th element contains the position of the (quantumk)-th zero).
protected final 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

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 AbstractCollection

isEmpty, toArray, toArray

Methods inherited from class Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface 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:

• 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 (quantumk)-th one).

skipToZero

protected final long[] skipToZero

The skips for zeroes (the k-th element contains the position of the (quantumk)-th zero).

quantum

protected final int quantum

The indexing quantum.

log2Quantum

protected final int log2Quantum

The base-2 logarithm of quantum.

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 by iterator.

upperBound - an upper bound to the values returned by iterator (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 by iterator.

upperBound - an upper bound to the values returned by iterator (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 by iterator.

upperBound - an upper bound to the values returned by iterator (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 by iterator.

upperBound - an upper bound to the values returned by iterator (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 by iterator and a (strict) upper bound to the values returned by iterator.

iterator - an iterator returning nondecreasing elements.

Method Details

numBits

public long numBits()

getLong

public long getLong(long index)

Specified by:

getLong in interface it.unimi.dsi.fastutil.longs.LongBigList

size64

public long size64()

Specified by:

size64 in interface it.unimi.dsi.fastutil.Size64