|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectit.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
public class SparseSelect
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. In that
case, numBits()
counts just the new data used to build the class, and not the shared part.
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 | |
---|---|
protected boolean |
fromRank
Whether this structure was built from a SparseRank structure, and thus shares part of its internal state. |
Fields inherited from class it.unimi.dsi.sux4j.util.EliasFanoMonotoneLongBigList |
---|
l, length, lowerBits, selectUpper |
Constructor Summary | |
---|---|
|
SparseSelect(BitVector bitVector)
Creates a new select structure using a bit vector. |
|
SparseSelect(long[] bits,
long length)
Creates a new select structure using a long array. |
|
SparseSelect(LongBigList list)
Creates a new select structure using a big list of longs. |
|
SparseSelect(LongList list)
Creates a new select structure using a list of longs. |
protected |
SparseSelect(long n,
long m,
int l,
LongBigList lowerBits,
SimpleSelect selectUpper)
|
|
SparseSelect(long n,
long m,
LongIterator iterator)
Creates a new select structure using an iterator. |
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. |
boolean |
equals(Object o)
|
long |
getLong(long pos)
|
SparseRank |
getRank()
Creates a new SparseRank structure sharing data with this instance. |
int |
hashCode()
|
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. |
int |
size()
|
String |
toString()
|
Methods inherited from class it.unimi.dsi.util.AbstractLongBigList |
---|
add, ensureIndex, ensureRestrictedIndex, getLong, length, removeLong, set, 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, get, getElements, 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 |
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, get, 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 |
Field Detail |
---|
protected final boolean fromRank
SparseRank
structure, and thus shares part of its internal state.
Constructor Detail |
---|
public SparseSelect(long[] bits, long length)
The resulting structure keeps no reference to the original array.
bits
- a long array containing the bits.length
- the number of valid bits in bits
.public SparseSelect(BitVector bitVector)
The resulting structure keeps no reference to the original bit vector.
bitVector
- the input bit vector.public SparseSelect(long n, long m, LongIterator iterator)
This constructor is particularly useful if the positions of the ones are provided by some sequential source.
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.public SparseSelect(LongList list)
This constructor is particularly useful if the positions of the ones are provided by some sequential source.
list
- the list of the positions of ones.public SparseSelect(LongBigList list)
This constructor is particularly useful if the positions of the ones are provided by some sequential source.
list
- the list of the positions of ones.protected SparseSelect(long n, long m, int l, LongBigList lowerBits, SimpleSelect selectUpper)
Method Detail |
---|
public SparseRank getRank()
SparseRank
structure sharing data with this instance.
SparseRank
structure sharing data with this instance.public long length()
length
in interface LongBigList
length
in class EliasFanoMonotoneLongBigList
public int size()
size
in interface Collection<Long>
size
in interface List<Long>
size
in class AbstractLongBigList
public long getLong(long pos)
getLong
in interface LongBigList
getLong
in class EliasFanoMonotoneLongBigList
public long numBits()
Select
numBits
in interface Select
numBits
in class EliasFanoMonotoneLongBigList
public long select(long rank)
Select
select
in interface Select
rank
- a rank.
public BitVector bitVector()
bitVector
in interface Select
public int hashCode()
hashCode
in interface Collection<Long>
hashCode
in interface List<Long>
hashCode
in class AbstractLongList
public boolean equals(Object o)
equals
in interface Collection<Long>
equals
in interface List<Long>
equals
in class AbstractLongList
public String toString()
toString
in class AbstractLongList
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |