{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE CPP          #-}

-- | This module contains a 'HashTable' typeclass for the hash table
-- implementations in this package. This allows you to provide functions which
-- will work for any hash table implementation in this collection.
--
-- It is recommended to create a concrete type alias in your code when using this
-- package, i.e.:
--
-- > import qualified Data.HashTable.IO as H
-- >
-- > type HashTable k v = H.BasicHashTable k v
-- >
-- > foo :: IO (HashTable Int Int)
-- > foo = do
-- >     ht <- H.new
-- >     H.insert ht 1 1
-- >     return ht
--
-- or
--
-- > import qualified Data.HashTable.ST.Cuckoo as C
-- > import qualified Data.HashTable.Class as H
-- >
-- > type HashTable s k v = C.HashTable s k v
-- >
-- > foo :: ST s (HashTable s k v)
-- > foo = do
-- >     ht <- H.new
-- >     H.insert ht 1 1
-- >     return ht
--
-- Firstly, this makes it easy to switch to a different hash table
-- implementation, and secondly, using a concrete type rather than leaving your
-- functions abstract in the 'HashTable' class should allow GHC to optimize
-- away the typeclass dictionaries.
--
-- Note that the functions in this typeclass are in the 'ST' monad; if you want
-- hash tables in 'IO', use the convenience wrappers in "Data.HashTable.IO".
--
module Data.HashTable.Class
  ( HashTable(..)
  , fromList
  , fromListWithSizeHint
  , toList
  ) where

#if !MIN_VERSION_base(4,8,0)
import           Control.Applicative
import           Data.Word           (Word)
#endif
import           Control.Monad.ST
import           Data.Hashable
import           Prelude             hiding (mapM_)

-- | A typeclass for hash tables in the 'ST' monad. The operations on these
-- hash tables are typically both key- and value-strict.
class HashTable h where
    -- | Creates a new, default-sized hash table. /O(1)/.
    new      :: ST s (h s k v)

    -- | Creates a new hash table sized to hold @n@ elements. /O(n)/.
    newSized :: Int -> ST s (h s k v)

    -- | Generalized update. Given a key /k/, and a user function /f/, calls:
    --
    --   - `f Nothing` if the key did not exist in the hash table
    --   - `f (Just v)` otherwise
    --
    -- If the user function returns @(Nothing, _)@, then the value is deleted
    -- from the hash table. Otherwise the mapping for /k/ is inserted or
    -- replaced with the provided value.
    --
    -- Returns the second part of the tuple returned by /f/.
    mutate :: (Eq k, Hashable k) =>
              h s k v -> k -> (Maybe v -> (Maybe v, a)) -> ST s a
    mutate h s k v
tbl k
k Maybe v -> (Maybe v, a)
f = h s k v -> k -> (Maybe v -> ST s (Maybe v, a)) -> ST s a
forall (h :: * -> * -> * -> *) k s v a.
(HashTable h, Eq k, Hashable k) =>
h s k v -> k -> (Maybe v -> ST s (Maybe v, a)) -> ST s a
mutateST h s k v
tbl k
k ((Maybe v, a) -> ST s (Maybe v, a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure ((Maybe v, a) -> ST s (Maybe v, a))
-> (Maybe v -> (Maybe v, a)) -> Maybe v -> ST s (Maybe v, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe v -> (Maybe v, a)
f)

    -- | As 'mutate', except that the action can perform additional side
    -- effects.
    mutateST :: (Eq k, Hashable k) =>
                h s k v -> k -> (Maybe v -> ST s (Maybe v, a)) -> ST s a

    -- | Inserts a key/value mapping into a hash table, replacing any existing
    -- mapping for that key.
    --
    -- /O(n)/ worst case, /O(1)/ amortized.
    insert   :: (Eq k, Hashable k) => h s k v -> k -> v -> ST s ()

    -- | Deletes a key-value mapping from a hash table. /O(n)/ worst case,
    -- /O(1)/ amortized.
    delete   :: (Eq k, Hashable k) => h s k v -> k -> ST s ()

    -- | Looks up a key-value mapping in a hash table. /O(n)/ worst case,
    -- (/O(1)/ for cuckoo hash), /O(1)/ amortized.
    lookup   :: (Eq k, Hashable k) => h s k v -> k -> ST s (Maybe v)

    -- | A strict fold over the key-value records of a hash table in the 'ST'
    -- monad. /O(n)/.
    foldM    :: (a -> (k,v) -> ST s a) -> a -> h s k v -> ST s a

    -- | A side-effecting map over the key-value records of a hash
    -- table. /O(n)/.
    mapM_    :: ((k,v) -> ST s b) -> h s k v -> ST s ()

    -- | Looks up the index of a key-value mapping in a hash table suitable
    -- for passing to 'nextByIndex'.
    lookupIndex :: (Eq k, Hashable k) => h s k v -> k -> ST s (Maybe Word)

    -- | Returns the next key-value mapping stored at the given index or at
    -- a greater index. The index, key, and value of the next record are
    -- returned.
    nextByIndex :: h s k v -> Word -> ST s (Maybe (Word,k,v))

    -- | Computes the overhead (in words) per key-value mapping. Used for
    -- debugging, etc; time complexity depends on the underlying hash table
    -- implementation. /O(n)/.
    computeOverhead :: h s k v -> ST s Double


------------------------------------------------------------------------------
-- | Create a hash table from a list of key-value pairs. /O(n)/.
fromList :: (HashTable h, Eq k, Hashable k) => [(k,v)] -> ST s (h s k v)
fromList :: [(k, v)] -> ST s (h s k v)
fromList [(k, v)]
l = do
    h s k v
ht <- ST s (h s k v)
forall (h :: * -> * -> * -> *) s k v. HashTable h => ST s (h s k v)
new
    h s k v -> [(k, v)] -> ST s (h s k v)
forall (h :: * -> * -> * -> *) k s v.
(HashTable h, Hashable k) =>
h s k v -> [(k, v)] -> ST s (h s k v)
go h s k v
ht [(k, v)]
l

  where
    go :: h s k v -> [(k, v)] -> ST s (h s k v)
go h s k v
ht = [(k, v)] -> ST s (h s k v)
go'
      where
        go' :: [(k, v)] -> ST s (h s k v)
go' [] = h s k v -> ST s (h s k v)
forall (m :: * -> *) a. Monad m => a -> m a
return h s k v
ht
        go' ((!k
k,!v
v):[(k, v)]
xs) = do
            h s k v -> k -> v -> ST s ()
forall (h :: * -> * -> * -> *) k s v.
(HashTable h, Eq k, Hashable k) =>
h s k v -> k -> v -> ST s ()
insert h s k v
ht k
k v
v
            [(k, v)] -> ST s (h s k v)
go' [(k, v)]
xs
{-# INLINE fromList #-}


------------------------------------------------------------------------------
-- | Create a hash table from a list of key-value pairs, with a size hint. /O(n)/.
fromListWithSizeHint :: (HashTable h, Eq k, Hashable k) =>
                        Int
                     -> [(k,v)]
                     -> ST s (h s k v)
fromListWithSizeHint :: Int -> [(k, v)] -> ST s (h s k v)
fromListWithSizeHint Int
n [(k, v)]
l = do
    h s k v
ht <- Int -> ST s (h s k v)
forall (h :: * -> * -> * -> *) s k v.
HashTable h =>
Int -> ST s (h s k v)
newSized Int
n
    h s k v -> [(k, v)] -> ST s (h s k v)
forall (h :: * -> * -> * -> *) k s v.
(HashTable h, Hashable k) =>
h s k v -> [(k, v)] -> ST s (h s k v)
go h s k v
ht [(k, v)]
l

  where
    go :: h s k v -> [(k, v)] -> ST s (h s k v)
go h s k v
ht = [(k, v)] -> ST s (h s k v)
go'
      where
        go' :: [(k, v)] -> ST s (h s k v)
go' [] = h s k v -> ST s (h s k v)
forall (m :: * -> *) a. Monad m => a -> m a
return h s k v
ht
        go' ((!k
k,!v
v):[(k, v)]
xs) = do
            h s k v -> k -> v -> ST s ()
