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


-- | a simple pure LRU cache
--   
--   This package contains a simple pure LRU cache, implemented in terms of
--   <a>Data.Map</a>.
--   
--   It also contains a mutable IO wrapper providing atomic updates to an
--   LRU cache.
@package lrucache
@version 0.1


-- | This module provides access to all the internals use by the LRU type.
--   This can be used to create data structures that violate the invariants
--   the public interface maintains. Be careful when using this module. The
--   <a>valid</a> function can be used to check if an LRU structure
--   satisfies the invariants the public interface maintains.
--   
--   If this degree of control isn't needed, consider using
--   <a>Data.Cache.LRU</a> instead.
module Data.Cache.LRU.Internal

-- | Stores the information that makes up an LRU cache
data LRU key val
LRU :: Maybe key -> Maybe key -> Int -> Map key (LinkedVal key val) -> LRU key val

-- | the key of the most recently accessed entry
first :: LRU key val -> Maybe key

-- | the key of the least recently accessed entry
last :: LRU key val -> Maybe key

-- | the maximum size of the LRU cache
maxSize :: LRU key val -> Int

-- | the backing <a>Map</a>
content :: LRU key val -> Map key (LinkedVal key val)

-- | The values stored in the Map of the LRU cache. They embed a
--   doubly-linked list through the values of the <a>Map</a>.
data LinkedVal key val
Link :: val -> Maybe key -> Maybe key -> LinkedVal key val

-- | The actual value
value :: LinkedVal key val -> val

-- | the key of the value before this one
prev :: LinkedVal key val -> Maybe key

-- | the key of the value after this one
next :: LinkedVal key val -> Maybe key

-- | Make an LRU. The LRU is guaranteed to not grow above the specified
--   number of entries.
newLRU :: (Ord key) => Int -> LRU key val

-- | Build a new LRU from the given maximum size and list of contents, in
--   order from most recently accessed to least recently accessed.
fromList :: (Ord key) => Int -> [(key, val)] -> LRU key val

-- | Retrieve a list view of an LRU. The items are returned in order from
--   most recently accessed to least recently accessed.
toList :: (Ord key) => LRU key val -> [(key, val)]

-- | Add an item to an LRU. If the key was already present in the LRU, the
--   value is changed to the new value passed in. The item added is marked
--   as the most recently accessed item in the LRU returned.
--   
--   If this would cause the LRU to exceed its maximum size, the least
--   recently used item is dropped from the cache.
insert :: (Ord key) => key -> val -> LRU key val -> LRU key val

-- | Look up an item in an LRU. If it was present, it is marked as the most
--   recently accesed in the returned LRU.
lookup :: (Ord key) => key -> LRU key val -> (LRU key val, Maybe val)

-- | Remove an item from an LRU. Returns the new LRU, and if the item was
--   present to be removed.
delete :: (Ord key) => key -> LRU key val -> (LRU key val, Bool)

-- | Returns the number of elements the LRU currently contains.
size :: LRU key val -> Int

-- | Internal function. The key passed in must be present in the LRU. Moves
--   the item associated with that key to the most recently accessed
--   position.
hit' :: (Ord key) => key -> LRU key val -> LRU key val

-- | Internal function. This checks the three structural invariants of the
--   LRU cache structure:
--   
--   <ol>
--   <li>The cache's size does not exceed the specified max size.</li>
--   <li>The linked list through the nodes is consistent in both
--   directions.</li>
--   <li>The linked list contains the same number of nodes as the
--   cache.</li>
--   </ol>
valid :: (Ord key) => LRU key val -> Bool


-- | Implements an LRU cache.
--   
--   This module provides a pure LRU cache based on a doubly-linked list
--   through a Data.Map structure. This gives O(log n) operations on
--   <a>insert</a> and <a>lookup</a>, and O(n) for <a>toList</a>.
--   
--   The interface this module provides is opaque. If further control is
--   desired, the <a>Data.Cache.LRU.Internal</a> module can be used.
module Data.Cache.LRU

-- | Stores the information that makes up an LRU cache
data LRU key val

-- | Make an LRU. The LRU is guaranteed to not grow above the specified
--   number of entries.
newLRU :: (Ord key) => Int -> LRU key val

-- | Build a new LRU from the given maximum size and list of contents, in
--   order from most recently accessed to least recently accessed.
fromList :: (Ord key) => Int -> [(key, val)] -> LRU key val

-- | Retrieve a list view of an LRU. The items are returned in order from
--   most recently accessed to least recently accessed.
toList :: (Ord key) => LRU key val -> [(key, val)]

-- | the maximum size of the LRU cache
maxSize :: LRU key val -> Int

-- | Add an item to an LRU. If the key was already present in the LRU, the
--   value is changed to the new value passed in. The item added is marked
--   as the most recently accessed item in the LRU returned.
--   
--   If this would cause the LRU to exceed its maximum size, the least
--   recently used item is dropped from the cache.
insert :: (Ord key) => key -> val -> LRU key val -> LRU key val

-- | Look up an item in an LRU. If it was present, it is marked as the most
--   recently accesed in the returned LRU.
lookup :: (Ord key) => key -> LRU key val -> (LRU key val, Maybe val)

-- | Remove an item from an LRU. Returns the new LRU, and if the item was
--   present to be removed.
delete :: (Ord key) => key -> LRU key val -> (LRU key val, Bool)

-- | Returns the number of elements the LRU currently contains.
size :: LRU key val -> Int


-- | This module contains a mutable wrapping of an LRU in the IO monad,
--   providing atomic access in a concurrent environment. All calls
--   preserve the same semantics as those in <a>Data.Cache.LRU</a>, but
--   perform updates in place.
--   
--   (This implementation uses an MVar for coarse locking. It's unclear if
--   anything else would give better performance, given that many calls
--   alter the head of the access list.)
module Data.Cache.LRU.IO

-- | The opaque wrapper type
data AtomicLRU key val

-- | Make a new AtomicLRU with the given maximum size.
newAtomicLRU :: (Ord key) => Int -> IO (AtomicLRU key val)

-- | Build a new LRU from the given maximum size and list of contents. See
--   <a>fromList</a> for the semantics.
fromList :: (Ord key) => Int -> [(key, val)] -> IO (AtomicLRU key val)

-- | Retreive a list view of an AtomicLRU. See <a>toList</a> for the
--   semantics.
toList :: (Ord key) => AtomicLRU key val -> IO [(key, val)]
maxSize :: AtomicLRU key val -> IO Int

-- | Insert a key/value pair into an AtomicLRU. See <a>insert</a> for the
--   semantics.
insert :: (Ord key) => key -> val -> AtomicLRU key val -> IO ()

-- | Look up a key in an AtomicLRU. See <a>lookup</a> for the semantics.
lookup :: (Ord key) => key -> AtomicLRU key val -> IO (Maybe val)

-- | Remove an item from an AtomicLRU. Returns whether the item was present
--   to be removed.
delete :: (Ord key) => key -> AtomicLRU key val -> IO Bool

-- | Returns the number of elements the AtomicLRU currently contains.
size :: AtomicLRU key val -> IO Int