-- | An example cache-policy implementation: Least-Recently-Used.
--
-- >>> withAssocCache $ withFiniteCache 2 $ withLruCache testC
-- one
-- two
-- testing
-- [3,3,3,3,7,7]
--
-- >>> withAssocCache $ withFiniteCache 1 $ withLruCache testC
-- one
-- two
-- one
-- two
-- testing
-- [3,3,3,3,7,7]
--
-- >>> withAssocCache $ withFiniteCache 0 $ withLruCache testC
-- one
-- two
-- one
-- two
-- testing
-- testing
-- [3,3,3,3,7,7]
lruCache :: (Monad m, Eq k) => Cache m k a -> Cache (StateT [k] m) k a
lruCache c = Cache
    { readCache      = \k   -> do
      r <- lift $ readCache c k
      when (isJust r) $ touch k
      return r
    , writeCache     = \k v -> do
        r <- lift $ writeCache c k v
        if r
          then return True
          else do
            makeRoom
            lift $ writeCache c k v
    , clearCache     =                     (lift $ clearCache     c    )
    , clearFromCache = \k   -> remove k >> (lift $ clearFromCache c k  )
    }
  where
    touch k = write k
    makeRoom = do
        mostRecentlyUsed <- get
        case mostRecentlyUsed of
          (k:ks) -> do
            put ks
            lift $ clearFromCache c k
          [] -> do
            -- the cache is both full and empty? try to reset.
            lift $ clearCache c

    write  k = modify (k:)
    remove k = modify $ filter (/= k)
lruCache :: (Monad m, Eq k) => Cache m k a -> Cache (StateT [k] m) k a
lruCache c = Cache
    { readCache      = \k   -> do
      r <- lift $ readCache c k
      when (isJust r) $ touch k
      return r
    , writeCache     = \k v -> do
        r <- lift $ writeCache c k v
        if r
          then return True
          else do
            makeRoom
            lift $ writeCache c k v
    , clearCache     =                     (lift $ clearCache     c    )
    , clearFromCache = \k   -> remove k >> (lift $ clearFromCache c k  )
    }
  where
    touch k = write k
    makeRoom = do
        mostRecentlyUsed <- get
        case mostRecentlyUsed of
          (k:ks) -> do
            put ks
            lift $ clearFromCache c k
          [] -> do
            -- the cache is both full and empty? try to reset.
            lift $ clearCache c

    write  k = modify (k:)
    remove k = modify $ filter (/= k)
lruCache c = Cache
    { readCache      = \k   -> do
      r <- lift $ readCache c k
      when (isJust r) $ touch k
      return r
    , writeCache     = \k v -> do
        r <- lift $ writeCache c k v
        if r
          then return True
          else do
            makeRoom
            lift $ writeCache c k v
    , clearCache     =                     (lift $ clearCache     c    )
    , clearFromCache = \k   -> remove k >> (lift $ clearFromCache c k  )
    }
  where
    touch k = write k
    makeRoom = do
        mostRecentlyUsed <- get
        case mostRecentlyUsed of
          (k:ks) -> do
            put ks
            lift $ clearFromCache c k
          [] -> do
            -- the cache is both full and empty? try to reset.
            lift $ clearCache c

    write  k = modify (k:)
    remove k = modify $ filter (/= k)