Package it.unimi.dsi.sux4j.bits
Class SimpleSelectZero
- java.lang.Object
-
- it.unimi.dsi.sux4j.bits.SimpleSelectZero
-
- All Implemented Interfaces:
SelectZero
,java.io.Serializable
public class SimpleSelectZero extends java.lang.Object implements SelectZero
A simple zero-select implementation based on a two-level inventory, a spill list and broadword bit search.This implementation uses around 13.75% additional space on evenly distributed bit arrays, and, under the same conditions, provide very fast selects. For very unevenly distributed arrays the space occupancy will grow significantly, and access time might vary wildly.
- See Also:
- Serialized Form
- Implementation Notes:
- The bulk methods makes it possible to
select several consecutive bits at high speed, if the array is reasonably uniform. This
is the typical case when this structure is backing an
EliasFanoMonotoneLongBigList
.
-
-
Constructor Summary
Constructors Constructor Description SimpleSelectZero(long[] bits, long length)
Creates a new selection structure using a bit vector specified by an array of longs and a number of bits.SimpleSelectZero(it.unimi.dsi.bits.BitVector bitVector)
Creates a new selection structure using the specified bit vector.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description it.unimi.dsi.bits.BitVector
bitVector()
Returns the bit vector indexed by this structure.long
numBits()
Returns the overall number of bits allocated by this structure.long
selectZero(long rank)
Returns the position of the bit of given zero rank.long[]
selectZero(long rank, long[] dest)
Performs a bulk select of consecutive ranks into a given array.long[]
selectZero(long rank, long[] dest, int offset, int length)
Performs a bulk select of consecutive ranks into a given array fragment.
-
-
-
Constructor Detail
-
SimpleSelectZero
public SimpleSelectZero(long[] bits, long length)
Creates a new selection structure using a bit vector specified by an array of longs and a number of bits.- Parameters:
bits
- an array of longs representing a bit array.length
- the number of bits to use frombits
.
-
SimpleSelectZero
public SimpleSelectZero(it.unimi.dsi.bits.BitVector bitVector)
Creates a new selection structure using the specified bit vector.- Parameters:
bitVector
- a bit vector.
-
-
Method Detail
-
selectZero
public long selectZero(long rank)
Description copied from interface:SelectZero
Returns the position of the bit of given zero rank. Equivalently, returns the greatest position that is preceded by the specified number of zeroes.- Specified by:
selectZero
in interfaceSelectZero
- Parameters:
rank
- a zero rank.- Returns:
- the position of the bit of given zero rank; if no such bit exists, behavior is undefined .
-
selectZero
public long[] selectZero(long rank, long[] dest, int offset, int length)
Performs a bulk select of consecutive ranks into a given array fragment.- Specified by:
selectZero
in interfaceSelectZero
- Parameters:
rank
- the first rank to select.dest
- the destination array; it will be filled withlength
positions of consecutive bits starting at positionoffset
; must be of length greater thanoffset
.offset
- the first bit position written indest
.length
- the number of bit positions indest
starting atoffset
.- Returns:
dest
- See Also:
selectZero(long, long[])
- Implementation Notes:
dest
must be of length greater thanoffset
even iflength
is zero.
-
selectZero
public long[] selectZero(long rank, long[] dest)
Performs a bulk select of consecutive ranks into a given array.- Specified by:
selectZero
in interfaceSelectZero
- Parameters:
rank
- the first rank to select.dest
- the destination array; it will be filled with position of consecutive bits; must be of length greater than zero.- Returns:
dest
- See Also:
selectZero(long, long[], int, int)
- Implementation Notes:
dest
must be of length greater than zero.
-
numBits
public long numBits()
Description copied from interface:SelectZero
Returns the overall number of bits allocated by this structure.- Specified by:
numBits
in interfaceSelectZero
- Returns:
- the overall number of bits allocated by this structure (not including the bits of the indexed vector).
-
bitVector
public it.unimi.dsi.bits.BitVector bitVector()
Description copied from interface:SelectZero
Returns the bit vector indexed by this structure.Note that you are not supposed to modify the returned vector.
- Specified by:
bitVector
in interfaceSelectZero
- Returns:
- the bit vector indexed by this structure.
-
-