{-|
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 FlexibleContexts #-}
{-# LANGUAGE RecordWildCards  #-}
{-# LANGUAGE TypeFamilies     #-}
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.
--
-- *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
--
-- Different vectors could be used for keys and values:
--
-- - storable,
-- - mutable,
-- - unboxed.
--
-- In most cases unboxed vectors should be used. Nevertheless, it is up to you to decide about final form of hastable.
newtype Dictionary s ks k vs v = DRef { 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 {
    Dictionary_ s ks k vs v -> IntArray s
hashCode,
    Dictionary_ s ks k vs v -> IntArray s
next,
    Dictionary_ s ks k vs v -> IntArray s
buckets,
    Dictionary_ s ks k vs v -> IntArray s
refs :: IntArray s,
    Dictionary_ s ks k vs v -> ks s k
key :: ks s k,
    Dictionary_ s ks k vs v -> vs s v
value :: vs s v
}

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 {
    FrozenDictionary ks k vs v -> PrimArray Int
fhashCode,
    FrozenDictionary ks k vs v -> PrimArray Int
fnext,
    FrozenDictionary ks k vs v -> PrimArray Int
fbuckets :: A.PrimArray Int,
    FrozenDictionary ks k vs v -> Int
count, FrozenDictionary ks k vs v -> Int
freeList, FrozenDictionary ks k vs v -> Int
freeCount :: Int,
    FrozenDictionary ks k vs v -> ks k
fkey :: ks k,
    FrozenDictionary ks k vs v -> vs v
fvalue :: vs v
} 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
/= :: 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
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
min :: 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
max :: FrozenDictionary ks k vs v
-> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v
$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
>= :: 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
$c< :: forall (ks :: * -> *) k (vs :: * -> *) v.
(Ord (ks k), Ord (vs v)) =>
FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool
compare :: FrozenDictionary ks k vs v
-> FrozenDictionary ks k vs v -> Ordering
$ccompare :: forall (ks :: * -> *) k (vs :: * -> *) v.
(Ord (ks k), Ord (vs v)) =>
FrozenDictionary ks k vs v
-> FrozenDictionary ks k vs v -> Ordering
$cp1Ord :: forall (ks :: * -> *) k (vs :: * -> *) v.
(Ord (ks k), Ord (vs v)) =>
Eq (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
showList :: [FrozenDictionary ks k vs v] -> ShowS
$cshowList :: forall (ks :: * -> *) k (vs :: * -> *) v.
(Show (ks k), Show (vs v)) =>
[FrozenDictionary ks k vs v] -> ShowS
show :: FrozenDictionary ks k vs v -> String
$cshow :: forall (ks :: * -> *) k (vs :: * -> *) v.
(Show (ks k), Show (vs v)) =>
FrozenDictionary ks k vs v -> String
showsPrec :: Int -> FrozenDictionary ks k vs v -> ShowS
$cshowsPrec :: forall (ks :: * -> *) k (vs :: * -> *) v.
(Show (ks k), Show (vs v)) =>
Int -> 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 :: FrozenDictionary ks k vs v -> k -> Int
findElem FrozenDictionary{ks k
vs v
Int
PrimArray Int
fvalue :: vs v
fkey :: ks k
freeCount :: Int
freeList :: Int
count :: Int
fbuckets :: PrimArray Int
fnext :: PrimArray Int
fhashCode :: PrimArray Int
fvalue :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> vs v
fkey :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> ks k
freeCount :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> Int
freeList :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> Int
count :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> Int
fbuckets :: 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
fhashCode :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> PrimArray Int
..} 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 -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` PrimArray Int -> Int
forall a. Prim a => PrimArray a -> Int
A.sizeofPrimArray PrimArray Int
fbuckets) 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
!~ :: v (PrimState m) a -> Int -> m a
(!~) = 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

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

-- | Infix version of @unsafeWrite@.
(<~~) :: (MVector v a, PrimMonad m) => v (PrimState m) a -> Int -> a -> m ()
<~~ :: v (PrimState m) a -> Int -> a -> m ()
(<~~) = 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

-- | Infix version of @readPrimArray@.
(!) :: PrimMonad m => A.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 ()
<~ :: 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 :: Int -> m (Dictionary (PrimState m) ks k vs v)
initialize Int
capacity = do
    let size :: Int
size = Int -> Int
getPrime Int
capacity
    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.
(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.
(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 :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
IntArray s
-> IntArray s
-> IntArray s
-> IntArray s
-> ks s k
-> vs s v
-> Dictionary_ s ks k vs v
Dictionary {ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
..}
    Dictionary (PrimState m) ks k vs v
-> m (Dictionary (PrimState m) ks k vs v)
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 :: 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 :: 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)
..} = do
    Dictionary {ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
IntArray s
-> IntArray s
-> IntArray s
-> IntArray s
-> ks s k
-> vs s v
-> Dictionary_ s ks k vs v
Dictionary {ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
..}
    Dictionary (PrimState m) ks k vs v
-> m (Dictionary (PrimState m) ks k vs v)
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 :: 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 :: 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)
..} = do
    Dictionary {IntArray (PrimState m)
Mutable ks (PrimState m) k
Mutable vs (PrimState m) v
value :: Mutable vs (PrimState m) v
key :: Mutable ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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
    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 (m :: * -> *) a. Monad m => a -> m a
return FrozenDictionary :: forall (ks :: * -> *) k (vs :: * -> *) v.
PrimArray Int
-> PrimArray Int
-> PrimArray Int
-> Int
-> Int
-> Int
-> ks k
-> vs v
-> FrozenDictionary ks k vs v
FrozenDictionary {ks k
vs v
Int
PrimArray Int
fvalue :: vs v
fkey :: ks k
freeCount :: Int
freeList :: Int
count :: Int
fbuckets :: PrimArray Int
fnext :: PrimArray Int
fhashCode :: PrimArray Int
fvalue :: vs v
fkey :: ks k
freeCount :: Int
freeList :: Int
count :: Int
fbuckets :: PrimArray Int
fnext :: PrimArray Int
fhashCode :: PrimArray Int
..}

-- | /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 :: FrozenDictionary ks k vs v
-> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)
unsafeThaw FrozenDictionary {ks k
vs v
Int
PrimArray Int
fvalue :: vs v
fkey :: ks k
freeCount :: Int
freeList :: Int
count :: Int
fbuckets :: PrimArray Int
fnext :: PrimArray Int
fhashCode :: PrimArray Int
fvalue :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> vs v
fkey :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> ks k
freeCount :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> Int
freeList :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> Int
count :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> Int
fbuckets :: 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
fhashCode :: forall (ks :: * -> *) k (vs :: * -> *) v.
FrozenDictionary ks k vs v -> PrimArray Int
..} = do
    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 :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
IntArray s
-> IntArray s
-> IntArray s
-> IntArray s
-> ks s k
-> vs s v
-> Dictionary_ s ks k vs v
Dictionary {IntArray (PrimState m)
Mutable ks (PrimState m) k
Mutable vs (PrimState m) v
value :: Mutable vs (PrimState m) v
key :: Mutable ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: Mutable vs (PrimState m) v
key :: Mutable ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
..}
    Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v
-> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)
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 :: 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 :: 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)
..} = do
    Dictionary{vs (PrimState m) v
IntArray (PrimState m)
Mutable ks (PrimState m) k
value :: vs (PrimState m) v
key :: Mutable ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 (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 :: 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 :: 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)
..} = do
    Dictionary{ks (PrimState m) k
IntArray (PrimState m)
Mutable vs (PrimState m) v
value :: Mutable vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 (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 :: Dictionary (PrimState m) ks k vs v -> k -> m v
at Dictionary (PrimState m) ks k vs v
d k
k = 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 do
            Dictionary{ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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
            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 String -> m v
forall a. HasCallStack => String -> a
error String
"KeyNotFoundException!"
{-# 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' :: Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
at' Dictionary (PrimState m) ks k vs v
d k
k = 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 do
          Dictionary{ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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
          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 (f :: * -> *) a. Applicative f => a -> f a
pure 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 :: 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 :: Dictionary (PrimState m) ks k vs v -> k -> m Int
findEntry Dictionary (PrimState m) ks k vs v
d k
key' = do
    Dictionary{ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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
    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 (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 (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 -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` IntArray (PrimState m) -> Int
forall a s. Prim a => MutablePrimArray s a -> Int
A.length IntArray (PrimState m)
buckets)
{-# 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 :: Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
insert DRef{MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
getDRef :: 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)
..} 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)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` IntArray (PrimState m) -> Int
forall a s. Prim a => MutablePrimArray s a -> Int
A.length IntArray (PrimState m)
buckets

        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
                    if Int
count Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== IntArray (PrimState m) -> Int
forall a s. Prim a => MutablePrimArray s a -> Int
A.length IntArray (PrimState m)
next
                        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 (m :: * -> *) (v :: * -> * -> *) a (v :: * -> * -> *) a.
(PrimMonad m, MVector v a, MVector v a) =>
Dictionary_ (PrimState m) v a v a
-> Int -> Int -> a -> a -> m (Dictionary_ (PrimState m) v a v a)
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 -> Int -> k -> v -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v) -> Dictionary_ (PrimState m) ks k vs v -> Int -> m ()
insertWithIndex :: 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)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} 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
-> 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
key' v
value' MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
getDRef 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
=<< 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
-> 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
key' v
value' MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
getDRef 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
=<< 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 -> Int -> k -> v -> MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v) -> Dictionary_ (PrimState m) ks k vs v -> m ()
addOrResize :: 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)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..}  = 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
            if Int
count Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== IntArray (PrimState m) -> Int
forall a s. Prim a => MutablePrimArray s a -> Int
A.length IntArray (PrimState m)
next
                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 (m :: * -> *) (v :: * -> * -> *) a (v :: * -> * -> *) a.
(PrimMonad m, MVector v a, MVector v a) =>
Dictionary_ (PrimState m) v a v a
-> Int -> Int -> a -> a -> m (Dictionary_ (PrimState m) v a v a)
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 :: 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)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} = 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 :: Dictionary_ (PrimState m) v a v a
-> Int -> Int -> a -> a -> m (Dictionary_ (PrimState m) v a v a)
resize Dictionary{v (PrimState m) a
v (PrimState m) a
IntArray (PrimState m)
value :: v (PrimState m) a
key :: v (PrimState m) a
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} Int
index Int
hashCode' a
key' a
value' = do
    let newSize :: Int
newSize = Int -> Int
getPrime (Int
indexInt -> Int -> Int
forall a. Num a => a -> a -> a
*Int
2)
        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
    v (PrimState m) a
key <- v (PrimState m) a -> Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
V.grow v (PrimState m) a
key Int
delta
    v (PrimState m) a
value <- v (PrimState m) a -> Int -> m (v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
V.grow v (PrimState m) a
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 -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` Int
newSize
                    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 (m :: * -> *) a. Monad m => a -> m a
return ()
    Int -> m ()
go Int
0

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

{-# INLINE resize #-}

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

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

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

instance DeleteEntry B.MVector where
    deleteEntry :: 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 :: Dictionary (PrimState m) ks k vs v -> k -> m ()
delete DRef{MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
getDRef :: 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)
..} k
key' = do
    Dictionary{ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` IntArray (PrimState m) -> Int
forall a s. Prim a => MutablePrimArray s a -> Int
A.length IntArray (PrimState m)
buckets
        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 (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 (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 (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 :: 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)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} 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 (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 (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 (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 :: 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' :: 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 :: 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 (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 :: Dictionary (PrimState m) ks k vs v -> m Bool
null Dictionary (PrimState m) ks k vs v
ht = Bool -> m Bool
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 :: Dictionary (PrimState m) ks k vs v -> m Int
length DRef {MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
getDRef :: 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)
..} = do
    Dictionary {ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 (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 :: 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 :: 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 (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 :: 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 (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 (@'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'.
--
-- > 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 :: 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)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` IntArray (PrimState m) -> Int
forall a s. Prim a => MutablePrimArray s a -> Int
A.length IntArray (PrimState m)
buckets

      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)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 (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 :: 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)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` IntArray (PrimState m) -> Int
forall a s. Prim a => MutablePrimArray s a -> Int
A.length IntArray (PrimState m)
buckets

      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)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 (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 :: 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 :: (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 :: (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 -> Int -> Int
forall a. Integral a => a -> a -> a
`rem` MutablePrimArray (PrimState m) Int -> Int
forall a s. Prim a => MutablePrimArray s a -> Int
A.length (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
buckets 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
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: MutablePrimArray (PrimState m) Int
buckets :: MutablePrimArray (PrimState m) Int
next :: MutablePrimArray (PrimState m) Int
hashCode :: MutablePrimArray (PrimState m) Int
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: MutablePrimArray (PrimState m) Int
buckets :: MutablePrimArray (PrimState m) Int
next :: MutablePrimArray (PrimState m) Int
hashCode :: MutablePrimArray (PrimState m) Int
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 (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 :: 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 (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 (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 :: (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 (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 (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 :: 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 (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 (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 :: (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 (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 (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 :: (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 (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 (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 :: [(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 (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 :: Dictionary (PrimState m) ks k vs v -> m [(k, v)]
toList DRef {MutVar (PrimState m) (Dictionary_ (PrimState m) ks k vs v)
getDRef :: 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)
..} = do
    Dictionary {ks (PrimState m) k
vs (PrimState m) v
IntArray (PrimState m)
value :: vs (PrimState m) v
key :: ks (PrimState m) k
refs :: IntArray (PrimState m)
buckets :: IntArray (PrimState m)
next :: IntArray (PrimState m)
hashCode :: IntArray (PrimState m)
value :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> vs s v
key :: forall s (ks :: * -> * -> *) k (vs :: * -> * -> *) v.
Dictionary_ s ks k vs v -> ks s k
refs :: 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
next :: 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
..} <- 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 (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

primes :: UI.Vector Int
primes :: Vector Int
primes = [Int] -> Vector Int
forall a. Unbox a => [a] -> Vector a
UI.fromList [
    Int
3, Int
7, Int
11, Int
17, Int
23, Int
29, Int
37, Int
47, Int
59, Int
71, Int
89, Int
107, Int
131, Int
163, Int
197, Int
239, Int
293, Int
353, Int
431, Int
521, Int
631,
    Int
761, Int
919, Int
1103, Int
1327, Int
1597, Int
1931, Int
2333, Int
2801, Int
3371, Int
4049, Int
4861, Int
5839, Int
7013, Int
8419, Int
10103, Int
12143,
    Int
14591, Int
17519, Int
21023, Int
25229, Int
30293, Int
36353, Int
43627, Int
52361, Int
62851, Int
75431, Int
90523, Int
108631, Int
130363,
    Int
156437, Int
187751, Int
225307, Int
270371, Int
324449, Int
389357, Int
467237, Int
560689, Int
672827, Int
807403, Int
968897,
    Int
1162687, Int
1395263, Int
1674319, Int
2009191, Int
2411033, Int
2893249, Int
3471899, Int
4166287, Int
4999559, Int
5999471,
    Int
7199369, Int
8639249, Int
10367101, Int
12440537, Int
14928671, Int
17914409, Int
21497293, Int
25796759, Int
30956117,
    Int
37147349, Int
44576837, Int
53492207, Int
64190669, Int
77028803, Int
92434613, Int
110921543, Int
133105859, Int
159727031,
    Int
191672443, Int
230006941, Int
276008387, Int
331210079, Int
397452101, Int
476942527, Int
572331049, Int
686797261,
    Int
824156741, Int
988988137, Int
1186785773, Int
1424142949, Int
1708971541, Int
2050765853 ]

getPrime :: Int -> Int
getPrime :: Int -> Int
getPrime Int
n = Maybe Int -> Int
forall a. HasCallStack => Maybe a -> a
fromJust (Maybe Int -> Int) -> Maybe Int -> Int
forall a b. (a -> b) -> a -> b
$ (Int -> Bool) -> Vector Int -> Maybe Int
forall a. Unbox a => (a -> Bool) -> Vector a -> Maybe a
UI.find (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n) Vector Int
primes