Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.WaveletMatrix.BitVector

Description

Bit vector (in the context of wavelet matrix) is a collection of bits that can handle rank (freq) in $O(1)$ and select (findIndex) in $O(\log N)$ without much memory.

There are two popular ways for implementing such a bit vector.

Word-based cumulative sum

One way to implement such a bit vector is to use a cumulative sum of bits by words (& bytes). This module is implemented with that.

Succinct bit vector

Another way to implement a bit vector with less memory is using a succinct bit vector. Unless large $N$ problems come, I might not implement it.

Synopsis

wordWM :: Int
data BitVector = BitVector {
- bitsBV :: !(Vector Bit)
- csumBV :: !(Vector Int)
}
csumInPlaceBV :: PrimMonad m => MVector (PrimState m) Int -> Vector Bit -> m Int
newCSumBV :: Vector Bit -> Vector Int
freq0BV :: BitVector -> Int -> Int
freq1BV :: BitVector -> Int -> Int
findKthIndex0BV :: BitVector -> Int -> Maybe Int
findKthIndex1BV :: BitVector -> Int -> Maybe Int
lrFindKthIndex0BV :: BitVector -> Int -> Int -> Int -> Maybe Int
lrFindKthIndex1BV :: BitVector -> Int -> Int -> Int -> Maybe Int

Documentation

wordWM :: Int #

Block sized for the internal cumultaive sum in the bit vector.

data BitVector #

Bit vector is a collection of bits that can handle rank (freq) in $O(1)$ and select (findIndex) in $O(N)$.

Constructors

BitVector
Fields bitsBV :: !(Vector Bit) Bits. csumBV :: !(Vector Int) Cumulative sum of bits by words.

Instances

Instances details

Show BitVector #
Instance details Defined in Data.WaveletMatrix.BitVector Methods showsPrec :: Int -> BitVector -> ShowS # show :: BitVector -> String # showList :: [BitVector] -> ShowS #
Eq BitVector #
Instance details Defined in Data.WaveletMatrix.BitVector Methods (==) :: BitVector -> BitVector -> Bool # (/=) :: BitVector -> BitVector -> Bool #

csumInPlaceBV :: PrimMonad m => MVector (PrimState m) Int -> Vector Bit -> m Int #

$O(N)$ Calculates the cumulative sum by word for the bit vector in-place.

newCSumBV :: Vector Bit -> Vector Int #

$O(N)$ Calculates the cumulative sum by word for the bit vector.

freq0BV :: BitVector -> Int -> Int #

$O(1)$ Counts the number of 0 bits in interval [0, i). The input is a cumulative sum of bit vector by word. Rank 0.

freq1BV :: BitVector -> Int -> Int #

$O(1)$ Counts the number of 1 bits in interval [0, i). The input is a cumulative sum of bit vector by word. Rank 1.

findKthIndex0BV :: BitVector -> Int -> Maybe Int #

$O(\log N)$ Finds the index of kth 0. Select 0.

findKthIndex1BV :: BitVector -> Int -> Maybe Int #

$O(\log N)$ Finds the index of kth 1. Select 1.

lrFindKthIndex0BV :: BitVector -> Int -> Int -> Int -> Maybe Int #

$O(\log N)$ Finds the index of kth 0 in [l, r]. Select 0.

lrFindKthIndex1BV :: BitVector -> Int -> Int -> Int -> Maybe Int #

$O(\log N)$ Finds the index of kth 1 in [l, r]. Select 1.