it.unimi.dsi.sux4j.bits
Class SimpleSelectZero

java.lang.Object
  extended by 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 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

Constructor Summary
SimpleSelectZero(BitVector bitVector)
           
SimpleSelectZero(long[] bits, long length)
           
 
Method Summary
 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 rank.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

SimpleSelectZero

public SimpleSelectZero(long[] bits,
                        long length)

SimpleSelectZero

public SimpleSelectZero(BitVector bitVector)
Method Detail

selectZero

public long selectZero(long rank)
Description copied from interface: SelectZero
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:
selectZero in interface SelectZero
Parameters:
rank - a rank.
Returns:
the position of the bit of given rank; if no such position exists, −1 is returned.

numBits

public long numBits()
Description copied from interface: SelectZero
Returns the overall number of bits allocated by this structure.

Specified by:
numBits in interface SelectZero
Returns:
the overall number of bits allocated by this structure (not including the bits of the indexed vector).

bitVector

public 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 interface SelectZero
Returns:
the bit vector indexed by this structure.