-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A text compression library.
--   
--   This package contains efficient implementations of various text
--   compression algorithms.
@package text-compression
@version 0.1.0.8


-- | <h1>WARNING</h1>
--   
--   This module is considered <b>internal</b>.
--   
--   The Package Versioning Policy <b>does not apply</b>.
--   
--   The contents of this module may change <b>in any way whatsoever</b>
--   and <b>without any warning</b> 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
--   <a>containers</a> library for the above warning text.
--   
--   <h1>Description</h1>
--   
--   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 Boxed vectors,
--   <a>Vector</a>, and Unboxed vectors, <a>Vector</a>, provided by the
--   <a>vector</a>.
--   
--   The internal <a>BWTMatrix</a> data type relies upon the <a>massiv</a>
--   package.
module Data.BWT.Internal

-- | Basic suffix data type. Used to describe the core data inside of the
--   <a>SuffixArray</a> data type.
data Suffix a
Suffix :: Int -> Int -> Maybe (Vector a) -> Suffix a
[suffixindex] :: Suffix a -> Int
[suffixstartpos] :: Suffix a -> Int
[suffix] :: Suffix a -> Maybe (Vector a)

-- | The SuffixArray data type. Uses <a>Vector</a> internally.
type SuffixArray a = Vector (Suffix a)

-- | The BWT data type. Uses <a>Vector</a> internally.
newtype BWT a
BWT :: Vector (Maybe a) -> BWT a

-- | The BWTMatrix data type. Uses a massiv array internally.
type BWTMatrix = Array BN Ix1 String

-- | Computes the Burrows-Wheeler Transform (BWT) using the suffix array
--   and the original string (represented as a <a>Vector</a> for
--   performance).
saToBWT :: Unbox a => SuffixArray a -> Vector a -> BWT a

-- | <a>Vector</a> based implementation of the well-known tails function in
--   the List library.
tailsV :: Unbox a => Vector a -> [Vector a]

-- | Custom sort function for <a>Vector</a>s used in the
--   <a>createSuffixArray</a> function.
sortVecSA :: Ord a => Vector (Int, a) -> Vector (Int, a)

-- | Custom sort function for <a>Vector</a>s used in the fromBWT function.
sortVecBWT :: Ord a => Vector (a, Int) -> Vector (a, Int)

-- | Computes the corresponding <a>SuffixArray</a> of a given string.
--   Please see <a>suffix array</a> for more information.
createSuffixArray :: (Unbox a, Ord a) => Vector a -> SuffixArray a

-- | Hierarchical sorting scheme that compares fst first then snd.
--   Necessary for the setting up the BWT in order to correctly invert it
--   using the <a>Magic</a> algorithm.
sortTB :: (Ord a1, Ord a2) => (a1, a2) -> (a1, a2) -> Ordering

-- | Abstract BWTSeq type utilizing a sequence.
type BWTVec a = Vector a

-- | Abstract data type representing a <a>BWTVec</a> in the (strict) ST
--   monad.
type STBWTVec s a = STRef s (BWTVec a)

-- | State function to push <a>BWTVec</a> data into stack.
pushSTBWTVec :: STBWTVec s a -> a -> ST s ()

-- | State function to create empty <a>STBWTVec</a> type.
emptySTBWTVec :: ST s (STBWTVec s a)

-- | Abstract BWTCounter and associated state type.
type STBWTCounter s a = STRef s Int

-- | State function to update BWTCounter.
updateSTBWTCounter :: STBWTCounter s Int -> Int -> ST s ()

-- | State function to create empty STBWTCounter type.
emptySTBWTCounter :: ST s (STBWTCounter s Int)

-- | <a>Magic</a> Inverse BWT function.
magicInverseBWT :: Vector (Maybe a, Int) -> ST s (BWTVec a)

-- | Simple yet efficient implementation of converting a given string into
--   a BWT Matrix (the BWTMatrix type is a massiv array).
createBWTMatrix :: String -> BWTMatrix
instance GHC.Generics.Generic (Data.BWT.Internal.Suffix a)
instance (Data.Vector.Unboxed.Base.Unbox a, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.BWT.Internal.Suffix a)
instance (Data.Vector.Unboxed.Base.Unbox a, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.BWT.Internal.Suffix a)
instance (GHC.Read.Read a, Data.Vector.Unboxed.Base.Unbox a) => GHC.Read.Read (Data.BWT.Internal.Suffix a)
instance (GHC.Show.Show a, Data.Vector.Unboxed.Base.Unbox a) => GHC.Show.Show (Data.BWT.Internal.Suffix a)
instance GHC.Generics.Generic (Data.BWT.Internal.BWT a)
instance GHC.Read.Read a => GHC.Read.Read (Data.BWT.Internal.BWT a)
instance GHC.Show.Show a => GHC.Show.Show (Data.BWT.Internal.BWT a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.BWT.Internal.BWT a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.BWT.Internal.BWT a)


