Package it.unimi.dsi.sux4j.util

Class MappedEliasFanoMonotoneLongBigList

java.lang.Object

java.util.AbstractCollection<Long>

it.unimi.dsi.fastutil.longs.AbstractLongCollection

it.unimi.dsi.fastutil.longs.AbstractLongBigList

it.unimi.dsi.sux4j.util.MappedEliasFanoMonotoneLongBigList

All Implemented Interfaces:

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

public class MappedEliasFanoMonotoneLongBigList
extends AbstractLongBigList
implements Serializable, Closeable, FlyweightPrototype<MappedEliasFanoMonotoneLongBigList>

A memory-mapped implementation of EliasFanoMonotoneLongBigList/EliasFanoMonotoneBigLongBigList.

This class makes it possible to use an EliasFanoMonotoneLongBigList (or EliasFanoMonotoneBigLongBigList) without actually loading the lower bits, but rather mapping them into memory. You build an EliasFanoMonotoneLongBigList (or EliasFanoMonotoneBigLongBigList) instance first, and then you use the dump it to disk providing a basename. The same basename must be used when loading an instance of this class.

After usage, you should close() instances of this class to release the associated FileChannel.

Instances of this class are not thread safe, but the copy() method provides a lightweight duplicate that can be read independently by another thread. The method uses LongMappedBigList.copy() to provide an independent mapping of the lower bits. Note that the close() method, when invoked on any copy, will stop mapping of all copies. *

See Also:

• EliasFanoMonotoneLongBigList
• EliasFanoMonotoneBigLongBigList
• Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	MappedEliasFanoMonotoneLongBigList.MappedEliasFanoMonotoneLongBigListIterator	A list iterator over the values of this MappedEliasFanoMonotoneLongBigList.

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.
static final String	LOWER_BITS_EXTENSION
protected LongMappedBigList	lowerBits	The list of lower bits of each element, stored explicitly.
protected final long	lowerBitsMask	The mask for the lower bits.
static final String	OBJECT_EXTENSION
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	MappedEliasFanoMonotoneLongBigList(long length, int l, long[][] upperBits, SimpleBigSelect selectUpper, boolean littleEndian)

Method Summary

Modifier and Type	Method	Description
void	close()
MappedEliasFanoMonotoneLongBigList	copy()
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.
MappedEliasFanoMonotoneLongBigList.MappedEliasFanoMonotoneLongBigListIterator	iterator()	Returns a list iterator over the values of this MappedEliasFanoMonotoneLongBigList.
MappedEliasFanoMonotoneLongBigList.MappedEliasFanoMonotoneLongBigListIterator	listIterator()	Returns a list iterator over the values of this MappedEliasFanoMonotoneLongBigList.
MappedEliasFanoMonotoneLongBigList.MappedEliasFanoMonotoneLongBigListIterator	listIterator(long from)	Returns a list iterator over the values of this MappedEliasFanoMonotoneLongBigList.
static MappedEliasFanoMonotoneLongBigList	load(String basename)	Maps an Elias–Fano monotone list into memory.
MappedEliasFanoMonotoneLongBigList	lowerBits(String lowerBits)	Maps the lower bits of this list from a file.
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

OBJECT_EXTENSION

public static final String OBJECT_EXTENSION

See Also:

• Constant Field Values

LOWER_BITS_EXTENSION

public static final String LOWER_BITS_EXTENSION

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.

upperBits

protected long[][] upperBits

The upper bits, stored as unary gaps.

lowerBits

protected LongMappedBigList lowerBits

The list of lower bits of each element, stored explicitly.

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

MappedEliasFanoMonotoneLongBigList

protected MappedEliasFanoMonotoneLongBigList(long length,
 int l,
 long[][] upperBits,
 SimpleBigSelect selectUpper,
 boolean littleEndian)

Method Details

load

public static MappedEliasFanoMonotoneLongBigList load(String basename)
                                               throws IOException,
ClassNotFoundException

Maps an Elias–Fano monotone list into memory.

Parameters:

basename - the basename of the dumped list. From the basename, two files will be derived: a serialized object with extension OBJECT_EXTENSION and a list of longs with extension LOWER_BITS_EXTENSION.

Returns:

an instance of this class.

Throws:

IOException

ClassNotFoundException

lowerBits

public MappedEliasFanoMonotoneLongBigList lowerBits(String lowerBits)
                                             throws IOException

Maps the lower bits of this list from a file.

This method is low level and should not be used in geneneral. There is no check that the file you are using is actually the right file for this instance.

Parameters:

lowerBits - the name of the file containing the lower bits.

Returns:

this instance.

Throws:

IOException

close

public void close()
           throws IOException

Specified by:

close in interface AutoCloseable

Specified by:

close in interface Closeable

Throws:

IOException

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 MappedEliasFanoMonotoneLongBigList.MappedEliasFanoMonotoneLongBigListIterator listIterator(long from)

Returns a list iterator over the values of this MappedEliasFanoMonotoneLongBigList.

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 MappedEliasFanoMonotoneLongBigList.

See Also:

• MappedEliasFanoMonotoneLongBigList.MappedEliasFanoMonotoneLongBigListIterator

listIterator

public MappedEliasFanoMonotoneLongBigList.MappedEliasFanoMonotoneLongBigListIterator listIterator()

Returns a list iterator over the values of this MappedEliasFanoMonotoneLongBigList.

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 MappedEliasFanoMonotoneLongBigList.

See Also:

• MappedEliasFanoMonotoneLongBigList.MappedEliasFanoMonotoneLongBigListIterator

iterator

public MappedEliasFanoMonotoneLongBigList.MappedEliasFanoMonotoneLongBigListIterator iterator()

Returns a list iterator over the values of this MappedEliasFanoMonotoneLongBigList.

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 MappedEliasFanoMonotoneLongBigList.

See Also:

• MappedEliasFanoMonotoneLongBigList.MappedEliasFanoMonotoneLongBigListIterator

size64

public long size64()

Specified by:

size64 in interface Size64

copy

public MappedEliasFanoMonotoneLongBigList copy()

Specified by:

copy in interface FlyweightPrototype<MappedEliasFanoMonotoneLongBigList>