toy-lib-0.1.0.0
Safe HaskellSafe-Inferred
LanguageHaskell2010

Data.WaveletMatrix.Raw

Description

Wavelet Matrix without index comperssion.

https://miti-7.hatenablog.com/entry/2018/04/28/152259

Synopsis

Documentation

data RawWaveletMatrix #

Wavelet Matrix without index comperssion.

Constructors

RawWaveletMatrix 

Fields

  • heightRWM :: !Int

    \(\lceil \log_2 N \rceil\).

  • lengthRWM :: !Int

    The length of the original array.

  • bitsRWM :: !(Vector BitVector)

    The bit matrix. Each row represents (heightRWM - 1 - iRow) bit's on/off. It takes memory space of \(N\) bytes.

  • nZerosRWM :: !(Vector Int)

    The number of zeros in each row in the bit matrix. TODO: consider removing it ('cause we have csumsRWM). It could be even faster.

Instances

Instances details
Show RawWaveletMatrix # 
Instance details

Defined in Data.WaveletMatrix.Raw

Methods

showsPrec :: Int -> RawWaveletMatrix -> ShowS #

show :: RawWaveletMatrix -> String #

showList :: [RawWaveletMatrix] -> ShowS #

Eq RawWaveletMatrix # 
Instance details

Defined in Data.WaveletMatrix.Raw

Methods

(==) :: RawWaveletMatrix -> RawWaveletMatrix -> Bool #

(/=) :: RawWaveletMatrix -> RawWaveletMatrix -> Bool #

buildRWM :: Int -> Vector Int -> RawWaveletMatrix #

\(O(N \log N)\) Creates a RawWaveletMatrix.

  • nx: The number of different x, starting from zero. In other words, every x is in \([0, nx)\).

accessRWM :: RawWaveletMatrix -> Int -> Int #

\(O(\log a)\) Returns a[k].

TODO: Return Maybe?

kth min (safe)

_goDownRWM :: RawWaveletMatrix -> Int -> Int -> Int -> (Int, Int, Int, Int) #

\(O(\log a)\) Goes down the wavelet matrix for collecting kth minimum value.

_goUpRWM :: RawWaveletMatrix -> Int -> Int -> Maybe Int #

\(O(\log a)\) Goes up the wavelet matrix for collecting the value x.

kthMinRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int #

\(O(\log a)\) Returns k-th (0-based) smallest number in [l, r]. Two different values are treated as separate values. Quantile with index.

ikthMinRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe (Int, Int) #

\(O(\log a)\)

kthMaxRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int #

\(O(\log a)\) Returns k-th (0-based) biggest number in [l, r]. Two different values are treated as separate values.

ikthMaxRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe (Int, Int) #

\(O(\log a)\)

kth min (no boundary check)

unsafeKthMinRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Int #

\(O(\log a)\) Returns k-th (0-based) smallest number in [l, r]. Two different values are treated as separate values. Quantile with index.

unsafeIKthMinRWM :: RawWaveletMatrix -> Int -> Int -> Int -> (Int, Int) #

\(O(\log a)\)

unsafeKthMaxRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Int #

\(O(\log a)\) Returns k-th (0-based) biggest number in [l, r]. Two different values are treated as separate values.

unsafeIKthMaxRWM :: RawWaveletMatrix -> Int -> Int -> Int -> (Int, Int) #

\(O(\log a)\)

Freq

freqLTRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Int #

\(O(\log a)\) Returns the number of \(x s.t. x < \mathcal{upper} in [l .. r]\).

freqInRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Int -> Int #

\(O(\log a)\) Returns the number of x in [l .. r] in [xl, xr].

freqRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Int #

\(O(\log a)\) Returns the number of x in [l .. r].

Find index

findIndexRWM :: RawWaveletMatrix -> Int -> Maybe Int #

\(O(\log a)\) Finds index of x. Select.

findKthIndexRWM :: RawWaveletMatrix -> Int -> Int -> Maybe Int #

\(O(\log a)\) Finds kth index of x. Select.

lrFindIndexRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int #

\(O(\log a)\) Finds index of x. Select.

lrFindKthIndexRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Int -> Maybe Int #

\(O(\log a)\) Finds kth index of x. Select.

Lookup

lookupLERWM :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int #

\(O(\log a)\) Finds maximum \(x\) in \([l, r]\) s.t. \(x_{ref} \le x\).

lookupLTRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int #

\(O(\log a)\) Finds maximum \(x\) in \([l, r]\) s.t. \(x_{ref} \lt x\).

lookupGERWM :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int #

\(O(\log a)\) Finds minimum \(x\) in \([l, r]\) s.t. \(x_{ref} \gt x\).

lookupGTRWM :: RawWaveletMatrix -> Int -> Int -> Int -> Maybe Int #

\(O(\log a)\) Finds minimum \(x\) in \([l, r]\) s.t. \(x_{ref} \ge x\).

Associations of (freq, value)

_assocsWithRWM :: RawWaveletMatrix -> Int -> Int -> (Int -> Int) -> [(Int, Int)] #

\(O(\log A \min(|A|, L))\) Internal implementation of assocs.

_descAssocsWithRWM :: RawWaveletMatrix -> Int -> Int -> (Int -> Int) -> [(Int, Int)] #

\(O(\log A \min(|A|, L))\) Internal implementation of descAssoc.

assocsRWM :: RawWaveletMatrix -> Int -> Int -> [(Int, Int)] #

\(O(\log A \min(|A|, L))\) Collects \((x, freq)\) in range \([l, r]\) in ascending order of x. Be warned that it's very slow unless the domain \(A\) is very small.

descAssocsRWM :: RawWaveletMatrix -> Int -> Int -> [(Int, Int)] #

\(O(\log A \min(|A|, L))\) Collects \((x, freq)\) in range \([l, r]\) in descending order of x. Be warned that it's very slow unless the domain \(A\) is very small.