-- 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 Data.Map.
--   
--   It also contains a mutable IO wrapper providing atomic updates to an
--   LRU cache.
@package lrucache
@version 1.2.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
--   valid 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
--   Data.Cache.LRU instead.
module Data.Cache.LRU.Internal

-- | Stores the information that makes up an LRU cache
data LRU key val
LRU :: !Maybe key -> !Maybe key -> !Maybe Integer -> !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 -> !Maybe Integer

-- | the backing Map
[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 Map.
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. If a size limit is specified, the LRU is guaranteed to
--   not grow above the specified number of entries.
newLRU :: Ord key => Maybe Integer -> 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 => Maybe Integer -> [(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)]

-- | Traverse the (key, value) pairs of the LRU, in a read-only way. This
--   is a Fold in the sense used by the lens package. It
--   must be read-only because alterations could break the underlying
--   Map structure.
pairs :: (Ord key, Applicative f, Contravariant f) => ((key, val) -> f (key, val)) -> LRU key val -> f (LRU key val)

-- | Traverse the keys of the LRU, in a read-only way. This is a
--   Fold in the sense used by the lens package. It must be
--   read-only because alterations could break the underlying Map
--   structure.
keys :: (Ord key, Applicative f, Contravariant f) => (key -> f key) -> LRU key val -> f (LRU 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

-- | Same as insert, but also returns element which was dropped from
--   cache, if any.
insertInforming :: Ord key => key -> val -> LRU key val -> (LRU key val, Maybe (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 the value removed
--   if the key was present.
delete :: Ord key => key -> LRU key val -> (LRU key val, Maybe val)

-- | Removes the least-recently accessed element from the LRU. Returns the
--   new LRU, and the key and value from the least-recently used element,
--   if there was one.
pop :: Ord key => LRU key val -> (LRU key val, Maybe (key, val))

-- | 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

-- | An internal function used by insert (when the cache is full)
--   and delete. This function has strict requirements on its
--   arguments in order to work properly.
--   
--   As this is intended to be an internal function, the arguments were
--   chosen to avoid repeated computation, rather than for simplicity of
--   calling this function.
delete' :: Ord key => key -> LRU key val -> Map key (LinkedVal key val) -> LinkedVal key val -> LRU key val

-- | Internal function. This is very similar to adjust, with two
--   major differences. First, it's strict in the application of the
--   function, which is a huge win when working with this structure.
--   
--   Second, it requires that the key be present in order to work. If the
--   key isn't present, undefined will be inserted into the
--   Map, which will cause problems later.
adjust' :: Ord k => (a -> a) -> k -> Map k a -> Map k a

-- | Internal function. This checks the four structural invariants of the
--   LRU cache structure:
--   
--   
--   
- The cache's size does not exceed the specified max size.
--   
- The linked list through the nodes is consistent in both
--   directions.
--   
- The linked list contains the same number of nodes as the
--   cache.
--   
- Every key in the linked list is in the Map.
--   
valid :: Ord key => LRU key val -> Bool
instance (GHC.Internal.Data.Data.Data key, GHC.Internal.Data.Data.Data val, GHC.Classes.Ord key) => GHC.Internal.Data.Data.Data (Data.Cache.LRU.Internal.LRU key val)
instance (GHC.Internal.Data.Data.Data key, GHC.Internal.Data.Data.Data val) => GHC.Internal.Data.Data.Data (Data.Cache.LRU.Internal.LinkedVal key val)
instance (GHC.Classes.Eq key, GHC.Classes.Eq val) => GHC.Classes.Eq (Data.Cache.LRU.Internal.LRU key val)
instance (GHC.Classes.Eq val, GHC.Classes.Eq key) => GHC.Classes.Eq (Data.Cache.LRU.Internal.LinkedVal key val)
instance GHC.Classes.Ord key => GHC.Internal.Data.Foldable.Foldable (Data.Cache.LRU.Internal.LRU key)
instance GHC.Internal.Data.Foldable.Foldable (Data.Cache.LRU.Internal.LinkedVal key)
instance GHC.Internal.Base.Functor (Data.Cache.LRU.Internal.LRU key)
instance GHC.Internal.Base.Functor (Data.Cache.LRU.Internal.LinkedVal key)
instance (GHC.Classes.Ord key, GHC.Internal.Show.Show key, GHC.Internal.Show.Show val) => GHC.Internal.Show.Show (Data.Cache.LRU.Internal.LRU key val)
instance GHC.Classes.Ord key => GHC.Internal.Data.Traversable.Traversable (Data.Cache.LRU.Internal.LRU key)
instance GHC.Internal.Data.Traversable.Traversable (Data.Cache.LRU.Internal.LinkedVal key)

-- | 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
--   insert, lookup, delete, and pop, and O(n *
--   log n) for toList.
--   
--   The interface this module provides is opaque. If further control is
--   desired, the Data.Cache.LRU.Internal module can be used.
module Data.Cache.LRU

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

-- | Make an LRU. If a size limit is specified, the LRU is guaranteed to
--   not grow above the specified number of entries.
newLRU :: Ord key => Maybe Integer -> 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 => Maybe Integer -> [(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)]

-- | Traverse the (key, value) pairs of the LRU, in a read-only way. This
--   is a Fold in the sense used by the lens package. It
--   must be read-only because alterations could break the underlying
--   Map structure.
pairs :: (Ord key, Applicative f, Contravariant f) => ((key, val) -> f (key, val)) -> LRU key val -> f (LRU key val)

-- | Traverse the keys of the LRU, in a read-only way. This is a
--   Fold in the sense used by the lens package. It must be
--   read-only because alterations could break the underlying Map
--   structure.
keys :: (Ord key, Applicative f, Contravariant f) => (key -> f key) -> LRU key val -> f (LRU key val)

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

-- | 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

-- | Same as insert, but also returns element which was dropped from
--   cache, if any.
insertInforming :: Ord key => key -> val -> LRU key val -> (LRU key val, Maybe (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 the value removed
--   if the key was present.
delete :: Ord key => key -> LRU key val -> (LRU key val, Maybe val)

-- | Removes the least-recently accessed element from the LRU. Returns the
--   new LRU, and the key and value from the least-recently used element,
--   if there was one.
pop :: Ord key => LRU key val -> (LRU key val, Maybe (key, val))

-- | 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 Data.Cache.LRU, but
--   perform updates in place.
--   
--   This module contains the internal implementation details. It's
--   possible to put an AtomicLRU into a bad state with this module.
--   It is highly recommended that the external interface,
--   Data.Cache.LRU.IO, be used instead.
module Data.Cache.LRU.IO.Internal

-- | The opaque wrapper type
newtype AtomicLRU key val
C :: MVar (LRU key val) -> AtomicLRU key val

-- | Make a new AtomicLRU that will not grow beyond the optional maximum
--   size, if specified.
newAtomicLRU :: Ord key => Maybe Integer -> IO (AtomicLRU key val)

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

-- | Retrieve a list view of an AtomicLRU. See toList for the
--   semantics.
toList :: Ord key => AtomicLRU key val -> IO [(key, val)]
maxSize :: AtomicLRU key val -> IO (Maybe Integer)

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

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

-- | Remove an item from an AtomicLRU. Returns the value for the removed
--   key, if it was present
delete :: Ord key => key -> AtomicLRU key val -> IO (Maybe val)

-- | Remove the least-recently accessed item from an AtomicLRU. Returns the
--   (key, val) pair removed, if one was present.
pop :: Ord key => AtomicLRU key val -> IO (Maybe (key, val))

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

-- | Given a function that takes an LRU and returns one of the same
--   type, use it to modify the contents of this AtomicLRU.
modifyAtomicLRU :: (LRU key val -> LRU key val) -> AtomicLRU key val -> IO ()

-- | Given a function that takes an LRU and returns an IO action
--   producting one of the same type, use it to modify the contents of this
--   AtomicLRU.
modifyAtomicLRU' :: (LRU key val -> IO (LRU key val)) -> AtomicLRU key val -> IO ()

-- | A version of modifyMVar_ that forces the result of the function
--   application to WHNF.
modifyMVar_' :: MVar a -> (a -> IO a) -> IO ()

-- | A version of modifyMVar that forces the result of the function
--   application to WHNF.
modifyMVar' :: MVar a -> (a -> IO (a, b)) -> IO b

-- | 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 Data.Cache.LRU, but
--   perform updates in place. All functions use a single atomic update of
--   the backing structure.
--   
--   The interface this module provides is opaque. If further control is
--   desired, the Data.Cache.LRU.IO.Internal module can be used in
--   combination with Data.Cache.LRU.Internal.
--   
--   (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 that will not grow beyond the optional maximum
--   size, if specified.
newAtomicLRU :: Ord key => Maybe Integer -> IO (AtomicLRU key val)

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

-- | Retrieve a list view of an AtomicLRU. See toList for the
--   semantics.
toList :: Ord key => AtomicLRU key val -> IO [(key, val)]
maxSize :: AtomicLRU key val -> IO (Maybe Integer)

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

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

-- | Remove an item from an AtomicLRU. Returns the value for the removed
--   key, if it was present
delete :: Ord key => key -> AtomicLRU key val -> IO (Maybe val)

-- | Remove the least-recently accessed item from an AtomicLRU. Returns the
--   (key, val) pair removed, if one was present.
pop :: Ord key => AtomicLRU key val -> IO (Maybe (key, val))

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

-- | Given a function that takes an LRU and returns one of the same
--   type, use it to modify the contents of this AtomicLRU.
modifyAtomicLRU :: (LRU key val -> LRU key val) -> AtomicLRU key val -> IO ()

-- | Given a function that takes an LRU and returns an IO action
--   producting one of the same type, use it to modify the contents of this
--   AtomicLRU.
modifyAtomicLRU' :: (LRU key val -> IO (LRU key val)) -> AtomicLRU key val -> IO ()
