Class SparseSelect
- 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.bits.SparseSelect
-
- 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>
,Select
,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 SparseSelect extends EliasFanoMonotoneLongBigList implements Select
A select implementation for sparse bit arrays based on the Elias–Fano representation of monotone functions.Instances of this classes do not add support to a bit vector: rather, they replace the bit vector with a succinct representation of the positions of the ones in the bit vector.
Note that some data may be shared with
SparseRank
: just use the factory methodSparseRank.getSelect()
to obtain an instance. In that case,numBits()
counts just the new data used to build the class, and not the shared part.- See Also:
- Serialized Form
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
EliasFanoMonotoneLongBigList.EliasFanoMonotoneLongBigListIterator
-
-
Field Summary
Fields Modifier and Type Field Description protected boolean
fromRank
Whether this structure was built from aSparseRank
structure, and thus shares part of its internal state.-
Fields inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
l, length, lowerBits, lowerBitsMask, selectUpper, upperBits
-
-
Constructor Summary
Constructors Modifier Constructor Description SparseSelect(long[] bits, long length)
Creates a new select structure using a long array.protected
SparseSelect(long n, long m, int l, long[] lowerBits, SimpleSelect selectUpper)
SparseSelect(long n, long m, it.unimi.dsi.fastutil.longs.LongIterator iterator)
Creates a new select structure using an iterator.SparseSelect(it.unimi.dsi.bits.BitVector bitVector)
Creates a new select structure using a bit vector.SparseSelect(it.unimi.dsi.fastutil.longs.LongBigList list)
Creates a new select structure using a big list of longs.SparseSelect(it.unimi.dsi.fastutil.longs.LongList list)
Creates a new select structure using a list of longs.
-
Method Summary
All Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description it.unimi.dsi.bits.BitVector
bitVector()
Returns the bit vector indexed; since the bits are not stored in this data structure, a copy is built on purpose and returned.boolean
equals(java.lang.Object o)
long
getLong(long pos)
Returns the element at the specified position.SparseRank
getRank()
Creates a newSparseRank
structure sharing data with this instance.int
hashCode()
long
numBits()
Returns the overall number of bits allocated by this structure.long
select(long rank)
Returns the position of the bit of given rank.int
size()
Deprecated.long
size64()
java.lang.String
toString()
-
Methods inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
dump, dump, fits, get, get, getDelta, iterator, listIterator, listIterator
-
Methods inherited from class it.unimi.dsi.fastutil.longs.AbstractLongBigList
add, add, add, addAll, addAll, addAll, addAll, addElements, addElements, clear, compareTo, contains, ensureIndex, ensureRestrictedIndex, forEach, get, getElements, indexOf, indexOf, lastIndexOf, lastIndexOf, peek, peekLong, pop, popLong, push, push, rem, remove, removeElements, removeLong, set, set, setElements, size, subList, top, topLong
-
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
-
fromRank
protected final boolean fromRank
Whether this structure was built from aSparseRank
structure, and thus shares part of its internal state.
-
-
Constructor Detail
-
SparseSelect
public SparseSelect(long[] bits, long length)
Creates a new select structure using a long array.The resulting structure keeps no reference to the original array.
- Parameters:
bits
- a long array containing the bits.length
- the number of valid bits inbits
.
-
SparseSelect
public SparseSelect(it.unimi.dsi.bits.BitVector bitVector)
Creates a new select structure using a bit vector.The resulting structure keeps no reference to the original bit vector.
- Parameters:
bitVector
- the input bit vector.
-
SparseSelect
public SparseSelect(long n, long m, it.unimi.dsi.fastutil.longs.LongIterator iterator)
Creates a new select structure using an iterator.This constructor is particularly useful if the positions of the ones are provided by some sequential source.
- Parameters:
n
- the number of bits in the underlying bit vector.m
- the number of ones in the underlying bit vector.iterator
- an iterator returning the positions of the ones in the underlying bit vector in increasing order.
-
SparseSelect
public SparseSelect(it.unimi.dsi.fastutil.longs.LongList list)
Creates a new select structure using a list of longs.- Parameters:
list
- the list of the positions of ones.
-
SparseSelect
public SparseSelect(it.unimi.dsi.fastutil.longs.LongBigList list)
Creates a new select structure using a big list of longs.This constructor is particularly useful if the positions of the ones are provided by some sequential source.
- Parameters:
list
- the list of the positions of ones.
-
SparseSelect
protected SparseSelect(long n, long m, int l, long[] lowerBits, SimpleSelect selectUpper)
-
-
Method Detail
-
getRank
public SparseRank getRank()
Creates a newSparseRank
structure sharing data with this instance.- Returns:
- a new
SparseRank
structure sharing data with this instance.
-
size64
public long size64()
- Specified by:
size64
in interfaceit.unimi.dsi.fastutil.Size64
- Overrides:
size64
in classEliasFanoMonotoneLongBigList
-
size
@Deprecated public int size()
Deprecated.- Specified by:
size
in interfaceit.unimi.dsi.fastutil.BigList<java.lang.Long>
- Specified by:
size
in interfacejava.util.Collection<java.lang.Long>
- Specified by:
size
in interfaceit.unimi.dsi.fastutil.Size64
- Overrides:
size
in classit.unimi.dsi.fastutil.longs.AbstractLongBigList
-
getLong
public long getLong(long pos)
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:
pos
- a position in the list.- Returns:
- the element at the specified position; if
index
is out of bounds, behavior is undefined.
-
numBits
public long numBits()
Description copied from interface:Select
Returns the overall number of bits allocated by this structure.- Specified by:
numBits
in interfaceSelect
- Overrides:
numBits
in classEliasFanoMonotoneLongBigList
- Returns:
- the overall number of bits allocated by this structure (not including the bits of the indexed vector).
-
select
public long select(long rank)
Description copied from interface:Select
Returns the position of the bit of given rank. Equivalently, returns the greatest position that is preceded by the specified number of ones.
-
bitVector
public it.unimi.dsi.bits.BitVector bitVector()
Returns the bit vector indexed; since the bits are not stored in this data structure, a copy is built on purpose and returned.
-
hashCode
public int hashCode()
- Specified by:
hashCode
in interfacejava.util.Collection<java.lang.Long>
- Overrides:
hashCode
in classit.unimi.dsi.fastutil.longs.AbstractLongBigList
-
equals
public boolean equals(java.lang.Object o)
- Specified by:
equals
in interfacejava.util.Collection<java.lang.Long>
- Overrides:
equals
in classit.unimi.dsi.fastutil.longs.AbstractLongBigList
-
toString
public java.lang.String toString()
- Overrides:
toString
in classit.unimi.dsi.fastutil.longs.AbstractLongBigList
-
-