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
|
{-# LANGUAGE RecordWildCards #-}
module Network.Control.LRUCache (
-- * LRU cache
LRUCache,
empty,
insert,
delete,
lookup,
) where
import Prelude hiding (lookup)
import Data.OrdPSQ (OrdPSQ)
import qualified Data.OrdPSQ as PSQ
type Priority = Int
-- | Sized cache based on least recently used.
data LRUCache k v = LRUCache
{ lcLimit :: Int
, lcSize :: Int
, lcTick :: Priority
, lcQueue :: OrdPSQ k Priority v
}
-- | Empty 'LRUCache'.
empty
:: Int
-- ^ The size of 'LRUCache'.
-> LRUCache k v
empty lim = LRUCache lim 0 0 PSQ.empty
-- | Inserting.
insert :: Ord k => k -> v -> LRUCache k v -> LRUCache k v
insert k v c@LRUCache{..}
| lcSize == lcLimit =
let q = PSQ.insert k lcTick v $ PSQ.deleteMin lcQueue
in c{lcTick = lcTick + 1, lcQueue = q}
| otherwise =
let q = PSQ.insert k lcTick v lcQueue
in c{lcTick = lcTick + 1, lcQueue = q, lcSize = lcSize + 1}
-- | Deleting.
delete :: Ord k => k -> LRUCache k v -> LRUCache k v
delete k c@LRUCache{..} =
let q = PSQ.delete k lcQueue
in c{lcQueue = q, lcSize = lcSize - 1}
-- | Looking up.
lookup :: Ord k => k -> LRUCache k v -> Maybe v
lookup k LRUCache{..} = snd <$> PSQ.lookup k lcQueue
|
