    {-|
    Module      : Data.Vector.Hashtables.Internal
    Description : Provides internals of hashtables and set of utilities.
    Copyright   : (c) klapaucius, swamp_agr, 2016-2021
    License     : BSD3
    -}
    {-# LANGUAGE BangPatterns     #-}
    {-# LANGUAGE CPP              #-}
    {-# LANGUAGE FlexibleContexts #-}
    {-# LANGUAGE MagicHash        #-}
    {-# LANGUAGE RecordWildCards  #-}
    {-# LANGUAGE TypeFamilies     #-}
    {-# LANGUAGE UnboxedTuples    #-}
    module Data.Vector.Hashtables.Internal where

    import           Control.Monad
    import           Control.Monad.Primitive
    import           Data.Bits
    import           Data.Hashable
    import           Data.Maybe
    import           Data.Primitive.MutVar
    import           Data.Vector.Generic          (Mutable, Vector)
    import qualified Data.Vector.Generic          as VI
    import           Data.Vector.Generic.Mutable  (MVector)
    import qualified Data.Vector.Generic.Mutable  as V
    import qualified Data.Vector.Mutable          as B
    import qualified Data.Vector.Storable         as SI
    import qualified Data.Vector.Storable.Mutable as S
    import qualified Data.Vector.Unboxed          as UI
    import qualified Data.Vector.Unboxed.Mutable  as U
    import qualified GHC.Exts                     as Exts
    import           Prelude                      hiding (length, lookup)

    import qualified Data.Primitive.PrimArray as A
    import qualified Data.Primitive.PrimArray.Utils as A

    import           Data.Vector.Hashtables.Internal.Mask (mask)

    -- | Alias for 'MutablePrimArray' @s@ 'Int'.
    type IntArray s = A.MutablePrimArray s Int

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

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

    getCount, getFreeList, getFreeCount :: Int
    getCount :: Int
    getCount = Int
    0
    getFreeList :: Int
    getFreeList = Int
    1
    getFreeCount :: Int
    getFreeCount = Int
    2

    -- | Represents immutable dictionary as collection of immutable arrays and vectors.
    -- See 'unsafeFreeze' and 'unsafeThaw' for conversions from/to mutable dictionary.
    data FrozenDictionary ks k vs v = FrozenDictionary {
        forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> PrimArray Int
    fhashCode,
        forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> PrimArray Int
    fnext,
        forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> PrimArray Int
    fbuckets :: !(A.PrimArray Int),
        forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> Int
    count, forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> Int
    freeList, forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> Int
    freeCount :: !Int,
        forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> ks k
    fkey :: !(ks k),
        forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> vs v
    fvalue :: !(vs v),
        forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> FastRem
    fremSize :: {-# UNPACK #-} !FastRem
    } deriving (FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    (FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool)
    -> (FrozenDictionary ks k vs v
        -> FrozenDictionary ks k vs v -> Bool)
    -> Eq (FrozenDictionary ks k vs v)
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    forall (ks :: * -> *) k (vs :: * -> *) v.
    (Eq (ks k), Eq (vs v)) =>
    FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    $c== :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Eq (ks k), Eq (vs v)) =>
    FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    == :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    $c/= :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Eq (ks k), Eq (vs v)) =>
    FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    /= :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    Eq, Eq (FrozenDictionary ks k vs v)
    Eq (FrozenDictionary ks k vs v) =>
    (FrozenDictionary ks k vs v
     -> FrozenDictionary ks k vs v -> Ordering)
    -> (FrozenDictionary ks k vs v
        -> FrozenDictionary ks k vs v -> Bool)
    -> (FrozenDictionary ks k vs v
        -> FrozenDictionary ks k vs v -> Bool)
    -> (FrozenDictionary ks k vs v
        -> FrozenDictionary ks k vs v -> Bool)
    -> (FrozenDictionary ks k vs v
        -> FrozenDictionary ks k vs v -> Bool)
    -> (FrozenDictionary ks k vs v
        -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v)
    -> (FrozenDictionary ks k vs v
        -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v)
    -> Ord (FrozenDictionary ks k vs v)
    FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    FrozenDictionary ks k vs v
    -> FrozenDictionary ks k vs v -> Ordering
    FrozenDictionary ks k vs v
    -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    Eq (FrozenDictionary ks k vs v)
    forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    FrozenDictionary ks k vs v
    -> FrozenDictionary ks k vs v -> Ordering
    forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    FrozenDictionary ks k vs v
    -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v
    $ccompare :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    FrozenDictionary ks k vs v
    -> FrozenDictionary ks k vs v -> Ordering
    compare :: FrozenDictionary ks k vs v
    -> FrozenDictionary ks k vs v -> Ordering
    $c< :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    < :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    $c<= :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    <= :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    $c> :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    > :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    $c>= :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    >= :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
    $cmax :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    FrozenDictionary ks k vs v
    -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v
    max :: FrozenDictionary ks k vs v
    -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v
    $cmin :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Ord (ks k), Ord (vs v)) =>
    FrozenDictionary ks k vs v
    -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v
    min :: FrozenDictionary ks k vs v
    -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v
    Ord, Int -> FrozenDictionary ks k vs v -> ShowS
    [FrozenDictionary ks k vs v] -> ShowS
    FrozenDictionary ks k vs v -> String
    (Int -> FrozenDictionary ks k vs v -> ShowS)
    -> (FrozenDictionary ks k vs v -> String)
    -> ([FrozenDictionary ks k vs v] -> ShowS)
    -> Show (FrozenDictionary ks k vs v)
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    forall (ks :: * -> *) k (vs :: * -> *) v.
    (Show (ks k), Show (vs v)) =>
    Int -> FrozenDictionary ks k vs v -> ShowS
    forall (ks :: * -> *) k (vs :: * -> *) v.
    (Show (ks k), Show (vs v)) =>
    [FrozenDictionary ks k vs v] -> ShowS
    forall (ks :: * -> *) k (vs :: * -> *) v.
    (Show (ks k), Show (vs v)) =>
    FrozenDictionary ks k vs v -> String
    $cshowsPrec :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Show (ks k), Show (vs v)) =>
    Int -> FrozenDictionary ks k vs v -> ShowS
    showsPrec :: Int -> FrozenDictionary ks k vs v -> ShowS
    $cshow :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Show (ks k), Show (vs v)) =>
    FrozenDictionary ks k vs v -> String
    show :: FrozenDictionary ks k vs v -> String
    $cshowList :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Show (ks k), Show (vs v)) =>
    [FrozenDictionary ks k vs v] -> ShowS
    showList :: [FrozenDictionary ks k vs v] -> ShowS
    Show)

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- Find dictionary entry by given key in immutable 'FrozenDictionary'.
    -- If entry not found @-1@ returned.
    findElem :: (Vector ks k, Vector vs v, Hashable k, Eq k)
             => FrozenDictionary ks k vs v -> k -> Int
    findElem :: forall (ks :: * -> *) k (vs :: * -> *) v.
    (Vector ks k, Vector vs v, Hashable k, Eq k) =>
    FrozenDictionary ks k vs v -> k -> Int
    findElem FrozenDictionary{ks k
    vs v
    Int
    PrimArray Int
    FastRem
    fhashCode :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> PrimArray Int
    fnext :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> PrimArray Int
    fbuckets :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> PrimArray Int
    count :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> Int
    freeList :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> Int
    freeCount :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> Int
    fkey :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> ks k
    fvalue :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> vs v
    fremSize :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> FastRem
    fhashCode :: PrimArray Int
    fnext :: PrimArray Int
    fbuckets :: PrimArray Int
    count :: Int
    freeList :: Int
    freeCount :: Int
    fkey :: ks k
    fvalue :: vs v
    fremSize :: FastRem
    ..} k
    key' = Int -> Int
    go (Int -> Int) -> Int -> Int
    forall a b. (a -> b) -> a -> b
    $ PrimArray Int
    fbuckets PrimArray Int -> Int -> Int
    !. (Int
    hashCode' Int -> FastRem -> Int
    `fastRem` FastRem
    fremSize) where
        hashCode' :: Int
    hashCode' = k -> Int
    forall a. Hashable a => a -> Int
    hash k
    key' Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    mask
        go :: Int -> Int
    go Int
    i | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0 =
                if PrimArray Int
    fhashCode PrimArray Int -> Int -> Int
    !. Int
    i Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    hashCode' Bool -> Bool -> Bool
    && ks k
    fkey ks k -> Int -> k
    forall (v :: * -> *) a. Vector v a => v a -> Int -> a
    !.~ Int
    i k -> k -> Bool
    forall a. Eq a => a -> a -> Bool
    == k
    key'
                    then Int
    i else Int -> Int
    go (Int -> Int) -> Int -> Int
    forall a b. (a -> b) -> a -> b
    $ PrimArray Int
    fnext PrimArray Int -> Int -> Int
    !. Int
    i
             | Bool
    otherwise = -Int
    1
    {-# INLINE findElem #-}

    -- | Infix version of @unsafeRead@.
    (!~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> m a
    !~ :: forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    v (PrimState m) a -> Int -> m a
    (!~) v (PrimState m) a
    xs !Int
    i = v (PrimState m) a -> Int -> m a
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> m a
    V.unsafeRead v (PrimState m) a
    xs Int
    i
    -- Why do we need ! before i?
    -- The reason is that V.unsafeRead is essentially V.basicUnsafeRead,
    -- which is an opaque class member and, unless V.unsafeRead was
    -- already specialised to a specific v, GHC has no clue that i is most certainly
    -- to be used eagerly. Bang before i hints this vital for optimizer information.

    -- | Infix version of @unsafeIndex@.
    (!.~) :: (Vector v a) => v a -> Int -> a
    !.~ :: forall (v :: * -> *) a. Vector v a => v a -> Int -> a
    (!.~) v a
    xs !Int
    i = v a -> Int -> a
    forall (v :: * -> *) a. Vector v a => v a -> Int -> a
    VI.unsafeIndex v a
    xs Int
    i

    -- | Infix version of @unsafeWrite@.
    (<~~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> a -> m ()
    <~~ :: forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    v (PrimState m) a -> Int -> a -> m ()
    (<~~) v (PrimState m) a
    xs !Int
    i a
    x = v (PrimState m) a -> Int -> a -> m ()
    forall (m :: * -> *) (v :: * -> * -> *) a.
    (PrimMonad m, MVector v a) =>
    v (PrimState m) a -> Int -> a -> m ()
    V.unsafeWrite v (PrimState m) a
    xs Int
    i a
    x

    -- | Infix version of @readPrimArray@.
    (!) :: PrimMonad m => A.MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! :: forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    (!) = MutablePrimArray (PrimState m) Int -> Int -> m Int
    forall a (m :: * -> *).
    (Prim a, PrimMonad m) =>
    MutablePrimArray (PrimState m) a -> Int -> m a
    A.readPrimArray

    -- | Infix version of @indexPrimArray@.
    (!.) :: A.PrimArray Int -> Int -> Int
    !. :: PrimArray Int -> Int -> Int
    (!.) = PrimArray Int -> Int -> Int
    forall a. Prim a => PrimArray a -> Int -> a
    A.indexPrimArray

    -- | Infix version of @writePrimArray@.
    (<~) :: PrimMonad m => A.MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
    <~ :: forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
    (<~) = MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
    forall a (m :: * -> *).
    (Prim a, PrimMonad m) =>
    MutablePrimArray (PrimState m) a -> Int -> a -> m ()
    A.writePrimArray

    -- | /O(1)/ Dictionary with given capacity.
    initialize
        :: (MVector ks k, MVector vs v, PrimMonad m)
        => Int
        -> m (Dictionary (PrimState m) ks k vs v)
    initialize :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m) =>
    Int -> m (Dictionary (PrimState m) ks k vs v)
    initialize Int
    capacity = do
        let !remSize :: FastRem
    remSize = Int -> FastRem
    getFastRem Int
    capacity
            size :: Int
    size = FastRem -> Int
    frmPrime FastRem
    remSize
        hashCode <- Int -> Int -> m (IntArray (PrimState m))
    forall (m :: * -> *) a.
    (PrimMonad m, Prim a) =>
    Int -> a -> m (MutablePrimArray (PrimState m) a)
    A.replicate Int
    size Int
    0
        next     <- A.replicate size 0
        key      <- V.new size
        value    <- V.new size
        buckets  <- A.replicate size (-1)
        refs     <- A.replicate 3 0
        refs     <~ 1 $ -1
        dr       <- newMutVar Dictionary {..}
        return . DRef $ dr

    -- | 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)
    clone :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m) =>
    Dictionary (PrimState m) ks k vs v
    -> m (Dictionary (PrimState m) ks k vs v)
    clone DRef {MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef :: MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    ..} = do
        Dictionary {..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef
        hashCode        <- A.clone hashCode
        next            <- A.clone next
        key             <- V.clone key
        value           <- V.clone value
        buckets         <- A.clone buckets
        refs            <- A.clone refs
        dr              <- newMutVar Dictionary {..}
        return . DRef $ dr

    -- | /O(1)/ Unsafe convert a mutable dictionary to an immutable one without copying.
    -- The mutable dictionary may not be used after this operation.
    unsafeFreeze
        :: (VI.Vector ks k, VI.Vector vs v, PrimMonad m)
        => Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v
        -> m (FrozenDictionary ks k vs v)
    unsafeFreeze :: forall (ks :: * -> *) k (vs :: * -> *) v (m :: * -> *).
    (Vector ks k, Vector vs v, PrimMonad m) =>
    Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v
    -> m (FrozenDictionary ks k vs v)
    unsafeFreeze DRef {MutVar
      (PrimState m)
      (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
    getDRef :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef :: MutVar
      (PrimState m)
      (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
    ..} = do
        Dictionary {..} <- MutVar
      (PrimState m)
      (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
    -> m (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar
      (PrimState m)
      (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
    getDRef
        let fremSize = FastRem
    remSize
        fhashCode       <- A.unsafeFreeze hashCode
        fnext           <- A.unsafeFreeze next
        fbuckets        <- A.unsafeFreeze buckets
        count           <- refs ! getCount
        freeList        <- refs ! getFreeList
        freeCount       <- refs ! getFreeCount
        fkey            <- VI.unsafeFreeze key
        fvalue          <- VI.unsafeFreeze value
        return FrozenDictionary {..}

    -- | /O(1)/ Unsafely convert immutable 'FrozenDictionary' to a mutable 'Dictionary' 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)
    unsafeThaw :: forall (ks :: * -> *) k (vs :: * -> *) v (m :: * -> *).
    (Vector ks k, Vector vs v, PrimMonad m) =>
    FrozenDictionary ks k vs v
    -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)
    unsafeThaw FrozenDictionary {ks k
    vs v
    Int
    PrimArray Int
    FastRem
    fhashCode :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> PrimArray Int
    fnext :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> PrimArray Int
    fbuckets :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> PrimArray Int
    count :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> Int
    freeList :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> Int
    freeCount :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> Int
    fkey :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> ks k
    fvalue :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> vs v
    fremSize :: forall (ks :: * -> *) k (vs :: * -> *) v.
    FrozenDictionary ks k vs v -> FastRem
    fhashCode :: PrimArray Int
    fnext :: PrimArray Int
    fbuckets :: PrimArray Int
    count :: Int
    freeList :: Int
    freeCount :: Int
    fkey :: ks k
    fvalue :: vs v
    fremSize :: FastRem
    ..} = do
        let remSize :: FastRem
    remSize = FastRem
    fremSize
        hashCode <- PrimArray Int -> m (IntArray (PrimState m))
    forall (m :: * -> *) a.
    PrimMonad m =>
    PrimArray a -> m (MutablePrimArray (PrimState m) a)
    A.unsafeThaw PrimArray Int
    fhashCode
        next     <- A.unsafeThaw fnext
        buckets  <- A.unsafeThaw fbuckets
        refs     <- A.unsafeThaw $ A.primArrayFromListN 3 [count, freeList, freeCount]
        key      <- VI.unsafeThaw fkey
        value    <- VI.unsafeThaw fvalue
        dr       <- newMutVar Dictionary {..}
        return . DRef $ dr

    -- | /O(n)/ Retrieve list of keys from 'Dictionary'.
    keys :: (Vector ks k, PrimMonad m)
         => Dictionary (PrimState m) (Mutable ks) k vs v -> m (ks k)
    keys :: forall (ks :: * -> *) k (m :: * -> *) (vs :: * -> * -> *) v.
    (Vector ks k, PrimMonad m) =>
    Dictionary (PrimState m) (Mutable ks) k vs v -> m (ks k)
    keys DRef{MutVar
      (PrimState m) (Dictionary_ (PrimState m) (Mutable ks) k vs v)
    getDRef :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef :: MutVar
      (PrimState m) (Dictionary_ (PrimState m) (Mutable ks) k vs v)
    ..} = do
        Dictionary{..} <- MutVar
      (PrimState m) (Dictionary_ (PrimState m) (Mutable ks) k vs v)
    -> m (Dictionary_ (PrimState m) (Mutable ks) k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar
      (PrimState m) (Dictionary_ (PrimState m) (Mutable ks) k vs v)
    getDRef
        hcs <- A.freeze hashCode
        ks <- VI.freeze key
        count <- refs ! getCount
        return . VI.ifilter (\Int
    i k
    _ -> PrimArray Int
    hcs PrimArray Int -> Int -> Int
    !. Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0) . VI.take count $ ks

    -- | /O(n)/ Retrieve list of values from 'Dictionary'.
    values :: (Vector vs v, PrimMonad m)
           => Dictionary (PrimState m) ks k (Mutable vs) v -> m (vs v)
    values :: forall (vs :: * -> *) v (m :: * -> *) (ks :: * -> * -> *) k.
    (Vector vs v, PrimMonad m) =>
    Dictionary (PrimState m) ks k (Mutable vs) v -> m (vs v)
    values DRef{MutVar
      (PrimState m) (Dictionary_ (PrimState m) ks k (Mutable vs) v)
    getDRef :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef :: MutVar
      (PrimState m) (Dictionary_ (PrimState m) ks k (Mutable vs) v)
    ..} = do
        Dictionary{..} <- MutVar
      (PrimState m) (Dictionary_ (PrimState m) ks k (Mutable vs) v)
    -> m (Dictionary_ (PrimState m) ks k (Mutable vs) v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar
      (PrimState m) (Dictionary_ (PrimState m) ks k (Mutable vs) v)
    getDRef
        hcs <- A.freeze hashCode
        vs <- VI.freeze value
        count <- refs ! getCount
        return . VI.ifilter (\Int
    i v
    _ -> PrimArray Int
    hcs PrimArray Int -> Int -> Int
    !. Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0) . VI.take count $ vs

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- Find value by given key in 'Dictionary'. 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
    at :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m v
    at Dictionary (PrimState m) ks k vs v
    d k
    k = v -> Maybe v -> v
    forall a. a -> Maybe a -> a
    fromMaybe (String -> v
    forall a. HasCallStack => String -> a
    error String
    "KeyNotFoundException!") (Maybe v -> v) -> m (Maybe v) -> m v
    forall (m :: * -> *) a b. Monad m => (a -> b) -> m a -> m b
    <$!> Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    at' Dictionary (PrimState m) ks k vs v
    d k
    k
    {-# INLINE at #-}

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- Find value by given key in 'Dictionary'. Like 'at'' but return 'Nothing' 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)
    at' :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    at' Dictionary (PrimState m) ks k vs v
    d k
    k = do
      d_@Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    d
      i <- findEntry_ d_ k
      if i >= 0
        then Just <$> value !~ i
        else return Nothing
    {-# INLINE at' #-}

    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
    atWithOrElse :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *) a.
    (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
    atWithOrElse Dictionary (PrimState m) ks k vs v
    d k
    k Dictionary (PrimState m) ks k vs v -> Int -> m a
    onFound Dictionary (PrimState m) ks k vs v -> m a
    onNothing = do
      i <- Dictionary (PrimState m) ks k vs v -> k -> m Int
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m Int
    findEntry Dictionary (PrimState m) ks k vs v
    d k
    k
      if i >= 0
          then onFound d i
          else onNothing d
    {-# INLINE atWithOrElse #-}

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- Find dictionary entry by given key. If entry not found @-1@ returned.
    findEntry :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)
              => Dictionary (PrimState m) ks k vs v -> k -> m Int
    findEntry :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m Int
    findEntry Dictionary (PrimState m) ks k vs v
    d k
    key' = do
        d_ <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    d
        findEntry_ d_ key'
    {-# INLINE findEntry #-}

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- Same as 'findEntry', but for 'Dictionary_'.
    findEntry_ :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)
              => Dictionary_ (PrimState m) ks k vs v -> k -> m Int
    findEntry_ :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary_ (PrimState m) ks k vs v -> k -> m Int
    findEntry_ Dictionary{ks (PrimState m) k
    vs (PrimState m) v
    IntArray (PrimState m)
    FastRem
    hashCode :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    next :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    buckets :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    refs :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> ks s k
    value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> vs s v
    remSize :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> FastRem
    hashCode :: IntArray (PrimState m)
    next :: IntArray (PrimState m)
    buckets :: IntArray (PrimState m)
    refs :: IntArray (PrimState m)
    key :: ks (PrimState m) k
    value :: vs (PrimState m) v
    remSize :: FastRem
    ..} k
    key' = do
        let hashCode' :: Int
    hashCode' = k -> Int
    forall a. Hashable a => a -> Int
    hash k
    key' Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    mask
            go :: Int -> m Int
    go Int
    i | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0 = do
                    hc <- IntArray (PrimState m)
    hashCode IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! Int
    i
                    if hc == hashCode'
                        then do
                            k <- key !~ i
                            if k == key'
                                then return i
                                else go =<< next ! i
                        else go =<< next ! i
                 | Bool
    otherwise = Int -> m Int
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Int -> m Int) -> Int -> m Int
    forall a b. (a -> b) -> a -> b
    $ -Int
    1
        Int -> m Int
    go (Int -> m Int) -> m Int -> m Int
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< IntArray (PrimState m)
    buckets IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! (Int
    hashCode' Int -> FastRem -> Int
    `fastRem` FastRem
    remSize)
    {-# INLINE findEntry_ #-}

    -- | /O(1)/ in the best case, /O(n)/ 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 ()
    insert :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    insert DRef{MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef :: MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    ..} k
    key' v
    value' = do
        d@Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef
        let
            hashCode' = k -> Int
    forall a. Hashable a => a -> Int
    hash k
    key' Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    mask
            !targetBucket = Int
    hashCode' Int -> FastRem -> Int
    `fastRem` FastRem
    remSize

            go Int
    i    | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0 = do
                        hc <- IntArray (PrimState m)
    hashCode IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! Int
    i
                        if hc == hashCode'
                            then do
                                k  <- key !~ i
                                if k == key'
                                    then value <~~ i $ value'
                                    else go =<< next ! i
                            else go =<< next ! i
                    | Bool
    otherwise = m ()
    addOrResize

            addOrResize = do
                freeCount <- IntArray (PrimState m)
    refs IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! Int
    getFreeCount
                if freeCount > 0
                    then do
                        index <- refs ! getFreeList
                        nxt <- next ! index
                        refs <~ getFreeList $ nxt
                        refs <~ getFreeCount $ freeCount - 1
                        add index targetBucket
                    else do
                        count <- refs ! getCount
                        refs <~ getCount $ count + 1
                        nextLen <- A.length next
                        if count == nextLen
                            then do
                                nd <- resize d count hashCode' key' value'
                                writeMutVar getDRef nd
                            else add (fromIntegral count) (fromIntegral targetBucket)

            add !Int
    index !Int
    targetBucket = do
                IntArray (PrimState m)
    hashCode IntArray (PrimState m) -> Int -> Int -> m ()
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
    <~ Int
    index (Int -> m ()) -> Int -> m ()
    forall a b. (a -> b) -> a -> b
    $ Int
    hashCode'
                b <- IntArray (PrimState m)
    buckets IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! Int
    targetBucket
                next <~ index $ b
                key <~~ index $ key'
                value <~~ index $ value'
                buckets <~ targetBucket $ index

        go =<< buckets ! targetBucket
    {-# INLINE insert #-}

    insertWithIndex
      :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)
      => Int
      -- ^ Target bucket, key's hash modulo table size
      -> Int
      -- ^ Key's hash
      -> k
      -- ^ Key
      -> v
      -- ^ Value
      -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
      -- ^ MutVar with 'Dictionary_'
      -> Dictionary_ (PrimState m) ks k vs v
      -- ^ 'Dictionary_' itself
      -> Int
      -> m ()
    insertWithIndex :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    insertWithIndex !Int
    targetBucket !Int
    hashCode' k
    key' v
    value' MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef d :: Dictionary_ (PrimState m) ks k vs v
    d@Dictionary{ks (PrimState m) k
    vs (PrimState m) v
    IntArray (PrimState m)
    FastRem
    hashCode :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    next :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    buckets :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    refs :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> ks s k
    value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> vs s v
    remSize :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> FastRem
    hashCode :: IntArray (PrimState m)
    next :: IntArray (PrimState m)
    buckets :: IntArray (PrimState m)
    refs :: IntArray (PrimState m)
    key :: ks (PrimState m) k
    value :: vs (PrimState m) v
    remSize :: FastRem
    ..} = Int -> m ()
    go where
      go :: Int -> m ()
    go Int
    i
        | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0 = do
             hc <- IntArray (PrimState m)
    hashCode IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! Int
    i
             if hc == hashCode'
                 then do
                     k  <- key !~ i
                     if k == key'
                         then value <~~ i $ value'
                         else go =<< next ! i
                 else go =<< next ! i
        | Bool
    otherwise = Int
    -> Int
    -> k
    -> v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> Dictionary_ (PrimState m) ks k vs v
    -> m ()
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    addOrResize Int
    targetBucket Int
    hashCode' k
    key' v
    value' MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef Dictionary_ (PrimState m) ks k vs v
    d
    {-# INLINE insertWithIndex #-}

    addOrResize
        :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)
        => Int
        -- ^ Target bucket, key's hash modulo table size
        -> Int
        -- ^ Key's hash
        -> k
        -- ^ Key
        -> v
        -- ^ Value
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
        -- ^ MutVar with 'Dictionary_'
        -> Dictionary_ (PrimState m) ks k vs v
        -- ^ 'Dictionary_' itself
        -> m ()
    addOrResize :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    addOrResize !Int
    targetBucket !Int
    hashCode' !k
    key' !v
    value' MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    dref d :: Dictionary_ (PrimState m) ks k vs v
    d@Dictionary{ks (PrimState m) k
    vs (PrimState m) v
    IntArray (PrimState m)
    FastRem
    hashCode :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    next :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    buckets :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    refs :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> ks s k
    value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> vs s v
    remSize :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> FastRem
    hashCode :: IntArray (PrimState m)
    next :: IntArray (PrimState m)
    buckets :: IntArray (PrimState m)
    refs :: IntArray (PrimState m)
    key :: ks (PrimState m) k
    value :: vs (PrimState m) v
    remSize :: FastRem
    ..}  = do
        freeCount <- IntArray (PrimState m)
    refs IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! Int
    getFreeCount
        if freeCount > 0
            then do
                index <- refs ! getFreeList
                nxt <- next ! index
                refs <~ getFreeList $ nxt
                refs <~ getFreeCount $ freeCount - 1
                add index targetBucket hashCode' key' value' d
            else do
                count <- refs ! getCount
                refs <~ getCount $ count + 1
                nextLen <- A.length next
                if count == nextLen
                    then do
                        nd <- resize d count hashCode' key' value'
                        writeMutVar dref nd
                    else add (fromIntegral count) (fromIntegral targetBucket) hashCode' key' value' d
    {-# INLINE addOrResize #-}

    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 ()
    add :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    add !Int
    index !Int
    targetBucket !Int
    hashCode' !k
    key' !v
    value' Dictionary{ks (PrimState m) k
    vs (PrimState m) v
    IntArray (PrimState m)
    FastRem
    hashCode :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    next :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    buckets :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    refs :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> ks s k
    value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> vs s v
    remSize :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> FastRem
    hashCode :: IntArray (PrimState m)
    next :: IntArray (PrimState m)
    buckets :: IntArray (PrimState m)
    refs :: IntArray (PrimState m)
    key :: ks (PrimState m) k
    value :: vs (PrimState m) v
    remSize :: FastRem
    ..} = do
        IntArray (PrimState m)
    hashCode IntArray (PrimState m) -> Int -> Int -> m ()
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
    <~ Int
    index (Int -> m ()) -> Int -> m ()
    forall a b. (a -> b) -> a -> b
    $ Int
    hashCode'
        b <- IntArray (PrimState m)
    buckets IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! Int
    targetBucket
        next <~ index $ b
        key <~~ index $ key'
        value <~~ index $ value'
        buckets <~ targetBucket $ index
    {-# INLINE add #-}

    resize
        :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)
        => Dictionary_ (PrimState m) ks k vs v
        -- ^ The original 'Dictionary_'
        -> Int
        --
        -> Int
        -- ^ Key's hash
        -> k
        -- ^ Key
        -> v
        -- ^ Value
        -> m (Dictionary_ (PrimState m) ks k vs v)
    resize :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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)
    resize Dictionary{ks (PrimState m) k
    vs (PrimState m) v
    IntArray (PrimState m)
    FastRem
    hashCode :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    next :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    buckets :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    refs :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> ks s k
    value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> vs s v
    remSize :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> FastRem
    hashCode :: IntArray (PrimState m)
    next :: IntArray (PrimState m)
    buckets :: IntArray (PrimState m)
    refs :: IntArray (PrimState m)
    key :: ks (PrimState m) k
    value :: vs (PrimState m) v
    remSize :: FastRem
    ..} Int
    index Int
    hashCode' k
    key' v
    value' = do
        let !newRemSize :: FastRem
    newRemSize = Int -> FastRem
    getFastRem (Int
    indexInt -> Int -> Int
    forall a. Num a => a -> a -> a
    *Int
    2)
            newSize :: Int
    newSize = FastRem -> Int
    frmPrime FastRem
    newRemSize
            delta :: Int
    delta = Int
    newSize Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    index

        buckets <- Int -> Int -> m (IntArray (PrimState m))
    forall (m :: * -> *) a.
    (PrimMonad m, Prim a) =>
    Int -> a -> m (MutablePrimArray (PrimState m) a)
    A.replicate Int
    newSize (-Int
    1)

        hashCode <- A.growNoZ hashCode delta
        next <- A.growNoZ next delta
        key <- V.grow key delta
        value <- V.grow value delta

        let go Int
    i | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    index = do
                    hc <- IntArray (PrimState m)
    hashCode IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! Int
    i
                    when (hc >= 0) $ do
                        let !bucket = Int
    hc Int -> FastRem -> Int
    `fastRem` FastRem
    newRemSize
                        nx <- buckets ! bucket
                        next <~ i $ nx
                        buckets <~ bucket $ i
                    go (i + 1)
                 | Bool
    otherwise = () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
        go 0

        let !targetBucket = Int
    hashCode' Int -> FastRem -> Int
    `fastRem` FastRem
    newRemSize
        hashCode <~ index $ hashCode'
        b <- buckets ! targetBucket
        next <~ index $ b
        key <~~ index $ key'
        value <~~ index $ value'
        buckets <~ targetBucket $ index
        let remSize = FastRem
    newRemSize
        return Dictionary{..}

    {-# INLINE resize #-}

    class DeleteEntry xs where
        deleteEntry :: (MVector xs x, PrimMonad m) => xs (PrimState m) x -> Int -> m ()

    instance DeleteEntry S.MVector where
        deleteEntry :: forall x (m :: * -> *).
    (MVector MVector x, PrimMonad m) =>
    MVector (PrimState m) x -> Int -> m ()
    deleteEntry MVector (PrimState m) x
    _ Int
    _ = () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()

    instance DeleteEntry U.MVector where
        deleteEntry :: forall x (m :: * -> *).
    (MVector MVector x, PrimMonad m) =>
    MVector (PrimState m) x -> Int -> m ()
    deleteEntry MVector (PrimState m) x
    _ Int
    _ = () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()

    instance DeleteEntry B.MVector where
        deleteEntry :: forall x (m :: * -> *).
    (MVector MVector x, PrimMonad m) =>
    MVector (PrimState m) x -> Int -> m ()
    deleteEntry MVector (PrimState m) x
    v Int
    i = MVector (PrimState m) x
    v MVector (PrimState m) x -> Int -> x -> m ()
    forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    v (PrimState m) a -> Int -> a -> m ()
    <~~ Int
    i (x -> m ()) -> x -> m ()
    forall a b. (a -> b) -> a -> b
    $ x
    forall a. HasCallStack => a
    undefined

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- Delete entry from 'Dictionary' 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 ()
    delete :: forall k (ks :: * -> * -> *) (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    delete DRef{MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef :: MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    ..} k
    key' = do
        Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef
        let hashCode' = k -> Int
    forall a. Hashable a => a -> Int
    hash k
    key' Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    mask
            !bucket = Int
    hashCode' Int -> FastRem -> Int
    `fastRem` FastRem
    remSize
            go !Int
    last !Int
    i | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0 = do
                hc <- IntArray (PrimState m)
    hashCode IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! Int
    i
                k  <- key !~ i
                if hc == hashCode' && k == key' then do
                    nxt <- next ! i
                    if last < 0
                        then buckets <~ bucket $ nxt
                        else next <~ last $ nxt
                    hashCode <~ i $ -1
                    next <~ i =<< refs ! getFreeList
                    deleteEntry key i
                    deleteEntry value i
                    refs <~ getFreeList $ i
                    fc <- refs ! getFreeCount
                    refs <~ getFreeCount $ fc + 1
                else go i =<< next ! i
                | Bool
    otherwise = () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
        go (-1) =<< buckets ! bucket

    {-# INLINE delete #-}

    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 ()
    deleteWithIndex :: forall k (ks :: * -> * -> *) (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    deleteWithIndex !Int
    bucket !Int
    hashCode' d :: Dictionary_ (PrimState m) ks k vs v
    d@Dictionary{ks (PrimState m) k
    vs (PrimState m) v
    IntArray (PrimState m)
    FastRem
    hashCode :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    next :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    buckets :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    refs :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> IntArray s
    key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> ks s k
    value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> vs s v
    remSize :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> FastRem
    hashCode :: IntArray (PrimState m)
    next :: IntArray (PrimState m)
    buckets :: IntArray (PrimState m)
    refs :: IntArray (PrimState m)
    key :: ks (PrimState m) k
    value :: vs (PrimState m) v
    remSize :: FastRem
    ..} k
    key' !Int
    last !Int
    i
      | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0 = do
          hc <- IntArray (PrimState m)
    hashCode IntArray (PrimState m) -> Int -> m Int
    forall (m :: * -> *).
    PrimMonad m =>
    MutablePrimArray (PrimState m) Int -> Int -> m Int
    ! Int
    i
          k <- key !~ i
          if hc == hashCode' && k == key' then do
              nxt <- next ! i
              if last < 0
                  then buckets <~ bucket $ nxt
                  else next <~ last $ nxt
              hashCode <~ i $ -1
              next <~ i =<< refs ! getFreeList
              deleteEntry key i
              deleteEntry value i
              refs <~ getFreeList $ i
              fc <- refs ! getFreeCount
              refs <~ getFreeCount $ fc + 1
            else deleteWithIndex bucket hashCode' d key' i =<< next ! i
      | Bool
    otherwise = () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
    {-# INLINE deleteWithIndex #-}

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- Find value by given key in 'Dictionary'. Like 'lookup'' but return 'Nothing' 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)
    lookup :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    lookup = Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    at'
    {-# INLINE lookup #-}

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- Find value by given key in 'Dictionary'. 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
    lookup' :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m v
    lookup' = Dictionary (PrimState m) ks k vs v -> k -> m v
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m v
    at
    {-# INLINE lookup' #-}

    -- | /O(1)/ in the best case, /O(n)/ 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)
    lookupIndex :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe Int)
    lookupIndex Dictionary (PrimState m) ks k vs v
    ht k
    k = do
        let safeIndex :: a -> Maybe a
    safeIndex a
    i | a
    i a -> a -> Bool
    forall a. Ord a => a -> a -> Bool
    < a
    0 = Maybe a
    forall a. Maybe a
    Nothing
                        | Bool
    otherwise = a -> Maybe a
    forall a. a -> Maybe a
    Just a
    i
        Maybe Int -> m (Maybe Int)
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Maybe Int -> m (Maybe Int))
    -> (Int -> Maybe Int) -> Int -> m (Maybe Int)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> Maybe Int
    forall {a}. (Ord a, Num a) => a -> Maybe a
    safeIndex (Int -> m (Maybe Int)) -> m Int -> m (Maybe Int)
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Dictionary (PrimState m) ks k vs v -> k -> m Int
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m Int
    findEntry Dictionary (PrimState m) ks k vs v
    ht k
    k
    {-# INLINE lookupIndex #-}

    -- | /O(1)/ Return 'True' if dictionary is empty, 'False' otherwise.
    null
      :: (MVector ks k, PrimMonad m)
      => Dictionary (PrimState m) ks k vs v -> m Bool
    null :: forall (ks :: * -> * -> *) k (m :: * -> *) (vs :: * -> * -> *) v.
    (MVector ks k, PrimMonad m) =>
    Dictionary (PrimState m) ks k vs v -> m Bool
    null Dictionary (PrimState m) ks k vs v
    ht = Bool -> m Bool
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Bool -> m Bool) -> (Int -> Bool) -> Int -> m Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    0) (Int -> m Bool) -> m Int -> m Bool
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Dictionary (PrimState m) ks k vs v -> m Int
    forall (ks :: * -> * -> *) k (m :: * -> *) (vs :: * -> * -> *) v.
    (MVector ks k, PrimMonad m) =>
    Dictionary (PrimState m) ks k vs v -> m Int
    length Dictionary (PrimState m) ks k vs v
    ht
    {-# INLINE null #-}

    -- | /O(1)/ Return the number of non-empty entries of dictionary.
    length
      :: (MVector ks k, PrimMonad m)
      => Dictionary (PrimState m) ks k vs v -> m Int
    length :: forall (ks :: * -> * -> *) k (m :: * -> *) (vs :: * -> * -> *) v.
    (MVector ks k, PrimMonad m) =>
    Dictionary (PrimState m) ks k vs v -> m Int
    length DRef {MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef :: MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    ..} = do
        Dictionary {..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef
        count           <- refs ! getCount
        freeCount       <- refs ! getFreeCount
        return (count - freeCount)
    {-# INLINE length #-}

    -- | /O(1)/ Return the number of non-empty entries of dictionary. Synonym of 'length'.
    size
      :: (MVector ks k, PrimMonad m)
      => Dictionary (PrimState m) ks k vs v -> m Int
    size :: forall (ks :: * -> * -> *) k (m :: * -> *) (vs :: * -> * -> *) v.
    (MVector ks k, PrimMonad m) =>
    Dictionary (PrimState m) ks k vs v -> m Int
    size = Dictionary (PrimState m) ks k vs v -> m Int
    forall (ks :: * -> * -> *) k (m :: * -> *) (vs :: * -> * -> *) v.
    (MVector ks k, PrimMonad m) =>
    Dictionary (PrimState m) ks k vs v -> m Int
    length
    {-# INLINE size #-}

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- Return 'True' if the specified key is present in the dictionary, 'False' otherwise.
    member
      :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)
      => Dictionary (PrimState m) ks k vs v -> k -> m Bool
    member :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m Bool
    member Dictionary (PrimState m) ks k vs v
    ht k
    k = Bool -> m Bool
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Bool -> m Bool) -> (Int -> Bool) -> Int -> m Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0) (Int -> m Bool) -> m Int -> m Bool
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Dictionary (PrimState m) ks k vs v -> k -> m Int
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m Int
    findEntry Dictionary (PrimState m) ks k vs v
    ht k
    k
    {-# INLINE member #-}

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- The expression @'findWithDefault' ht def k@ returns
    -- the value at key @k@ or returns default value @def@
    -- 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
    findWithDefault :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> v -> k -> m v
    findWithDefault Dictionary (PrimState m) ks k vs v
    ht v
    v k
    k = v -> m v
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (v -> m v) -> (Maybe v -> v) -> Maybe v -> m v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . v -> Maybe v -> v
    forall a. a -> Maybe a -> a
    fromMaybe v
    v (Maybe v -> m v) -> m (Maybe v) -> m v
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    at' Dictionary (PrimState m) ks k vs v
    ht k
    k
    {-# INLINE findWithDefault #-}

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- The expression (@'upsert' ht f k@) updates or inserts the value @x@ at @k@.
    --
    -- It's a responsibility of 'MVector' @vs@ to force evaluation of the updated value.
    -- Unboxed / storable vectors do it automatically. If you use boxed vectors,
    -- consider employing strict ones from
    -- [@strict-containers@](https://hackage.haskell.org/package/strict-containers)
    -- to eliminate potential accumulation of thunks.
    --
    -- > let f _ = "c"
    -- > ht <- fromList [(5,"a"), (3,"b")]
    -- > upsert ht f 7
    -- > toList ht
    -- > [(3, "b"), (5, "a"), (7, "c")]
    --
    -- > ht <- fromList [(5,"a"), (3,"b")]
    -- > upsert ht f 5
    -- > toList ht
    -- > [(3, "b"), (5, "c")]
    --
    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 ()
    upsert :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> (Maybe v -> v) -> k -> m ()
    upsert Dictionary (PrimState m) ks k vs v
    ht Maybe v -> v
    f k
    k = do
      d@Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    ht
      let
          hashCode' = k -> Int
    forall a. Hashable a => a -> Int
    hash k
    k Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    mask
          !targetBucket = Int
    hashCode' Int -> FastRem -> Int
    `fastRem` FastRem
    remSize

          onFound' v
    value' Dictionary_ (PrimState m) ks k vs v
    dict Int
    i = Int
    -> Int
    -> k
    -> v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> Dictionary_ (PrimState m) ks k vs v
    -> Int
    -> m ()
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    insertWithIndex Int
    targetBucket Int
    hashCode' k
    k v
    value' (Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef Dictionary (PrimState m) ks k vs v
    ht) Dictionary_ (PrimState m) ks k vs v
    dict Int
    i

          onFound Dictionary (PrimState m) ks k vs v
    dict Int
    i = do
            d'@Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    dict
            v <- value !~ i
            onFound' (f (Just v)) d' i

          onNothing Dictionary (PrimState m) ks k vs v
    dict = do
            d' <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    dict
            onFound' (f Nothing) d' (-1)

      void $ atWithOrElse ht k onFound onNothing

    {-# INLINE upsert #-}

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- The expression (@'alter' ht f k@) alters the value @x@ at @k@, or absence thereof.
    -- 'alter' can be used to insert, delete, or update a value in a 'Dictionary'.
    --
    -- It's a responsibility of 'MVector' @vs@ to force evaluation of the updated value.
    -- Unboxed / storable vectors do it automatically. If you use boxed vectors,
    -- consider employing strict ones from
    -- [@strict-containers@](https://hackage.haskell.org/package/strict-containers)
    -- to eliminate potential accumulation of thunks.
    --
    -- > let f _ = Nothing
    -- > ht <- fromList [(5,"a"), (3,"b")]
    -- > alter ht f 7
    -- > toList ht
    -- > [(3, "b"), (5, "a")]
    --
    -- > ht <- fromList [(5,"a"), (3,"b")]
    -- > alter ht f 5
    -- > toList ht
    -- > [(3 "b")]
    --
    -- > let f _ = Just "c"
    -- > ht <- fromList [(5,"a"), (3,"b")]
    -- > alter ht f 7
    -- > toList ht
    -- > [(3, "b"), (5, "a"), (7, "c")]
    --
    -- > ht <- fromList [(5,"a"), (3,"b")]
    -- > alter ht f 5
    -- > toList ht
    -- > [(3, "b"), (5, "c")]
    --
    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 ()
    alter :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    alter Dictionary (PrimState m) ks k vs v
    ht Maybe v -> Maybe v
    f k
    k = do
      d@Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    ht
      let
          hashCode' = k -> Int
    forall a. Hashable a => a -> Int
    hash k
    k Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    mask
          !targetBucket = Int
    hashCode' Int -> FastRem -> Int
    `fastRem` FastRem
    remSize

          onFound' v
    value' Dictionary_ (PrimState m) ks k vs v
    dict Int
    i = Int
    -> Int
    -> k
    -> v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> Dictionary_ (PrimState m) ks k vs v
    -> Int
    -> m ()
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    insertWithIndex Int
    targetBucket Int
    hashCode' k
    k v
    value' (Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef Dictionary (PrimState m) ks k vs v
    ht) Dictionary_ (PrimState m) ks k vs v
    dict Int
    i
          onNothing' Dictionary_ (PrimState m) ks k vs v
    dict Int
    i = Int
    -> Int
    -> Dictionary_ (PrimState m) ks k vs v
    -> k
    -> Int
    -> Int
    -> m ()
    forall k (ks :: * -> * -> *) (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    deleteWithIndex Int
    targetBucket Int
    hashCode' Dictionary_ (PrimState m) ks k vs v
    d k
    k (-Int
    1) Int
    i

          onFound Dictionary (PrimState m) ks k vs v
    dict Int
    i = do
            d'@Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    dict
            v <- value !~ i
            case f (Just v) of
              Maybe v
    Nothing -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
    onNothing' Dictionary_ (PrimState m) ks k vs v
    d' Int
    i
              Just v
    v' ->  v -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
    onFound' v
    v' Dictionary_ (PrimState m) ks k vs v
    d' Int
    i

          onNothing Dictionary (PrimState m) ks k vs v
    dict = do
            d' <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    dict
            case f Nothing of
              Maybe v
    Nothing -> () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
              Just v
    v' -> v -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
    onFound' v
    v' Dictionary_ (PrimState m) ks k vs v
    d' (-Int
    1)

      void $ atWithOrElse ht k onFound onNothing

    {-# INLINE alter #-}

    -- | /O(1)/ in the best case, /O(n)/ in the worst case.
    -- The expression (@'alterM' ht f k@) alters the value @x@ at @k@, or absence thereof.
    -- 'alterM' can be used to insert, delete, or update a value in a 'Dictionary' in the same @'PrimMonad' m@.
    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 ()
    alterM :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    alterM Dictionary (PrimState m) ks k vs v
    ht Maybe v -> m (Maybe v)
    f k
    k = do
      d@Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    ht
      let
          hashCode' = k -> Int
    forall a. Hashable a => a -> Int
    hash k
    k Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    mask
          !targetBucket = Int
    hashCode' Int -> FastRem -> Int
    `fastRem` FastRem
    remSize

          onFound' v
    value' Dictionary_ (PrimState m) ks k vs v
    dict Int
    i = Int
    -> Int
    -> k
    -> v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> Dictionary_ (PrimState m) ks k vs v
    -> Int
    -> m ()
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    insertWithIndex Int
    targetBucket Int
    hashCode' k
    k v
    value' (Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef Dictionary (PrimState m) ks k vs v
    ht) Dictionary_ (PrimState m) ks k vs v
    dict Int
    i
          onNothing' Dictionary_ (PrimState m) ks k vs v
    dict Int
    i = Int
    -> Int
    -> Dictionary_ (PrimState m) ks k vs v
    -> k
    -> Int
    -> Int
    -> m ()
    forall k (ks :: * -> * -> *) (vs :: * -> * -> *) v (m :: * -> *).
    (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 ()
    deleteWithIndex Int
    targetBucket Int
    hashCode' Dictionary_ (PrimState m) ks k vs v
    d k
    k (-Int
    1) Int
    i

          onFound Dictionary (PrimState m) ks k vs v
    dict Int
    i = do
            d'@Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    dict
            v <- value !~ i
            res <- f (Just v)
            case res of
              Maybe v
    Nothing -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
    onNothing' Dictionary_ (PrimState m) ks k vs v
    d' Int
    i
              Just v
    v' ->  v -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
    onFound' v
    v' Dictionary_ (PrimState m) ks k vs v
    d' Int
    i

          onNothing Dictionary (PrimState m) ks k vs v
    dict = do
            d' <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    dict
            res <- f Nothing
            case res of
              Maybe v
    Nothing -> () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
              Just v
    v' -> v -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
    onFound' v
    v' Dictionary_ (PrimState m) ks k vs v
    d' (-Int
    1)

      void $ atWithOrElse ht k onFound onNothing

    {-# INLINE alterM #-}

    -- * Combine

    -- | /O(min n m)/ in the best case, /O(min n m * max n m)/ 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)
    union :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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)
    union = (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)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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)
    unionWith v -> v -> v
    forall a b. a -> b -> a
    const

    {-# INLINE union #-}

    -- | /O(min n m)/ in the best case, /O(min n m * max n m)/ 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)
    unionWith :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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)
    unionWith v -> v -> v
    f = (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)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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)
    unionWithKey ((v -> v -> v) -> k -> v -> v -> v
    forall a b. a -> b -> a
    const v -> v -> v
    f)

    {-# INLINE unionWith #-}

    -- | /O(min n m)/ in the best case, /O(min n m * max n m)/ 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)
    unionWithKey :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (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)
    unionWithKey k -> v -> v -> v
    f Dictionary (PrimState m) ks k vs v
    t1 Dictionary (PrimState m) ks k vs v
    t2 = do
      l1 <- Dictionary (PrimState m) ks k vs v -> m Int
    forall (ks :: * -> * -> *) k (m :: * -> *) (vs :: * -> * -> *) v.
    (MVector ks k, PrimMonad m) =>
    Dictionary (PrimState m) ks k vs v -> m Int
    length Dictionary (PrimState m) ks k vs v
    t1
      l2 <- length t2
      let smallest = Int -> Int -> Int
    forall a. Ord a => a -> a -> a
    min Int
    l1 Int
    l2
          greatest = Int -> Int -> Int
    forall a. Ord a => a -> a -> a
    max Int
    l1 Int
    l2
          g k
    k v
    v1 v
    v2 = if Int
    smallest Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    l1 then k -> v -> v -> v
    f k
    k v
    v1 v
    v2 else k -> v -> v -> v
    f k
    k v
    v2 v
    v1
          (tS, tG) = if smallest == l1 then (t1, t2) else (t2, t1)
      ht <- clone tG
      dictG <- readMutVar . getDRef $ tG
      dictS <- readMutVar . getDRef $ tS
      hcsS <- A.freeze . hashCode $ dictS
      let indices = [Maybe Int] -> [Int]
    forall a. [Maybe a] -> [a]
    catMaybes ([Maybe Int] -> [Int])
    -> (PrimArray Int -> [Maybe Int]) -> PrimArray Int -> [Int]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int -> Int -> Maybe Int) -> [Int] -> [Int] -> [Maybe Int]
    forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
    zipWith Int -> Int -> Maybe Int
    collect [Int
    0 ..] ([Int] -> [Maybe Int])
    -> (PrimArray Int -> [Int]) -> PrimArray Int -> [Maybe Int]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> [Int] -> [Int]
    forall a. Int -> [a] -> [a]
    take Int
    smallest ([Int] -> [Int])
    -> (PrimArray Int -> [Int]) -> PrimArray Int -> [Int]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . PrimArray Int -> [Int]
    forall a. Prim a => PrimArray a -> [a]
    A.primArrayToList (PrimArray Int -> [Int]) -> PrimArray Int -> [Int]
    forall a b. (a -> b) -> a -> b
    $ PrimArray Int
    hcsS
          collect Int
    i Int
    _ | PrimArray Int
    hcsS PrimArray Int -> Int -> Int
    !. Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0 = Int -> Maybe Int
    forall a. a -> Maybe a
    Just Int
    i
                      | Bool
    otherwise       = Maybe Int
    forall a. Maybe a
    Nothing

          go !Int
    i = do
            k <- Dictionary_ (PrimState m) ks k vs v -> ks (PrimState m) k
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> ks s k
    key Dictionary_ (PrimState m) ks k vs v
    dictS ks (PrimState m) k -> Int -> m k
    forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    v (PrimState m) a -> Int -> m a
    !~ Int
    i
            v <- value dictS !~ i
            let
               hashCode' = k -> Int
    forall a. Hashable a => a -> Int
    hash k
    k Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    mask
               !targetBucket = Int
    hashCode' Int -> FastRem -> Int
    `fastRem` Dictionary_ (PrimState m) ks k vs v -> FastRem
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary_ s ks k vs v -> FastRem
    remSize Dictionary_ (PrimState m) ks k vs v
    dictG

               onFound Dictionary (PrimState m) ks k vs v
    dict Int
    i = do
                 d@Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    dict
                 vG <- value !~ i
                 insertWithIndex targetBucket hashCode' k (g k v vG) (getDRef dict) d i

               onNothing Dictionary (PrimState m) ks k vs v
    dict = do
                 d@Dictionary{..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> (Dictionary (PrimState m) ks k vs v
        -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Dictionary (PrimState m) ks k vs v
    -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef (Dictionary (PrimState m) ks k vs v
     -> m (Dictionary_ (PrimState m) ks k vs v))
    -> Dictionary (PrimState m) ks k vs v
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall a b. (a -> b) -> a -> b
    $ Dictionary (PrimState m) ks k vs v
    dict
                 insertWithIndex targetBucket hashCode' k v (getDRef dict) d
                   =<< buckets ! targetBucket

            void $ atWithOrElse ht k onFound onNothing
      mapM_ go indices
      return ht

    {-# INLINE unionWithKey #-}

    -- * Difference and intersection

    -- | /O(n)/ in the best case, /O(n * m)/ 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)
    difference :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v w (m :: * -> *).
    (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)
    difference Dictionary (PrimState m) ks k vs v
    a Dictionary (PrimState m) ks k vs w
    b = do
      kvs <- Dictionary (PrimState m) ks k vs v -> m [(k, v)]
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> m [(k, v)]
    toList Dictionary (PrimState m) ks k vs v
    a
      ht <- initialize 10
      mapM_ (go ht) kvs
      return ht
      where
        go :: Dictionary (PrimState m) ks k vs v -> (k, v) -> m ()
    go Dictionary (PrimState m) ks k vs v
    ht (!k
    k, !v
    v) = do
          mv <- Dictionary (PrimState m) ks k vs w -> k -> m (Maybe w)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    lookup Dictionary (PrimState m) ks k vs w
    b k
    k
          case mv of
            Maybe w
    Nothing -> Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    insert Dictionary (PrimState m) ks k vs v
    ht k
    k v
    v
            Maybe w
    _       -> () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
    {-# INLINE difference #-}

    -- | /O(n)/ in the best case, /O(n * m)/ 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 'Nothing', the element is discarded (proper set difference). If
    -- it returns (@'Just' y@), the element is updated with a new value @y@.
    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)
    differenceWith :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v w (m :: * -> *).
    (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)
    differenceWith v -> w -> Maybe v
    f Dictionary (PrimState m) ks k vs v
    a Dictionary (PrimState m) ks k vs w
    b = do
      kvs <- Dictionary (PrimState m) ks k vs v -> m [(k, v)]
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> m [(k, v)]
    toList Dictionary (PrimState m) ks k vs v
    a
      ht <- initialize 10
      mapM_ (go ht) kvs
      return ht
      where
        go :: Dictionary (PrimState m) ks k vs v -> (k, v) -> m ()
    go Dictionary (PrimState m) ks k vs v
    ht (!k
    k, !v
    v) = do
          mv <- Dictionary (PrimState m) ks k vs w -> k -> m (Maybe w)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    lookup Dictionary (PrimState m) ks k vs w
    b k
    k
          case mv of
            Maybe w
    Nothing -> Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    insert Dictionary (PrimState m) ks k vs v
    ht k
    k v
    v
            Just w
    w  -> m () -> (v -> m ()) -> Maybe v -> m ()
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe (() -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()) (Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    insert Dictionary (PrimState m) ks k vs v
    ht k
    k) (v -> w -> Maybe v
    f v
    v w
    w)
    {-# INLINE differenceWith #-}

    -- | /O(n)/ in the best case, /O(n * m)/ 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 :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v w (m :: * -> *).
    (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 Dictionary (PrimState m) ks k vs v
    a Dictionary (PrimState m) ks k vs w
    b = do
      kvs <- Dictionary (PrimState m) ks k vs v -> m [(k, v)]
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> m [(k, v)]
    toList Dictionary (PrimState m) ks k vs v
    a
      ht <- initialize 10
      mapM_ (go ht) kvs
      return ht
      where
        go :: Dictionary (PrimState m) ks k vs v -> (k, v) -> m ()
    go Dictionary (PrimState m) ks k vs v
    ht (!k
    k, !v
    v) = do
          mv <- Dictionary (PrimState m) ks k vs w -> k -> m (Maybe w)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    lookup Dictionary (PrimState m) ks k vs w
    b k
    k
          case mv of
            Maybe w
    Nothing -> () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
            Just w
    _  -> Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    insert Dictionary (PrimState m) ks k vs v
    ht k
    k v
    v
    {-# INLINE intersection #-}

    -- | 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)
    intersectionWith :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v1 v2 v3
           (m :: * -> *).
    (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)
    intersectionWith v1 -> v2 -> v3
    f Dictionary (PrimState m) ks k vs v1
    a Dictionary (PrimState m) ks k vs v2
    b = do
      kvs <- Dictionary (PrimState m) ks k vs v1 -> m [(k, v1)]
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> m [(k, v)]
    toList Dictionary (PrimState m) ks k vs v1
    a
      ht <- initialize 10
      mapM_ (go ht) kvs
      return ht
      where
        go :: Dictionary (PrimState m) ks k vs v3 -> (k, v1) -> m ()
    go Dictionary (PrimState m) ks k vs v3
    ht (!k
    k, !v1
    v) = do
          mv <- Dictionary (PrimState m) ks k vs v2 -> k -> m (Maybe v2)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    lookup Dictionary (PrimState m) ks k vs v2
    b k
    k
          case mv of
            Maybe v2
    Nothing -> () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
            Just v2
    w  -> Dictionary (PrimState m) ks k vs v3 -> k -> v3 -> m ()
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    insert Dictionary (PrimState m) ks k vs v3
    ht k
    k (v1 -> v2 -> v3
    f v1
    v v2
    w)
    {-# INLINE intersectionWith #-}

    -- | 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)
    intersectionWithKey :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v1 v2 v3
           (m :: * -> *).
    (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)
    intersectionWithKey k -> v1 -> v2 -> v3
    f Dictionary (PrimState m) ks k vs v1
    a Dictionary (PrimState m) ks k vs v2
    b = do
      kvs <- Dictionary (PrimState m) ks k vs v1 -> m [(k, v1)]
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> m [(k, v)]
    toList Dictionary (PrimState m) ks k vs v1
    a
      ht <- initialize 10
      mapM_ (go ht) kvs
      return ht
      where
        go :: Dictionary (PrimState m) ks k vs v3 -> (k, v1) -> m ()
    go Dictionary (PrimState m) ks k vs v3
    ht (!k
    k, !v1
    v) = do
          mv <- Dictionary (PrimState m) ks k vs v2 -> k -> m (Maybe v2)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
    lookup Dictionary (PrimState m) ks k vs v2
    b k
    k
          case mv of
            Maybe v2
    Nothing -> () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
            Just v2
    w  -> Dictionary (PrimState m) ks k vs v3 -> k -> v3 -> m ()
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
    insert Dictionary (PrimState m) ks k vs v3
    ht k
    k (k -> v1 -> v2 -> v3
    f k
    k v1
    v v2
    w)
    {-# INLINE intersectionWithKey #-}

    -- * List conversions

    -- | /O(n)/ Convert list to a 'Dictionary'.
    fromList
      :: (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k)
      => [(k, v)] -> m (Dictionary (PrimState m) ks k vs v)
    fromList :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    [(k, v)] -> m (Dictionary (PrimState m) ks k vs v)
    fromList [(k, v)]
    kv = do
        ht <- Int -> m (Dictionary (PrimState m) ks k vs v)
    forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m) =>
    Int -> m (Dictionary (PrimState m) ks k vs v)
    initialize Int
    1
        mapM_ (uncurry (insert ht)) kv
        return ht

    {-# INLINE fromList #-}

    -- | /O(n)/ Convert 'Dictionary' 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)]
    toList :: forall (ks :: * -> * -> *) k (vs :: * -> * -> *) v (m :: * -> *).
    (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) =>
    Dictionary (PrimState m) ks k vs v -> m [(k, v)]
    toList DRef {MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
    Dictionary s ks k vs v -> MutVar s (Dictionary_ s ks k vs v)
    getDRef :: MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    ..} = do
        Dictionary {..} <- MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    -> m (Dictionary_ (PrimState m) ks k vs v)
    forall (m :: * -> *) a.
    PrimMonad m =>
    MutVar (PrimState m) a -> m a
    readMutVar MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
    getDRef
        hcs <- A.freeze hashCode
        count <- refs ! getCount
        let go !Int
    i [(k, v)]
    xs
              | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    0 = [(k, v)] -> m [(k, v)]
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return [(k, v)]
    xs
              | PrimArray Int
    hcs PrimArray Int -> Int -> Int
    !. Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    0 = Int -> [(k, v)] -> m [(k, v)]
    go (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) [(k, v)]
    xs
              | Bool
    otherwise = do
                  k <- ks (PrimState m) k
    key ks (PrimState m) k -> Int -> m k
    forall (v :: * -> * -> *) a (m :: * -> *).
    (MVector v a, PrimMonad m) =>
    v (PrimState m) a -> Int -> m a
    !~ Int
    i
                  v <- value !~ i
                  go (i - 1) ((k, v) : xs)
            {-# INLINE go #-}
        go (count - 1) []
    {-# INLINE toList #-}

    -- * Extras

    -- | 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 >= 0
    -- it holds that n \`'quot'\` p = (n * m) \`'shiftR'\` (64 + s),
    -- enabling faster computation of remainders.
    primesWithFastRem :: UI.Vector (Int, Int, Int)
    primesWithFastRem :: Vector (Int, Int, Int)
    primesWithFastRem = [(Int, Int, Int)] -> Vector (Int, Int, Int)
    forall a. Unbox a => [a] -> Vector a
    UI.fromList ([(Int, Int, Int)] -> Vector (Int, Int, Int))
    -> [(Int, Int, Int)] -> Vector (Int, Int, Int)
    forall a b. (a -> b) -> a -> b
    $
      if Int -> Int
    forall b. FiniteBits b => b -> Int
    finiteBitSize (Int
    0 :: Int) Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    32
      then [(Int
    5,Int
    1717986919,Int
    1),(Int
    11,Int
    780903145,Int
    1),(Int
    17,Int
    2021161081,Int
    3),(Int
    41,Int
    1676084799,Int
    4),(Int
    53,Int
    1296593901,Int
    4),(Int
    67,Int
    128207979,Int
    1),(Int
    83,Int
    827945503,Int
    4),(Int
    101,Int
    680390859,Int
    4),(Int
    131,Int
    1049152317,Int
    5),(Int
    163,Int
    210795941,Int
    3),(Int
    197,Int
    1395319325,Int
    6),(Int
    241,Int
    285143057,Int
    4),(Int
    311,Int
    883851791,Int
    6),(Int
    379,Int
    1450543045,Int
    7),(Int
    457,Int
    601483385,Int
    6),(Int
    557,Int
    123374285,Int
    4),(Int
    673,Int
    1633746847,Int
    8),(Int
    809,Int
    84943729,Int
    4),(Int
    977,Int
    562697865,Int
    7),(Int
    1187,Int
    1852589095,Int
    9),(Int
    1427,Int
    24078303,Int
    3),(Int
    1721,Int
    638879505,Int
    8),(Int
    2069,Int
    2125687053,Int
    10),(Int
    2503,Int
    1757110073,Int
    10),(Int
    3041,Int
    723125043,Int
    9),(Int
    3673,Int
    299349749,Int
    8),(Int
    4409,Int
    1995031305,Int
    11),(Int
    5297,Int
    103786259,Int
    7),(Int
    6367,Int
    1381512961,Int
    11),(Int
    7649,Int
    287491601,Int
    9),(Int
    9181,Int
    1916151405,Int
    12),(Int
    11047,Int
    1592485385,Int
    12),(Int
    13291,Int
    330904109,Int
    10),(Int
    15959,Int
    1102336365,Int
    12),(Int
    19157,Int
    57394771,Int
    8),(Int
    22993,Int
    382555257,Int
    11),(Int
    27611,Int
    637144111,Int
    12),(Int
    33149,Int
    1061400709,Int
    13),(Int
    39779,Int
    1768992287,Int
    14),(Int
    47741,Int
    736984397,Int
    13),(Int
    57301,Int
    1228054383,Int
    14),(Int
    68767,Int
    511646169,Int
    13),(Int
    82529,Int
    426327377,Int
    13),(Int
    99041,Int
    177625287,Int
    12),(Int
    118861,Int
    1184051021,Int
    15),(Int
    142657,Int
    1973089135,Int
    16),(Int
    171203,Int
    1644100727,Int
    16),(Int
    205477,Int
    684930617,Int
    15),(Int
    246577,Int
    285382433,Int
    14),(Int
    295901,Int
    951247129,Int
    16),(Int
    355087,Int
    792692993,Int
    16),(Int
    426131,Int
    1321072519,Int
    17),(Int
    511361,Int
    1100885585,Int
    17),(Int
    613637,Int
    917398973,Int
    17),(Int
    736369,Int
    1528988737,Int
    18),(Int
    883661,Int
    637065519,Int
    17),(Int
    1060421,Int
    2123496059,Int
    19),(Int
    1272539,Int
    1769533047,Int
    19),(Int
    1527061,Int
    184324645,Int
    16),(Int
    1832497,Int
    1228815007,Int
    19),(Int
    2199061,Int
    2047964849,Int
    20),(Int
    2638879,Int
    1706633623,Int
    20),(Int
    3166661,Int
    1422191901,Int
    20),(Int
    3800051,Int
    1185141891,Int
    20),(Int
    4560071,Int
    123452015,Int
    17),(Int
    5472109,Int
    411504927,Int
    19),(Int
    6566551,Int
    685839435,Int
    20),(Int
    7879897,Int
    285765133,Int
    19),(Int
    9455881,Int
    238137495,Int
    19),(Int
    11347079,Int
    793790125,Int
    21),(Int
    13616503,Int
    1322982745,Int
    22),(Int
    16339877,Int
    275620167,Int
    20),(Int
    19607893,Int
    229682997,Int
    20),(Int
    23529511,Int
    191402177,Int
    20),(Int
    28235483,Int
    1276011359,Int
    23),(Int
    33882593,Int
    2126684757,Int
    24),(Int
    40659149,Int
    1772235667,Int
    24),(Int
    48791009,Int
    738431071,Int
    23),(Int
    58549219,Int
    1230718279,Int
    24),(Int
    70259107,Int
    1025597921,Int
    24),(Int
    84310943,Int
    427332393,Int
    23),(Int
    101173139,Int
    712220603,Int
    24),(Int
    121407857,Int
    74189591,Int
    21),(Int
    145689433,Int
    1978389031,Int
    26),(Int
    174827333,Int
    206082175,Int
    23),(Int
    209792827,Int
    1373880987,Int
    26),(Int
    251751509,Int
    286225073,Int
    24),(Int
    302101841,Int
    1908166963,Int
    27),(Int
    362522213,Int
    1590139119,Int
    27),(Int
    435026701,Int
    662557897,Int
    26),(Int
    522032051,Int
    1104263141,Int
    27),(Int
    626438489,Int
    1840438487,Int
    28),(Int
    751726211,Int
    766849345,Int
    27),(Int
    902071483,Int
    1278082199,Int
    28)]
      else [(Int
    5,Int
    7378697629483820647,Int
    1),(Int
    7,Int
    5270498306774157605,Int
    1),(Int
    11,Int
    3353953467947191203,Int
    1),(Int
    17,Int
    8680820740569200761,Int
    3),(Int
    29,Int
    5088756985850910791,Int
    3),(Int
    37,Int
    3988485205126389539,Int
    3),(Int
    47,Int
    6279742663390485657,Int
    4),(Int
    67,Int
    8810385229234412713,Int
    5),(Int
    83,Int
    3555998857582564167,Int
    4),(Int
    107,Int
    1379195818595106663,Int
    3),(Int
    131,Int
    281629680514649643,Int
    1),(Int
    163,Int
    7242893378634425175,Int
    6),(Int
    197,Int
    1498212716646461045,Int
    4),(Int
    241,Int
    1224680104478642431,Int
    4),(Int
    293,Int
    503665367200260795,Int
    3),(Int
    353,Int
    1672226091667721393,Int
    5),(Int
    433,Int
    681634884940768651,Int
    4),(Int
    521,Int
    9064043153300662599,Int
    8),(Int
    631,Int
    7483940543375032035,Int
    8),(Int
    761,Int
    3102737505170594753,Int
    7),(Int
    919,Int
    642324059149842929,Int
    5),(Int
    1103,Int
    4281383937325154319,Int
    8),(Int
    1327,Int
    7117357170866081709,Int
    9),(Int
    1597,Int
    739255867700320165,Int
    6),(Int
    1949,Int
    2422968949650921095,Int
    8),(Int
    2339,Int
    4037936282915472607,Int
    9),(Int
    2833,Int
    6667654758728761333,Int
    10),(Int
    3407,Int
    5544310517017487777,Int
    10),(Int
    4093,Int
    4615066193862345677,Int
    10),(Int
    4919,Int
    7680205705012637063,Int
    11),(Int
    5903,Int
    6399954576140464461,Int
    11),(Int
    7103,Int
    2659364484228999135,Int
    10),(Int
    8527,Int
    8861013688977873041,Int
    12),(Int
    10243,Int
    7376536534795892163,Int
    12),(Int
    12301,Int
    6142416366629893783,Int
    12),(Int
    14767,Int
    2558334926725615339,Int
    11),(Int
    17729,Int
    4261823212020662385,Int
    12),(Int
    21277,Int
    887788030806907969,Int
    10),(Int
    25561,Int
    1477991153043979567,Int
    11),(Int
    30677,Int
    4926026907840683471,Int
    13),(Int
    36821,Int
    4104063644437376683,Int
    13),(Int
    44201,Int
    1709415255897249461,Int
    12),(Int
    53051,Int
    5696998264003643545,Int
    14),(Int
    63667,Int
    4747066060968119963,Int
    14),(Int
    76403,Int
    7911507529904775825,Int
    15),(Int
    91691,Int
    6592390854143968191,Int
    15),(Int
    110039,Int
    5493169783506889261,Int
    15),(Int
    132047,Int
    9155269105808001505,Int
    16),(Int
    158507,Int
    3813477700084630883,Int
    15),(Int
    190243,Int
    6354640221267690137,Int
    16),(Int
    228299,Int
    5295361870243098633,Int
    16),(Int
    273967,Int
    8825338961368552963,Int
    17),(Int
    328777,Int
    3677038903617434233,Int
    16),(Int
    394549,Int
    6128140330426026551,Int
    17),(Int
    473471,Int
    5106652021410515849,Int
    17),(Int
    568171,Int
    8510999819523553119,Int
    18),(Int
    681809,Int
    3546230160102401625,Int
    17),(Int
    818173,Int
    5910367707634591583,Int
    18),(Int
    981809,Int
    4925299399841024781,Int
    18),(Int
    1178173,Int
    8208817004732779819,Int
    19),(Int
    1413827,Int
    1710146743009758867,Int
    17),(Int
    1696601,Int
    5700460247823167261,Int
    19),(Int
    2035927,Int
    4750370006840634953,Int
    19),(Int
    2443151,Int
    7917158257444614269,Int
    20),(Int
    2931793,Int
    6597605326786054403,Int
    20),(Int
    3518209,Int
    5497914738389352877,Int
    20),(Int
    4221851,Int
    9163190796564855935,Int
    21),(Int
    5066231,Int
    7635977559583866901,Int
    21),(Int
    6079481,Int
    3181655327787695495,Int
    20),(Int
    7295381,Int
    1325689029389559421,Int
    19),(Int
    8754461,Int
    8837923026367501915,Int
    22),(Int
    10505377,Int
    7364919169996114103,Int
    22),(Int
    12606463,Int
    1534356870268374785,Int
    20),(Int
    15127831,Int
    5114497409135273073,Int
    22),(Int
    18153427,Int
    8524148355606494265,Int
    23),(Int
    21784129,Int
    7103451550010217731,Int
    23),(Int
    26140973,Int
    5919538837007808943,Int
    23),(Int
    31369243,Int
    2466468586931991543,Int
    22),(Int
    37643093,Int
    8221561650668425911,Int
    24),(Int
    45171733,Int
    856412266221181587,Int
    21),(Int
    54206099,Int
    5709413064779759723,Int
    24),(Int
    65047343,Int
    4757842450557051481,Int
    24),(Int
    78056833,Int
    247804226362015825,Int
    20),(Int
    93668203,Int
    6608112463123586747,Int
    25),(Int
    112401881,Int
    1376689638411589699,Int
    23),(Int
    134882263,Int
    9177930528088635901,Int
    26),(Int
    161858731,Int
    7648274712381010049,Int
    26),(Int
    194230481,Int
    3186781067811339753,Int
    25),(Int
    233076601,Int
    663912654667005953,Int
    23),(Int
    279691949,Int
    4426083924515754563,Int
    26),(Int
    335630353,Int
    7376806228758340429,Int
    27),(Int
    402756463,Int
    48026077520285669,Int
    20),(Int
    483307787,Int
    5122781269342057073,Int
    27),(Int
    579969349,Int
    4268984357259129137,Int
    27),(Int
    695963227,Int
    7114973844934943811,Int
    28),(Int
    835155913,Int
    5929144582541584783,Int
    28),(Int
    1002187163,Int
    617619185811393333,Int
    25),(Int
    1202624651,Int
    8234922098136039455,Int
    29),(Int
    1443149623,Int
    6862434883013541971,Int
    29),(Int
    1731779563,Int
    357418480311913773,Int
    25),(Int
    2078135531,Int
    4765579610448921293,Int
    29),(Int
    2493762643,Int
    7942632665608538591,Int
    30),(Int
    2992515199,Int
    3309430247035160405,Int
    29),(Int
    3591018241,Int
    5515717075012787271,Int
    30),(Int
    4309221899,Int
    9192861770781641709,Int
    31),(Int
    5171066297,Int
    7660718115355497017,Int
    31),(Int
    6205279567,Int
    6383931751891069761,Int
    31),(Int
    7446335483,Int
    1329985781179588333,Int
    29),(Int
    8935602619,Int
    2216642958858742015,Int
    30),(Int
    10722723161,Int
    3694404925160612267,Int
    31),(Int
    12867267797,Int
    6157341540115949263,Int
    32),(Int
    15440721377,Int
    1282779485812755651,Int
    30),(Int
    18528865703,Int
    8551863215397642261,Int
    33),(Int
    22234638851,Int
    890819084640777303,Int
    30),(Int
    26681566631,Int
    2969396947711947027,Int
    32),(Int
    32017880003,Int
    309312181610871977,Int
    29),(Int
    38421456013,Int
    4124162420469296211,Int
    33),(Int
    46105747229,Int
    6873604032117775405,Int
    34),(Int
    55326896741,Int
    1432000838311112129,Int
    32),(Int
    66392276177,Int
    1193334030347810553,Int
    32),(Int
    79670731433,Int
    3977780100130856927,Int
    34),(Int
    95604877727,Int
    6629633499704948593,Int
    35),(Int
    114725853301,Int
    172646705678443951,Int
    30),(Int
    137671023989,Int
    575489018811937629,Int
    32),(Int
    165205228889,Int
    3836593456372840199,Int
    35),(Int
    198246274687,Int
    6394322426636527325,Int
    36),(Int
    237895529659,Int
    5328602021422103605,Int
    36),(Int
    285474635629,Int
    4440501683924226201,Int
    36),(Int
    342569562761,Int
    7400836139739766199,Int
    37),(Int
    411083475323,Int
    3083681724818056003,Int
    36),(Int
    493300170481,Int
    1284867385097583665,Int
    35),(Int
    591960204599,Int
    8565782567001774073,Int
    38),(Int
    710352245527,Int
    7138152139085745311,Int
    38),(Int
    852422694637,Int
    5948460115872687585,Int
    38),(Int
    1022907233639,Int
    4957050096199058351,Int
    38),(Int
    1227488680427,Int
    4130875079963290535,Int
    38),(Int
    1472986416527,Int
    3442395899935288315,Int
    38),(Int
    1767583699907,Int
    5737326499650006151,Int
    39),(Int
    2121100439917,Int
    2390552708155269385,Int
    38),(Int
    2545320527903,Int
    996063628397011449,Int
    37),(Int
    3054384633659,Int
    6640424188932079035,Int
    40),(Int
    3665261560423,Int
    5533686824061451401,Int
    40),(Int
    4398313872521,Int
    9222811373407653915,Int
    41),(Int
    5277976647059,Int
    7685676144457159429,Int
    41),(Int
    6333571976483,Int
    6404730120368629123,Int
    41),(Int
    7600286371789,Int
    2668637550150294909,Int
    40),(Int
    9120343646191,Int
    8895458500457872893,Int
    42),(Int
    10944412375433,Int
    7412882083712320257,Int
    42),(Int
    13133294850551,Int
    6177401736412164183,Int
    42),(Int
    15759953820697,Int
    5147834780331776433,Int
    42),(Int
    18911944584839,Int
    1072465579235639315,Int
    40),(Int
    22694333501813,Int
    7149770528235642145,Int
    43),(Int
    27233200202177,Int
    2979071053431364413,Int
    42),(Int
    32679840242663,Int
    1241279605594479897,Int
    41),(Int
    39215808291301,Int
    8275197370607624801,Int
    44),(Int
    47058969949679,Int
    3447998904411212491,Int
    43),(Int
    56470763939783,Int
    1436666210167059381,Int
    42),(Int
    67764916727749,Int
    1197221841805716745,Int
    42),(Int
    81317900073323,Int
    7981478945369069699,Int
    45),(Int
    97581480088031,Int
    3325616227235633285,Int
    44),(Int
    117097776105689,Int
    5542693712056936913,Int
    45),(Int
    140517331326899,Int
    4618911426711740825,Int
    45),(Int
    168620797592327,Int
    3849092855592017097,Int
    45),(Int
    202344957110837,Int
    3207577379659307247,Int
    45),(Int
    242813948533111,Int
    5345962299429831765,Int
    46),(Int
    291376738239791,Int
    8909937165714618823,Int
    47),(Int
    349652085887761,Int
    3712473819047632555,Int
    46),(Int
    419582503065331,Int
    1546864091269781275,Int
    45),(Int
    503499003678427,Int
    5156213637565632409,Int
    47),(Int
    604198804414123,Int
    8593689395942569915,Int
    48),(Int
    725038565296949,Int
    7161407829952127767,Int
    48),(Int
    870046278356531,Int
    745979982286515183,Int
    45),(Int
    1044055534027841,Int
    4973199881910083119,Int
    48),(Int
    1252866640833481,Int
    259020827182801985,Int
    44),(Int
    1503439969000181,Int
    6907222058208035475,Int
    49),(Int
    1804127962800257,Int
    2878009190919951291,Int
    48),(Int
    2164953555360361,Int
    299792624054154309,Int
    45),(Int
    2597944266432433,Int
    999308746847181107,Int
    47),(Int
    3117533119718951,Int
    1665514578078618403,Int
    48),(Int
    3741039743662841,Int
    693964407532739155,Int
    47),(Int
    4489247692395509,Int
    4626429383551491517,Int
    50),(Int
    5387097230874631,Int
    7710715639252456949,Int
    51),(Int
    6464516677049609,Int
    1606399091510915659,Int
    49),(Int
    7757420012459563,Int
    5354663638369696637,Int
    51),(Int
    9308904014951479,Int
    2231109849320706117,Int
    50),(Int
    11170684817941799,Int
    7437032831069004279,Int
    52),(Int
    13404821781530213,Int
    3098763679612072587,Int
    51),(Int
    16085786137836413,Int
    5164606132686737109,Int
    52),(Int
    19302943365403697,Int
    8607676887811227891,Int
    53),(Int
    23163532038484451,Int
    7173064073176018721,Int
    53),(Int
    27796238446181363,Int
    2988776697156672123,Int
    52),(Int
    33355486135417657,Int
    4981294495261117009,Int
    53),(Int
    40026583362501191,Int
    8302157492101861143,Int
    54),(Int
    48031900035001457,Int
    1729616144187886737,Int
    52),(Int
    57638280042001759,Int
    2882693573646477365,Int
    53),(Int
    69165936050402159,Int
    1201122322352698065,Int
    52),(Int
    82999123260482599,Int
    8007482149017986309,Int
    55),(Int
    99598947912579133,Int
    6672901790848320973,Int
    55),(Int
    119518737495095009,Int
    347546968273349907,Int
    51),(Int
    143422484994114059,Int
    4633959576977997203,Int
    55),(Int
    172106981992936889,Int
    7723265961629994521,Int
    56),(Int
    206528378391524347,Int
    6436054968024992935,Int
    56),(Int
    247834054069829309,Int
    2681689570010412721,Int
    55),(Int
    297400864883795143,Int
    8938965233368043239,Int
    57),(Int
    356881037860554209,Int
    7449137694473368585,Int
    57),(Int
    428257245432665101,Int
    6207614745394473093,Int
    57),(Int
    513908694519198103,Int
    5173012287828727761,Int
    57),(Int
    616690433423037709,Int
    8621687146381213139,Int
    58),(Int
    740028520107645211,Int
    898092411081376417,Int
    55),(Int
    888034224129174191,Int
    2993641370271254933,Int
    57),(Int
    1065641068955008969,Int
    2494701141892712585,Int
    57),(Int
    1278769282746010901,Int
    4157835236487853859,Int
    58),(Int
    1534523139295213087,Int
    216553918567075721,Int
    54),(Int
    1841427767154255641,Int
    1443692790447171523,Int
    57),(Int
    2209713320585106689,Int
    2406154650745285959,Int
    58),(Int
    2651655984702128147,Int
    8020515502484286167,Int
    60),(Int
    3181987181642553871,Int
    1670940729684226235,Int
    58),(Int
    3818384617971064327,Int
    5569802432280754581,Int
    60),(Int
    4582061541565277261,Int
    1160375506725157187,Int
    58)]

    getFastRem :: Int -> FastRem
    getFastRem :: Int -> FastRem
    getFastRem Int
    n =
      (\(Int
    p, Int
    m, Int
    s) -> Int -> Int -> Int -> FastRem
    FastRem Int
    p Int
    m Int
    s) ((Int, Int, Int) -> FastRem) -> (Int, Int, Int) -> FastRem
    forall a b. (a -> b) -> a -> b
    $ Maybe (Int, Int, Int) -> (Int, Int, Int)
    forall a. HasCallStack => Maybe a -> a
    fromJust (Maybe (Int, Int, Int) -> (Int, Int, Int))
    -> Maybe (Int, Int, Int) -> (Int, Int, Int)
    forall a b. (a -> b) -> a -> b
    $
        ((Int, Int, Int) -> Bool)
    -> Vector (Int, Int, Int) -> Maybe (Int, Int, Int)
    forall a. Unbox a => (a -> Bool) -> Vector a -> Maybe a
    UI.find (\(Int
    p, Int
    _, Int
    _) -> Int
    p Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    n) Vector (Int, Int, Int)
    primesWithFastRem

    -- | For 64-bit architectures
    -- 'frmPrime' is a prime number such that for each @n@ >= 0
    -- it holds that @n@ \`'quot'\` 'frmPrime' = (n * '_frmMulHi') \`'shiftR'\` (64 + s).
    data FastRem = FastRem
      { FastRem -> Int
    frmPrime :: !Int
      , FastRem -> Int
    _frmMulHi :: !Int
      , FastRem -> Int
    _frmShift :: !Int
      } deriving (FastRem -> FastRem -> Bool
    (FastRem -> FastRem -> Bool)
    -> (FastRem -> FastRem -> Bool) -> Eq FastRem
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: FastRem -> FastRem -> Bool
    == :: FastRem -> FastRem -> Bool
    $c/= :: FastRem -> FastRem -> Bool
    /= :: FastRem -> FastRem -> Bool
    Eq, Eq FastRem
    Eq FastRem =>
    (FastRem -> FastRem -> Ordering)
    -> (FastRem -> FastRem -> Bool)
    -> (FastRem -> FastRem -> Bool)
    -> (FastRem -> FastRem -> Bool)
    -> (FastRem -> FastRem -> Bool)
    -> (FastRem -> FastRem -> FastRem)
    -> (FastRem -> FastRem -> FastRem)
    -> Ord FastRem
    FastRem -> FastRem -> Bool
    FastRem -> FastRem -> Ordering
    FastRem -> FastRem -> FastRem
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    $ccompare :: FastRem -> FastRem -> Ordering
    compare :: FastRem -> FastRem -> Ordering
    $c< :: FastRem -> FastRem -> Bool
    < :: FastRem -> FastRem -> Bool
    $c<= :: FastRem -> FastRem -> Bool
    <= :: FastRem -> FastRem -> Bool
    $c> :: FastRem -> FastRem -> Bool
    > :: FastRem -> FastRem -> Bool
    $c>= :: FastRem -> FastRem -> Bool
    >= :: FastRem -> FastRem -> Bool
    $cmax :: FastRem -> FastRem -> FastRem
    max :: FastRem -> FastRem -> FastRem
    $cmin :: FastRem -> FastRem -> FastRem
    min :: FastRem -> FastRem -> FastRem
    Ord, Int -> FastRem -> ShowS
    [FastRem] -> ShowS
    FastRem -> String
    (Int -> FastRem -> ShowS)
    -> (FastRem -> String) -> ([FastRem] -> ShowS) -> Show FastRem
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> FastRem -> ShowS
    showsPrec :: Int -> FastRem -> ShowS
    $cshow :: FastRem -> String
    show :: FastRem -> String
    $cshowList :: [FastRem] -> ShowS
    showList :: [FastRem] -> ShowS
    Show)

    fastRem :: Int -> FastRem -> Int
    #ifndef aarch64_HOST_ARCH
    fastRem :: Int -> FastRem -> Int
    fastRem !Int
    i (FastRem !Int
    p !Int
    m !Int
    s) = Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    p Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * Int
    q
      where
        q :: Int
    q = Word -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Word -> Word -> Word
    mulHi (Int -> Word
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Int
    i) (Int -> Word
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Int
    m)) Int -> Int -> Int
    forall a. Bits a => a -> Int -> a
    `unsafeShiftR` Int
    s
        mulHi :: Word -> Word -> Word
    mulHi (Exts.W# Word#
    x) (Exts.W# Word#
    y) =
          let (# Word#
    z, Word#
    _ #) = Word# -> Word# -> (# Word#, Word# #)
    Exts.timesWord2# Word#
    x Word#
    y in Word# -> Word
    Exts.W# Word#
    z
    #else
    -- At the moment GHC NCG does not make use of UMULH instruction,
    -- so timesWord2# is painfully slow on ARM. This is being worked on
    -- at https://gitlab.haskell.org/ghc/ghc/-/merge_requests/10832,
    -- but in the meantime we should resort to a usual division.
    fastRem !i (FastRem !p _ _) = i `rem` p
    #endif