Class RankSelectBitSet

Namespace

BelNytheraSeiche.TrieDictionary

Assembly

BelNytheraSeiche.TrieDictionary.dll

An immutable bit set optimized for high-performance Rank and Select operations.

public sealed class RankSelectBitSet : ImmutableBitSet

Inheritance

object

ImmutableBitSet

RankSelectBitSet

Inherited Members

ImmutableBitSet.Buffer

ImmutableBitSet.Count

ImmutableBitSet.this[int]

ImmutableBitSet.At(int)

ImmutableBitSet.ToRankSelect(bool)

ImmutableBitSet.ToRankSelect(ImmutableBitSet, bool)

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Remarks

This data structure uses auxiliary indexes (lookup tables) to perform Rank (counting bits) and Select (finding the n-th bit) operations in near-constant time, making it suitable for succinct data structures like LOUDS Tries.

Constructors

RankSelectBitSet(ulong[], int)

An immutable bit set optimized for high-performance Rank and Select operations.

public RankSelectBitSet(ulong[] buffer, int count)

Parameters

buffer ulong[]

The underlying ulong array that stores the bits.

count int

The total number of bits in the set.

Remarks

This data structure uses auxiliary indexes (lookup tables) to perform Rank (counting bits) and Select (finding the n-th bit) operations in near-constant time, making it suitable for succinct data structures like LOUDS Tries.

Methods

CreateAuxDir(ImmutableBitSet)

Creates the auxiliary directories required for fast Rank and Select operations from a given bit set.

public static (int[], short[], int[]) CreateAuxDir(ImmutableBitSet bitSet)

Parameters

bitSet ImmutableBitSet

The immutable bit set to process.

Returns

(int[], short[], int[])

A tuple containing the generated directories for rank and select.

GetAuxDir()

Gets the pre-calculated auxiliary directories for Rank and Select operations.

public (int[], short[], int[]) GetAuxDir()

Returns

(int[], short[], int[])

A tuple containing the rank primary directory, rank secondary directory, and the select directory.

LastRank1()

Gets the total number of set bits (1s) in the entire bit set.

public int LastRank1()

Returns

int

The total count of set bits.

Rank0(int)

Calculates the rank of a bit '0' at a specified position. Rank0 is the total number of unset bits (0s) up to, but not including, the given position k.

public int Rank0(int k)

Parameters

k int

The zero-based position index.

Returns

int

The number of unset bits before position k.

Rank1(int)

Calculates the rank of a bit '1' at a specified position. Rank is the total number of set bits (1s) up to and including the given position k.

public int Rank1(int k)

Parameters

k int

The zero-based position index.

Returns

int

The number of set bits up to and including position k.

Select0(int)

Finds the position of the k-th unset bit (0).

public int Select0(int k)

Parameters

k int

The one-based rank of the unset bit to find (e.g., k=1 for the first '0').

Returns

int

The zero-based index of the k-th unset bit, or -1 if not found.

Select1(int)

Finds the position of the k-th set bit (1).

public int Select1(int k)

Parameters

k int

The one-based rank of the set bit to find (e.g., k=1 for the first '1').

Returns

int

The zero-based index of the k-th set bit, or -1 if not found.

SetAuxDir((int[], short[], int[]))

Sets the pre-calculated auxiliary directories for Rank and Select operations.

public void SetAuxDir((int[], short[], int[]) auxDir)

Parameters

auxDir (int[], short[], int[])

A tuple containing the rank primary directory, rank secondary directory, and the select directory.