-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Implements an LRU data structure
--   
--   Implements an LRU data structure
@package LRU
@version 0.1.1


-- | This module implements a least-recently-used structure. Conceptually,
--   it's a list of values where the head of the list is the most recently
--   used value. When a value is used, it's moved from its place in the
--   list to the head of the list. The last element in the list is thus the
--   least-recently-used value.
--   
--   This structure is often used in caches to decide which values to evict
--   when the cache becomes full.
--   
--   This module uses a Map to implement the LRU efficiently and thus
--   there's the requirement that the elements of the LRU be instances of
--   Ord, which a more general (but slower) LRU implementation could avoid.
module Data.LRU

-- | An LRU. Contains the head element, last element and the map from
--   elements to their Items
data Ord a => LRU a

-- | Returns an empty LRU. O(1)
empty :: Ord a => LRU a

-- | Returns True iff the LRU is empty. O(1)
null :: Ord a => LRU a -> Bool

-- | Returns the number of elements in the LRU. O(1)
size :: Ord a => LRU a -> Int

-- | Insert a value into an LRU. If the value is already in the LRU, it's
--   moved to the head of the list. O(log n)
hit :: Ord a => a -> LRU a -> LRU a

-- | Removes an element from the LRU, if it exists. O(log n)
delete :: Ord a => a -> LRU a -> LRU a

-- | Returns a list of the members of the LRU in order, newest first.
--   O(n(log n))
toList :: Ord a => LRU a -> [a]

-- | Returns true iff the given element is in the LRU. O(log n)
member :: Ord a => a -> LRU a -> Bool

-- | Remove the last element of the LRU. Errors out if the LRU is empty.
--   O(log n)
pop :: Ord a => LRU a -> LRU a

-- | Return the last element of the LRU. O(1)
last :: (Ord a, Monad m) => LRU a -> m a
instance (Ord a, Show a) => Show (LRU a)