-- | <h1>Burrows-Wheeler Transform (BWT)</h1>
--   
--   The two functions that most users will utilize are <a>toBWT</a> and
--   <a>fromBWT</a>. There are auxilary function(s) inside of
--   <tt><a>Data.BWT.Internal</a></tt>.
--   
--   The helper functions for ByteString, <a>bytestringToBWT</a>,
--   <a>bytestringFromWord8BWT</a> , <a>bytestringFromByteStringBWT</a> and
--   Text, <a>textToBWT</a> and <a>textFromBWT</a> should help for common
--   use cases.
--   
--   <tt><a>Data.BWT.Internal</a></tt> also has the function
--   <a>createBWTMatrix</a>, which can be useful as well, although not used
--   by either <a>toBWT</a> or <a>fromBWT</a>.
module Data.BWT

-- | Takes a String and returns the Burrows-Wheeler Transform (BWT).
--   Implemented via a <a>SuffixArray</a>.
toBWT :: (Unbox a, Ord a) => [a] -> BWT a

-- | Helper function for converting a <a>ByteString</a> to a <a>BWT</a>
--   <a>Word8</a>.
bytestringToBWT :: ByteString -> BWT Word8

-- | A newtype to ensure you only uncompress a BWT created from textToBWT,
--   since [Word8] -&gt; Text is partial.
newtype TextBWT
TextBWT :: BWT Word8 -> TextBWT

-- | Helper function for converting <a>Text</a> to a <a>TextBWT</a>.
textToBWT :: Text -> TextBWT

-- | Takes a BWT data type (please see <tt><a>Data.BWT.Internal</a></tt>)
--   and inverts it back to the original string.
--   
--   This function utilizes the state monad (strict) in order to implement
--   the <a>Magic</a> Inverse BWT algorithm by backtracking indices
--   starting with the (<b>Nothing</b>,_) entry.
fromBWT :: Ord a => BWT a -> [a]

-- | Helper function for converting a <a>BWT</a> of <a>Word8</a>s to a
--   <a>ByteString</a>.
bytestringFromWord8BWT :: BWT Word8 -> ByteString

-- | Helper function for converting a <a>BWT</a> <a>ByteString</a>s to a
--   <a>ByteString</a>.
bytestringFromByteStringBWT :: BWT ByteString -> ByteString

-- | Helper function for converting <a>TextBWT</a> to a <a>Text</a>
textFromBWT :: TextBWT -> Text
instance GHC.Generics.Generic Data.BWT.TextBWT
instance GHC.Read.Read Data.BWT.TextBWT
instance GHC.Show.Show Data.BWT.TextBWT
instance GHC.Classes.Ord Data.BWT.TextBWT
instance GHC.Classes.Eq Data.BWT.TextBWT


-- | <h1>WARNING</h1>
--   
--   This module is considered <b>internal</b>.
--   
--   The Package Versioning Policy <b>does not apply</b>.
--   
--   The contents of this module may change <b>in any way whatsoever</b>
--   and <b>without any warning</b> 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
--   <a>containers</a> library for the above warning text.
--   
--   <h1>Description</h1>
--   
--   Various data structures and custom data types to describe the
--   Run-length encoding (RLE) and the Inverse RLE implementations, namely
--   <a>vecToRLEB</a>, <a>vecToRLET</a>, <a>vecFromRLEB</a>, and
--   <a>vecFromRLET</a>.
--   
--   The RLE implementations rely heavily upon <a>Vector</a> provided by
--   the <a>vector</a> library, <a>STRef</a> and associated functions in
--   the <a>stref</a> library, and <a>runST</a> in the
--   <a>Control.Monad.ST</a> library.
module Data.RLE.Internal

-- | Basic RLE (<a>ByteString</a>) data type.
newtype RLEB
RLEB :: Vector (Maybe ByteString) -> RLEB

-- | Basic RLE (<a>Text</a>) data type.
newtype RLET
RLET :: Vector (Maybe Text) -> RLET

-- | Abstract <a>RLEVecB</a> type utilizing a sequence.
type RLEVecB = Vector (Maybe ByteString)

-- | Abstract data type representing a <a>RLEVecB</a> in the (strict) ST
--   monad.
type STRLEVecB s a = STRef s RLEVecB

-- | State function to push <a>RLEVecB</a> data into stack.
pushSTRLEVecB :: STRLEVecB s (Maybe ByteString) -> Maybe ByteString -> ST s ()

