Copyright | (c) Matthew Mosior 2022 |
---|---|
License | BSD-style |
Maintainer | mattm.github@gmail.com |
Portability | portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
WARNING
This module is considered internal.
The Package Versioning Policy does not apply.
The contents of this module may change in any way whatsoever and without any warning between minor versions of this package.
Authors importing this library are expected to track development closely.
All credit goes to the author(s)/maintainer(s) of the containers library for the above warning text.
Description
Various data structures and custom data types to describe the Burrows-Wheeler Transform (BWT) and the Inverse BWT.
The implementation of the BWT relies upon Seq
provided
by the containers.
The internal BWTMatrix
data type relies upon the Seq
as well.
Synopsis
- data Suffix a = Suffix {
- suffixindex :: Int
- suffixstartpos :: Int
- suffix :: Maybe (Seq a)
- type SuffixArray a = Seq (Suffix a)
- newtype BWT a = BWT (Seq (Maybe a))
- newtype BWTMatrix a = BWTMatrix (Seq (Seq (Maybe a)))
- saToBWT :: SuffixArray a -> Seq a -> Seq (Maybe a)
- createSuffixArray :: Ord a => Seq a -> SuffixArray a
- sortTB :: (Ord a1, Ord a2) => (a1, a2) -> (a1, a2) -> Ordering
- type BWTSeq a = Seq a
- type STBWTSeq s a = STRef s (BWTSeq a)
- pushSTBWTSeq :: STBWTSeq s a -> a -> ST s ()
- emptySTBWTSeq :: ST s (STBWTSeq s a)
- type STBWTCounter s a = STRef s Int
- updateSTBWTCounter :: STBWTCounter s Int -> Int -> ST s ()
- emptySTBWTCounter :: ST s (STBWTCounter s Int)
- magicInverseBWT :: Seq (Maybe a, Int) -> ST s (BWTSeq a)
- createBWTMatrix :: Ord a => [a] -> BWTMatrix a
Documentation
Basic suffix data type. Used to describe
the core data inside of the SuffixArray
data type.
Suffix | |
|
Instances
Generic (Suffix a) Source # | |
Read a => Read (Suffix a) Source # | |
Show a => Show (Suffix a) Source # | |
Eq a => Eq (Suffix a) Source # | |
Ord a => Ord (Suffix a) Source # | |
Defined in Data.BWT.Internal | |
type Rep (Suffix a) Source # | |
Defined in Data.BWT.Internal type Rep (Suffix a) = D1 ('MetaData "Suffix" "Data.BWT.Internal" "text-compression-0.1.0.14-9ORM6NM9jqVJfQeS6LjkQQ" 'False) (C1 ('MetaCons "Suffix" 'PrefixI 'True) (S1 ('MetaSel ('Just "suffixindex") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedStrict) (Rec0 Int) :*: (S1 ('MetaSel ('Just "suffixstartpos") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedStrict) (Rec0 Int) :*: S1 ('MetaSel ('Just "suffix") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedStrict) (Rec0 (Maybe (Seq a)))))) |
The BWT data type.
Uses Seq
internally.
The BWTMatrix data type.
Uses a Array
internally.
Instances
Generic (BWTMatrix a) Source # | |
Read a => Read (BWTMatrix a) Source # | |
Show a => Show (BWTMatrix a) Source # | |
Eq a => Eq (BWTMatrix a) Source # | |
Ord a => Ord (BWTMatrix a) Source # | |
Defined in Data.BWT.Internal | |
type Rep (BWTMatrix a) Source # | |
Defined in Data.BWT.Internal type Rep (BWTMatrix a) = D1 ('MetaData "BWTMatrix" "Data.BWT.Internal" "text-compression-0.1.0.14-9ORM6NM9jqVJfQeS6LjkQQ" 'True) (C1 ('MetaCons "BWTMatrix" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Seq (Seq (Maybe a)))))) |
saToBWT :: SuffixArray a -> Seq a -> Seq (Maybe a) Source #
Computes the Burrows-Wheeler Transform (BWT) using the suffix array
and the original string (represented as a Seq
for performance).
createSuffixArray :: Ord a => Seq a -> SuffixArray a Source #
Computes the corresponding SuffixArray
of a given string. Please see suffix array
for more information.
sortTB :: (Ord a1, Ord a2) => (a1, a2) -> (a1, a2) -> Ordering Source #
Hierarchical sorting scheme that compares fst first then snd. Necessary for the setting up the BWT in order to correctly invert it using the Magic algorithm.
type STBWTSeq s a = STRef s (BWTSeq a) Source #
Abstract data type representing a BWTSeq in the (strict) ST monad.
pushSTBWTSeq :: STBWTSeq s a -> a -> ST s () Source #
State function to push BWTString data into stack.
emptySTBWTSeq :: ST s (STBWTSeq s a) Source #
State function to create empty STBWTString type.
type STBWTCounter s a = STRef s Int Source #
Abstract BWTCounter and associated state type.
updateSTBWTCounter :: STBWTCounter s Int -> Int -> ST s () Source #
State function to update BWTCounter.
emptySTBWTCounter :: ST s (STBWTCounter s Int) Source #
State function to create empty STBWTCounter type.