-- | This internal module is exposed only for testing and benchmarking. You
-- don't need to import it.
{-# LANGUAGE RecordWildCards #-}
module Text.Regex.Applicative.StateQueue
    ( StateQueue
    , empty
    , insert
    , insertUnique
    , getElements
    ) where

import Prelude hiding (read, lookup, replicate)
import qualified Data.IntSet as IntSet
import Data.Foldable as F

-- | 'StateQueue' is a data structure that can efficiently insert elements
-- (preserving their order)
-- and check whether an element with the given 'Int' key is already in the queue.
data StateQueue a = StateQueue
    { forall a. StateQueue a -> [a]
elements :: [a]
    , forall a. StateQueue a -> IntSet
ids :: !IntSet.IntSet
    }
    deriving (StateQueue a -> StateQueue a -> Bool
forall a. Eq a => StateQueue a -> StateQueue a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: StateQueue a -> StateQueue a -> Bool
$c/= :: forall a. Eq a => StateQueue a -> StateQueue a -> Bool
== :: StateQueue a -> StateQueue a -> Bool
$c== :: forall a. Eq a => StateQueue a -> StateQueue a -> Bool
Eq,Int -> StateQueue a -> ShowS
forall a. Show a => Int -> StateQueue a -> ShowS
forall a. Show a => [StateQueue a] -> ShowS
forall a. Show a => StateQueue a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [StateQueue a] -> ShowS
$cshowList :: forall a. Show a => [StateQueue a] -> ShowS
show :: StateQueue a -> String
$cshow :: forall a. Show a => StateQueue a -> String
showsPrec :: Int -> StateQueue a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> StateQueue a -> ShowS
Show)

instance Foldable StateQueue where
  foldr :: forall a b. (a -> b -> b) -> b -> StateQueue a -> b
foldr a -> b -> b
f b
a = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
F.foldr a -> b -> b
f b
a forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. StateQueue a -> [a]
getElements

-- | Get the list of all elements
getElements :: StateQueue a -> [a]
getElements :: forall a. StateQueue a -> [a]
getElements = forall a. [a] -> [a]
reverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. StateQueue a -> [a]
elements

{-# INLINE empty #-}
-- | The empty state queue
empty :: StateQueue a
empty :: forall a. StateQueue a
empty = StateQueue
    { elements :: [a]
elements = []
    , ids :: IntSet
ids = IntSet
IntSet.empty
    }

{-# INLINE insert #-}
-- | Insert an element in the state queue, unless there is already an element with the same key
insertUnique
    :: Int -- ^ key
    -> a
    -> StateQueue a
    -> StateQueue a
insertUnique :: forall a. Int -> a -> StateQueue a -> StateQueue a
insertUnique Int
i a
v sq :: StateQueue a
sq@StateQueue { ids :: forall a. StateQueue a -> IntSet
ids = IntSet
ids, elements :: forall a. StateQueue a -> [a]
elements = [a]
elements } =
    if Int
i Int -> IntSet -> Bool
`IntSet.member` IntSet
ids
        then StateQueue a
sq
        else StateQueue a
sq { elements :: [a]
elements = a
v forall a. a -> [a] -> [a]
: [a]
elements
                , ids :: IntSet
ids = Int -> IntSet -> IntSet
IntSet.insert Int
i IntSet
ids
                }

-- | Insert an element in the state queue without a key.
--
-- Since 'insert' doesn't take a key, it won't affect any 'insertUnique'.
insert
    :: a
    -> StateQueue a
    -> StateQueue a
insert :: forall a. a -> StateQueue a -> StateQueue a
insert a
v StateQueue a
sq =
    StateQueue a
sq { elements :: [a]
elements = a
v forall a. a -> [a] -> [a]
: forall a. StateQueue a -> [a]
elements StateQueue a
sq }