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


-- | Efficient vector-based mutable hashtables implementation.
--   
--   This package provides efficient vector-based hashtable implementation
--   similar to .NET Generic Dictionary implementation (at the time of
--   2015).
--   
--   See <a>Data.Vector.Hashtables</a> for documentation.
@package vector-hashtables
@version 0.1.2.0


module Data.Primitive.PrimArray.Utils
replicate :: (PrimMonad m, Prim a) => Int -> a -> m (MutablePrimArray (PrimState m) a)
clone :: (PrimMonad m, Prim a) => MutablePrimArray (PrimState m) a -> m (MutablePrimArray (PrimState m) a)
unsafeFreeze :: PrimMonad m => MutablePrimArray (PrimState m) a -> m (PrimArray a)
unsafeThaw :: PrimMonad m => PrimArray a -> m (MutablePrimArray (PrimState m) a)
growWith :: (PrimMonad m, Prim a) => a -> MutablePrimArray (PrimState m) a -> Int -> m (MutablePrimArray (PrimState m) a)
growNoZ :: (PrimMonad m, Prim a) => MutablePrimArray (PrimState m) a -> Int -> m (MutablePrimArray (PrimState m) a)
freeze :: (PrimMonad m, Prim a) => MutablePrimArray (PrimState m) a -> m (PrimArray a)
length :: (PrimMonad m, Prim a) => MutablePrimArray (PrimState m) a -> m Int


module Data.Vector.Hashtables.Internal.Mask

-- | <a>Int</a> mask. For 32-bit it is equal to <tt>0x7FFFFFFF</tt>.
--   Otherwise, <tt>0x7FFFFFFFFFFFFFFF</tt>.
mask :: Int


module Data.Vector.Hashtables.Internal

-- | Alias for <tt>MutablePrimArray</tt> <tt>s</tt> <a>Int</a>.
type IntArray s = MutablePrimArray s Int

-- | Single-element mutable array of <a>Dictionary_</a> with primitive
--   state token parameterized with state, keys and values types.
--   
--   Different flavors of <a>MVector</a> could be used for keys and values.
--   It's preferable to use <a>Data.Vector.Unboxed.Mutable</a> or
--   <a>Data.Vector.Storable.Mutable</a> if possible. Otherwise, if you
--   must use boxed vectors, consider employing strict ones from
--   <a><tt>strict-containers</tt></a> to eliminate potential accumulation
--   of thunks.
--   
--   <h4>Example</h4>
--   
--   <pre>
--   &gt;&gt;&gt; import qualified Data.Vector.Storable.Mutable as VM
--   
--   &gt;&gt;&gt; import qualified Data.Vector.Unboxed.Mutable  as UM
--   
--   &gt;&gt;&gt; import Data.Vector.Hashtables
--   
--   &gt;&gt;&gt; type HashTable k v = Dictionary (PrimState IO) VM.MVector k UM.MVector v
--   </pre>
newtype Dictionary s ks k vs v
DRef :: MutVar s (Dictionary_ s ks k vs v) -> Dictionary s ks k vs v
[getDRef] :: Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)

