Class EliasFanoMonotoneBigLongBigList
- 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.EliasFanoMonotoneBigLongBigList
-
- 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 EliasFanoMonotoneBigLongBigList extends it.unimi.dsi.fastutil.longs.AbstractLongBigList implements java.io.Serializable
An implementation of Elias–Fano's representation of monotone sequences identical toEliasFanoMonotoneLongBigList
, but slightly slower and without size limitations.Instances of this class can be memory mapped using
MappedEliasFanoMonotoneLongBigList
.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator
A list iterator over the values of thisEliasFanoMonotoneBigLongBigList
.
-
Field Summary
Fields Modifier and Type Field Description protected int
l
The number of lower bits.protected 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 long
lowerBitsMask
The mask for the lower bits.protected 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, it.unimi.dsi.fastutil.longs.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, it.unimi.dsi.fastutil.bytes.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, it.unimi.dsi.fastutil.ints.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, it.unimi.dsi.fastutil.longs.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, it.unimi.dsi.fastutil.shorts.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(it.unimi.dsi.fastutil.bytes.ByteIterable list)
Creates an Elias–Fano representation of the values returned by the given iterable object.EliasFanoMonotoneBigLongBigList(it.unimi.dsi.fastutil.ints.IntIterable list)
Creates an Elias–Fano representation of the values returned by the given iterable object.EliasFanoMonotoneBigLongBigList(it.unimi.dsi.fastutil.longs.LongIterable list)
Creates an Elias–Fano representation of the values returned by the given iterable object.EliasFanoMonotoneBigLongBigList(it.unimi.dsi.fastutil.shorts.ShortIterable list)
Creates an Elias–Fano representation of the values returned by the given iterable object.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
dump(java.lang.String basename)
Dumps this list's lower bits in native order so that it can be used withMappedEliasFanoMonotoneLongBigList
.void
dump(java.lang.String basename, java.nio.ByteOrder byteOrder)
Dumps this list's lower bits so that it can be used withMappedEliasFanoMonotoneLongBigList
.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 thisEliasFanoMonotoneBigLongBigList
.EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator
listIterator()
Returns a list iterator over the values of thisEliasFanoMonotoneBigLongBigList
.EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator
listIterator(long from)
Returns a list iterator over the values of thisEliasFanoMonotoneBigLongBigList
.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.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
-
-
-
-
Field Detail
-
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 Detail
-
EliasFanoMonotoneBigLongBigList
protected EliasFanoMonotoneBigLongBigList(long length, int l, long[][] upperBits, long[][] lowerBits, SimpleBigSelect selectUpper)
-
EliasFanoMonotoneBigLongBigList
public EliasFanoMonotoneBigLongBigList(it.unimi.dsi.fastutil.ints.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(it.unimi.dsi.fastutil.shorts.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(it.unimi.dsi.fastutil.bytes.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(it.unimi.dsi.fastutil.longs.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, it.unimi.dsi.fastutil.bytes.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 byiterator
.upperBound
- a strict upper bound to the values returned byiterator
(note that it used to be non-strict).iterator
- an iterator returning nondecreasing natural numbers.
-
EliasFanoMonotoneBigLongBigList
public EliasFanoMonotoneBigLongBigList(long n, long upperBound, it.unimi.dsi.fastutil.shorts.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 byiterator
.upperBound
- a strict upper bound to the values returned byiterator
(note that it used to be non-strict).iterator
- an iterator returning nondecreasing natural numbers.
-
EliasFanoMonotoneBigLongBigList
public EliasFanoMonotoneBigLongBigList(long n, long upperBound, it.unimi.dsi.fastutil.ints.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 byiterator
.upperBound
- a strict upper bound to the values returned byiterator
(note that it used to be non-strict).iterator
- an iterator returning nondecreasing natural numbers.
-
EliasFanoMonotoneBigLongBigList
public EliasFanoMonotoneBigLongBigList(long n, long upperBound, it.unimi.dsi.fastutil.longs.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 byiterator
.upperBound
- a strict upper bound to the values returned byiterator
(note that it used to be non-strict).iterator
- an iterator returning nondecreasing natural numbers.
-
EliasFanoMonotoneBigLongBigList
protected EliasFanoMonotoneBigLongBigList(long[] a, it.unimi.dsi.fastutil.longs.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 byiterator
and a strict upper bound to the values returned byiterator
(note that it used to be non-strict).iterator
- an iterator returning nondecreasing natural numbers.
-
-
Method Detail
-
numBits
public long numBits()
-
getLong
public long getLong(long index)
Returns the element at the specified position.- Specified by:
getLong
in interfaceit.unimi.dsi.fastutil.longs.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 thensize64()
- 1).- Returns:
- the difference between the element of position
index + 1
and that of positionindex
; ifindex
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 withlength
consecutive entries starting at positionoffset
; must be of length greater thanoffset
.offset
- the first position written indest
.length
- the number of elements written indest
starting atoffset
.- 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
; ifindex
is out of bounds ordest
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 thisEliasFanoMonotoneBigLongBigList
.Forward iteration will be faster than iterated calls to
getLong()
. Backward iteration is available, but it will perform 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 classit.unimi.dsi.fastutil.longs.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 thisEliasFanoMonotoneBigLongBigList
.Forward iteration will be faster than iterated calls to
getLong()
. Backward iteration is available, but it will perform 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 classit.unimi.dsi.fastutil.longs.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 thisEliasFanoMonotoneBigLongBigList
.Forward iteration will be faster than iterated calls to
getLong()
. Backward iteration is available, but it will perform 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 classit.unimi.dsi.fastutil.longs.AbstractLongBigList
- Returns:
- a list iterator over the values of this
EliasFanoMonotoneBigLongBigList
. - See Also:
EliasFanoMonotoneBigLongBigList.EliasFanoMonotoneLongBigListIterator
-
size64
public long size64()
- Specified by:
size64
in interfaceit.unimi.dsi.fastutil.Size64
-
dump
public void dump(java.lang.String basename) throws java.io.IOException
Dumps this list's lower bits in native order so that it can be used withMappedEliasFanoMonotoneLongBigList
.- Parameters:
basename
- the basename of the generated files.- Throws:
java.io.IOException
-
dump
public void dump(java.lang.String basename, java.nio.ByteOrder byteOrder) throws java.io.IOException
Dumps this list's lower bits so that it can be used withMappedEliasFanoMonotoneLongBigList
.Two files will be generated: a serialized object with extension
MappedEliasFanoMonotoneLongBigList.OBJECT_EXTENSION
and a list of longs in the specified byte order with extensionMappedEliasFanoMonotoneLongBigList.LOWER_BITS_EXTENSION
.- Parameters:
basename
- the basename of the generated files.byteOrder
- the desired byte order.- Throws:
java.io.IOException
-
-