1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
-- | 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
{ elements :: [a]
, ids :: !IntSet.IntSet
}
deriving (Eq,Show)
instance Foldable StateQueue where
foldr f a = F.foldr f a . getElements
-- | Get the list of all elements
getElements :: StateQueue a -> [a]
getElements = reverse . elements
{-# INLINE empty #-}
-- | The empty state queue
empty :: StateQueue a
empty = StateQueue
{ elements = []
, ids = 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 i v sq@StateQueue { ids = ids, elements = elements } =
if i `IntSet.member` ids
then sq
else 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 v sq =
sq { elements = v : elements sq }
|
