{-|
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
    IntArray (PrimState m)
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
    IntArray (PrimState m)
next     <- 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
    ks (PrimState m) k
key      <- Int -> m (ks (PrimState m) k)
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
V.new Int
size
    vs (PrimState m) v
value    <- Int -> m (vs (PrimState m) v)
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
Int -> m (v (PrimState m) a)
V.new Int
size
    IntArray (PrimState m)
buckets  <- 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
1)
    IntArray (PrimState m)
refs     <- Int -> Int -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
Int -> a -> m (MutablePrimArray (PrimState m) a)
A.replicate Int
3 Int
0
    IntArray (PrimState m)
refs     IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
1 (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ -Int
1
    MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
dr       <- Dictionary_ (PrimState m) ks k vs v
-> m (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar Dictionary {ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
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
remSize :: FastRem
hashCode :: IntArray (PrimState m)
next :: IntArray (PrimState m)
key :: ks (PrimState m) k
value :: vs (PrimState m) v
buckets :: IntArray (PrimState m)
refs :: IntArray (PrimState m)
..}
    Dictionary (PrimState m) ks k vs v
-> m (Dictionary (PrimState m) ks k vs v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Dictionary (PrimState m) ks k vs v
 -> m (Dictionary (PrimState m) ks k vs v))
-> (MutVar (PrimState 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)
-> m (Dictionary (PrimState m) ks k vs v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
-> Dictionary (PrimState m) ks k vs v
forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
MutVar s (Dictionary_ s ks k vs v) -> Dictionary s ks k vs v
DRef (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
 -> m (Dictionary (PrimState m) ks k vs v))
-> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
-> m (Dictionary (PrimState m) ks k vs v)
forall a b. (a -> b) -> a -> b
$ MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
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 {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
..} <- 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
    IntArray (PrimState m)
hashCode        <- IntArray (PrimState m) -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> m (MutablePrimArray (PrimState m) a)
A.clone IntArray (PrimState m)
hashCode
    IntArray (PrimState m)
next            <- IntArray (PrimState m) -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> m (MutablePrimArray (PrimState m) a)
A.clone IntArray (PrimState m)
next
    ks (PrimState m) k
key             <- ks (PrimState m) k -> m (ks (PrimState m) k)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m (v (PrimState m) a)
V.clone ks (PrimState m) k
key
    vs (PrimState m) v
value           <- vs (PrimState m) v -> m (vs (PrimState m) v)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> m (v (PrimState m) a)
V.clone vs (PrimState m) v
value
    IntArray (PrimState m)
buckets         <- IntArray (PrimState m) -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> m (MutablePrimArray (PrimState m) a)
A.clone IntArray (PrimState m)
buckets
    IntArray (PrimState m)
refs            <- IntArray (PrimState m) -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> m (MutablePrimArray (PrimState m) a)
A.clone IntArray (PrimState m)
refs
    MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
dr              <- Dictionary_ (PrimState m) ks k vs v
-> m (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar Dictionary {ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
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
remSize :: FastRem
hashCode :: IntArray (PrimState m)
next :: IntArray (PrimState m)
key :: ks (PrimState m) k
value :: vs (PrimState m) v
buckets :: IntArray (PrimState m)
refs :: IntArray (PrimState m)
..}
    Dictionary (PrimState m) ks k vs v
-> m (Dictionary (PrimState m) ks k vs v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Dictionary (PrimState m) ks k vs v
 -> m (Dictionary (PrimState m) ks k vs v))
-> (MutVar (PrimState 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)
-> m (Dictionary (PrimState m) ks k vs v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
-> Dictionary (PrimState m) ks k vs v
forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
MutVar s (Dictionary_ s ks k vs v) -> Dictionary s ks k vs v
DRef (MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
 -> m (Dictionary (PrimState m) ks k vs v))
-> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
-> m (Dictionary (PrimState m) ks k vs v)
forall a b. (a -> b) -> a -> b
$ MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
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 {IntArray (PrimState m)
Mutable ks (PrimState m) k
Mutable vs (PrimState m) v
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 :: Mutable ks (PrimState m) k
value :: Mutable vs (PrimState m) v
remSize :: FastRem
..} <- 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
fremSize = FastRem
remSize
    PrimArray Int
fhashCode       <- IntArray (PrimState m) -> m (PrimArray Int)
forall (m :: * -> *) a.
PrimMonad m =>
MutablePrimArray (PrimState m) a -> m (PrimArray a)
A.unsafeFreeze IntArray (PrimState m)
hashCode
    PrimArray Int
fnext           <- IntArray (PrimState m) -> m (PrimArray Int)
forall (m :: * -> *) a.
PrimMonad m =>
MutablePrimArray (PrimState m) a -> m (PrimArray a)
A.unsafeFreeze IntArray (PrimState m)
next
    PrimArray Int
fbuckets        <- IntArray (PrimState m) -> m (PrimArray Int)
forall (m :: * -> *) a.
PrimMonad m =>
MutablePrimArray (PrimState m) a -> m (PrimArray a)
A.unsafeFreeze IntArray (PrimState m)
buckets
    Int
count           <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getCount
    Int
freeList        <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getFreeList
    Int
freeCount       <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getFreeCount
    ks k
fkey            <- Mutable ks (PrimState m) k -> m (ks k)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
VI.unsafeFreeze Mutable ks (PrimState m) k
key
    vs v
fvalue          <- Mutable vs (PrimState m) v -> m (vs v)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
VI.unsafeFreeze Mutable vs (PrimState m) v
value
    FrozenDictionary ks k vs v -> m (FrozenDictionary ks k vs v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return FrozenDictionary {ks k
vs v
Int
PrimArray Int
FastRem
fhashCode :: PrimArray Int
fnext :: PrimArray Int
fbuckets :: PrimArray Int
count :: Int
freeList :: Int
freeCount :: Int
fkey :: ks k
fvalue :: vs v
fremSize :: FastRem
fremSize :: FastRem
fhashCode :: PrimArray Int
fnext :: PrimArray Int
fbuckets :: PrimArray Int
count :: Int
freeList :: Int
freeCount :: Int
fkey :: ks k
fvalue :: vs v
..}

-- | /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
    IntArray (PrimState m)
hashCode <- PrimArray Int -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
PrimArray a -> m (MutablePrimArray (PrimState m) a)
A.unsafeThaw PrimArray Int
fhashCode
    IntArray (PrimState m)
next     <- PrimArray Int -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
PrimArray a -> m (MutablePrimArray (PrimState m) a)
A.unsafeThaw PrimArray Int
fnext
    IntArray (PrimState m)
buckets  <- PrimArray Int -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
PrimArray a -> m (MutablePrimArray (PrimState m) a)
A.unsafeThaw PrimArray Int
fbuckets
    IntArray (PrimState m)
refs     <- PrimArray Int -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
PrimArray a -> m (MutablePrimArray (PrimState m) a)
A.unsafeThaw (PrimArray Int -> m (IntArray (PrimState m)))
-> PrimArray Int -> m (IntArray (PrimState m))
forall a b. (a -> b) -> a -> b
$ Int -> [Int] -> PrimArray Int
forall a. Prim a => Int -> [a] -> PrimArray a
A.primArrayFromListN Int
3 [Int
count, Int
freeList, Int
freeCount]
    Mutable ks (PrimState m) k
key      <- ks k -> m (Mutable ks (PrimState m) k)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
v a -> m (Mutable v (PrimState m) a)
VI.unsafeThaw ks k
fkey
    Mutable vs (PrimState m) v
value    <- vs v -> m (Mutable vs (PrimState m) v)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
v a -> m (Mutable v (PrimState m) a)
VI.unsafeThaw vs v
fvalue
    MutVar
  (PrimState m)
  (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
dr       <- Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v
-> m (MutVar
        (PrimState m)
        (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar Dictionary {IntArray (PrimState m)
Mutable ks (PrimState m) k
Mutable vs (PrimState m) v
FastRem
hashCode :: IntArray (PrimState m)
next :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
refs :: IntArray (PrimState m)
key :: Mutable ks (PrimState m) k
value :: Mutable vs (PrimState m) v
remSize :: FastRem
remSize :: FastRem
hashCode :: IntArray (PrimState m)
next :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
refs :: IntArray (PrimState m)
key :: Mutable ks (PrimState m) k
value :: Mutable vs (PrimState m) v
..}
    Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v
-> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v
 -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v))
-> (MutVar
      (PrimState m)
      (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
    -> Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)
-> MutVar
     (PrimState m)
     (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
-> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MutVar
  (PrimState m)
  (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
-> Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v
forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
MutVar s (Dictionary_ s ks k vs v) -> Dictionary s ks k vs v
DRef (MutVar
   (PrimState m)
   (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
 -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v))
-> MutVar
     (PrimState m)
     (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
-> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)
forall a b. (a -> b) -> a -> b
$ MutVar
  (PrimState m)
  (Dictionary_ (PrimState m) (Mutable ks) k (Mutable vs) v)
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{vs (PrimState m) v
IntArray (PrimState m)
Mutable ks (PrimState m) k
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 :: Mutable ks (PrimState m) k
value :: vs (PrimState m) v
remSize :: FastRem
..} <- 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
    PrimArray Int
hcs <- IntArray (PrimState m) -> m (PrimArray Int)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> m (PrimArray a)
A.freeze IntArray (PrimState m)
hashCode
    ks k
ks <- Mutable ks (PrimState m) k -> m (ks k)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
VI.freeze Mutable ks (PrimState m) k
key
    Int
count <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getCount
    ks k -> m (ks k)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (ks k -> m (ks k)) -> (ks k -> ks k) -> ks k -> m (ks k)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> k -> Bool) -> ks k -> ks k
forall (v :: * -> *) a.
Vector v a =>
(Int -> a -> Bool) -> v a -> v a
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) (ks k -> ks k) -> (ks k -> ks k) -> ks k -> ks k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> ks k -> ks k
forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
VI.take Int
count (ks k -> m (ks k)) -> ks k -> m (ks k)
forall a b. (a -> b) -> a -> b
$ ks k
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{ks (PrimState m) k
IntArray (PrimState m)
Mutable vs (PrimState m) v
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 :: Mutable vs (PrimState m) v
remSize :: FastRem
..} <- 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
    PrimArray Int
hcs <- IntArray (PrimState m) -> m (PrimArray Int)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> m (PrimArray a)
A.freeze IntArray (PrimState m)
hashCode
    vs v
vs <- Mutable vs (PrimState m) v -> m (vs v)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
VI.freeze Mutable vs (PrimState m) v
value
    Int
count <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getCount
    vs v -> m (vs v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (vs v -> m (vs v)) -> (vs v -> vs v) -> vs v -> m (vs v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> v -> Bool) -> vs v -> vs v
forall (v :: * -> *) a.
Vector v a =>
(Int -> a -> Bool) -> v a -> v a
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) (vs v -> vs v) -> (vs v -> vs v) -> vs v -> vs v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> vs v -> vs v
forall (v :: * -> *) a. Vector v a => Int -> v a -> v a
VI.take Int
count (vs v -> m (vs v)) -> vs v -> m (vs v)
forall a b. (a -> b) -> a -> b
$ vs v
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_ (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
..} <- 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
  Int
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 Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0
    then v -> Maybe v
forall a. a -> Maybe a
Just (v -> Maybe v) -> m v -> m (Maybe v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> vs (PrimState m) v
value vs (PrimState m) v -> Int -> m v
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m a
!~ Int
i
    else Maybe v -> m (Maybe v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe v
forall a. Maybe a
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
  Int
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 Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0
      then Dictionary (PrimState m) ks k vs v -> Int -> m a
onFound Dictionary (PrimState m) ks k vs v
d Int
i
      else Dictionary (PrimState m) ks k vs v -> m a
onNothing Dictionary (PrimState m) ks k vs v
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
    Dictionary_ (PrimState m) ks k vs v
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
    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
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
                Int
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 Int
hc Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
hashCode'
                    then do
                        k
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
                        if k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
key'
                            then Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Int
i
                            else 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)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
i
                    else 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)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
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_ (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
..} <- 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' :: 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
        !targetBucket :: Int
targetBucket = Int
hashCode' Int -> FastRem -> Int
`fastRem` FastRem
remSize

        go :: Int -> m ()
go Int
i    | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = do
                    Int
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 Int
hc Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
hashCode'
                        then do
                            k
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
                            if k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
key'
                                then vs (PrimState m) v
value vs (PrimState m) v -> Int -> v -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> a -> m ()
<~~ Int
i (v -> m ()) -> v -> m ()
forall a b. (a -> b) -> a -> b
$ v
value'
                                else Int -> m ()
go (Int -> m ()) -> m Int -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
i
                        else Int -> m ()
go (Int -> m ()) -> m Int -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
i
                | Bool
otherwise = m ()
addOrResize

        addOrResize :: m ()
addOrResize = do
            Int
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 Int
freeCount Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0
                then do
                    Int
index <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getFreeList
                    Int
nxt <- IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
index
                    IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
getFreeList (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
nxt
                    IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
getFreeCount (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
freeCount Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
                    Int -> Int -> m ()
add Int
index Int
targetBucket
                else do
                    Int
count <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getCount
                    IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
getCount (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
count Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
                    Int
nextLen <- IntArray (PrimState m) -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> m Int
A.length IntArray (PrimState m)
next
                    if Int
count Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
nextLen
                        then do
                            Dictionary_ (PrimState m) ks k vs v
nd <- Dictionary_ (PrimState m) ks k vs v
-> Int -> Int -> k -> 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) =>
Dictionary_ (PrimState m) ks k vs v
-> Int -> Int -> k -> v -> m (Dictionary_ (PrimState m) ks k vs v)
resize Dictionary_ (PrimState m) ks k vs v
d Int
count Int
hashCode' k
key' v
value'
                            MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
-> Dictionary_ (PrimState m) ks k vs v -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
getDRef Dictionary_ (PrimState m) ks k vs v
nd
                        else Int -> Int -> m ()
add (Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
count) (Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
targetBucket)

        add :: Int -> Int -> m ()
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'
            Int
b <- IntArray (PrimState m)
buckets IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
targetBucket
            IntArray (PrimState m)
next 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
b
            ks (PrimState m) k
key ks (PrimState m) k -> Int -> k -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> a -> m ()
<~~ Int
index (k -> m ()) -> k -> m ()
forall a b. (a -> b) -> a -> b
$ k
key'
            vs (PrimState m) v
value vs (PrimState m) v -> Int -> v -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> a -> m ()
<~~ Int
index (v -> m ()) -> v -> m ()
forall a b. (a -> b) -> a -> b
$ v
value'
            IntArray (PrimState m)
buckets IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
targetBucket (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
index

    Int -> m ()
go (Int -> m ()) -> m Int -> m ()
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
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
         Int
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 Int
hc Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
hashCode'
             then do
                 k
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
                 if k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
key'
                     then vs (PrimState m) v
value vs (PrimState m) v -> Int -> v -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> a -> m ()
<~~ Int
i (v -> m ()) -> v -> m ()
forall a b. (a -> b) -> a -> b
$ v
value'
                     else Int -> m ()
go (Int -> m ()) -> m Int -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
i
             else Int -> m ()
go (Int -> m ()) -> m Int -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
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
    Int
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 Int
freeCount Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0
        then do
            Int
index <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getFreeList
            Int
nxt <- IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
index
            IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
getFreeList (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
nxt
            IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
getFreeCount (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
freeCount Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
            Int
-> Int
-> Int
-> k
-> 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
-> Int
-> k
-> v
-> Dictionary_ (PrimState m) ks k vs v
-> m ()
add Int
index Int
targetBucket Int
hashCode' k
key' v
value' Dictionary_ (PrimState m) ks k vs v
d
        else do
            Int
count <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getCount
            IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
getCount (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
count Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
            Int
nextLen <- IntArray (PrimState m) -> m Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> m Int
A.length IntArray (PrimState m)
next
            if Int
count Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
nextLen
                then do
                    Dictionary_ (PrimState m) ks k vs v
nd <- Dictionary_ (PrimState m) ks k vs v
-> Int -> Int -> k -> 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) =>
Dictionary_ (PrimState m) ks k vs v
-> Int -> Int -> k -> v -> m (Dictionary_ (PrimState m) ks k vs v)
resize Dictionary_ (PrimState m) ks k vs v
d Int
count Int
hashCode' k
key' v
value'
                    MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
-> Dictionary_ (PrimState m) ks k vs v -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
dref Dictionary_ (PrimState m) ks k vs v
nd
                else Int
-> Int
-> Int
-> k
-> 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
-> Int
-> k
-> v
-> Dictionary_ (PrimState m) ks k vs v
-> m ()
add (Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
count) (Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
targetBucket) Int
hashCode' k
key' v
value' Dictionary_ (PrimState m) ks k vs v
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'
    Int
b <- IntArray (PrimState m)
buckets IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
targetBucket
    IntArray (PrimState m)
next 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
b
    ks (PrimState m) k
key ks (PrimState m) k -> Int -> k -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> a -> m ()
<~~ Int
index (k -> m ()) -> k -> m ()
forall a b. (a -> b) -> a -> b
$ k
key'
    vs (PrimState m) v
value vs (PrimState m) v -> Int -> v -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> a -> m ()
<~~ Int
index (v -> m ()) -> v -> m ()
forall a b. (a -> b) -> a -> b
$ v
value'
    IntArray (PrimState m)
buckets IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
targetBucket (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
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

    IntArray (PrimState m)
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)

    IntArray (PrimState m)
hashCode <- IntArray (PrimState m) -> Int -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> Int -> m (MutablePrimArray (PrimState m) a)
A.growNoZ IntArray (PrimState m)
hashCode Int
delta
    IntArray (PrimState m)
next <- IntArray (PrimState m) -> Int -> m (IntArray (PrimState m))
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> Int -> m (MutablePrimArray (PrimState m) a)
A.growNoZ IntArray (PrimState m)
next Int
delta
    ks (PrimState m) k
key <- ks (PrimState m) k -> Int -> m (ks (PrimState m) k)
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
V.grow ks (PrimState m) k
key Int
delta
    vs (PrimState m) v
value <- vs (PrimState m) v -> Int -> m (vs (PrimState m) v)
forall (m :: * -> *) (v :: * -> * -> *) a.
(HasCallStack, PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
V.grow vs (PrimState m) v
value Int
delta

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

    let !targetBucket :: Int
targetBucket = Int
hashCode' Int -> FastRem -> Int
`fastRem` FastRem
newRemSize
    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'
    Int
b <- IntArray (PrimState m)
buckets IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
targetBucket
    IntArray (PrimState m)
next 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
b
    ks (PrimState m) k
key ks (PrimState m) k -> Int -> k -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> a -> m ()
<~~ Int
index (k -> m ()) -> k -> m ()
forall a b. (a -> b) -> a -> b
$ k
key'
    vs (PrimState m) v
value vs (PrimState m) v -> Int -> v -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> a -> m ()
<~~ Int
index (v -> m ()) -> v -> m ()
forall a b. (a -> b) -> a -> b
$ v
value'
    IntArray (PrimState m)
buckets IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
targetBucket (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
index
    let remSize :: FastRem
remSize = FastRem
newRemSize
    Dictionary_ (PrimState m) ks k vs v
-> m (Dictionary_ (PrimState m) ks k vs v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Dictionary{ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
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
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
next :: IntArray (PrimState m)
key :: ks (PrimState m) k
value :: vs (PrimState m) v
remSize :: FastRem
..}

{-# 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{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
..} <- 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' :: 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
        !bucket :: Int
bucket = Int
hashCode' Int -> FastRem -> Int
`fastRem` FastRem
remSize
        go :: Int -> Int -> m ()
go !Int
last !Int
i | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0 = do
            Int
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
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
            if Int
hc Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
hashCode' Bool -> Bool -> Bool
&& k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
key' then do
                Int
nxt <- IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
i
                if Int
last Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0
                    then IntArray (PrimState m)
buckets IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
bucket (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
nxt
                    else IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
last (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
nxt
                IntArray (PrimState m)
hashCode IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
i (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ -Int
1
                IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
i (Int -> m ()) -> m Int -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getFreeList
                ks (PrimState m) k -> Int -> m ()
forall x (m :: * -> *).
(MVector ks x, PrimMonad m) =>
ks (PrimState m) x -> Int -> m ()
forall (xs :: * -> * -> *) x (m :: * -> *).
(DeleteEntry xs, MVector xs x, PrimMonad m) =>
xs (PrimState m) x -> Int -> m ()
deleteEntry ks (PrimState m) k
key Int
i
                vs (PrimState m) v -> Int -> m ()
forall x (m :: * -> *).
(MVector vs x, PrimMonad m) =>
vs (PrimState m) x -> Int -> m ()
forall (xs :: * -> * -> *) x (m :: * -> *).
(DeleteEntry xs, MVector xs x, PrimMonad m) =>
xs (PrimState m) x -> Int -> m ()
deleteEntry vs (PrimState m) v
value Int
i
                IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
getFreeList (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
i
                Int
fc <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getFreeCount
                IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
getFreeCount (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
fc Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
            else Int -> Int -> m ()
go Int
i (Int -> m ()) -> m Int -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
i
            | Bool
otherwise = () -> m ()
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
    Int -> Int -> m ()
go (-Int
1) (Int -> m ()) -> m Int -> m ()
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
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
      Int
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
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
      if Int
hc Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
hashCode' Bool -> Bool -> Bool
&& k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
key' then do
          Int
nxt <- IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
i
          if Int
last Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0
              then IntArray (PrimState m)
buckets IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
bucket (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
nxt
              else IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
last (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
nxt
          IntArray (PrimState m)
hashCode IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
i (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ -Int
1
          IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
i (Int -> m ()) -> m Int -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getFreeList
          ks (PrimState m) k -> Int -> m ()
forall x (m :: * -> *).
(MVector ks x, PrimMonad m) =>
ks (PrimState m) x -> Int -> m ()
forall (xs :: * -> * -> *) x (m :: * -> *).
(DeleteEntry xs, MVector xs x, PrimMonad m) =>
xs (PrimState m) x -> Int -> m ()
deleteEntry ks (PrimState m) k
key Int
i
          vs (PrimState m) v -> Int -> m ()
forall x (m :: * -> *).
(MVector vs x, PrimMonad m) =>
vs (PrimState m) x -> Int -> m ()
forall (xs :: * -> * -> *) x (m :: * -> *).
(DeleteEntry xs, MVector xs x, PrimMonad m) =>
xs (PrimState m) x -> Int -> m ()
deleteEntry vs (PrimState m) v
value Int
i
          IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
getFreeList (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
i
          Int
fc <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getFreeCount
          IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> Int -> m ()
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> Int -> m ()
<~ Int
getFreeCount (Int -> m ()) -> Int -> m ()
forall a b. (a -> b) -> a -> b
$ Int
fc Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
        else 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
bucket Int
hashCode' Dictionary_ (PrimState m) ks k vs v
d k
key' Int
i (Int -> m ()) -> m Int -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< IntArray (PrimState m)
next IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
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 {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
..} <- 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
    Int
count           <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getCount
    Int
freeCount       <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getFreeCount
    Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
count Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
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_ (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
..} <- 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' :: Int
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
targetBucket = Int
hashCode' Int -> FastRem -> Int
`fastRem` FastRem
remSize

      onFound' :: v -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
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 -> Int -> m ()
onFound Dictionary (PrimState m) ks k vs v
dict Int
i = do
        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
..} <- 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
v <- vs (PrimState m) v
value vs (PrimState m) v -> Int -> m v
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m a
!~ Int
i
        v -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
onFound' (Maybe v -> v
f (v -> Maybe v
forall a. a -> Maybe a
Just v
v)) Dictionary_ (PrimState m) ks k vs v
d' Int
i

      onNothing :: Dictionary (PrimState m) ks k vs v -> m ()
onNothing Dictionary (PrimState m) ks k vs v
dict = do
        Dictionary_ (PrimState m) ks k vs v
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
        v -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
onFound' (Maybe v -> v
f Maybe v
forall a. Maybe a
Nothing) Dictionary_ (PrimState m) ks k vs v
d' (-Int
1)

  m () -> m ()
forall (f :: * -> *) a. Functor f => f a -> f ()
void (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Dictionary (PrimState m) ks k vs v
-> k
-> (Dictionary (PrimState m) ks k vs v -> Int -> m ())
-> (Dictionary (PrimState m) ks k vs v -> m ())
-> m ()
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
ht k
k Dictionary (PrimState m) ks k vs v -> Int -> m ()
onFound Dictionary (PrimState m) ks k vs v -> m ()
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_ (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
..} <- 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' :: Int
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
targetBucket = Int
hashCode' Int -> FastRem -> Int
`fastRem` FastRem
remSize

      onFound' :: v -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
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 -> Int -> m ()
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 -> Int -> m ()
onFound Dictionary (PrimState m) ks k vs v
dict Int
i = do
        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
..} <- 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
v <- vs (PrimState m) v
value vs (PrimState m) v -> Int -> m v
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m a
!~ Int
i
        case Maybe v -> Maybe v
f (v -> Maybe v
forall a. a -> Maybe a
Just v
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 -> m ()
onNothing Dictionary (PrimState m) ks k vs v
dict = do
        Dictionary_ (PrimState m) ks k vs v
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 Maybe v -> Maybe v
f Maybe v
forall a. Maybe a
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)

  m () -> m ()
forall (f :: * -> *) a. Functor f => f a -> f ()
void (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Dictionary (PrimState m) ks k vs v
-> k
-> (Dictionary (PrimState m) ks k vs v -> Int -> m ())
-> (Dictionary (PrimState m) ks k vs v -> m ())
-> m ()
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
ht k
k Dictionary (PrimState m) ks k vs v -> Int -> m ()
onFound Dictionary (PrimState m) ks k vs v -> m ()
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_ (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
..} <- 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' :: Int
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
targetBucket = Int
hashCode' Int -> FastRem -> Int
`fastRem` FastRem
remSize

      onFound' :: v -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
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 -> Int -> m ()
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 -> Int -> m ()
onFound Dictionary (PrimState m) ks k vs v
dict Int
i = do
        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
..} <- 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
v <- vs (PrimState m) v
value vs (PrimState m) v -> Int -> m v
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m a
!~ Int
i
        Maybe v
res <- Maybe v -> m (Maybe v)
f (v -> Maybe v
forall a. a -> Maybe a
Just v
v)
        case Maybe v
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 -> m ()
onNothing Dictionary (PrimState m) ks k vs v
dict = do
        Dictionary_ (PrimState m) ks k vs v
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
        Maybe v
res <- Maybe v -> m (Maybe v)
f Maybe v
forall a. Maybe a
Nothing
        case Maybe v
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)

  m () -> m ()
forall (f :: * -> *) a. Functor f => f a -> f ()
void (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Dictionary (PrimState m) ks k vs v
-> k
-> (Dictionary (PrimState m) ks k vs v -> Int -> m ())
-> (Dictionary (PrimState m) ks k vs v -> m ())
-> m ()
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
ht k
k Dictionary (PrimState m) ks k vs v -> Int -> m ()
onFound Dictionary (PrimState m) ks k vs v -> m ()
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
  Int
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
  Int
l2 <- 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
t2
  let smallest :: Int
smallest = Int -> Int -> Int
forall a. Ord a => a -> a -> a
min Int
l1 Int
l2
      greatest :: Int
greatest = Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
l1 Int
l2
      g :: k -> v -> v -> v
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
      (Dictionary (PrimState m) ks k vs v
tS, Dictionary (PrimState m) ks k vs v
tG) = if Int
smallest Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
l1 then (Dictionary (PrimState m) ks k vs v
t1, Dictionary (PrimState m) ks k vs v
t2) else (Dictionary (PrimState m) ks k vs v
t2, Dictionary (PrimState m) ks k vs v
t1)
  Dictionary (PrimState m) ks k vs v
ht <- 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) =>
Dictionary (PrimState m) ks k vs v
-> m (Dictionary (PrimState m) ks k vs v)
clone Dictionary (PrimState m) ks k vs v
tG
  Dictionary_ (PrimState m) ks k vs v
dictG <- 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
tG
  Dictionary_ (PrimState m) ks k vs v
dictS <- 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
tS
  PrimArray Int
hcsS <- MutablePrimArray (PrimState m) Int -> m (PrimArray Int)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> m (PrimArray a)
A.freeze (MutablePrimArray (PrimState m) Int -> m (PrimArray Int))
-> (Dictionary_ (PrimState m) ks k vs v
    -> MutablePrimArray (PrimState m) Int)
-> Dictionary_ (PrimState m) ks k vs v
-> m (PrimArray Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Dictionary_ (PrimState m) ks k vs v
-> MutablePrimArray (PrimState m) Int
forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> IntArray s
hashCode (Dictionary_ (PrimState m) ks k vs v -> m (PrimArray Int))
-> Dictionary_ (PrimState m) ks k vs v -> m (PrimArray Int)
forall a b. (a -> b) -> a -> b
$ Dictionary_ (PrimState m) ks k vs v
dictS
  let indices :: [Int]
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 -> Int -> Maybe Int
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 -> m ()
go !Int
i = do
        k
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
v <- Dictionary_ (PrimState m) ks k vs v -> vs (PrimState m) v
forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
value Dictionary_ (PrimState m) ks k vs v
dictS vs (PrimState m) v -> Int -> m v
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m a
!~ Int
i
        let
           hashCode' :: Int
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
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 -> Int -> m ()
onFound Dictionary (PrimState m) ks k vs v
dict Int
i = do
             d :: Dictionary_ (PrimState m) ks k vs v
d@Dictionary{ks (PrimState m) k
vs (PrimState m) v
MutablePrimArray (PrimState m) Int
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 :: MutablePrimArray (PrimState m) Int
next :: MutablePrimArray (PrimState m) Int
buckets :: MutablePrimArray (PrimState m) Int
refs :: MutablePrimArray (PrimState m) Int
key :: ks (PrimState m) k
value :: vs (PrimState m) v
remSize :: FastRem
..} <- 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
vG <- vs (PrimState m) v
value vs (PrimState m) v -> Int -> m v
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m a
!~ 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 (k -> v -> v -> v
g k
k v
v v
vG) (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
dict) Dictionary_ (PrimState m) ks k vs v
d Int
i

           onNothing :: Dictionary (PrimState m) ks k vs v -> m ()
onNothing Dictionary (PrimState m) ks k vs v
dict = do
             d :: Dictionary_ (PrimState m) ks k vs v
d@Dictionary{ks (PrimState m) k
vs (PrimState m) v
MutablePrimArray (PrimState m) Int
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 :: MutablePrimArray (PrimState m) Int
next :: MutablePrimArray (PrimState m) Int
buckets :: MutablePrimArray (PrimState m) Int
refs :: MutablePrimArray (PrimState m) Int
key :: ks (PrimState m) k
value :: vs (PrimState m) v
remSize :: FastRem
..} <- 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
             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
v (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
dict) Dictionary_ (PrimState m) ks k vs v
d
               (Int -> m ()) -> m Int -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MutablePrimArray (PrimState m) Int
buckets MutablePrimArray (PrimState m) Int -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
targetBucket

        m () -> m ()
forall (f :: * -> *) a. Functor f => f a -> f ()
void (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ Dictionary (PrimState m) ks k vs v
-> k
-> (Dictionary (PrimState m) ks k vs v -> Int -> m ())
-> (Dictionary (PrimState m) ks k vs v -> m ())
-> m ()
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
ht k
k Dictionary (PrimState m) ks k vs v -> Int -> m ()
onFound Dictionary (PrimState m) ks k vs v -> m ()
onNothing
  (Int -> m ()) -> [Int] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ Int -> m ()
go [Int]
indices
  Dictionary (PrimState m) ks k vs v
-> m (Dictionary (PrimState m) ks k vs v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Dictionary (PrimState m) ks k vs v
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
  [(k, v)]
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
  Dictionary (PrimState m) ks k vs v
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
10
  ((k, v) -> m ()) -> [(k, v)] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (Dictionary (PrimState m) ks k vs v -> (k, v) -> m ()
go Dictionary (PrimState m) ks k vs v
ht) [(k, v)]
kvs
  Dictionary (PrimState m) ks k vs v
-> m (Dictionary (PrimState m) ks k vs v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Dictionary (PrimState m) ks k vs v
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
      Maybe w
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 Maybe w
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
  [(k, v)]
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
  Dictionary (PrimState m) ks k vs v
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
10
  ((k, v) -> m ()) -> [(k, v)] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (Dictionary (PrimState m) ks k vs v -> (k, v) -> m ()
go Dictionary (PrimState m) ks k vs v
ht) [(k, v)]
kvs
  Dictionary (PrimState m) ks k vs v
-> m (Dictionary (PrimState m) ks k vs v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Dictionary (PrimState m) ks k vs v
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
      Maybe w
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 Maybe w
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
  [(k, v)]
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
  Dictionary (PrimState m) ks k vs v
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
10
  ((k, v) -> m ()) -> [(k, v)] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (Dictionary (PrimState m) ks k vs v -> (k, v) -> m ()
go Dictionary (PrimState m) ks k vs v
ht) [(k, v)]
kvs
  Dictionary (PrimState m) ks k vs v
-> m (Dictionary (PrimState m) ks k vs v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Dictionary (PrimState m) ks k vs v
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
      Maybe w
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 Maybe w
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
  [(k, v1)]
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
  Dictionary (PrimState m) ks k vs v3
ht <- Int -> m (Dictionary (PrimState m) ks k vs v3)
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
10
  ((k, v1) -> m ()) -> [(k, v1)] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (Dictionary (PrimState m) ks k vs v3 -> (k, v1) -> m ()
go Dictionary (PrimState m) ks k vs v3
ht) [(k, v1)]
kvs
  Dictionary (PrimState m) ks k vs v3
-> m (Dictionary (PrimState m) ks k vs v3)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Dictionary (PrimState m) ks k vs v3
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
      Maybe v2
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 Maybe v2
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
  [(k, v1)]
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
  Dictionary (PrimState m) ks k vs v3
ht <- Int -> m (Dictionary (PrimState m) ks k vs v3)
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
10
  ((k, v1) -> m ()) -> [(k, v1)] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ (Dictionary (PrimState m) ks k vs v3 -> (k, v1) -> m ()
go Dictionary (PrimState m) ks k vs v3
ht) [(k, v1)]
kvs
  Dictionary (PrimState m) ks k vs v3
-> m (Dictionary (PrimState m) ks k vs v3)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Dictionary (PrimState m) ks k vs v3
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
      Maybe v2
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 Maybe v2
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
    Dictionary (PrimState m) ks k vs v
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
    ((k, v) -> m ()) -> [(k, v)] -> m ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
(a -> m b) -> t a -> m ()
mapM_ ((k -> v -> m ()) -> (k, v) -> m ()
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (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, v)]
kv
    Dictionary (PrimState m) ks k vs v
-> m (Dictionary (PrimState m) ks k vs v)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Dictionary (PrimState m) ks k vs v
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 {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
..} <- 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
    PrimArray Int
hcs <- IntArray (PrimState m) -> m (PrimArray Int)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> m (PrimArray a)
A.freeze IntArray (PrimState m)
hashCode
    Int
count <- IntArray (PrimState m)
refs IntArray (PrimState m) -> Int -> m Int
forall (m :: * -> *).
PrimMonad m =>
MutablePrimArray (PrimState m) Int -> Int -> m Int
! Int
getCount
    let go :: Int -> [(k, v)] -> m [(k, v)]
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
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
v <- vs (PrimState m) v
value vs (PrimState m) v -> Int -> m v
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m a
!~ Int
i
              Int -> [(k, v)] -> m [(k, v)]
go (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) ((k
k, v
v) (k, v) -> [(k, v)] -> [(k, v)]
forall a. a -> [a] -> [a]
: [(k, v)]
xs)
        {-# INLINE go #-}
    Int -> [(k, v)] -> m [(k, v)]
go (Int
count Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
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