Package it.unimi.dsi.sux4j.bits
Class SimpleSelect
java.lang.Object
it.unimi.dsi.sux4j.bits.SimpleSelect
 All Implemented Interfaces:
Select
,Serializable
A simple select implementation based on a twolevel 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:
 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
ConstructorDescriptionSimpleSelect
(long[] bits, long length) Creates a new selection structure using a bit vector specified by an array of longs and a number of bits.SimpleSelect
(BitVector bitVector) Creates a new selection structure using the specified bit vector. 
Method Summary
Modifier and TypeMethodDescriptionReturns the bit vector indexed by this structure.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.long[]
select
(long rank, long[] dest) Performs a bulk select of consecutive ranks into a given array.long[]
select
(long rank, long[] dest, int offset, int length) Performs a bulk select of consecutive ranks into a given array fragment.

Constructor Details

SimpleSelect
public SimpleSelect(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
.

SimpleSelect
Creates a new selection structure using the specified bit vector. Parameters:
bitVector
 a bit vector.


Method Details

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. 
select
public long[] select(long rank, long[] dest, int offset, int length) Performs a bulk select of consecutive ranks into a given array fragment. Specified by:
select
in interfaceSelect
 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:
 Implementation Notes:
dest
must be of length greater thanoffset
even iflength
is zero.

select
public long[] select(long rank, long[] dest) Performs a bulk select of consecutive ranks into a given array. 
numBits
public long numBits()Description copied from interface:Select
Returns the overall number of bits allocated by this structure. Specified by:
numBits
in interfaceSelect
 Returns:
 the overall number of bits allocated by this structure (not including the bits of the indexed vector).

bitVector
Description copied from interface:Select
Returns the bit vector indexed by this structure.Note that you are not supposed to modify the returned vector.
