{-# LANGUAGE RecordWildCards #-}
module Network.Control.LRUCache (
LRUCache,
empty,
insert,
delete,
lookup,
) where
import Prelude hiding (lookup)
import Data.OrdPSQ (OrdPSQ)
import qualified Data.OrdPSQ as PSQ
type Priority = Int
data LRUCache k v = LRUCache
{ forall k v. LRUCache k v -> Int
lcLimit :: Int
, forall k v. LRUCache k v -> Int
lcSize :: Int
, forall k v. LRUCache k v -> Int
lcTick :: Priority
, forall k v. LRUCache k v -> OrdPSQ k Int v
lcQueue :: OrdPSQ k Priority v
}
empty
:: Int
-> LRUCache k v
empty :: forall k v. Int -> LRUCache k v
empty Int
lim = forall k v. Int -> Int -> Int -> OrdPSQ k Int v -> LRUCache k v
LRUCache Int
lim Int
0 Int
0 forall k p v. OrdPSQ k p v
PSQ.empty
insert :: Ord k => k -> v -> LRUCache k v -> LRUCache k v
insert :: forall k v. Ord k => k -> v -> LRUCache k v -> LRUCache k v
insert k
k v
v c :: LRUCache k v
c@LRUCache{Int
OrdPSQ k Int v
lcQueue :: OrdPSQ k Int v
lcTick :: Int
lcSize :: Int
lcLimit :: Int
lcQueue :: forall k v. LRUCache k v -> OrdPSQ k Int v
lcTick :: forall k v. LRUCache k v -> Int
lcSize :: forall k v. LRUCache k v -> Int
lcLimit :: forall k v. LRUCache k v -> Int
..}
| Int
lcSize forall a. Eq a => a -> a -> Bool
== Int
lcLimit =
let q :: OrdPSQ k Int v
q = forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
PSQ.insert k
k Int
lcTick v
v forall a b. (a -> b) -> a -> b
$ forall k p v. (Ord k, Ord p) => OrdPSQ k p v -> OrdPSQ k p v
PSQ.deleteMin OrdPSQ k Int v
lcQueue
in LRUCache k v
c{lcTick :: Int
lcTick = Int
lcTick forall a. Num a => a -> a -> a
+ Int
1, lcQueue :: OrdPSQ k Int v
lcQueue = OrdPSQ k Int v
q}
| Bool
otherwise =
let q :: OrdPSQ k Int v
q = forall k p v.
(Ord k, Ord p) =>
k -> p -> v -> OrdPSQ k p v -> OrdPSQ k p v
PSQ.insert k
k Int
lcTick v
v OrdPSQ k Int v
lcQueue
in LRUCache k v
c{lcTick :: Int
lcTick = Int
lcTick forall a. Num a => a -> a -> a
+ Int
1, lcQueue :: OrdPSQ k Int v
lcQueue = OrdPSQ k Int v
q, lcSize :: Int
lcSize = Int
lcSize forall a. Num a => a -> a -> a
+ Int
1}
delete :: Ord k => k -> LRUCache k v -> LRUCache k v
delete :: forall k v. Ord k => k -> LRUCache k v -> LRUCache k v
delete k
k c :: LRUCache k v
c@LRUCache{Int
OrdPSQ k Int v
lcQueue :: OrdPSQ k Int v
lcTick :: Int
lcSize :: Int
lcLimit :: Int
lcQueue :: forall k v. LRUCache k v -> OrdPSQ k Int v
lcTick :: forall k v. LRUCache k v -> Int
lcSize :: forall k v. LRUCache k v -> Int
lcLimit :: forall k v. LRUCache k v -> Int
..} =
let q :: OrdPSQ k Int v
q = forall k p v. (Ord k, Ord p) => k -> OrdPSQ k p v -> OrdPSQ k p v
PSQ.delete k
k OrdPSQ k Int v
lcQueue
in LRUCache k v
c{lcQueue :: OrdPSQ k Int v
lcQueue = OrdPSQ k Int v
q, lcSize :: Int
lcSize = Int
lcSize forall a. Num a => a -> a -> a
- Int
1}
lookup :: Ord k => k -> LRUCache k v -> Maybe v
lookup :: forall k v. Ord k => k -> LRUCache k v -> Maybe v
lookup k
k LRUCache{Int
OrdPSQ k Int v
lcQueue :: OrdPSQ k Int v
lcTick :: Int
lcSize :: Int
lcLimit :: Int
lcQueue :: forall k v. LRUCache k v -> OrdPSQ k Int v
lcTick :: forall k v. LRUCache k v -> Int
lcSize :: forall k v. LRUCache k v -> Int
lcLimit :: forall k v. LRUCache k v -> Int
..} = forall a b. (a, b) -> b
snd forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall k p v. Ord k => k -> OrdPSQ k p v -> Maybe (p, v)
PSQ.lookup k
k OrdPSQ k Int v
lcQueue