| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.WaveletMatrix
Description
Wavelet Matrix with automatic index compression.
Typical problems
FIXME: My wavelet matrix is somehow slow.
Synopsis
- data WaveletMatrix = WaveletMatrix {
- rawWM :: !RawWaveletMatrix
- dictWM :: !(Vector Int)
- buildWM :: Vector Int -> WaveletMatrix
- accessWM :: HasCallStack => WaveletMatrix -> Int -> Int
- ikthMinWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe (Int, Int)
- kthMinWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int
- ikthMaxWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe (Int, Int)
- kthMaxWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int
- unsafeIKthMinWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> (Int, Int)
- unsafeKthMinWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Int
- unsafeIKthMaxWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> (Int, Int)
- unsafeKthMaxWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Int
- freqInWM :: WaveletMatrix -> Int -> Int -> Int -> Int -> Int
- freqWM :: WaveletMatrix -> Int -> Int -> Int -> Int
- findIndexWM :: HasCallStack => WaveletMatrix -> Int -> Maybe Int
- findKthIndexWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Maybe Int
- lrFindIndexWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int
- lrFindKthIndexWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Int -> Maybe Int
- lookupLEWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int
- lookupLTWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int
- lookupGEWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int
- lookupGTWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int
- assocsWM :: WaveletMatrix -> Int -> Int -> [(Int, Int)]
- descAssocsWM :: WaveletMatrix -> Int -> Int -> [(Int, Int)]
Documentation
data WaveletMatrix #
Wavelet Matrix with automatic index compression.
Constructors
| WaveletMatrix | |
Fields
| |
buildWM :: Vector Int -> WaveletMatrix #
\(O(N \log N)\) Creates WaveletMatrix, internally performing index compression.
accessWM :: HasCallStack => WaveletMatrix -> Int -> Int #
\(O(\log a)\) Returns a[k].
TODO: filter invalid index.
kth min (safe)
ikthMinWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe (Int, Int) #
\(O(\log a)\) Returns k-th (0-based) smallest number in [l, r]. Two different values are treated as separate values. Quantile.
kthMinWM :: HasCallStack => WaveletMatrix -> 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.
ikthMaxWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe (Int, Int) #
\(O(\log a)\) Returns k-th (0-based) smallest number in [l, r]. Two different values are treated as separate values. Quantile.
kthMaxWM :: HasCallStack => WaveletMatrix -> 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.
kth min (no boundary check)
unsafeIKthMinWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> (Int, Int) #
\(O(\log a)\)
unsafeKthMinWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Int #
\(O(\log a)\)
unsafeIKthMaxWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> (Int, Int) #
\(O(\log a)\)
unsafeKthMaxWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Int #
\(O(\log a)\)
Frequencies
freqInWM :: WaveletMatrix -> Int -> Int -> Int -> Int -> Int #
\(O(\log a)\) Returns the number of x in [l .. r] in [xl, xr].
freqWM :: WaveletMatrix -> Int -> Int -> Int -> Int #
\(O(\log a)\) Returns the number of x in [l .. r].
Find index
findIndexWM :: HasCallStack => WaveletMatrix -> Int -> Maybe Int #
\(O(\log a)\) Finds index of x. Select.
findKthIndexWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Maybe Int #
\(O(\log a)\) Finds kth index of x. Select.
lrFindIndexWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int #
\(O(\log a)\) Finds index of x in [l, r]. Select.
lrFindKthIndexWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Int -> Maybe Int #
\(O(\log a)\) Finds kth index of x in [l, r]. Select.
Lookup
lookupLEWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int #
\(O(\log a)\) Finds maximum \(x\) in \([l, r]\) s.t. \(x_{ref} \le x\).
lookupLTWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int #
\(O(\log a)\) Finds maximum \(x\) in \([l, r]\) s.t. \(x_{ref} \lt x\).
lookupGEWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int #
\(O(\log a)\) Finds minimum \(x\) in \([l, r]\) s.t. \(x_{ref} \gt x\).
lookupGTWM :: HasCallStack => WaveletMatrix -> Int -> Int -> Int -> Maybe Int #
\(O(\log a)\) Finds minimum \(x\) in \([l, r]\) s.t. \(x_{ref} \ge x\).
assocsWM :: WaveletMatrix -> Int -> Int -> [(Int, Int)] #
\(O(\log A \min(|A|, L))\) Collects \((x, freq)\) in range \([l, r]\) in ascending order of
x. It's only fast when the domain \(A\) is very small.
descAssocsWM :: WaveletMatrix -> Int -> Int -> [(Int, Int)] #
\(O(\log A \min(|A|, L))\) Collects \((x, freq)\) in range \([l, r]\) in ascending order of
x. It's only fast when the domain \(A\) is very small.