forall (h :: * -> * -> * -> *) k s v.
(HashTable h, Eq k, Hashable k) =>
h s k v -> k -> v -> ST s ()
insert h s k v
ht k
k v
v
            [(k, v)] -> ST s (h s k v)
go' [(k, v)]
xs
{-# INLINE fromListWithSizeHint #-}


------------------------------------------------------------------------------
-- | Given a hash table, produce a list of key-value pairs. /O(n)/.
toList :: (HashTable h) => h s k v -> ST s [(k,v)]
toList :: h s k v -> ST s [(k, v)]
toList h s k v
ht = do
    [(k, v)]
l <- ([(k, v)] -> (k, v) -> ST s [(k, v)])
-> [(k, v)] -> h s k v -> ST s [(k, v)]
forall (h :: * -> * -> * -> *) a k v s.
HashTable h =>
(a -> (k, v) -> ST s a) -> a -> h s k v -> ST s a
foldM [(k, v)] -> (k, v) -> ST s [(k, v)]
forall (m :: * -> *) a. Monad m => [a] -> a -> m [a]
f [] h s k v
ht
    [(k, v)] -> ST s [(k, v)]
forall (m :: * -> *) a. Monad m => a -> m a
return [(k, v)]
l

  where
    f :: [a] -> a -> m [a]
f ![a]
l !a
t = [a] -> m [a]
forall (m :: * -> *) a. Monad m => a -> m a
return (a
ta -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
l)
{-# INLINE toList #-}