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


-- | A text compression library.
--   
--   This package contains efficient implementations of the Burrows-Wheeler
--   Transform (BWT) and Inverse BWT algorithms.
@package text-compression
@version 0.1.0.4


-- | <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 sequence provided by the
--   <a>containers</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
Suffix :: Int -> Int -> Seq Char -> Suffix
[suffixindex] :: Suffix -> Int
[suffixstartpos] :: Suffix -> Int
[suffix] :: Suffix -> Seq Char

-- | The SuffixArray data type. Uses sequence internally.
type SuffixArray = Seq Suffix

-- | The BWT data type. Uses sequence internally.
type BWT = Seq Char

-- | 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 sequence for performance).
saToBWT :: SuffixArray -> Seq Char -> BWT

-- | Computes the corresponding <a>SuffixArray</a> of a given string.
--   Please see <a>suffix array</a> for more information.
createSuffixArray :: Seq Char -> SuffixArray

-- | 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 BWTSeq a = Seq Char

-- | Abstract data type representing a BWTSeq in the (strict) ST monad.
type STBWTSeq s a = STRef s (BWTSeq Char)

-- | State function to push BWTString data into stack.
pushSTBWTSeq :: STBWTSeq s Char -> Char -> ST s ()

-- | State function to create empty STBWTString type.
emptySTBWTSeq :: ST s (STBWTSeq s Char)

-- | 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 :: Seq (Char, Int) -> ST s (BWTSeq Char)

-- | Easy way to grab the first two elements of a sequence.
grabHeadChunks :: Seq (Seq Char) -> (Seq Char, Seq Char)

-- | 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
instance GHC.Classes.Ord Data.BWT.Internal.Suffix
instance GHC.Classes.Eq Data.BWT.Internal.Suffix
instance GHC.Read.Read Data.BWT.Internal.Suffix
instance GHC.Show.Show Data.BWT.Internal.Suffix


-- | <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>.
--   
--   <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>.
--   
--   Works with alphanumeric characters (A-Za-z0-9), as well as special
--   characters `~?!@#%^&amp;*()_+&lt;&gt;';:[]{}/|"-., Does <b>NOT</b>
--   work with an input containing the <b>$</b> character.
--   
--   Appends the <b>$</b> character to the input automatically.
toBWT :: String -> BWT

-- | 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>$</b> character.
fromBWT :: BWT -> String