{-# 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
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
(StateQueue a -> StateQueue a -> Bool)
-> (StateQueue a -> StateQueue a -> Bool) -> Eq (StateQueue a)
forall a. Eq a => StateQueue a -> StateQueue a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$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
/= :: StateQueue a -> StateQueue a -> Bool
Eq,Int -> StateQueue a -> ShowS
[StateQueue a] -> ShowS
StateQueue a -> String
(Int -> StateQueue a -> ShowS)
-> (StateQueue a -> String)
-> ([StateQueue a] -> ShowS)
-> Show (StateQueue a)
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
$cshowsPrec :: forall a. Show a => Int -> StateQueue a -> ShowS
showsPrec :: Int -> StateQueue a -> ShowS
$cshow :: forall a. Show a => StateQueue a -> String
show :: StateQueue a -> String
$cshowList :: forall a. Show a => [StateQueue a] -> ShowS
showList :: [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 = (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
F.foldr a -> b -> b
f b
a ([a] -> b) -> (StateQueue a -> [a]) -> StateQueue a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StateQueue a -> [a]
forall a. StateQueue a -> [a]
getElements
getElements :: StateQueue a -> [a]
getElements :: forall a. StateQueue a -> [a]
getElements = [a] -> [a]
forall a. [a] -> [a]
reverse ([a] -> [a]) -> (StateQueue a -> [a]) -> StateQueue a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StateQueue a -> [a]
forall a. StateQueue a -> [a]
elements
{-# INLINE empty #-}
empty :: StateQueue a
empty :: forall a. StateQueue a
empty = StateQueue
{ elements :: [a]
elements = []
, ids :: IntSet
ids = IntSet
IntSet.empty
}
{-# INLINE insert #-}
insertUnique
:: Int
-> 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 = v : elements
, ids = IntSet.insert i ids
}
insert
:: a
-> StateQueue a
-> StateQueue a
insert :: forall a. a -> StateQueue a -> StateQueue a
insert a
v StateQueue a
sq =
StateQueue a
sq { elements = v : elements sq }