{-# LANGUAGE MultiWayIf       #-}
{-# LANGUAGE ViewPatterns     #-}
{-# LANGUAGE Strict           #-}
{-# LANGUAGE DeriveGeneric    #-}
{-# LANGUAGE TypeApplications #-}


-- |
-- Module      :  Data.FMIndex.Internal
-- Copyright   :  (c) Matthew Mosior 2022
-- License     :  BSD-style
-- Maintainer  :  mattm.github@gmail.com
-- Portability :  portable
--
-- = 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](https://hackage.haskell.org/package/containers) library
-- for the above warning text.
--
-- = Description
--
-- Various data structures and custom data types to describe the
-- [Full-text Minute-space index (FM-index)](https://en.wikipedia.org/wiki/FM-index)
-- and the Inverse FM-index implementations, namely 'seqToFMIndexB', 'seqToFMIndexT', 'seqFromFMIndexB', and 'seqFromFMIndexT'.
--
-- The FM-index implementations rely heavily upon 'Seq' provided by the [containers](https://hackage.haskell.org/package/containers),
-- 'STRef' and associated functions in the [stref](https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-STRef.html) library,
-- and 'runST' in the [Control.Monad.ST](https://hackage.haskell.org/package/base-4.17.0.0/docs/Control-Monad-ST.html) library.
--
-- = Example FM-index Output
--
-- The below example is taken from [this](https://en.wikipedia.org/wiki/FM-index) wikipedia page.
--
-- FM-index output of the Burrows-Wheeler transform of the input "abracadabra" -> "ard$rcaaaabb"
--
--
-- Occ(c,k) of "ard$rcaaaabb"
--
-- +---+---+---+---+---+---+---+---+---+---+----+----+----+
-- |   | a | r | d | $ | r | c | a | a | a | a  | b  | b  |
-- +---+---+---+---+---+---+---+---+---+---+----+----+----+
-- |   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
-- +===+===+===+===+===+===+===+===+===+===+====+====+====+
-- | $ | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1  | 1  | 1  |
-- +---+---+---+---+---+---+---+---+---+---+----+----+----+
-- | a | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 5  | 5  | 5  |
-- +---+---+---+---+---+---+---+---+---+---+----+----+----+
-- | b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0  | 1  | 2  |
-- +---+---+---+---+---+---+---+---+---+---+----+----+----+
-- | c | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1  | 1  | 1  |
-- +---+---+---+---+---+---+---+---+---+---+----+----+----+
-- | d | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1  | 1  | 1  |
-- +---+---+---+---+---+---+---+---+---+---+----+----+----+
-- | r | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2  | 2  | 2  |
-- +---+---+---+---+---+---+---+---+---+---+----+----+----+


module Data.FMIndex.Internal where

import Data.BWT.Internal()
import Data.MTF.Internal

import Control.Monad as CM
import Control.Monad.ST as CMST
import Control.Monad.State.Strict()
import Data.ByteString as BS
import Data.ByteString.Char8()
import Data.ByteString.Internal()
import Data.Foldable()
import Data.List()
import Data.Maybe()
import Data.Sequence as DS (Seq(..),ViewR(..),empty,(|>))
import Data.Sequence.Internal as DSI
import Data.STRef as DSTR
import Data.Text as DText
import GHC.Generics (Generic)
import Prelude as P


{-Base level types.-}

-- | Basic FMIndex ('ByteString') data type.
newtype FMIndexB = FMIndexB (Seq (Maybe ByteString,Seq (Int,Int,Maybe ByteString)))
  deriving (FMIndexB -> FMIndexB -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FMIndexB -> FMIndexB -> Bool
$c/= :: FMIndexB -> FMIndexB -> Bool
== :: FMIndexB -> FMIndexB -> Bool
$c== :: FMIndexB -> FMIndexB -> Bool
Eq,Eq FMIndexB
FMIndexB -> FMIndexB -> Bool
FMIndexB -> FMIndexB -> Ordering
FMIndexB -> FMIndexB -> FMIndexB
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: FMIndexB -> FMIndexB -> FMIndexB
$cmin :: FMIndexB -> FMIndexB -> FMIndexB
max :: FMIndexB -> FMIndexB -> FMIndexB
$cmax :: FMIndexB -> FMIndexB -> FMIndexB
>= :: FMIndexB -> FMIndexB -> Bool
$c>= :: FMIndexB -> FMIndexB -> Bool
> :: FMIndexB -> FMIndexB -> Bool
$c> :: FMIndexB -> FMIndexB -> Bool
<= :: FMIndexB -> FMIndexB -> Bool
$c<= :: FMIndexB -> FMIndexB -> Bool
< :: FMIndexB -> FMIndexB -> Bool
$c< :: FMIndexB -> FMIndexB -> Bool
compare :: FMIndexB -> FMIndexB -> Ordering
$ccompare :: FMIndexB -> FMIndexB -> Ordering
Ord,Int -> FMIndexB -> ShowS
[FMIndexB] -> ShowS
FMIndexB -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [FMIndexB] -> ShowS
$cshowList :: [FMIndexB] -> ShowS
show :: FMIndexB -> String
$cshow :: FMIndexB -> String
showsPrec :: Int -> FMIndexB -> ShowS
$cshowsPrec :: Int -> FMIndexB -> ShowS
Show,ReadPrec [FMIndexB]
ReadPrec FMIndexB
Int -> ReadS FMIndexB
ReadS [FMIndexB]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [FMIndexB]
$creadListPrec :: ReadPrec [FMIndexB]
readPrec :: ReadPrec FMIndexB
$creadPrec :: ReadPrec FMIndexB
readList :: ReadS [FMIndexB]
$creadList :: ReadS [FMIndexB]
readsPrec :: Int -> ReadS FMIndexB
$creadsPrec :: Int -> ReadS FMIndexB
Read,forall x. Rep FMIndexB x -> FMIndexB
forall x. FMIndexB -> Rep FMIndexB x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cto :: forall x. Rep FMIndexB x -> FMIndexB
$cfrom :: forall x. FMIndexB -> Rep FMIndexB x
Generic)

-- | Basic FMIndex ('Text') data type.
newtype FMIndexT = FMIndexT (Seq (Maybe Text,Seq (Int,Int,Maybe Text)))
  deriving (FMIndexT -> FMIndexT -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FMIndexT -> FMIndexT -> Bool
$c/= :: FMIndexT -> FMIndexT -> Bool
== :: FMIndexT -> FMIndexT -> Bool
$c== :: FMIndexT -> FMIndexT -> Bool
Eq,Eq FMIndexT
FMIndexT -> FMIndexT -> Bool
FMIndexT -> FMIndexT -> Ordering
FMIndexT -> FMIndexT -> FMIndexT
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: FMIndexT -> FMIndexT -> FMIndexT
$cmin :: FMIndexT -> FMIndexT -> FMIndexT
max :: FMIndexT -> FMIndexT -> FMIndexT
$cmax :: FMIndexT -> FMIndexT -> FMIndexT
>= :: FMIndexT -> FMIndexT -> Bool
$c>= :: FMIndexT -> FMIndexT -> Bool
> :: FMIndexT -> FMIndexT -> Bool
$c> :: FMIndexT -> FMIndexT -> Bool
<= :: FMIndexT -> FMIndexT -> Bool
$c<= :: FMIndexT -> FMIndexT -> Bool
< :: FMIndexT -> FMIndexT -> Bool
$c< :: FMIndexT -> FMIndexT -> Bool
compare :: FMIndexT -> FMIndexT -> Ordering
$ccompare :: FMIndexT -> FMIndexT -> Ordering
Ord,Int -> FMIndexT -> ShowS
[FMIndexT] -> ShowS
FMIndexT -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [FMIndexT] -> ShowS
$cshowList :: [FMIndexT] -> ShowS
show :: FMIndexT -> String
$cshow :: FMIndexT -> String
showsPrec :: Int -> FMIndexT -> ShowS
$cshowsPrec :: Int -> FMIndexT -> ShowS
Show,ReadPrec [FMIndexT]
ReadPrec FMIndexT
Int -> ReadS FMIndexT
ReadS [FMIndexT]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [FMIndexT]
$creadListPrec :: ReadPrec [FMIndexT]
readPrec :: ReadPrec FMIndexT
$creadPrec :: ReadPrec FMIndexT
readList :: ReadS [FMIndexT]
$creadList :: ReadS [FMIndexT]
readsPrec :: Int -> ReadS FMIndexT
$creadsPrec :: Int -> ReadS FMIndexT
Read,forall x. Rep FMIndexT x -> FMIndexT
forall x. FMIndexT -> Rep FMIndexT x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cto :: forall x. Rep FMIndexT x -> FMIndexT
$cfrom :: forall x. FMIndexT -> Rep FMIndexT x
Generic)

{-------------------}


{-toFMIndex (ByteString) functions.-}

-- | Abstract 'PBFMIndexSeqB' type utilizing a 'Seq'.
type PBFMIndexSeqB = Seq (Maybe ByteString)

-- | Abstract 'FMIndexSeqB' type utilizing a 'Seq'.
-- (c,(indexofinputcurrentelement,Occ(c,k),inputcurrentelement))
type FMIndexSeqB = Seq (Maybe ByteString,Seq (Int,Int,Maybe ByteString))

-- | Abstract data type representing a 'FMIndexSeqB' in the (strict) ST monad.
type STFMIndexSeqB s a = STRef s FMIndexSeqB

-- | State function to update 'FMIndexSeqB'
-- with each step of the FMIndex.
updateSTFMIndexSeqAB :: STFMIndexSeqB s (Seq (Maybe ByteString,Seq (Int,Int,Maybe ByteString)))
                     -> (Int,Int,Maybe ByteString)
                     -> ST s ()
updateSTFMIndexSeqAB :: forall s.
STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> (Int, Int, Maybe ByteString) -> ST s ()
updateSTFMIndexSeqAB STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
s (Int, Int, Maybe ByteString)
e = do
  Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
s2 <- forall s a. STRef s a -> ST s a
readSTRef STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
s
  case forall a. Seq a -> ViewR a
viewr Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
s2 of
    ViewR (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
EmptyR           -> forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
    (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
s2h DS.:> (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
s2fm) -> forall s a. STRef s a -> a -> ST s ()
writeSTRef STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
s2h forall a. Seq a -> a -> Seq a
DS.|> (((\(Maybe ByteString
a,Seq (Int, Int, Maybe ByteString)
_) -> Maybe ByteString
a) (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
s2fm),((\(Maybe ByteString
_,Seq (Int, Int, Maybe ByteString)
b) -> Seq (Int, Int, Maybe ByteString)
b) (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
s2fm) forall a. Seq a -> a -> Seq a
DS.|> (Int, Int, Maybe ByteString)
e))

-- | State function to update 'FMIndexSeqB'
-- with each step of the FMIndex.
updateSTFMIndexSeqBB :: STFMIndexSeqB s (Seq (Maybe ByteString,Seq (Int,Int,Maybe ByteString)))
                     -> Maybe ByteString
                     -> ST s ()
updateSTFMIndexSeqBB :: forall s.
STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> Maybe ByteString -> ST s ()
updateSTFMIndexSeqBB STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
s Maybe ByteString
e = do
  Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
s2 <- forall s a. STRef s a -> ST s a
readSTRef STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
s
  forall s a. STRef s a -> a -> ST s ()
writeSTRef STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
s2 forall a. Seq a -> a -> Seq a
DS.|> (Maybe ByteString
e,forall a. Seq a
DS.empty))

-- | State function to create empty 'STFMIndexSeqB' type.
emptySTFMIndexSeqB :: ST s (STFMIndexSeqB s a)
emptySTFMIndexSeqB :: forall s a. ST s (STFMIndexSeqB s a)
emptySTFMIndexSeqB = forall a s. a -> ST s (STRef s a)
newSTRef forall a. Seq a
DS.empty

-- | Abstract 'STFMIndexILB' and associated state type.
type STFMIndexILB s a = STRef s (Seq (Maybe ByteString))

-- | State function to load list into 'STFMIndexILB'.
loadSTFMIndexILB :: STMTFILB s (Maybe ByteString)
                 -> Seq (Maybe ByteString)
                 -> ST s ()
loadSTFMIndexILB :: forall s.
STMTFILB s (Maybe ByteString) -> Seq (Maybe ByteString) -> ST s ()
loadSTFMIndexILB STMTFILB s (Maybe ByteString)
s Seq (Maybe ByteString)
e = forall s a. STRef s a -> a -> ST s ()
writeSTRef STMTFILB s (Maybe ByteString)
s Seq (Maybe ByteString)
e

-- | State function to create empty 'STFMIndexILB' type.
emptySTFMIndexILB :: ST s (STFMIndexILB s a)
emptySTFMIndexILB :: forall s a. ST s (STFMIndexILB s a)
emptySTFMIndexILB = forall a s. a -> ST s (STRef s a)
newSTRef forall a. Seq a
DS.empty

-- | Abstract 'STFMIndexCounterB' and associated state type.
type STFMIndexCounterB s a = STRef s Int

-- | State function to update 'STFMIndexCounterB'.
updateSTFMIndexCounterB :: STFMIndexCounterB s Int
                        -> Int
                        -> ST s ()
updateSTFMIndexCounterB :: forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterB STFMIndexCounterB s Int
s Int
e = forall s a. STRef s a -> a -> ST s ()
writeSTRef STFMIndexCounterB s Int
s Int
e

-- | State function to create empty 'STFMIndexCounterB' type.
emptySTFMIndexCounterB :: ST s (STFMIndexCounterB s Int)
emptySTFMIndexCounterB :: forall s. ST s (STFMIndexCounterB s Int)
emptySTFMIndexCounterB = forall a s. a -> ST s (STRef s a)
newSTRef Int
0 

-- | Strict state monad function.
seqToFMIndexB :: PBFMIndexSeqB
              -> ST s FMIndexSeqB
seqToFMIndexB :: forall s.
Seq (Maybe ByteString)
-> ST s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
seqToFMIndexB Seq (Maybe ByteString)
DS.Empty      = do
  STFMIndexSeqB s Any
bfmiseqstackempty  <- forall s a. ST s (STFMIndexSeqB s a)
emptySTFMIndexSeqB
  Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
bfmiseqstackemptyr <- forall s a. STRef s a -> ST s a
readSTRef STFMIndexSeqB s Any
bfmiseqstackempty
  forall (m :: * -> *) a. Monad m => a -> m a
return Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
bfmiseqstackemptyr
seqToFMIndexB Seq (Maybe ByteString)
xs            = do
  STFMIndexSeqB s Any
bfmiseqstack     <- forall s a. ST s (STFMIndexSeqB s a)
emptySTFMIndexSeqB 
  STFMIndexILB s Any
bfmiinitiallist  <- forall s a. ST s (STFMIndexILB s a)
emptySTFMIndexILB
  STFMIndexCounterB s Int
bfmicounterstack <- forall s. ST s (STFMIndexCounterB s Int)
emptySTFMIndexCounterB
  let il :: Seq (Maybe ByteString)
il = forall a. Ord a => Seq (Maybe a) -> Seq (Maybe a)
nubSeq' Seq (Maybe ByteString)
xs
  forall s.
STMTFILB s (Maybe ByteString) -> Seq (Maybe ByteString) -> ST s ()
loadSTFMIndexILB STFMIndexILB s Any
bfmiinitiallist
                   Seq (Maybe ByteString)
il
  Seq (Maybe ByteString)
cbfmiinitiallist <- forall s a. STRef s a -> ST s a
readSTRef STFMIndexILB s Any
bfmiinitiallist
  forall {s}.
Seq (Maybe ByteString)
-> Seq (Maybe ByteString)
-> STFMIndexSeqB
     s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> STFMIndexCounterB s Int
-> ST s ()
iFMIndexB Seq (Maybe ByteString)
cbfmiinitiallist
            Seq (Maybe ByteString)
xs
            STFMIndexSeqB s Any
bfmiseqstack
            STFMIndexCounterB s Int
bfmicounterstack
  Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
bfmiseqstackr <- forall s a. STRef s a -> ST s a
readSTRef STFMIndexSeqB s Any
bfmiseqstack
  forall (m :: * -> *) a. Monad m => a -> m a
return Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
bfmiseqstackr
    where
      iFMIndexB :: Seq (Maybe ByteString)
-> Seq (Maybe ByteString)
-> STFMIndexSeqB
     s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> STFMIndexCounterB s Int
-> ST s ()
iFMIndexB Seq (Maybe ByteString)
DS.Empty      Seq (Maybe ByteString)
_      STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
_      STFMIndexCounterB s Int
_      = forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
      iFMIndexB (Maybe ByteString
y DS.:<| Seq (Maybe ByteString)
ys) Seq (Maybe ByteString)
zs     STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
bfmiss STFMIndexCounterB s Int
bfmics = do
        STFMIndexCounterB s Int
bfmiis <- forall s. ST s (STFMIndexCounterB s Int)
emptySTFMIndexCounterB
        forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterB STFMIndexCounterB s Int
bfmiis
                                Int
1
        forall s.
STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> Maybe ByteString -> ST s ()
updateSTFMIndexSeqBB STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
bfmiss
                             Maybe ByteString
y
        forall {s}.
Maybe ByteString
-> Seq (Maybe ByteString)
-> STFMIndexSeqB
     s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> STRef s Int
-> STRef s Int
-> ST s ()
iiFMIndexB Maybe ByteString
y
                   Seq (Maybe ByteString)
zs
                   STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
bfmiss
                   STFMIndexCounterB s Int
bfmiis
                   STFMIndexCounterB s Int
bfmics                           
        Seq (Maybe ByteString)
-> Seq (Maybe ByteString)
-> STFMIndexSeqB
     s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> STFMIndexCounterB s Int
-> ST s ()
iFMIndexB Seq (Maybe ByteString)
ys
                  Seq (Maybe ByteString)
zs
                  STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
bfmiss
                  STFMIndexCounterB s Int
bfmics
      iiFMIndexB :: Maybe ByteString
-> Seq (Maybe ByteString)
-> STFMIndexSeqB
     s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> STRef s Int
-> STRef s Int
-> ST s ()
iiFMIndexB Maybe ByteString
_  Seq (Maybe ByteString)
DS.Empty      STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
_      STRef s Int
_      STRef s Int
bfmics = do
        forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterB STRef s Int
bfmics
                                Int
0
        forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
      iiFMIndexB Maybe ByteString
as (Maybe ByteString
b DS.:<| Seq (Maybe ByteString)
bs) STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
bfmiss STRef s Int
bfmiis STRef s Int
bfmics = do
        Int
cbfmiis <- forall s a. STRef s a -> ST s a
readSTRef STRef s Int
bfmiis
        Int
cbfmics <- forall s a. STRef s a -> ST s a
readSTRef STRef s Int
bfmics
        if | Maybe ByteString
as forall a. Eq a => a -> a -> Bool
== Maybe ByteString
b
           -> do forall s.
STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> (Int, Int, Maybe ByteString) -> ST s ()
updateSTFMIndexSeqAB STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
bfmiss
                                      (Int
cbfmiis,Int
cbfmics forall a. Num a => a -> a -> a
+ Int
1,Maybe ByteString
b)
                 forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterB STRef s Int
bfmics
                                         (Int
cbfmics forall a. Num a => a -> a -> a
+ Int
1)
                 forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterB STRef s Int
bfmiis
                                         (Int
cbfmiis forall a. Num a => a -> a -> a
+ Int
1)
                 Maybe ByteString
-> Seq (Maybe ByteString)
-> STFMIndexSeqB
     s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> STRef s Int
-> STRef s Int
-> ST s ()
iiFMIndexB Maybe ByteString
as
                            Seq (Maybe ByteString)
bs
                            STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
bfmiss
                            STRef s Int
bfmiis
                            STRef s Int
bfmics    
           | Bool
otherwise
           -> do forall s.
STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> (Int, Int, Maybe ByteString) -> ST s ()
updateSTFMIndexSeqAB STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
bfmiss
                                      (Int
cbfmiis,Int
cbfmics,Maybe ByteString
b)
                 forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterB STRef s Int
bfmiis
                                         (Int
cbfmiis forall a. Num a => a -> a -> a
+ Int
1)
                 Maybe ByteString
-> Seq (Maybe ByteString)
-> STFMIndexSeqB
     s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
-> STRef s Int
-> STRef s Int
-> ST s ()
iiFMIndexB Maybe ByteString
as
                            Seq (Maybe ByteString)
bs
                            STFMIndexSeqB
  s (Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString)))
bfmiss
                            STRef s Int
bfmiis
                            STRef s Int
bfmics

{-----------------------------------}


{-toFMIndex (Text) functions.-}

-- | Abstract 'PTFMIndexSeqT' type utilizing a 'Seq'.
type PTFMIndexSeqT = Seq (Maybe Text)

-- | Abstract 'FMIndexSeqT' type utilizing a 'Seq'.
-- (c,(indexofinputcurrentelement,Occ(c,k),inputcurrentelement))
type FMIndexSeqT = Seq (Maybe Text,Seq (Int,Int,Maybe Text))

-- | Abstract data type representing a 'FMIndexSeqT' in the (strict) ST monad.
type STFMIndexSeqT s a = STRef s FMIndexSeqT

-- | State function to update 'FMIndexSeqT'
-- with each step of the FMIndex.
updateSTFMIndexSeqAT :: STFMIndexSeqT s (Seq (Maybe Text,Seq (Int,Int,Maybe Text)))
                     -> (Int,Int,Maybe Text)
                     -> ST s ()
updateSTFMIndexSeqAT :: forall s.
STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> (Int, Int, Maybe Text) -> ST s ()
updateSTFMIndexSeqAT STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
s (Int, Int, Maybe Text)
e = do
  Seq (Maybe Text, Seq (Int, Int, Maybe Text))
s2 <- forall s a. STRef s a -> ST s a
readSTRef STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
s
  case forall a. Seq a -> ViewR a
viewr Seq (Maybe Text, Seq (Int, Int, Maybe Text))
s2 of
    ViewR (Maybe Text, Seq (Int, Int, Maybe Text))
EmptyR           -> forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
    (Seq (Maybe Text, Seq (Int, Int, Maybe Text))
s2h DS.:> (Maybe Text, Seq (Int, Int, Maybe Text))
s2fm) -> forall s a. STRef s a -> a -> ST s ()
writeSTRef STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
s (Seq (Maybe Text, Seq (Int, Int, Maybe Text))
s2h forall a. Seq a -> a -> Seq a
DS.|> (((\(Maybe Text
a,Seq (Int, Int, Maybe Text)
_) -> Maybe Text
a) (Maybe Text, Seq (Int, Int, Maybe Text))
s2fm),((\(Maybe Text
_,Seq (Int, Int, Maybe Text)
b) -> Seq (Int, Int, Maybe Text)
b) (Maybe Text, Seq (Int, Int, Maybe Text))
s2fm) forall a. Seq a -> a -> Seq a
DS.|> (Int, Int, Maybe Text)
e))

-- | State function to update 'FMIndexSeqT'
-- with each step of the FMIndex.
updateSTFMIndexSeqBT :: STFMIndexSeqT s (Seq (Maybe Text,Seq (Int,Int,Maybe Text)))
                     -> Maybe Text
                     -> ST s ()
updateSTFMIndexSeqBT :: forall s.
STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> Maybe Text -> ST s ()
updateSTFMIndexSeqBT STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
s Maybe Text
e = do
  Seq (Maybe Text, Seq (Int, Int, Maybe Text))
s2 <- forall s a. STRef s a -> ST s a
readSTRef STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
s
  forall s a. STRef s a -> a -> ST s ()
writeSTRef STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
s (Seq (Maybe Text, Seq (Int, Int, Maybe Text))
s2 forall a. Seq a -> a -> Seq a
DS.|> (Maybe Text
e,forall a. Seq a
DS.empty))

-- | State function to create empty 'STFMIndexSeqT' type.
emptySTFMIndexSeqT :: ST s (STFMIndexSeqT s a)
emptySTFMIndexSeqT :: forall s a. ST s (STFMIndexSeqT s a)
emptySTFMIndexSeqT = forall a s. a -> ST s (STRef s a)
newSTRef forall a. Seq a
DS.empty

-- | Abstract 'STFMIndexILT' and associated state type.
type STFMIndexILT s a = STRef s (Seq (Maybe Text))

-- | State function to load list into 'STFMIndexILT'.
loadSTFMIndexILT :: STMTFILT s (Maybe Text)
                 -> Seq (Maybe Text)
                 -> ST s ()
loadSTFMIndexILT :: forall s. STMTFILT s (Maybe Text) -> Seq (Maybe Text) -> ST s ()
loadSTFMIndexILT STMTFILT s (Maybe Text)
s Seq (Maybe Text)
e = forall s a. STRef s a -> a -> ST s ()
writeSTRef STMTFILT s (Maybe Text)
s Seq (Maybe Text)
e

-- | State function to create empty 'STFMIndexILT' type.
emptySTFMIndexILT :: ST s (STFMIndexILT s a)
emptySTFMIndexILT :: forall s a. ST s (STFMIndexILT s a)
emptySTFMIndexILT = forall a s. a -> ST s (STRef s a)
newSTRef forall a. Seq a
DS.empty

-- | Abstract 'STFMIndexCounterT' and associated state type.
type STFMIndexCounterT s a = STRef s Int

-- | State function to update 'STFMIndexCounterT'.
updateSTFMIndexCounterT :: STFMIndexCounterT s Int
                        -> Int
                        -> ST s ()
updateSTFMIndexCounterT :: forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterT STFMIndexCounterT s Int
s Int
e = forall s a. STRef s a -> a -> ST s ()
writeSTRef STFMIndexCounterT s Int
s Int
e

-- | State function to create empty 'STFMIndexCounterT' type.
emptySTFMIndexCounterT :: ST s (STFMIndexCounterT s Int)
emptySTFMIndexCounterT :: forall s. ST s (STFMIndexCounterB s Int)
emptySTFMIndexCounterT = forall a s. a -> ST s (STRef s a)
newSTRef Int
0

-- | Strict state monad function.
seqToFMIndexT :: PTFMIndexSeqT
              -> ST s FMIndexSeqT
seqToFMIndexT :: forall s.
Seq (Maybe Text)
-> ST s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
seqToFMIndexT Seq (Maybe Text)
DS.Empty      = do
  STFMIndexSeqT s Any
tfmiseqstackempty  <- forall s a. ST s (STFMIndexSeqT s a)
emptySTFMIndexSeqT
  Seq (Maybe Text, Seq (Int, Int, Maybe Text))
tfmiseqstackemptyr <- forall s a. STRef s a -> ST s a
readSTRef STFMIndexSeqT s Any
tfmiseqstackempty
  forall (m :: * -> *) a. Monad m => a -> m a
return Seq (Maybe Text, Seq (Int, Int, Maybe Text))
tfmiseqstackemptyr
seqToFMIndexT Seq (Maybe Text)
xs            = do
  STFMIndexSeqT s Any
tfmiseqstack     <- forall s a. ST s (STFMIndexSeqT s a)
emptySTFMIndexSeqT
  STFMIndexILT s Any
tfmiinitiallist  <- forall s a. ST s (STFMIndexILT s a)
emptySTFMIndexILT
  STFMIndexCounterT s Int
tfmicounterstack <- forall s. ST s (STFMIndexCounterB s Int)
emptySTFMIndexCounterT
  let il :: Seq (Maybe Text)
il = forall a. Ord a => Seq (Maybe a) -> Seq (Maybe a)
nubSeq' Seq (Maybe Text)
xs
  forall s. STMTFILT s (Maybe Text) -> Seq (Maybe Text) -> ST s ()
loadSTFMIndexILT STFMIndexILT s Any
tfmiinitiallist
                   Seq (Maybe Text)
il
  Seq (Maybe Text)
ctfmiinitiallist <- forall s a. STRef s a -> ST s a
readSTRef STFMIndexILT s Any
tfmiinitiallist
  forall {s}.
Seq (Maybe Text)
-> Seq (Maybe Text)
-> STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> STFMIndexCounterT s Int
-> ST s ()
iFMIndexT Seq (Maybe Text)
ctfmiinitiallist
            Seq (Maybe Text)
xs
            STFMIndexSeqT s Any
tfmiseqstack
            STFMIndexCounterT s Int
tfmicounterstack
  Seq (Maybe Text, Seq (Int, Int, Maybe Text))
tfmiseqstackr <- forall s a. STRef s a -> ST s a
readSTRef STFMIndexSeqT s Any
tfmiseqstack
  forall (m :: * -> *) a. Monad m => a -> m a
return Seq (Maybe Text, Seq (Int, Int, Maybe Text))
tfmiseqstackr
    where
      iFMIndexT :: Seq (Maybe Text)
-> Seq (Maybe Text)
-> STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> STFMIndexCounterT s Int
-> ST s ()
iFMIndexT Seq (Maybe Text)
DS.Empty      Seq (Maybe Text)
_      STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
_      STFMIndexCounterT s Int
_      = forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
      iFMIndexT (Maybe Text
y DS.:<| Seq (Maybe Text)
ys) Seq (Maybe Text)
zs     STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
tfmiss STFMIndexCounterT s Int
tfmics = do
        STFMIndexCounterT s Int
tfmiis <- forall s. ST s (STFMIndexCounterB s Int)
emptySTFMIndexCounterT
        forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterT STFMIndexCounterT s Int
tfmiis
                                Int
1
        forall s.
STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> Maybe Text -> ST s ()
updateSTFMIndexSeqBT STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
tfmiss
                             Maybe Text
y
        forall {s}.
Maybe Text
-> Seq (Maybe Text)
-> STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> STRef s Int
-> STRef s Int
-> ST s ()
iiFMIndexT Maybe Text
y
                   Seq (Maybe Text)
zs
                   STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
tfmiss
                   STFMIndexCounterT s Int
tfmiis
                   STFMIndexCounterT s Int
tfmics
        Seq (Maybe Text)
-> Seq (Maybe Text)
-> STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> STFMIndexCounterT s Int
-> ST s ()
iFMIndexT Seq (Maybe Text)
ys
                  Seq (Maybe Text)
zs
                  STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
tfmiss
                  STFMIndexCounterT s Int
tfmics
      iiFMIndexT :: Maybe Text
-> Seq (Maybe Text)
-> STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> STRef s Int
-> STRef s Int
-> ST s ()
iiFMIndexT Maybe Text
_  Seq (Maybe Text)
DS.Empty      STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
_      STRef s Int
_      STRef s Int
tfmics = do
        forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterT STRef s Int
tfmics
                                Int
0
        forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
      iiFMIndexT Maybe Text
as (Maybe Text
b DS.:<| Seq (Maybe Text)
bs) STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
tfmiss STRef s Int
tfmiis STRef s Int
tfmics = do
        Int
ctfmiis <- forall s a. STRef s a -> ST s a
readSTRef STRef s Int
tfmiis
        Int
ctfmics <- forall s a. STRef s a -> ST s a
readSTRef STRef s Int
tfmics
        if | Maybe Text
as forall a. Eq a => a -> a -> Bool
== Maybe Text
b
           -> do forall s.
STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> (Int, Int, Maybe Text) -> ST s ()
updateSTFMIndexSeqAT STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
tfmiss
                                      (Int
ctfmiis,Int
ctfmics forall a. Num a => a -> a -> a
+ Int
1,Maybe Text
b)
                 forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterT STRef s Int
tfmics
                                         (Int
ctfmics forall a. Num a => a -> a -> a
+ Int
1)
                 forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterT STRef s Int
tfmiis
                                         (Int
ctfmiis forall a. Num a => a -> a -> a
+ Int
1)
                 Maybe Text
-> Seq (Maybe Text)
-> STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> STRef s Int
-> STRef s Int
-> ST s ()
iiFMIndexT Maybe Text
as
                            Seq (Maybe Text)
bs
                            STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
tfmiss
                            STRef s Int
tfmiis
                            STRef s Int
tfmics
           | Bool
otherwise
           -> do forall s.
STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> (Int, Int, Maybe Text) -> ST s ()
updateSTFMIndexSeqAT STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
tfmiss
                                      (Int
ctfmiis,Int
ctfmics,Maybe Text
b)
                 forall s. STFMIndexCounterB s Int -> Int -> ST s ()
updateSTFMIndexCounterT STRef s Int
tfmiis
                                         (Int
ctfmiis forall a. Num a => a -> a -> a
+ Int
1)
                 Maybe Text
-> Seq (Maybe Text)
-> STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
-> STRef s Int
-> STRef s Int
-> ST s ()
iiFMIndexT Maybe Text
as
                            Seq (Maybe Text)
bs
                            STFMIndexSeqT s (Seq (Maybe Text, Seq (Int, Int, Maybe Text)))
tfmiss
                            STRef s Int
tfmiis
                            STRef s Int
tfmics

{-----------------------------}


{-fromFMIndex (ByteString) functions.-}

-- | Abstract 'FFMIndexSeqB' type utilizing a 'Seq'.
type FFMIndexSeqB = Seq (Maybe ByteString)

-- | Simple Inverse FMIndex function. 
seqFromFMIndexB :: FMIndexB
                -> FFMIndexSeqB
seqFromFMIndexB :: FMIndexB -> Seq (Maybe ByteString)
seqFromFMIndexB (FMIndexB Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
DS.Empty) = forall a. Seq a
DS.Empty
seqFromFMIndexB FMIndexB
xs                  = do
  let xss :: Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
xss = (\(FMIndexB Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
b) -> Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
b) FMIndexB
xs
  forall {a} {a} {b} {a}. Seq (a, Seq (a, b, a)) -> Seq a
iFFMIndexB Seq (Maybe ByteString, Seq (Int, Int, Maybe ByteString))
xss
    where
      iFFMIndexB :: Seq (a, Seq (a, b, a)) -> Seq a
iFFMIndexB Seq (a, Seq (a, b, a))
DS.Empty         = forall a. Seq a
DS.Empty 
      iFFMIndexB ((a
_,Seq (a, b, a)
b) DS.:<| Seq (a, Seq (a, b, a))
_) =
        forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(a
_,b
_,a
e) -> a
e) Seq (a, b, a)
b

{-------------------------------------}


{-fromFMIndex (Text) functions.-}

-- | Abstract 'FFMIndexSeqT' type utilizing a 'Seq'.
type FFMIndexSeqT = Seq (Maybe Text)

-- | Simple Inverse FMIndex function.
seqFromFMIndexT :: FMIndexT
                -> FFMIndexSeqT
seqFromFMIndexT :: FMIndexT -> Seq (Maybe Text)
seqFromFMIndexT (FMIndexT Seq (Maybe Text, Seq (Int, Int, Maybe Text))
DS.Empty) = forall a. Seq a
DS.Empty
seqFromFMIndexT FMIndexT
xs                  = do
  let xss :: Seq (Maybe Text, Seq (Int, Int, Maybe Text))
xss = (\(FMIndexT Seq (Maybe Text, Seq (Int, Int, Maybe Text))
t) -> Seq (Maybe Text, Seq (Int, Int, Maybe Text))
t) FMIndexT
xs
  forall {a} {a} {b} {a}. Seq (a, Seq (a, b, a)) -> Seq a
iFFMIndexT Seq (Maybe Text, Seq (Int, Int, Maybe Text))
xss
    where
      iFFMIndexT :: Seq (a, Seq (a, b, a)) -> Seq a
iFFMIndexT Seq (a, Seq (a, b, a))
DS.Empty         = forall a. Seq a
DS.Empty
      iFFMIndexT ((a
_,Seq (a, b, a)
b) DS.:<| Seq (a, Seq (a, b, a))
_) =
        forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(a
_,b
_,a
e) -> a
e) Seq (a, b, a)
b

{-------------------------------}