-- | Represents collection of hashtable internal primitive arrays and
--   vectors.
--   
--   <ul>
--   <li>hash codes,</li>
--   <li>references to the next element,</li>
--   <li>buckets,</li>
--   <li>keys</li>
--   <li>and values.</li>
--   </ul>
data Dictionary_ s ks k vs v
Dictionary :: !IntArray s -> !ks s k -> !vs s v -> {-# UNPACK #-} !FastRem -> Dictionary_ s ks k vs v
[hashCode, next, buckets, refs] :: Dictionary_ s ks k vs v -> !IntArray s
[key] :: Dictionary_ s ks k vs v -> !ks s k
[value] :: Dictionary_ s ks k vs v -> !vs s v
[remSize] :: Dictionary_ s ks k vs v -> {-# UNPACK #-} !FastRem
getCount :: Int
getFreeList :: Int
getFreeCount :: Int

-- | Represents immutable dictionary as collection of immutable arrays and
--   vectors. See <a>unsafeFreeze</a> and <a>unsafeThaw</a> for conversions
--   from/to mutable dictionary.
data FrozenDictionary ks k vs v
FrozenDictionary :: !PrimArray Int -> !Int -> !ks k -> !vs v -> {-# UNPACK #-} !FastRem -> FrozenDictionary ks k vs v
[fhashCode, fnext, fbuckets] :: FrozenDictionary ks k vs v -> !PrimArray Int
[count, freeList, freeCount] :: FrozenDictionary ks k vs v -> !Int
[fkey] :: FrozenDictionary ks k vs v -> !ks k
[fvalue] :: FrozenDictionary ks k vs v -> !vs v
[fremSize] :: FrozenDictionary ks k vs v -> {-# UNPACK #-} !FastRem

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Find
--   dictionary entry by given key in immutable <a>FrozenDictionary</a>. If
--   entry not found <tt>-1</tt> returned.
findElem :: (Vector ks k, Vector vs v, Hashable k, Eq k) => FrozenDictionary ks k vs v -> k -> Int

-- | Infix version of <tt>unsafeRead</tt>.
(!~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> m a

-- | Infix version of <tt>unsafeIndex</tt>.
(!.~) :: Vector v a => v a -> Int -> a

-- | Infix version of <tt>unsafeWrite</tt>.
(<~~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> a -> m ()

-- | Infix version of <tt>readPrimArray</tt>.
(!) :: PrimMonad m => MutablePrimArray (PrimState m) Int -> Int -> m Int

-- | Infix version of <tt>indexPrimArray</tt>.
(!.) :: PrimArray Int -> Int -> Int

-- | Infix version of <tt>writePrimArray</tt>.
(<~) :: PrimMonad m => MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()

-- | <i>O(1)</i> Dictionary with given capacity.
initialize :: (MVector ks k, MVector vs v, PrimMonad m) => Int -> m (Dictionary (PrimState m) ks k vs v)

-- | Create a copy of mutable dictionary.
clone :: (MVector ks k, MVector vs v, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(1)</i> Unsafe convert a mutable dictionary to an immutable one
--   without copying. The mutable dictionary may not be used after this
--   operation.
unsafeFreeze :: (Vector ks k, Vector vs v, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v -> m (FrozenDictionary ks k vs v)

-- | <i>O(1)</i> Unsafely convert immutable <a>FrozenDictionary</a> to a
--   mutable <a>Dictionary</a> without copying. The immutable dictionary
--   may not be used after this operation.
unsafeThaw :: (Vector ks k, Vector vs v, PrimMonad m) => FrozenDictionary ks k vs v -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)

-- | <i>O(n)</i> Retrieve list of keys from <a>Dictionary</a>.
keys :: (Vector ks k, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k vs v -> m (ks k)

-- | <i>O(n)</i> Retrieve list of values from <a>Dictionary</a>.
values :: (Vector vs v, PrimMonad m) => Dictionary (PrimState m) ks k (Mutable vs) v -> m (vs v)

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Find
--   value by given key in <a>Dictionary</a>. Throws an error if value not
--   found.
at :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Find
--   value by given key in <a>Dictionary</a>. Like <a>at'</a> but return
--   <a>Nothing</a> if value not found.
at' :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
atWithOrElse :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> (Dictionary (PrimState m) ks k vs v -> Int -> m a) -> (Dictionary (PrimState m) ks k vs v -> m a) -> m a

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Find
--   dictionary entry by given key. If entry not found <tt>-1</tt>
--   returned.
findEntry :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m Int

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Same as
--   <a>findEntry</a>, but for <a>Dictionary_</a>.
findEntry_ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary_ (PrimState m) ks k vs v -> k -> m Int

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Insert
--   key and value in dictionary by key's hash. If entry with given key
--   found value will be replaced.
insert :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
insertWithIndex :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Int -> Int -> k -> v -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v) -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
addOrResize :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Int -> Int -> k -> v -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v) -> Dictionary_ (PrimState m) ks k vs v -> m ()
add :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Int -> Int -> Int -> k -> v -> Dictionary_ (PrimState m) ks k vs v -> m ()
resize :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary_ (PrimState m) ks k vs v -> Int -> Int -> k -> v -> m (Dictionary_ (PrimState m) ks k vs v)
class DeleteEntry xs
deleteEntry :: (DeleteEntry xs, MVector xs x, PrimMonad m) => xs (PrimState m) x -> Int -> m ()

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Delete
--   entry from <a>Dictionary</a> by given key.
delete :: (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs) => Dictionary (PrimState m) ks k vs v -> k -> m ()
deleteWithIndex :: (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs) => Int -> Int -> Dictionary_ (PrimState m) ks k vs v -> k -> Int -> Int -> m ()

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Find
--   value by given key in <a>Dictionary</a>. Like <a>lookup'</a> but
--   return <a>Nothing</a> if value not found.
lookup :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Find
--   value by given key in <a>Dictionary</a>. Throws an error if value not
--   found.
lookup' :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Lookup
--   the index of a key, which is its zero-based index in the sequence
--   sorted by keys. The index is a number from 0 up to, but not including,
--   the size of the dictionary.
lookupIndex :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe Int)

-- | <i>O(1)</i> Return <a>True</a> if dictionary is empty, <a>False</a>
--   otherwise.
null :: (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Bool

-- | <i>O(1)</i> Return the number of non-empty entries of dictionary.
length :: (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int

-- | <i>O(1)</i> Return the number of non-empty entries of dictionary.
--   Synonym of <a>length</a>.
size :: (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Return
--   <a>True</a> if the specified key is present in the dictionary,
--   <a>False</a> otherwise.
member :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m Bool

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. The
--   expression <tt><a>findWithDefault</a> ht def k</tt> returns the value
--   at key <tt>k</tt> or returns default value <tt>def</tt> when the key
--   is not in the dictionary.
findWithDefault :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> v -> k -> m v

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. The
--   expression (<tt><a>upsert</a> ht f k</tt>) updates or inserts the
--   value <tt>x</tt> at <tt>k</tt>.
--   
--   It's a responsibility of <a>MVector</a> <tt>vs</tt> to force
--   evaluation of the updated value. Unboxed / storable vectors do it
--   automatically. If you use boxed vectors, consider employing strict
--   ones from <a><tt>strict-containers</tt></a> to eliminate potential
--   accumulation of thunks.
--   
--   <pre>
--   let f _ = "c"
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   upsert ht f 7
--   toList ht
--   [(3, "b"), (5, "a"), (7, "c")]
--   </pre>
--   
--   <pre>
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   upsert ht f 5
--   toList ht
--   [(3, "b"), (5, "c")]
--   </pre>
upsert :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> v) -> k -> m ()

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. The
--   expression (<tt><a>alter</a> ht f k</tt>) alters the value <tt>x</tt>
--   at <tt>k</tt>, or absence thereof. <a>alter</a> can be used to insert,
--   delete, or update a value in a <a>Dictionary</a>.
--   
--   It's a responsibility of <a>MVector</a> <tt>vs</tt> to force
--   evaluation of the updated value. Unboxed / storable vectors do it
--   automatically. If you use boxed vectors, consider employing strict
--   ones from <a><tt>strict-containers</tt></a> to eliminate potential
--   accumulation of thunks.
--   
--   <pre>
--   let f _ = Nothing
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   alter ht f 7
--   toList ht
--   [(3, "b"), (5, "a")]
--   </pre>
--   
--   <pre>
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   alter ht f 5
--   toList ht
--   [(3 "b")]
--   </pre>
--   
--   <pre>
--   let f _ = Just "c"
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   alter ht f 7
--   toList ht
--   [(3, "b"), (5, "a"), (7, "c")]
--   </pre>
--   
--   <pre>
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   alter ht f 5
--   toList ht
--   [(3, "b"), (5, "c")]
--   </pre>
alter :: (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> Maybe v) -> k -> m ()

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. The
--   expression (<tt><a>alterM</a> ht f k</tt>) alters the value <tt>x</tt>
--   at <tt>k</tt>, or absence thereof. <a>alterM</a> can be used to
--   insert, delete, or update a value in a <a>Dictionary</a> in the same
--   <tt><a>PrimMonad</a> m</tt>.
alterM :: (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> m (Maybe v)) -> k -> m ()

-- | <i>O(min n m)</i> in the best case, <i>O(min n m * max n m)</i> in the
--   worst case. The union of two maps. If a key occurs in both maps, the
--   mapping from the first will be the mapping in the result.
union :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(min n m)</i> in the best case, <i>O(min n m * max n m)</i> in the
--   worst case. The union of two maps. The provided function (first
--   argument) will be used to compute the result.
unionWith :: (MVector ks k, MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(min n m)</i> in the best case, <i>O(min n m * max n m)</i> in the
--   worst case. The union of two maps. If a key occurs in both maps, the
--   provided function (first argument) will be used to compute the result.
unionWithKey :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (k -> v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(n)</i> in the best case, <i>O(n * m)</i> in the worst case.
--   Difference of two tables. Return elements of the first table not
--   existing in the second.
difference :: (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(n)</i> in the best case, <i>O(n * m)</i> in the worst case.
--   Difference with a combining function. When two equal keys are
--   encountered, the combining function is applied to the values of these
--   keys. If it returns <a>Nothing</a>, the element is discarded (proper
--   set difference). If it returns (<tt><a>Just</a> y</tt>), the element
--   is updated with a new value <tt>y</tt>.
differenceWith :: (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => (v -> w -> Maybe v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(n)</i> in the best case, <i>O(n * m)</i> in the worst case.
--   Intersection of two maps. Return elements of the first map for keys
--   existing in the second.
intersection :: (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)

-- | Intersection of two maps. If a key occurs in both maps the provided
--   function is used to combine the values from the two maps.
intersectionWith :: (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3)

-- | Intersection of two maps. If a key occurs in both maps the provided
--   function is used to combine the values from the two maps.
intersectionWithKey :: (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (k -> v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3)

-- | <i>O(n)</i> Convert list to a <a>Dictionary</a>.
fromList :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => [(k, v)] -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(n)</i> Convert <a>Dictionary</a> to a list.
toList :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> m [(k, v)]

-- | This data is auto-generated by GenPrimes.hs. The vector contains
--   tuples (p, m, s) such that p is prime and (assuming 64-bit
--   architecture) for every n &gt;= 0 it holds that n `<a>quot</a>` p = (n
--   * m) `<a>shiftR</a>` (64 + s), enabling faster computation of
--   remainders.
primesWithFastRem :: Vector (Int, Int, Int)
getFastRem :: Int -> FastRem

-- | For 64-bit architectures <a>frmPrime</a> is a prime number such that
--   for each <tt>n</tt> &gt;= 0 it holds that <tt>n</tt> `<a>quot</a>`
--   <a>frmPrime</a> = (n * <a>_frmMulHi</a>) `<a>shiftR</a>` (64 + s).
data FastRem
FastRem :: !Int -> !Int -> !Int -> FastRem
[frmPrime] :: FastRem -> !Int
[_frmMulHi] :: FastRem -> !Int
[_frmShift] :: FastRem -> !Int
fastRem :: Int -> FastRem -> Int
instance GHC.Show.Show Data.Vector.Hashtables.Internal.FastRem
instance GHC.Classes.Ord Data.Vector.Hashtables.Internal.FastRem
instance GHC.Classes.Eq Data.Vector.Hashtables.Internal.FastRem
instance (GHC.Show.Show (ks k), GHC.Show.Show (vs v)) => GHC.Show.Show (Data.Vector.Hashtables.Internal.FrozenDictionary ks k vs v)
instance (GHC.Classes.Ord (ks k), GHC.Classes.Ord (vs v)) => GHC.Classes.Ord (Data.Vector.Hashtables.Internal.FrozenDictionary ks k vs v)
instance (GHC.Classes.Eq (ks k), GHC.Classes.Eq (vs v)) => GHC.Classes.Eq (Data.Vector.Hashtables.Internal.FrozenDictionary ks k vs v)
instance Data.Vector.Hashtables.Internal.DeleteEntry Data.Vector.Storable.Mutable.MVector
instance Data.Vector.Hashtables.Internal.DeleteEntry Data.Vector.Unboxed.Base.MVector
instance Data.Vector.Hashtables.Internal.DeleteEntry Data.Vector.Mutable.MVector


module Data.Vector.Hashtables

-- | Single-element mutable array of <a>Dictionary_</a> with primitive
--   state token parameterized with state, keys and values types.
--   
--   Different flavors of <a>MVector</a> could be used for keys and values.
--   It's preferable to use <a>Data.Vector.Unboxed.Mutable</a> or
--   <a>Data.Vector.Storable.Mutable</a> if possible. Otherwise, if you
--   must use boxed vectors, consider employing strict ones from
--   <a><tt>strict-containers</tt></a> to eliminate potential accumulation
--   of thunks.
--   
--   <h4>Example</h4>
--   
--   <pre>
--   &gt;&gt;&gt; import qualified Data.Vector.Storable.Mutable as VM
--   
--   &gt;&gt;&gt; import qualified Data.Vector.Unboxed.Mutable  as UM
--   
--   &gt;&gt;&gt; import Data.Vector.Hashtables
--   
--   &gt;&gt;&gt; type HashTable k v = Dictionary (PrimState IO) VM.MVector k UM.MVector v
--   </pre>
newtype Dictionary s ks k vs v
DRef :: MutVar s (Dictionary_ s ks k vs v) -> Dictionary s ks k vs v
[getDRef] :: Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)

-- | Represents immutable dictionary as collection of immutable arrays and
--   vectors. See <a>unsafeFreeze</a> and <a>unsafeThaw</a> for conversions
--   from/to mutable dictionary.
data FrozenDictionary ks k vs v
FrozenDictionary :: !PrimArray Int -> !Int -> !ks k -> !vs v -> {-# UNPACK #-} !FastRem -> FrozenDictionary ks k vs v
[fhashCode, fnext, fbuckets] :: FrozenDictionary ks k vs v -> !PrimArray Int
[count, freeList, freeCount] :: FrozenDictionary ks k vs v -> !Int
[fkey] :: FrozenDictionary ks k vs v -> !ks k
[fvalue] :: FrozenDictionary ks k vs v -> !vs v
[fremSize] :: FrozenDictionary ks k vs v -> {-# UNPACK #-} !FastRem

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Find
--   dictionary entry by given key in immutable <a>FrozenDictionary</a>. If
--   entry not found <tt>-1</tt> returned.
findElem :: (Vector ks k, Vector vs v, Hashable k, Eq k) => FrozenDictionary ks k vs v -> k -> Int

-- | <i>O(1)</i> Dictionary with given capacity.
initialize :: (MVector ks k, MVector vs v, PrimMonad m) => Int -> m (Dictionary (PrimState m) ks k vs v)

-- | Create a copy of mutable dictionary.
clone :: (MVector ks k, MVector vs v, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(1)</i> Return <a>True</a> if dictionary is empty, <a>False</a>
--   otherwise.
null :: (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Bool

-- | <i>O(1)</i> Return the number of non-empty entries of dictionary.
--   Synonym of <a>length</a>.
size :: (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int

-- | <i>O(n)</i> Retrieve list of keys from <a>Dictionary</a>.
keys :: (Vector ks k, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k vs v -> m (ks k)

-- | <i>O(n)</i> Retrieve list of values from <a>Dictionary</a>.
values :: (Vector vs v, PrimMonad m) => Dictionary (PrimState m) ks k (Mutable vs) v -> m (vs v)

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Find
--   value by given key in <a>Dictionary</a>. Like <a>lookup'</a> but
--   return <a>Nothing</a> if value not found.
lookup :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Find
--   value by given key in <a>Dictionary</a>. Throws an error if value not
--   found.
lookup' :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Insert
--   key and value in dictionary by key's hash. If entry with given key
--   found value will be replaced.
insert :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> v -> m ()

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Delete
--   entry from <a>Dictionary</a> by given key.
delete :: (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs) => Dictionary (PrimState m) ks k vs v -> k -> m ()

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. The
--   expression (<tt><a>upsert</a> ht f k</tt>) updates or inserts the
--   value <tt>x</tt> at <tt>k</tt>.
--   
--   It's a responsibility of <a>MVector</a> <tt>vs</tt> to force
--   evaluation of the updated value. Unboxed / storable vectors do it
--   automatically. If you use boxed vectors, consider employing strict
--   ones from <a><tt>strict-containers</tt></a> to eliminate potential
--   accumulation of thunks.
--   
--   <pre>
--   let f _ = "c"
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   upsert ht f 7
--   toList ht
--   [(3, "b"), (5, "a"), (7, "c")]
--   </pre>
--   
--   <pre>
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   upsert ht f 5
--   toList ht
--   [(3, "b"), (5, "c")]
--   </pre>
upsert :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> v) -> k -> m ()

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. The
--   expression (<tt><a>alter</a> ht f k</tt>) alters the value <tt>x</tt>
--   at <tt>k</tt>, or absence thereof. <a>alter</a> can be used to insert,
--   delete, or update a value in a <a>Dictionary</a>.
--   
--   It's a responsibility of <a>MVector</a> <tt>vs</tt> to force
--   evaluation of the updated value. Unboxed / storable vectors do it
--   automatically. If you use boxed vectors, consider employing strict
--   ones from <a><tt>strict-containers</tt></a> to eliminate potential
--   accumulation of thunks.
--   
--   <pre>
--   let f _ = Nothing
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   alter ht f 7
--   toList ht
--   [(3, "b"), (5, "a")]
--   </pre>
--   
--   <pre>
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   alter ht f 5
--   toList ht
--   [(3 "b")]
--   </pre>
--   
--   <pre>
--   let f _ = Just "c"
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   alter ht f 7
--   toList ht
--   [(3, "b"), (5, "a"), (7, "c")]
--   </pre>
--   
--   <pre>
--   ht &lt;- fromList [(5,"a"), (3,"b")]
--   alter ht f 5
--   toList ht
--   [(3, "b"), (5, "c")]
--   </pre>
alter :: (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> Maybe v) -> k -> m ()

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. The
--   expression (<tt><a>alterM</a> ht f k</tt>) alters the value <tt>x</tt>
--   at <tt>k</tt>, or absence thereof. <a>alterM</a> can be used to
--   insert, delete, or update a value in a <a>Dictionary</a> in the same
--   <tt><a>PrimMonad</a> m</tt>.
alterM :: (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> m (Maybe v)) -> k -> m ()

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Find
--   dictionary entry by given key. If entry not found <tt>-1</tt>
--   returned.
findEntry :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m Int

-- | <i>O(min n m)</i> in the best case, <i>O(min n m * max n m)</i> in the
--   worst case. The union of two maps. If a key occurs in both maps, the
--   mapping from the first will be the mapping in the result.
union :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(min n m)</i> in the best case, <i>O(min n m * max n m)</i> in the
--   worst case. The union of two maps. The provided function (first
--   argument) will be used to compute the result.
unionWith :: (MVector ks k, MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(min n m)</i> in the best case, <i>O(min n m * max n m)</i> in the
--   worst case. The union of two maps. If a key occurs in both maps, the
--   provided function (first argument) will be used to compute the result.
unionWithKey :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (k -> v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(n)</i> in the best case, <i>O(n * m)</i> in the worst case.
--   Difference of two tables. Return elements of the first table not
--   existing in the second.
difference :: (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(n)</i> in the best case, <i>O(n * m)</i> in the worst case.
--   Difference with a combining function. When two equal keys are
--   encountered, the combining function is applied to the values of these
--   keys. If it returns <a>Nothing</a>, the element is discarded (proper
--   set difference). If it returns (<tt><a>Just</a> y</tt>), the element
--   is updated with a new value <tt>y</tt>.
differenceWith :: (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => (v -> w -> Maybe v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(n)</i> in the best case, <i>O(n * m)</i> in the worst case.
--   Intersection of two maps. Return elements of the first map for keys
--   existing in the second.
intersection :: (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)

-- | Intersection of two maps. If a key occurs in both maps the provided
--   function is used to combine the values from the two maps.
intersectionWith :: (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3)

-- | Intersection of two maps. If a key occurs in both maps the provided
--   function is used to combine the values from the two maps.
intersectionWithKey :: (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (k -> v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3)

-- | <i>O(1)</i> Unsafe convert a mutable dictionary to an immutable one
--   without copying. The mutable dictionary may not be used after this
--   operation.
unsafeFreeze :: (Vector ks k, Vector vs v, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v -> m (FrozenDictionary ks k vs v)

-- | <i>O(1)</i> Unsafely convert immutable <a>FrozenDictionary</a> to a
--   mutable <a>Dictionary</a> without copying. The immutable dictionary
--   may not be used after this operation.
unsafeThaw :: (Vector ks k, Vector vs v, PrimMonad m) => FrozenDictionary ks k vs v -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)

-- | <i>O(n)</i> Convert list to a <a>Dictionary</a>.
fromList :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => [(k, v)] -> m (Dictionary (PrimState m) ks k vs v)

-- | <i>O(n)</i> Convert <a>Dictionary</a> to a list.
toList :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> m [(k, v)]

-- | Represents collection of hashtable internal primitive arrays and
--   vectors.
--   
--   <ul>
--   <li>hash codes,</li>
--   <li>references to the next element,</li>
--   <li>buckets,</li>
--   <li>keys</li>
--   <li>and values.</li>
--   </ul>
data Dictionary_ s ks k vs v
Dictionary :: !IntArray s -> !ks s k -> !vs s v -> {-# UNPACK #-} !FastRem -> Dictionary_ s ks k vs v
[hashCode, next, buckets, refs] :: Dictionary_ s ks k vs v -> !IntArray s
[key] :: Dictionary_ s ks k vs v -> !ks s k
[value] :: Dictionary_ s ks k vs v -> !vs s v
[remSize] :: Dictionary_ s ks k vs v -> {-# UNPACK #-} !FastRem

-- | <i>O(1)</i> in the best case, <i>O(n)</i> in the worst case. Same as
--   <a>findEntry</a>, but for <a>Dictionary_</a>.
findEntry_ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary_ (PrimState m) ks k vs v -> k -> m Int