-- | State function to create empty <a>STRLEVecB</a> type.
emptySTRLEVecB :: ST s (STRLEVecB s a)

-- | Abstract <a>STRLETempB</a> and associated state type.
type STRLETempB s a = STRef s (Maybe ByteString)

-- | State function to update <a>STRLETempB</a>.
updateSTRLETempB :: STRLETempB s (Maybe ByteString) -> Maybe ByteString -> ST s ()

-- | State function to create empty <a>STRLETempB</a> type.
emptySTRLETempB :: ST s (STRLETempB s a)

-- | Abstract <a>STRLECounterB</a> state type.
type STRLECounterB s a = STRef s Int

-- | State function to update <a>STRLECounterB</a>.
updateSTRLECounterB :: STRLECounterB s Int -> Int -> ST s ()

-- | State function to create empty <a>STRLECounterB</a> type.
emptySTRLECounterB :: ST s (STRLECounterB s Int)

-- | Strict state monad function.
vecToRLEB :: RLEVecB -> ST s RLEVecB

-- | Abstract <a>RLEVecT</a> type utilizing a sequence.
type RLEVecT = Vector (Maybe Text)

-- | Abstract data type representing a <a>RLEVecT</a> in the (strict) ST
--   monad.
type STRLEVecT s a = STRef s RLEVecT

-- | State function to push <a>RLEVecT</a> data into stack.
pushSTRLEVecT :: STRLEVecT s (Maybe Text) -> Maybe Text -> ST s ()

-- | State function to create empty <a>STRLEVecT</a> type.
emptySTRLEVecT :: ST s (STRLEVecT s a)

-- | Abstract <a>STRLETempT</a> state type.
type STRLETempT s a = STRef s (Maybe Text)

-- | State function to update <a>STRLETempT</a>.
updateSTRLETempT :: STRLETempT s (Maybe Text) -> Maybe Text -> ST s ()

-- | State function to create empty <a>STRLETempT</a> type.
emptySTRLETempT :: ST s (STRLETempT s a)

-- | Abstract <a>STRLECounterT</a> and associated state type.
type STRLECounterT s a = STRef s Int

-- | State function to update <a>STRLECounterT</a>.
updateSTRLECounterT :: STRLECounterT s Int -> Int -> ST s ()

-- | State function to create empty <a>STRLECounterT</a> type.
emptySTRLECounterT :: ST s (STRLECounterT s Int)

-- | Strict state monad function.
vecToRLET :: RLEVecT -> ST s RLEVecT

-- | <a>Vector</a> auxilary function to pattern match on first two elements
--   of a vector.
unconsb2 :: Vector a -> Maybe (a, Vector a, Maybe (Vector a))

-- | Abstract <a>FRLEVecB</a> type utilizing a sequence.
type FRLEVecB = Vector (Maybe ByteString)

-- | Abstract data type representing a <a>FRLEVecB</a> in the (strict) ST
--   monad.
type FSTRLEVecB s a = STRef s FRLEVecB

-- | State function to push <a>FRLEVecB</a> data into stack.
pushFSTRLEVecB :: FSTRLEVecB s (Maybe ByteString) -> Maybe ByteString -> ST s ()

-- | State function to create empty <a>FSTRLEVecB</a> type.
emptyFSTRLEVecB :: ST s (FSTRLEVecB s a)

-- | Strict state monad function.
vecFromRLEB :: RLEB -> ST s FRLEVecB

-- | <a>Vector</a> auxilary function to pattern match on first two elements
--   of a vector.
unconst2 :: Vector a -> Maybe (a, Vector a, Maybe (Vector a))

-- | Abstract <a>FRLEVecT</a> type utilizing a sequence.
type FRLEVecT = Vector (Maybe Text)

-- | Abstract data type representing a <a>FRLEVecT</a> in the (strict) ST
--   monad.
type FSTRLEVecT s a = STRef s FRLEVecT

-- | State function to push <a>FSTRLEVecT</a> data into stack.
pushFSTRLEVecT :: FSTRLEVecT s (Maybe Text) -> Maybe Text -> ST s ()

-- | State function to create empty <a>FSTRLEVecT</a> type.
emptyFSTRLEVecT :: ST s (FSTRLEVecT s a)

-- | Strict state monad function.
vecFromRLET :: RLET -> ST s FRLEVecT
instance GHC.Generics.Generic Data.RLE.Internal.RLEB
instance GHC.Read.Read Data.RLE.Internal.RLEB
instance GHC.Show.Show Data.RLE.Internal.RLEB
instance GHC.Classes.Ord Data.RLE.Internal.RLEB
instance GHC.Classes.Eq Data.RLE.Internal.RLEB
instance GHC.Generics.Generic Data.RLE.Internal.RLET
instance GHC.Read.Read Data.RLE.Internal.RLET
instance GHC.Show.Show Data.RLE.Internal.RLET
instance GHC.Classes.Ord Data.RLE.Internal.RLET
instance GHC.Classes.Eq Data.RLE.Internal.RLET


