it.unimi.dsi.sux4j.bits
Class SparseSelect
java.lang.Object
it.unimi.dsi.fastutil.longs.AbstractLongCollection
it.unimi.dsi.fastutil.longs.AbstractLongList
it.unimi.dsi.util.AbstractLongBigList
it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList
it.unimi.dsi.sux4j.bits.SparseSelect
- All Implemented Interfaces:
- LongCollection, LongIterable, LongList, LongStack, Stack<java.lang.Long>, Select, LongBigList, java.io.Serializable, java.lang.Comparable<java.util.List<? extends java.lang.Long>>, java.lang.Iterable<java.lang.Long>, java.util.Collection<java.lang.Long>, java.util.List<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 method SparseRank.getSelect()
to obtain an instance.
- See Also:
- Serialized Form
Method Summary |
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. |
SparseRank |
getRank()
Creates a new SparseRank structure sharing data with this instance. |
long |
length()
|
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. |
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 |
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 in bits
.
SparseSelect
public SparseSelect(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,
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
protected SparseSelect(long n,
long m,
int l,
LongBigList lowerBits,
SimpleSelect selectUpper)
getRank
public SparseRank getRank()
- Creates a new
SparseRank
structure sharing data with this instance.
- Returns:
- a new
SparseRank
structure sharing data with this instance.
length
public long length()
- Specified by:
length
in interface LongBigList
- Overrides:
length
in class EliasFanoMonotoneLongBigList
numBits
public long numBits()
- Description copied from interface:
Select
- Returns the overall number of bits allocated by this structure.
- Specified by:
numBits
in interface Select
- Overrides:
numBits
in class EliasFanoMonotoneLongBigList
- 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.
- Specified by:
select
in interface Select
- Parameters:
rank
- a rank.
- Returns:
- the position of the bit of given rank; if no such position exists, −1 is returned.
bitVector
public 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.
- Specified by:
bitVector
in interface Select
- Returns:
- a copy of the underlying bit vector.