it.unimi.dsi.sux4j.bits
Class Rank9

java.lang.Object
  it.unimi.dsi.sux4j.bits.AbstractRank
      it.unimi.dsi.sux4j.bits.Rank9

All Implemented Interfaces:

Rank, Serializable

public class Rank9
extends AbstractRank
implements Rank

A rank9 implementation.

rank9 is a ranking structure using just 25% additional space and providing exceptionally fast ranking (on an Opteron at 2800 MHz this class ranks a million-bit array in less than 8 nanoseconds).

See Also:

Serialized Form

Field Summary

protected long[]	bits
protected BitVector	bitVector
protected long[]	count
protected long	lastOne
protected long	numOnes
protected int	numWords

Constructor Summary

Rank9(BitVector bitVector)

Rank9(long[] bits, long length)

Method Summary

BitVector	bitVector() Returns the bit vector indexed by this structure.
long	count() Returns the number of ones in the bit vector indexed by this class.
long	lastOne()
long	numBits() Returns the overall number of bits allocated by this structure.
long	rank(long pos) Returns the number of ones preceding the specified position.
long	rank(long from, long to) Returns the number of ones in the specified interval.

Methods inherited from class it.unimi.dsi.sux4j.bits.AbstractRank

rankZero, rankZero

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface it.unimi.dsi.sux4j.bits.Rank

rankZero, rankZero

Field Detail

bits

protected transient long[] bits

bitVector

protected final BitVector bitVector

count

protected final long[] count

numWords

protected final int numWords

numOnes

protected final long numOnes

lastOne

protected final long lastOne

Constructor Detail

Rank9

public Rank9(long[] bits,
             long length)

Rank9

public Rank9(BitVector bitVector)

Method Detail

rank

public long rank(long pos)

Description copied from interface: Rank

Returns the number of ones preceding the specified position.

Specified by:

rank in interface Rank

Parameters:

pos - a position in the bit vector.

Returns:

the number of ones preceding pos.

numBits

public long numBits()

Description copied from interface: Rank

Returns the overall number of bits allocated by this structure.

Specified by:

numBits in interface Rank

Returns:

the overall number of bits allocated by this structure (not including the bits of the indexed vector).

count

public long count()

Description copied from interface: Rank

Returns the number of ones in the bit vector indexed by this class.

Specified by:

count in interface Rank

Overrides:

count in class AbstractRank

Returns:

number of ones in the bit vector indexed by this class.

rank

public long rank(long from,
                 long to)

Description copied from interface: Rank

Returns the number of ones in the specified interval.

Specified by:

rank in interface Rank

Overrides:

rank in class AbstractRank

Parameters:

from - a position in the bit vector.

to - a position in the bit vector.

Returns:

the number of ones between from (inclusive) and to (exclusive); if to is smaller than from, 0 is returned.

lastOne

public long lastOne()

bitVector

public BitVector bitVector()

Description copied from interface: Rank

Returns the bit vector indexed by this structure.

Note that you are not supposed to modify the returned vector.

Specified by:

bitVector in interface Rank

Returns:

the bit vector indexed by this structure.