{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveTraversable #-}
{-|
Module      : Data.LruCache.Internal
Copyright   : (c) Moritz Kiefer, 2016
              (c) Jasper Van der Jeugt, 2015
License     : BSD3
Maintainer  : moritz.kiefer@purelyfunctional.org

This module contains internal datastructures. 
No guarantees are made as to the stability of this module
and violating invariants can result in unspecified behavior.
-}
module Data.LruCache.Internal
  ( LruCache(..)
  , Priority
  ) where
  
import           Control.DeepSeq (NFData,rnf)
import           Data.Int
import qualified Data.HashPSQ as HashPSQ
import           Data.Foldable (Foldable)
import           Data.Traversable (Traversable)

-- | Logical time at which an element was last accessed.
type Priority = Int64

-- | LRU cache based on hashing.
data LruCache k v = LruCache
  { forall k v. LruCache k v -> Int
lruCapacity :: !Int                         -- ^ The maximum number of elements in the queue
  , forall k v. LruCache k v -> Int
lruSize :: !Int                             -- ^ The current number of elements in the queue
  , forall k v. LruCache k v -> Priority
lruTick :: !Priority                        -- ^ The next logical time
  , forall k v. LruCache k v -> HashPSQ k Priority v
lruQueue :: !(HashPSQ.HashPSQ k Priority v) -- ^ Underlying priority queue
  } 
  deriving (LruCache k v -> LruCache k v -> Bool
(LruCache k v -> LruCache k v -> Bool)
-> (LruCache k v -> LruCache k v -> Bool) -> Eq (LruCache k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v.
(Eq v, Hashable k, Ord k) =>
LruCache k v -> LruCache k v -> Bool
$c== :: forall k v.
(Eq v, Hashable k, Ord k) =>
LruCache k v -> LruCache k v -> Bool
== :: LruCache k v -> LruCache k v -> Bool
$c/= :: forall k v.
(Eq v, Hashable k, Ord k) =>
LruCache k v -> LruCache k v -> Bool
/= :: LruCache k v -> LruCache k v -> Bool
Eq,Int -> LruCache k v -> ShowS
[LruCache k v] -> ShowS
LruCache k v -> String
(Int -> LruCache k v -> ShowS)
-> (LruCache k v -> String)
-> ([LruCache k v] -> ShowS)
-> Show (LruCache k v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k v. (Show k, Show v) => Int -> LruCache k v -> ShowS
forall k v. (Show k, Show v) => [LruCache k v] -> ShowS
forall k v. (Show k, Show v) => LruCache k v -> String
$cshowsPrec :: forall k v. (Show k, Show v) => Int -> LruCache k v -> ShowS
showsPrec :: Int -> LruCache k v -> ShowS
$cshow :: forall k v. (Show k, Show v) => LruCache k v -> String
show :: LruCache k v -> String
$cshowList :: forall k v. (Show k, Show v) => [LruCache k v] -> ShowS
showList :: [LruCache k v] -> ShowS
Show,(forall a b. (a -> b) -> LruCache k a -> LruCache k b)
-> (forall a b. a -> LruCache k b -> LruCache k a)
-> Functor (LruCache k)
forall a b. a -> LruCache k b -> LruCache k a
forall a b. (a -> b) -> LruCache k a -> LruCache k b
forall k a b. a -> LruCache k b -> LruCache k a
forall k a b. (a -> b) -> LruCache k a -> LruCache k b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall k a b. (a -> b) -> LruCache k a -> LruCache k b
fmap :: forall a b. (a -> b) -> LruCache k a -> LruCache k b
$c<$ :: forall k a b. a -> LruCache k b -> LruCache k a
<$ :: forall a b. a -> LruCache k b -> LruCache k a
Functor,(forall m. Monoid m => LruCache k m -> m)
-> (forall m a. Monoid m => (a -> m) -> LruCache k a -> m)
-> (forall m a. Monoid m => (a -> m) -> LruCache k a -> m)
-> (forall a b. (a -> b -> b) -> b -> LruCache k a -> b)
-> (forall a b. (a -> b -> b) -> b -> LruCache k a -> b)
-> (forall b a. (b -> a -> b) -> b -> LruCache k a -> b)
-> (forall b a. (b -> a -> b) -> b -> LruCache k a -> b)
-> (forall a. (a -> a -> a) -> LruCache k a -> a)
-> (forall a. (a -> a -> a) -> LruCache k a -> a)
-> (forall a. LruCache k a -> [a])
-> (forall a. LruCache k a -> Bool)
-> (forall a. LruCache k a -> Int)
-> (forall a. Eq a => a -> LruCache k a -> Bool)
-> (forall a. Ord a => LruCache k a -> a)
-> (forall a. Ord a => LruCache k a -> a)
-> (forall a. Num a => LruCache k a -> a)
-> (forall a. Num a => LruCache k a -> a)
-> Foldable (LruCache k)
forall a. Eq a => a -> LruCache k a -> Bool
forall a. Num a => LruCache k a -> a
forall a. Ord a => LruCache k a -> a
forall m. Monoid m => LruCache k m -> m
forall a. LruCache k a -> Bool
forall a. LruCache k a -> Int
forall a. LruCache k a -> [a]
forall a. (a -> a -> a) -> LruCache k a -> a
forall k a. Eq a => a -> LruCache k a -> Bool
forall k a. Num a => LruCache k a -> a
forall k a. Ord a => LruCache k a -> a
forall m a. Monoid m => (a -> m) -> LruCache k a -> m
forall k m. Monoid m => LruCache k m -> m
forall k a. LruCache k a -> Bool
forall k v. LruCache k v -> Int
forall k a. LruCache k a -> [a]
forall b a. (b -> a -> b) -> b -> LruCache k a -> b
forall a b. (a -> b -> b) -> b -> LruCache k a -> b
forall k a. (a -> a -> a) -> LruCache k a -> a
forall k m a. Monoid m => (a -> m) -> LruCache k a -> m
forall k b a. (b -> a -> b) -> b -> LruCache k a -> b
forall k a b. (a -> b -> b) -> b -> LruCache k a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall k m. Monoid m => LruCache k m -> m
fold :: forall m. Monoid m => LruCache k m -> m
$cfoldMap :: forall k m a. Monoid m => (a -> m) -> LruCache k a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> LruCache k a -> m
$cfoldMap' :: forall k m a. Monoid m => (a -> m) -> LruCache k a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> LruCache k a -> m
$cfoldr :: forall k a b. (a -> b -> b) -> b -> LruCache k a -> b
foldr :: forall a b. (a -> b -> b) -> b -> LruCache k a -> b
$cfoldr' :: forall k a b. (a -> b -> b) -> b -> LruCache k a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> LruCache k a -> b
$cfoldl :: forall k b a. (b -> a -> b) -> b -> LruCache k a -> b
foldl :: forall b a. (b -> a -> b) -> b -> LruCache k a -> b
$cfoldl' :: forall k b a. (b -> a -> b) -> b -> LruCache k a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> LruCache k a -> b
$cfoldr1 :: forall k a. (a -> a -> a) -> LruCache k a -> a
foldr1 :: forall a. (a -> a -> a) -> LruCache k a -> a
$cfoldl1 :: forall k a. (a -> a -> a) -> LruCache k a -> a
foldl1 :: forall a. (a -> a -> a) -> LruCache k a -> a
$ctoList :: forall k a. LruCache k a -> [a]
toList :: forall a. LruCache k a -> [a]
$cnull :: forall k a. LruCache k a -> Bool
null :: forall a. LruCache k a -> Bool
$clength :: forall k v. LruCache k v -> Int
length :: forall a. LruCache k a -> Int
$celem :: forall k a. Eq a => a -> LruCache k a -> Bool
elem :: forall a. Eq a => a -> LruCache k a -> Bool
$cmaximum :: forall k a. Ord a => LruCache k a -> a
maximum :: forall a. Ord a => LruCache k a -> a
$cminimum :: forall k a. Ord a => LruCache k a -> a
minimum :: forall a. Ord a => LruCache k a -> a
$csum :: forall k a. Num a => LruCache k a -> a
sum :: forall a. Num a => LruCache k a -> a
$cproduct :: forall k a. Num a => LruCache k a -> a
product :: forall a. Num a => LruCache k a -> a
Foldable,Functor (LruCache k)
Foldable (LruCache k)
(Functor (LruCache k), Foldable (LruCache k)) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> LruCache k a -> f (LruCache k b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    LruCache k (f a) -> f (LruCache k a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> LruCache k a -> m (LruCache k b))
-> (forall (m :: * -> *) a.
    Monad m =>
    LruCache k (m a) -> m (LruCache k a))
-> Traversable (LruCache k)
forall k. Functor (LruCache k)
forall k. Foldable (LruCache k)
forall k (m :: * -> *) a.
Monad m =>
LruCache k (m a) -> m (LruCache k a)
forall k (f :: * -> *) a.
Applicative f =>
LruCache k (f a) -> f (LruCache k a)
forall k (m :: * -> *) a b.
Monad m =>
(a -> m b) -> LruCache k a -> m (LruCache k b)
forall k (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> LruCache k a -> f (LruCache k b)
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a.
Monad m =>
LruCache k (m a) -> m (LruCache k a)
forall (f :: * -> *) a.
Applicative f =>
LruCache k (f a) -> f (LruCache k a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> LruCache k a -> m (LruCache k b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> LruCache k a -> f (LruCache k b)
$ctraverse :: forall k (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> LruCache k a -> f (LruCache k b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> LruCache k a -> f (LruCache k b)
$csequenceA :: forall k (f :: * -> *) a.
Applicative f =>
LruCache k (f a) -> f (LruCache k a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
LruCache k (f a) -> f (LruCache k a)
$cmapM :: forall k (m :: * -> *) a b.
Monad m =>
(a -> m b) -> LruCache k a -> m (LruCache k b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> LruCache k a -> m (LruCache k b)
$csequence :: forall k (m :: * -> *) a.
Monad m =>
LruCache k (m a) -> m (LruCache k a)
sequence :: forall (m :: * -> *) a.
Monad m =>
LruCache k (m a) -> m (LruCache k a)
Traversable)

instance (NFData k, NFData v) => NFData (LruCache k v) where
  rnf :: LruCache k v -> ()
rnf (LruCache Int
cap Int
size Priority
tick HashPSQ k Priority v
queue) =
    Int -> ()
forall a. NFData a => a -> ()
rnf Int
cap () -> () -> ()
forall a b. a -> b -> b
`seq` Int -> ()
forall a. NFData a => a -> ()
rnf Int
size () -> () -> ()
forall a b. a -> b -> b
`seq` Priority -> ()
forall a. NFData a => a -> ()
rnf Priority
tick () -> () -> ()
forall a b. a -> b -> b
`seq` HashPSQ k Priority v -> ()
forall a. NFData a => a -> ()
rnf HashPSQ k Priority v
queue