Package org.wikidata.wdtk.storage.datastructures

Interface RankedBitVector

All Superinterfaces:

BitVector

All Known Implementing Classes:

RankedBitVectorImpl

public interface RankedBitVector
extends BitVector

A ranked bit vector provides operations to compute:

• rank (countBits(boolean, long)): number of occurrences of a bit at a certain position
• select (findPosition(boolean, long)): position of the n-th occurrence of a certain bit

Author:

Julian Mendez

Field Summary

Fields

Modifier and Type	Field	Description
static final long	NOT_FOUND	This is a distinguished value, which denotes that the position of a n-th occurrence of a bit was not found.

Method Summary

Modifier and Type	Method	Description
long	countBits(boolean bit, long position)	This is the "rank" method of bit vectors.
long	findPosition(boolean bit, long nOccurrence)	This is the "select" method of bit vectors.

Methods inherited from interface org.wikidata.wdtk.storage.datastructures.BitVector

addBit, equals, getBit, iterator, setBit, size

Field Details

NOT_FOUND

static final long NOT_FOUND

This is a distinguished value, which denotes that the position of a n-th occurrence of a bit was not found. This value is a negative number.

See Also:

• findPosition(boolean, long)
• Constant Field Values

Method Details

countBits

long countBits(boolean bit,
 long position)

This is the "rank" method of bit vectors. This method returns the number of occurrences of bit up to position.

Parameters:

bit - bit

position - position

Returns:

number of occurrences of bit at position

findPosition

long findPosition(boolean bit,
 long nOccurrence)

This is the "select" method of bit vectors. This method returns the position of the n-th occurrence (nOccurrence) of bit or NOT_FOUND if there are not enough occurrences.

Parameters:

bit - bit

nOccurrence - number of occurrences

Returns:

position of the n-th occurrence (nOccurrence) of bit or NOT_FOUND if there are not enough occurrences