-- | <h1>Run-length encoding (RLE)</h1>
module Data.RLE

-- | Helper function for converting a <a>ByteString</a> to a <a>RLEB</a>
--   via a <a>BWT</a> first.
bytestringToBWTToRLEB :: ByteString -> RLEB

-- | Helper function for converting a <a>ByteString</a> to a <a>RLET</a>
--   via a <a>BWT</a> first.
bytestringToBWTToRLET :: ByteString -> RLET

-- | Helper function for converting a <a>Text</a> to a <a>RLEB</a> via a
--   <a>BWT</a> first.
textToBWTToRLEB :: Text -> RLEB

-- | Helper function for converting a <a>Text</a> to a <a>RLET</a> via a
--   <a>BWT</a> first.
textToBWTToRLET :: Text -> RLET

-- | Take a <a>BWT</a> of <a>Word8</a>s and generate the Run-length
--   encoding (<a>RLEB</a>).
textBWTToRLEB :: TextBWT -> RLEB

-- | Take a <a>BWT</a> of <a>Word8</a>s and generate the Run-length
--   encoding (<a>RLEB</a>).
bytestringBWTToRLEB :: BWT Word8 -> RLEB

-- | Take a <a>BWT</a> of <a>Word8</a>s and generate the Run-length
--   encoding (<a>RLEB</a>).
textBWTToRLET :: TextBWT -> RLET

-- | Take a <a>BWT</a> of <a>Word8</a>s and generate the Run-length
--   encoding (<a>RLET</a>).
bytestringBWTToRLET :: BWT Word8 -> RLET

-- | Takes a <a>Text</a> and returns the Run-length encoding (<a>RLEB</a>).
textToRLEB :: Vector (Maybe Text) -> RLEB

-- | Takes a <a>Vector</a> of <a>ByteString</a>s and returns the Run-length
--   encoding (<a>RLEB</a>).
bytestringToRLEB :: Vector (Maybe ByteString) -> RLEB

-- | Takes a <a>Text</a> and returns the Run-length encoding (RLE).
textToRLET :: Vector (Maybe Text) -> RLET

-- | Takes a <a>ByteString</a> and returns the Run-length encoding (RLE).
bytestringToRLET :: Vector (Maybe ByteString) -> RLET

-- | Helper function for converting a <a>BWT</a>ed <a>RLEB</a> back to the
--   original <a>ByteString</a>.
bytestringFromBWTFromRLEB :: RLEB -> ByteString

-- | Helper function for converting a <a>BWT</a>ed <a>RLET</a> back to the
--   original <a>ByteString</a>.
bytestringFromBWTFromRLET :: RLET -> ByteString

-- | Helper function for converting a <a>BWT</a>ed <a>RLEB</a> back to the
--   original <a>Text</a>.
textFromBWTFromRLEB :: RLEB -> Text

-- | Helper function for converting a <a>BWT</a>ed <a>RLET</a> back to the
--   original <a>Text</a>.
textFromBWTFromRLET :: RLET -> Text

-- | Takes a <a>RLET</a> and returns the <a>BWT</a> of <a>Text</a>s.
textBWTFromRLET :: RLET -> BWT Text

-- | Takes a <a>RLET</a> and returns the <a>BWT</a> of <a>ByteString</a>s.
bytestringBWTFromRLET :: RLET -> BWT ByteString

-- | Takes a <a>RLEB</a> and returns the <a>BWT</a> of <a>Text</a>s.
textBWTFromRLEB :: RLEB -> BWT Text

-- | Take a <a>RLEB</a> and returns the <a>BWT</a> of <a>ByteString</a>s.
bytestringBWTFromRLEB :: RLEB -> BWT ByteString

-- | Takes a <a>RLEB</a> and returns the original <a>Vector</a> of
--   <a>Text</a>s.
textFromRLEB :: RLEB -> Vector (Maybe Text)

-- | Takes a <a>RLEB</a> and returns the original <a>Vector</a> of
--   <a>ByteString</a>s.
bytestringFromRLEB :: RLEB -> Vector (Maybe ByteString)

-- | Takes a <a>RLET</a> and returns the original <a>Vector</a> of
--   <a>Text</a>s.
textFromRLET :: RLET -> Vector (Maybe Text)

-- | Takes a <a>RLET</a> and returns the original <a>Vector</a> of
--   <a>ByteString</a>s.
bytestringFromRLET :: RLET -> Vector (Maybe ByteString)