-- 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.6


-- | <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 a
Suffix :: Int -> Int -> Maybe (Seq a) -> Suffix a
[suffixindex] :: Suffix a -> Int
[suffixstartpos] :: Suffix a -> Int
[suffix] :: Suffix a -> Maybe (Seq a)

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

-- | The BWT data type. Uses sequence internally.
type BWT a = Seq (Maybe 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 sequence for performance).
saToBWT :: SuffixArray a -> Seq a -> BWT a

-- | Computes the corresponding <a>SuffixArray</a> of a given string.
--   Please see <a>suffix array</a> for more information.
createSuffixArray :: Ord a => Seq 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 BWTSeq a = Seq a

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

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

-- | State function to create empty STBWTString type.
emptySTBWTSeq :: ST s (STBWTSeq 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 :: Seq (Maybe a, Int) -> ST s (BWTSeq 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 GHC.Classes.Ord a => GHC.Classes.Ord (Data.BWT.Internal.Suffix a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.BWT.Internal.Suffix a)
instance GHC.Read.Read a => GHC.Read.Read (Data.BWT.Internal.Suffix a)
instance GHC.Show.Show a => GHC.Show.Show (Data.BWT.Internal.Suffix 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> and
--   <a>bytestringFromBWT</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 :: 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
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> <a>Word8</a> to a
--   <a>ByteString</a>.
bytestringFromBWT :: BWT Word8 -> ByteString

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