    -- | 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
    (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

    -- | Get the list of all elements
    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 #-}
    -- | 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 = v : elements
                    , ids = IntSet.insert i 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 = v : elements sq }