it.unimi.dsi.sux4j.util
Class EliasFanoPrefixSumLongBigList

java.lang.Object
  extended by it.unimi.dsi.fastutil.longs.AbstractLongCollection
      extended by it.unimi.dsi.fastutil.longs.AbstractLongList
          extended by it.unimi.dsi.util.AbstractLongBigList
              extended by it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
                  extended by it.unimi.dsi.sux4j.util.EliasFanoPrefixSumLongBigList
All Implemented Interfaces:
LongCollection, LongIterable, LongList, LongStack, Stack<Long>, LongBigList, Serializable, Comparable<List<? extends Long>>, Iterable<Long>, Collection<Long>, List<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 has been optimised so to avoid two calls to the getLong(long) method of the EliasFanoMonotoneLongBigList.

See Also:
Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from class it.unimi.dsi.util.AbstractLongBigList
AbstractLongBigList.LongSubBigList
 
Nested classes/interfaces inherited from class it.unimi.dsi.fastutil.longs.AbstractLongList
AbstractLongList.LongSubList
 
Field Summary
 
Fields inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
l, length, lowerBits, selectUpper
 
Constructor Summary
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
 long getLong(long index)
           
 long length()
           
 long prefixSum(long index)
          Returns the prefix sum of this list up to the given index.
 
Methods inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
numBits
 
Methods inherited from class it.unimi.dsi.util.AbstractLongBigList
add, ensureIndex, ensureRestrictedIndex, getLong, length, removeLong, set, size, subList
 
Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongList
add, add, add, addAll, addAll, addAll, addAll, addAll, addAll, addElements, addElements, compareTo, contains, ensureIndex, ensureRestrictedIndex, equals, get, getElements, hashCode, indexOf, indexOf, iterator, lastIndexOf, lastIndexOf, listIterator, listIterator, longListIterator, longListIterator, longSubList, peek, peekLong, pop, popLong, push, push, rem, remove, remove, removeElements, removeLong, set, set, size, subList, top, topLong, toString
 
Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongCollection
add, clear, contains, containsAll, containsAll, isEmpty, longIterator, rem, removeAll, removeAll, retainAll, retainAll, toArray, toArray, toArray, toLongArray, toLongArray
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface it.unimi.dsi.fastutil.longs.LongList
add, addAll, addAll, addAll, addElements, addElements, getElements, indexOf, iterator, lastIndexOf, listIterator, listIterator, longListIterator, longListIterator, longSubList, removeElements, removeLong, set, size, subList
 
Methods inherited from interface java.util.List
add, add, addAll, addAll, clear, contains, containsAll, equals, get, hashCode, indexOf, isEmpty, lastIndexOf, remove, remove, removeAll, retainAll, set, toArray, toArray
 
Methods inherited from interface java.lang.Comparable
compareTo
 
Methods inherited from interface it.unimi.dsi.fastutil.longs.LongCollection
add, addAll, contains, containsAll, longIterator, rem, removeAll, retainAll, toArray, toArray, toLongArray, toLongArray
 
Methods inherited from interface it.unimi.dsi.fastutil.Stack
isEmpty
 

Constructor Detail

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 Detail

getLong

public long getLong(long index)
Specified by:
getLong in interface LongBigList
Overrides:
getLong in class EliasFanoMonotoneLongBigList

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

length

public long length()
Specified by:
length in interface LongBigList
Overrides:
length in class EliasFanoMonotoneLongBigList