-- Simple FIFO queue in ST monad
module Text.AhoCorasick.Internal.Deque (
      mkDQ
    , pushBack
    , popFront
    , dqLength
    , DQ
    ) where

import Control.Monad.ST.Strict
import Data.STRef

data DQNode a s = DQNode {
      forall a s. DQNode a s -> a
dqnData    :: a
    , forall a s. DQNode a s -> Maybe (STRef s (DQNode a s))
dqnNext    :: Maybe (STRef s (DQNode a s))
    }

type DQ a s = STRef s (
    Maybe (
        STRef s (DQNode a s), 
        STRef s (DQNode a s)
        ),
    Int)

mkDQ :: ST s (DQ a s)
mkDQ :: forall s a. ST s (DQ a s)
mkDQ = forall a s. a -> ST s (STRef s a)
newSTRef (forall a. Maybe a
Nothing, Int
0)

pushBack :: DQ a s -> a -> ST s ()
pushBack :: forall a s. DQ a s -> a -> ST s ()
pushBack DQ a s
dq a
dt = do
    (Maybe (STRef s (DQNode a s), STRef s (DQNode a s)), Int)
dqr <- forall s a. STRef s a -> ST s a
readSTRef DQ a s
dq
    case (Maybe (STRef s (DQNode a s), STRef s (DQNode a s)), Int)
dqr of
        (Maybe (STRef s (DQNode a s), STRef s (DQNode a s))
Nothing,Int
_) -> do
            STRef s (DQNode a s)
nn <- forall a s. a -> ST s (STRef s a)
newSTRef forall a b. (a -> b) -> a -> b
$ forall a s. a -> Maybe (STRef s (DQNode a s)) -> DQNode a s
DQNode a
dt forall a. Maybe a
Nothing
            forall s a. STRef s a -> a -> ST s ()
writeSTRef DQ a s
dq (forall a. a -> Maybe a
Just (STRef s (DQNode a s)
nn, STRef s (DQNode a s)
nn), Int
1)
        (Just (STRef s (DQNode a s)
f,STRef s (DQNode a s)
l),Int
lng) -> do
            STRef s (DQNode a s)
nn <- forall a s. a -> ST s (STRef s a)
newSTRef forall a b. (a -> b) -> a -> b
$ forall a s. a -> Maybe (STRef s (DQNode a s)) -> DQNode a s
DQNode a
dt forall a. Maybe a
Nothing
            forall s a. STRef s a -> (a -> a) -> ST s ()
modifySTRef STRef s (DQNode a s)
l (\DQNode a s
v -> DQNode a s
v {dqnNext :: Maybe (STRef s (DQNode a s))
dqnNext = forall a. a -> Maybe a
Just STRef s (DQNode a s)
nn})
            forall s a. STRef s a -> a -> ST s ()
writeSTRef DQ a s
dq forall a b. (a -> b) -> a -> b
$ (forall a. a -> Maybe a
Just (STRef s (DQNode a s)
f,STRef s (DQNode a s)
nn),Int
lng forall a. Num a => a -> a -> a
+ Int
1)

popFront :: DQ a s -> ST s (Maybe a)
popFront :: forall a s. DQ a s -> ST s (Maybe a)
popFront DQ a s
dq = do
    (Maybe (STRef s (DQNode a s), STRef s (DQNode a s)), Int)
dqr <- forall s a. STRef s a -> ST s a
readSTRef DQ a s
dq
    case (Maybe (STRef s (DQNode a s), STRef s (DQNode a s)), Int)
dqr of
        (Maybe (STRef s (DQNode a s), STRef s (DQNode a s))
Nothing,Int
_) -> forall (m :: * -> *) a. Monad m => a -> m a
return forall a. Maybe a
Nothing
        (Just (STRef s (DQNode a s)
f,STRef s (DQNode a s)
l),Int
lng) -> do
            DQNode a s
fd <- forall s a. STRef s a -> ST s a
readSTRef STRef s (DQNode a s)
f
            case forall a s. DQNode a s -> Maybe (STRef s (DQNode a s))
dqnNext DQNode a s
fd of
                Maybe (STRef s (DQNode a s))
Nothing -> forall s a. STRef s a -> a -> ST s ()
writeSTRef DQ a s
dq (forall a. Maybe a
Nothing, Int
0)
                Just STRef s (DQNode a s)
k -> forall s a. STRef s a -> a -> ST s ()
writeSTRef DQ a s
dq forall a b. (a -> b) -> a -> b
$ (forall a. a -> Maybe a
Just (STRef s (DQNode a s)
k,STRef s (DQNode a s)
l),Int
lngforall a. Num a => a -> a -> a
-Int
1)
            forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a s. DQNode a s -> a
dqnData DQNode a s
fd

dqLength :: DQ a s -> ST s Int
dqLength :: forall a s. DQ a s -> ST s Int
dqLength DQ a s
dq = do
    (Maybe (STRef s (DQNode a s), STRef s (DQNode a s))
_,Int
l) <- forall s a. STRef s a -> ST s a
readSTRef DQ a s
dq
    forall (m :: * -> *) a. Monad m => a -> m a
return Int
l