Package it.unimi.dsi.sux4j.util

Class EliasFanoMonotoneBigLongBigList

java.lang.Object

java.util.AbstractCollection<Long>

it.unimi.dsi.fastutil.longs.AbstractLongCollection

it.unimi.dsi.fastutil.longs.AbstractLongBigList

it.unimi.dsi.sux4j.util.EliasFanoMonotoneBigLongBigList

All Implemented Interfaces:

BigList<Long>, LongBigList, LongCollection, LongIterable, LongStack, Size64, Stack<Long>, Serializable, Comparable<BigList<? extends Long>>, Iterable<Long>, Collection<Long>

public class EliasFanoMonotoneBigLongBigList
extends AbstractLongBigList
implements Serializable

An implementation of Elias–Fano's representation of monotone sequences identical to EliasFanoMonotoneLongBigList, but slightly slower and without size limitations.

Instances of this class can be memory mapped using MappedEliasFanoMonotoneLongBigList.

See Also:

• EliasFanoMonotoneLongBigList
• MappedEliasFanoMonotoneLongBigList
• Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator	A list iterator over the values of this EliasFanoMonotoneBigLongBigList.

Nested classes/interfaces inherited from class it.unimi.dsi.fastutil.longs.AbstractLongBigList

AbstractLongBigList.LongRandomAccessSubList, 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.
protected long[][]	lowerBits	The list of lower bits of each element, stored explicitly in a big array.
protected final long	lowerBitsMask	The mask for the lower bits.
protected final SimpleBigSelect	selectUpper	The select structure used to extract the upper bits.
protected long[][]	upperBits	The upper bits, stored as unary gaps.

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	EliasFanoMonotoneBigLongBigList(long[] a, 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	EliasFanoMonotoneBigLongBigList(long length, int l, long[][] upperBits, long[][] lowerBits, SimpleBigSelect selectUpper)
	EliasFanoMonotoneBigLongBigList(long n, long upperBound, 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.
	EliasFanoMonotoneBigLongBigList(long n, long upperBound, 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.
	EliasFanoMonotoneBigLongBigList(long n, long upperBound, 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.
	EliasFanoMonotoneBigLongBigList(long n, long upperBound, 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.
	EliasFanoMonotoneBigLongBigList(ByteIterable list)	Creates an Elias–Fano representation of the values returned by the given iterable object.
	EliasFanoMonotoneBigLongBigList(IntIterable list)	Creates an Elias–Fano representation of the values returned by the given iterable object.
	EliasFanoMonotoneBigLongBigList(LongIterable list)	Creates an Elias–Fano representation of the values returned by the given iterable object.
	EliasFanoMonotoneBigLongBigList(ShortIterable list)	Creates an Elias–Fano representation of the values returned by the given iterable object.

Method Summary

Modifier and Type	Method	Description
void	dump(String basename)	Dumps this list's lower bits in native order so that it can be used with MappedEliasFanoMonotoneLongBigList.
void	dump(String basename, ByteOrder byteOrder)	Dumps this list's lower bits so that it can be used with MappedEliasFanoMonotoneLongBigList.
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	getDelta(long index)	Returns the difference between two consecutive elements of the sequence.
long	getLong(long index)	Returns the element at the specified position.
EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator	iterator()	Returns a list iterator over the values of this EliasFanoMonotoneBigLongBigList.
EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator	listIterator()	Returns a list iterator over the values of this EliasFanoMonotoneBigLongBigList.
EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator	listIterator(long from)	Returns a list iterator over the values of this EliasFanoMonotoneBigLongBigList.
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, lastIndexOf, lastIndexOf, 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

length

protected final long length

The length of the sequence.

l

protected final int l

The number of lower bits.

upperBits

protected transient long[][] upperBits

The upper bits, stored as unary gaps.

lowerBits

protected long[][] lowerBits

The list of lower bits of each element, stored explicitly in a big array.

selectUpper

protected final SimpleBigSelect selectUpper

The select structure used to extract the upper bits.

lowerBitsMask

protected final long lowerBitsMask

The mask for the lower bits.

Constructor Details

EliasFanoMonotoneBigLongBigList

protected EliasFanoMonotoneBigLongBigList(long length,
 int l,
 long[][] upperBits,
 long[][] lowerBits,
 SimpleBigSelect selectUpper)

EliasFanoMonotoneBigLongBigList

public EliasFanoMonotoneBigLongBigList(IntIterable list)

Creates an Elias–Fano representation of the values returned by the given iterable object.

Parameters:

list - an iterable object returning nondecreasing natural numbers.

EliasFanoMonotoneBigLongBigList

public EliasFanoMonotoneBigLongBigList(ShortIterable list)

Creates an Elias–Fano representation of the values returned by the given iterable object.

Parameters:

list - an iterable object returning nondecreasing natural numbers.

EliasFanoMonotoneBigLongBigList

public EliasFanoMonotoneBigLongBigList(ByteIterable list)

Creates an Elias–Fano representation of the values returned by the given iterable object.

Parameters:

list - an iterable object returning nondecreasing natural numbers.

EliasFanoMonotoneBigLongBigList

public EliasFanoMonotoneBigLongBigList(LongIterable list)

Creates an Elias–Fano representation of the values returned by the given iterable object.

Parameters:

list - an iterable object returning nondecreasing natural numbers.

EliasFanoMonotoneBigLongBigList

public EliasFanoMonotoneBigLongBigList(long n,
 long upperBound,
 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 - a strict upper bound to the values returned by iterator (note that it used to be non-strict).

iterator - an iterator returning nondecreasing natural numbers.

EliasFanoMonotoneBigLongBigList

public EliasFanoMonotoneBigLongBigList(long n,
 long upperBound,
 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 - a strict upper bound to the values returned by iterator (note that it used to be non-strict).

iterator - an iterator returning nondecreasing natural numbers.

EliasFanoMonotoneBigLongBigList

public EliasFanoMonotoneBigLongBigList(long n,
 long upperBound,
 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 - a strict upper bound to the values returned by iterator (note that it used to be non-strict).

iterator - an iterator returning nondecreasing natural numbers.

EliasFanoMonotoneBigLongBigList

public EliasFanoMonotoneBigLongBigList(long n,
 long upperBound,
 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 - a strict upper bound to the values returned by iterator (note that it used to be non-strict).

iterator - an iterator returning nondecreasing natural numbers.

EliasFanoMonotoneBigLongBigList

protected EliasFanoMonotoneBigLongBigList(long[] a,
 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 (note that it used to be non-strict).

iterator - an iterator returning nondecreasing natural numbers.

Method Details

numBits

public long numBits()

getLong

public long getLong(long index)

Returns the element at the specified position.

Specified by:

getLong in interface LongBigList

Parameters:

index - a position in the list.

Returns:

the element at the specified position; if index is out of bounds, behavior is undefined.

getDelta

public long getDelta(long index)

Returns the difference between two consecutive elements of the sequence.

Parameters:

index - the index of an element (smaller then size64() - 1).

Returns:

the difference between the element of position index + 1 and that of position index; if index is out of bounds, behavior is undefined.

See Also:

• get(long, long[])

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 with length consecutive entries starting at position offset; must be of length greater than offset.

offset - the first position written in dest.

length - the number of elements written in dest starting at offset.

Returns:

dest; if the arguments are out of bounds, behavior is undefined.

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, of nonzero length; it will be filled with consecutive entries.

Returns:

dest; if index is out of bounds or dest has length zero, behavior is undefined.

See Also:

• get(long, long[], int, int)

listIterator

public EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator listIterator(long from)

Returns a list iterator over the values of this EliasFanoMonotoneBigLongBigList.

Forward iteration will be faster than iterated calls to getLong(). Backward iteration is available, but it will perform similarly to getLong().

Specified by:

listIterator in interface BigList<Long>

Specified by:

listIterator in interface LongBigList

Overrides:

listIterator in class AbstractLongBigList

Parameters:

from - the starting position in the sequence.

Returns:

a list iterator over the values of this EliasFanoMonotoneBigLongBigList.

See Also:

• EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator

listIterator

public EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator listIterator()

Returns a list iterator over the values of this EliasFanoMonotoneBigLongBigList.

Forward iteration will be faster than iterated calls to getLong(). Backward iteration is available, but it will perform similarly to getLong().

Specified by:

listIterator in interface BigList<Long>

Specified by:

listIterator in interface LongBigList

Overrides:

listIterator in class AbstractLongBigList

Returns:

a list iterator over the values of this EliasFanoMonotoneBigLongBigList.

See Also:

• EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator

iterator

public EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator iterator()

Returns a list iterator over the values of this EliasFanoMonotoneBigLongBigList.

Forward iteration will be faster than iterated calls to getLong(). Backward iteration is available, but it will perform similarly to getLong().

Specified by:

iterator in interface Collection<Long>

Specified by:

iterator in interface Iterable<Long>

Specified by:

iterator in interface LongBigList

Specified by:

iterator in interface LongCollection

Specified by:

iterator in interface LongIterable

Overrides:

iterator in class AbstractLongBigList

Returns:

a list iterator over the values of this EliasFanoMonotoneBigLongBigList.

See Also:

• EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator

size64

public long size64()

Specified by:

size64 in interface Size64

dump

public void dump(String basename)
          throws IOException

Dumps this list's lower bits in native order so that it can be used with MappedEliasFanoMonotoneLongBigList.

Parameters:

basename - the basename of the generated files.

Throws:

IOException

dump

public void dump(String basename,
 ByteOrder byteOrder)
          throws IOException

Dumps this list's lower bits so that it can be used with MappedEliasFanoMonotoneLongBigList.

Two files will be generated: a serialized object with extension MappedEliasFanoMonotoneLongBigList.OBJECT_EXTENSION and a list of longs in the specified byte order with extension MappedEliasFanoMonotoneLongBigList.LOWER_BITS_EXTENSION.

Parameters:

basename - the basename of the generated files.

byteOrder - the desired byte order.

Throws:

IOException