Class EliasFanoPrefixSumLongBigList
- 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.util.EliasFanoMonotoneLongBigList
-
- it.unimi.dsi.sux4j.util.EliasFanoPrefixSumLongBigList
-
- 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 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. ThegetLong(long)
method delegates toEliasFanoMonotoneLongBigList.getDelta(long)
. The iterator has the same properties of the iterator returned byEliasFanoMonotoneLongBiglist
.- 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 thisEliasFanoPrefixSumLongBigList
.-
Nested classes/interfaces inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
EliasFanoMonotoneLongBigList.EliasFanoMonotoneLongBigListIterator
-
-
Field Summary
-
Fields inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
l, length, lowerBits, lowerBitsMask, selectUpper
-
-
Constructor Summary
Constructors Constructor Description EliasFanoPrefixSumLongBigList(it.unimi.dsi.fastutil.bytes.ByteIterable elements)
Creates a new Elias–Fano prefix-sum long big list.EliasFanoPrefixSumLongBigList(it.unimi.dsi.fastutil.ints.IntIterable elements)
Creates a new Elias–Fano prefix-sum long big list.EliasFanoPrefixSumLongBigList(it.unimi.dsi.fastutil.longs.LongIterable elements)
Creates a new Elias–Fano prefix-sum long big list.EliasFanoPrefixSumLongBigList(it.unimi.dsi.fastutil.shorts.ShortIterable elements)
Creates a new Elias–Fano prefix-sum long big list.
-
Method Summary
All Methods Instance Methods Concrete Methods 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 thisEliasFanoPrefixSumLongBigList
.EliasFanoPrefixSumLongBigList.EliasFanoPrefixSumLongBigListIterator
listIterator()
Returns a list iterator over the values of thisEliasFanoPrefixSumLongBigList
.EliasFanoPrefixSumLongBigList.EliasFanoPrefixSumLongBigListIterator
listIterator(long from)
Returns a list iterator over the values of thisEliasFanoPrefixSumLongBigList
.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.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
-
-
-
-
Constructor Detail
-
EliasFanoPrefixSumLongBigList
public EliasFanoPrefixSumLongBigList(it.unimi.dsi.fastutil.longs.LongIterable elements)
Creates a new Elias–Fano prefix-sum long big list.- Parameters:
elements
- an iterable object.
-
EliasFanoPrefixSumLongBigList
public EliasFanoPrefixSumLongBigList(it.unimi.dsi.fastutil.ints.IntIterable elements)
Creates a new Elias–Fano prefix-sum long big list.- Parameters:
elements
- an iterable object.
-
EliasFanoPrefixSumLongBigList
public EliasFanoPrefixSumLongBigList(it.unimi.dsi.fastutil.shorts.ShortIterable elements)
Creates a new Elias–Fano prefix-sum long big list.- Parameters:
elements
- an iterable object.
-
EliasFanoPrefixSumLongBigList
public EliasFanoPrefixSumLongBigList(it.unimi.dsi.fastutil.bytes.ByteIterable elements)
Creates a new Elias–Fano prefix-sum long big list.- Parameters:
elements
- an iterable object.
-
-
Method Detail
-
getLong
public long getLong(long index)
Description copied from class:EliasFanoMonotoneLongBigList
Returns the element at the specified position.- Specified by:
getLong
in interfaceit.unimi.dsi.fastutil.longs.LongBigList
- Overrides:
getLong
in classEliasFanoMonotoneLongBigList
- 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 interfaceit.unimi.dsi.fastutil.Size64
- Overrides:
size64
in classEliasFanoMonotoneLongBigList
-
listIterator
public EliasFanoPrefixSumLongBigList.EliasFanoPrefixSumLongBigListIterator listIterator(long from)
Returns a list iterator over the values of thisEliasFanoPrefixSumLongBigList
.Forward iteration will be faster than iterated calls to
getLong()
. Backward iteration is available, but it will performs similarly togetLong()
.- Specified by:
listIterator
in interfaceit.unimi.dsi.fastutil.BigList<java.lang.Long>
- Specified by:
listIterator
in interfaceit.unimi.dsi.fastutil.longs.LongBigList
- Overrides:
listIterator
in classEliasFanoMonotoneLongBigList
- 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 thisEliasFanoPrefixSumLongBigList
.Forward iteration will be faster than iterated calls to
getLong()
. Backward iteration is available, but it will performs similarly togetLong()
.- Specified by:
listIterator
in interfaceit.unimi.dsi.fastutil.BigList<java.lang.Long>
- Specified by:
listIterator
in interfaceit.unimi.dsi.fastutil.longs.LongBigList
- Overrides:
listIterator
in classEliasFanoMonotoneLongBigList
- 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 thisEliasFanoPrefixSumLongBigList
.Forward iteration will be faster than iterated calls to
getLong()
. Backward iteration is available, but it will performs similarly togetLong()
.- Specified by:
iterator
in interfacejava.util.Collection<java.lang.Long>
- Specified by:
iterator
in interfacejava.lang.Iterable<java.lang.Long>
- Specified by:
iterator
in interfaceit.unimi.dsi.fastutil.longs.LongBigList
- Specified by:
iterator
in interfaceit.unimi.dsi.fastutil.longs.LongCollection
- Specified by:
iterator
in interfaceit.unimi.dsi.fastutil.longs.LongIterable
- Overrides:
iterator
in classEliasFanoMonotoneLongBigList
- Returns:
- a list iterator over the values of this
EliasFanoPrefixSumLongBigList
. - See Also:
EliasFanoMonotoneLongBigList.EliasFanoMonotoneLongBigListIterator
-
-