Package it.unimi.dsi.sux4j.util

Class EliasFanoPrefixSumLongBigList

java.lang.Object

java.util.AbstractCollection<Long>

it.unimi.dsi.fastutil.longs.AbstractLongCollection

it.unimi.dsi.fastutil.longs.AbstractLongBigList

it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList

it.unimi.dsi.sux4j.util.EliasFanoPrefixSumLongBigList

All Implemented Interfaces:

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

public class EliasFanoPrefixSumLongBigList
extends EliasFanoMonotoneLongBigList

A compressed big list of longs providing prefix sums; an element occupies a number of bits bounded by two plus the logarithm of the average value.

Instances of this class store in compacted form a list of longs. Values are provided either through an iterable object. As an additional service, this list provides access to the prefix sums of its values.

Implementation details

Instances of this class are essentially a view over an instance of EliasFanoMonotoneLongBigList storing the prefix sums. The getLong(long) method delegates to EliasFanoMonotoneLongBigList.getDelta(long). The iterator has the same properties of the iterator returned by EliasFanoMonotoneLongBiglist.

See Also:

• EliasFanoMonotoneLongBigList
• Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
class	EliasFanoPrefixSumLongBigList.EliasFanoPrefixSumLongBigListIterator	An list iterator over the values of this EliasFanoPrefixSumLongBigList.

Nested classes/interfaces inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList

EliasFanoMonotoneLongBigList.EliasFanoMonotoneLongBigListIterator

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

AbstractLongBigList.LongRandomAccessSubList, AbstractLongBigList.LongSubList

Field Summary

Fields inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList

l, length, lowerBits, lowerBitsMask, selectUpper

Constructor Summary

Constructors

Constructor	Description
EliasFanoPrefixSumLongBigList(ByteIterable elements)	Creates a new Elias–Fano prefix-sum long big list.
EliasFanoPrefixSumLongBigList(IntIterable elements)	Creates a new Elias–Fano prefix-sum long big list.
EliasFanoPrefixSumLongBigList(LongIterable elements)	Creates a new Elias–Fano prefix-sum long big list.
EliasFanoPrefixSumLongBigList(ShortIterable elements)	Creates a new Elias–Fano prefix-sum long big list.

Method Summary

Modifier and Type	Method	Description
long	getLong(long index)	Returns the element at the specified position.
EliasFanoPrefixSumLongBigList.EliasFanoPrefixSumLongBigListIterator	iterator()	Returns a list iterator over the values of this EliasFanoPrefixSumLongBigList.
EliasFanoPrefixSumLongBigList.EliasFanoPrefixSumLongBigListIterator	listIterator()	Returns a list iterator over the values of this EliasFanoPrefixSumLongBigList.
EliasFanoPrefixSumLongBigList.EliasFanoPrefixSumLongBigListIterator	listIterator(long from)	Returns a list iterator over the values of this EliasFanoPrefixSumLongBigList.
long	prefixSum(long index)	Returns the prefix sum of this list up to the given index.
long	size64()

Methods inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList

dump, dump, fits, get, get, getDelta, numBits

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

Constructor Details

EliasFanoPrefixSumLongBigList

public EliasFanoPrefixSumLongBigList(LongIterable elements)

Creates a new Elias–Fano prefix-sum long big list.

Parameters:

elements - an iterable object.

EliasFanoPrefixSumLongBigList

public EliasFanoPrefixSumLongBigList(IntIterable elements)

Creates a new Elias–Fano prefix-sum long big list.

Parameters:

elements - an iterable object.

EliasFanoPrefixSumLongBigList

public EliasFanoPrefixSumLongBigList(ShortIterable elements)

Creates a new Elias–Fano prefix-sum long big list.

Parameters:

elements - an iterable object.

EliasFanoPrefixSumLongBigList

public EliasFanoPrefixSumLongBigList(ByteIterable elements)

Creates a new Elias–Fano prefix-sum long big list.

Parameters:

elements - an iterable object.

Method Details

getLong

public long getLong(long index)

Description copied from class: EliasFanoMonotoneLongBigList

Returns the element at the specified position.

Specified by:

getLong in interface LongBigList

Overrides:

getLong in class EliasFanoMonotoneLongBigList

Parameters:

index - a position in the list.

Returns:

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

prefixSum

public long prefixSum(long index)

Returns the prefix sum of this list up to the given index.

Parameters:

index - an index from 0 to the length of this list.

Returns:

the sum of the values with index between 0 (inclusive) and index (exclusive).

size64

public long size64()

Specified by:

size64 in interface Size64

Overrides:

size64 in class EliasFanoMonotoneLongBigList

listIterator

public EliasFanoPrefixSumLongBigList.EliasFanoPrefixSumLongBigListIterator listIterator(long from)

Returns a list iterator over the values of this EliasFanoPrefixSumLongBigList.

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

Specified by:

listIterator in interface BigList<Long>

Specified by:

listIterator in interface LongBigList

Overrides:

listIterator in class EliasFanoMonotoneLongBigList

Parameters:

from - the starting element in the list.

Returns:

a list iterator over the values of this EliasFanoPrefixSumLongBigList.

See Also:

• EliasFanoMonotoneLongBigList.EliasFanoMonotoneLongBigListIterator

listIterator

public EliasFanoPrefixSumLongBigList.EliasFanoPrefixSumLongBigListIterator listIterator()

Returns a list iterator over the values of this EliasFanoPrefixSumLongBigList.

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

Specified by:

listIterator in interface BigList<Long>

Specified by:

listIterator in interface LongBigList

Overrides:

listIterator in class EliasFanoMonotoneLongBigList

Returns:

a list iterator over the values of this EliasFanoPrefixSumLongBigList.

See Also:

• EliasFanoMonotoneLongBigList.EliasFanoMonotoneLongBigListIterator

iterator

public EliasFanoPrefixSumLongBigList.EliasFanoPrefixSumLongBigListIterator iterator()

Returns a list iterator over the values of this EliasFanoPrefixSumLongBigList.

Forward iteration will be faster than iterated calls to getLong(). Backward iteration is available, but it will performs 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 EliasFanoMonotoneLongBigList

Returns:

a list iterator over the values of this EliasFanoPrefixSumLongBigList.

See Also:

• EliasFanoMonotoneLongBigList.EliasFanoMonotoneLongBigListIterator