{-# LANGUAGE BangPatterns, CPP, PatternGuards, MagicHash, UnboxedTuples #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE Trustworthy #-}
{-# OPTIONS_HADDOCK not-home #-}
module Data.HashMap.Internal.Strict
(
HashMap
, empty
, singleton
, HM.null
, size
, HM.member
, HM.lookup
, (HM.!?)
, HM.findWithDefault
, lookupDefault
, (!)
, insert
, insertWith
, delete
, adjust
, update
, alter
, alterF
, isSubmapOf
, isSubmapOfBy
, union
, unionWith
, unionWithKey
, unions
, compose
, map
, mapWithKey
, traverseWithKey
, mapKeys
, difference
, differenceWith
, intersection
, intersectionWith
, intersectionWithKey
, foldMapWithKey
, foldr'
, foldl'
, foldrWithKey'
, foldlWithKey'
, HM.foldr
, HM.foldl
, foldrWithKey
, foldlWithKey
, HM.filter
, filterWithKey
, mapMaybe
, mapMaybeWithKey
, keys
, elems
, toList
, fromList
, fromListWith
, fromListWithKey
) where
import Data.Bits ((.&.), (.|.))
#if !MIN_VERSION_base(4,8,0)
import Control.Applicative (Applicative (..), (<$>))
#endif
import qualified Data.List as L
import Data.Hashable (Hashable)
import Prelude hiding (map, lookup)
import qualified Data.HashMap.Internal.Array as A
import qualified Data.HashMap.Internal as HM
import Data.HashMap.Internal hiding (
alter, alterF, adjust, fromList, fromListWith, fromListWithKey,
insert, insertWith,
differenceWith, intersectionWith, intersectionWithKey, map, mapWithKey,
mapMaybe, mapMaybeWithKey, singleton, update, unionWith, unionWithKey,
traverseWithKey)
import Data.HashMap.Internal.Unsafe (runST)
#if MIN_VERSION_base(4,8,0)
import Data.Functor.Identity
#endif
import Control.Applicative (Const (..))
import Data.Coerce
singleton :: (Hashable k) => k -> v -> HashMap k v
singleton :: k -> v -> HashMap k v
singleton k
k !v
v = k -> v -> HashMap k v
forall k v. Hashable k => k -> v -> HashMap k v
HM.singleton k
k v
v
insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v
insert :: k -> v -> HashMap k v -> HashMap k v
insert k
k !v
v = k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HM.insert k
k v
v
{-# INLINABLE insert #-}
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v
-> HashMap k v
insertWith :: (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
insertWith v -> v -> v
f k
k0 v
v0 HashMap k v
m0 = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
forall k.
Eq k =>
Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 v
v0 Int
0 HashMap k v
m0
where
h0 :: Hash
h0 = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k0
go :: Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go !Hash
h !k
k v
x !Int
_ HashMap k v
Empty = Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k v
x
go Hash
h k
k v
x Int
s t :: HashMap k v
t@(Leaf Hash
hy l :: Leaf k v
l@(L k
ky v
y))
| Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h = if k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k
then Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k (v -> v -> v
f v
x v
y)
else v
x v -> HashMap k v -> HashMap k v
`seq` (Hash -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision Hash
h Leaf k v
l (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x))
| Bool
otherwise = v
x v -> HashMap k v -> HashMap k v
`seq` (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy HashMap k v
t)
go Hash
h k
k v
x Int
s (BitmapIndexed Hash
b Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
0 =
let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.insert Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k v
x
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m) Array (HashMap k v)
ary'
| Bool
otherwise =
let st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
st' :: HashMap k v
st' = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
st'
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b Array (HashMap k v)
ary'
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go Hash
h k
k v
x Int
s (Full Array (HashMap k v)
ary) =
let st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
st' :: HashMap k v
st' = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
update16 Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
st'
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
go Hash
h k
k v
x Int
s t :: HashMap k v
t@(Collision Hash
hy Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h ((v -> v -> v) -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(v -> v -> v) -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWith v -> v -> v
f k
k v
x Array (Leaf k v)
v)
| Bool
otherwise = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k v
x Int
s (HashMap k v -> HashMap k v) -> HashMap k v -> HashMap k v
forall a b. (a -> b) -> a -> b
$ Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash -> Int -> Hash
mask Hash
hy Int
s) (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton HashMap k v
t)
{-# INLINABLE insertWith #-}
unsafeInsertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v
-> HashMap k v
unsafeInsertWith :: (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWith v -> v -> v
f k
k0 v
v0 HashMap k v
m0 = (k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWithKey ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f) k
k0 v
v0 HashMap k v
m0
{-# INLINABLE unsafeInsertWith #-}
unsafeInsertWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> k -> v -> HashMap k v
-> HashMap k v
unsafeInsertWithKey :: (k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWithKey k -> v -> v -> v
f k
k0 v
v0 HashMap k v
m0 = (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
forall s.
Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h0 k
k0 v
v0 Int
0 HashMap k v
m0)
where
h0 :: Hash
h0 = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k0
go :: Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go !Hash
h !k
k v
x !Int
_ HashMap k v
Empty = HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k v
x
go Hash
h k
k v
x Int
s t :: HashMap k v
t@(Leaf Hash
hy l :: Leaf k v
l@(L k
ky v
y))
| Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h = if k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k
then HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k (k -> v -> v -> v
f k
k v
x v
y)
else do
let l' :: Leaf k v
l' = v
x v -> Leaf k v -> Leaf k v
`seq` (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision Hash
h Leaf k v
l Leaf k v
l'
| Bool
otherwise = v
x v -> ST s (HashMap k v) -> ST s (HashMap k v)
`seq` Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy HashMap k v
t
go Hash
h k
k v
x Int
s t :: HashMap k v
t@(BitmapIndexed Hash
b Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
0 = do
Array (HashMap k v)
ary' <- Array (HashMap k v)
-> Int -> HashMap k v -> ST s (Array (HashMap k v))
forall e s. Array e -> Int -> e -> ST s (Array e)
A.insertM Array (HashMap k v)
ary Int
i (HashMap k v -> ST s (Array (HashMap k v)))
-> HashMap k v -> ST s (Array (HashMap k v))
forall a b. (a -> b) -> a -> b
$! Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k v
x
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m) Array (HashMap k v)
ary'
| Bool
otherwise = do
HashMap k v
st <- Array (HashMap k v) -> Int -> ST s (HashMap k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (HashMap k v)
ary Int
i
HashMap k v
st' <- Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
Array (HashMap k v) -> Int -> HashMap k v -> ST s ()
forall e s. Array e -> Int -> e -> ST s ()
A.unsafeUpdateM Array (HashMap k v)
ary Int
i HashMap k v
st'
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v
t
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go Hash
h k
k v
x Int
s t :: HashMap k v
t@(Full Array (HashMap k v)
ary) = do
HashMap k v
st <- Array (HashMap k v) -> Int -> ST s (HashMap k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (HashMap k v)
ary Int
i
HashMap k v
st' <- Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
Array (HashMap k v) -> Int -> HashMap k v -> ST s ()
forall e s. Array e -> Int -> e -> ST s ()
A.unsafeUpdateM Array (HashMap k v)
ary Int
i HashMap k v
st'
HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v
t
where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
go Hash
h k
k v
x Int
s t :: HashMap k v
t@(Collision Hash
hy Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy = HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h ((k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey k -> v -> v -> v
f k
k v
x Array (Leaf k v)
v)
| Bool
otherwise = Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x Int
s (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$ Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash -> Int -> Hash
mask Hash
hy Int
s) (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton HashMap k v
t)
{-# INLINABLE unsafeInsertWithKey #-}
adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v
adjust :: (v -> v) -> k -> HashMap k v -> HashMap k v
adjust v -> v
f k
k0 HashMap k v
m0 = Hash -> k -> Int -> HashMap k v -> HashMap k v
forall k. Eq k => Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 Int
0 HashMap k v
m0
where
h0 :: Hash
h0 = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k0
go :: Hash -> k -> Int -> HashMap k v -> HashMap k v
go !Hash
_ !k
_ !Int
_ HashMap k v
Empty = HashMap k v
forall k v. HashMap k v
Empty
go Hash
h k
k Int
_ t :: HashMap k v
t@(Leaf Hash
hy (L k
ky v
y))
| Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h Bool -> Bool -> Bool
&& k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k = Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k (v -> v
f v
y)
| Bool
otherwise = HashMap k v
t
go Hash
h k
k Int
s t :: HashMap k v
t@(BitmapIndexed Hash
b Array (HashMap k v)
ary)
| Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
0 = HashMap k v
t
| Bool
otherwise = let st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
st' :: HashMap k v
st' = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
st'
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b Array (HashMap k v)
ary'
where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
go Hash
h k
k Int
s (Full Array (HashMap k v)
ary) =
let i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
st :: HashMap k v
st = Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary Int
i
st' :: HashMap k v
st' = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
update16 Array (HashMap k v)
ary Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
st'
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
go Hash
h k
k Int
_ t :: HashMap k v
t@(Collision Hash
hy Array (Leaf k v)
v)
| Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h ((v -> v) -> k -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(v -> v) -> k -> Array (Leaf k v) -> Array (Leaf k v)
updateWith v -> v
f k
k Array (Leaf k v)
v)
| Bool
otherwise = HashMap k v
t
{-# INLINABLE adjust #-}
update :: (Eq k, Hashable k) => (a -> Maybe a) -> k -> HashMap k a -> HashMap k a
update :: (a -> Maybe a) -> k -> HashMap k a -> HashMap k a
update a -> Maybe a
f = (Maybe a -> Maybe a) -> k -> HashMap k a -> HashMap k a
forall k v.
(Eq k, Hashable k) =>
(Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
alter (Maybe a -> (a -> Maybe a) -> Maybe a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Maybe a
f)
{-# INLINABLE update #-}
alter :: (Eq k, Hashable k) => (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
alter :: (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
alter Maybe v -> Maybe v
f k
k HashMap k v
m =
case Maybe v -> Maybe v
f (k -> HashMap k v -> Maybe v
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
HM.lookup k
k HashMap k v
m) of
Maybe v
Nothing -> k -> HashMap k v -> HashMap k v
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
delete k
k HashMap k v
m
Just v
v -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k v
v HashMap k v
m
{-# INLINABLE alter #-}
alterF :: (Functor f, Eq k, Hashable k)
=> (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterF :: (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterF Maybe v -> f (Maybe v)
f = \ !k
k !HashMap k v
m ->
let !h :: Hash
h = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k
mv :: Maybe v
mv = Hash -> k -> HashMap k v -> Maybe v
forall k v. Eq k => Hash -> k -> HashMap k v -> Maybe v
lookup' Hash
h k
k HashMap k v
m
in ((Maybe v -> HashMap k v) -> f (Maybe v) -> f (HashMap k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe v -> f (Maybe v)
f Maybe v
mv) ((Maybe v -> HashMap k v) -> f (HashMap k v))
-> (Maybe v -> HashMap k v) -> f (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \Maybe v
fres ->
case Maybe v
fres of
Maybe v
Nothing -> HashMap k v -> (v -> HashMap k v) -> Maybe v -> HashMap k v
forall b a. b -> (a -> b) -> Maybe a -> b
maybe HashMap k v
m (HashMap k v -> v -> HashMap k v
forall a b. a -> b -> a
const (Hash -> k -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> HashMap k v -> HashMap k v
delete' Hash
h k
k HashMap k v
m)) Maybe v
mv
Just !v
v' -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> v -> HashMap k v -> HashMap k v
insert' Hash
h k
k v
v' HashMap k v
m
{-# INLINABLE [0] alterF #-}
#if MIN_VERSION_base(4,8,0)
test_bottom :: a
test_bottom :: a
test_bottom = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.HashMap.alterF internal error: hit test_bottom"
bogus# :: (# #) -> (# a #)
bogus# :: (# #) -> (# a #)
bogus# (# #)
_ = [Char] -> (# a #)
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.HashMap.alterF internal error: hit bogus#"
impossibleAdjust :: a
impossibleAdjust :: a
impossibleAdjust = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.HashMap.alterF internal error: impossible adjust"
{-# RULES
-- See detailed notes on alterF rules in Data.HashMap.Internal.
"alterFWeird" forall f. alterF f =
alterFWeird (f Nothing) (f (Just test_bottom)) f
"alterFconstant" forall (f :: Maybe a -> Identity (Maybe a)) x.
alterFWeird x x f = \ !k !m ->
Identity (case runIdentity x of {Nothing -> delete k m; Just a -> insert k a m})
"alterFinsertWith" [1] forall (f :: Maybe a -> Identity (Maybe a)) x y.
alterFWeird (coerce (Just x)) (coerce (Just y)) f =
coerce (insertModifying x (\mold -> case runIdentity (f (Just mold)) of
Nothing -> bogus# (# #)
Just !new -> (# new #)))
-- This rule is written a bit differently than the one for lazy
-- maps because the adjust here is strict. We could write it the
-- same general way anyway, but this seems simpler.
"alterFadjust" forall (f :: Maybe a -> Identity (Maybe a)) x.
alterFWeird (coerce Nothing) (coerce (Just x)) f =
coerce (adjust (\a -> case runIdentity (f (Just a)) of
Just a' -> a'
Nothing -> impossibleAdjust))
"alterFlookup" forall _ign1 _ign2 (f :: Maybe a -> Const r (Maybe a)) .
alterFWeird _ign1 _ign2 f = \ !k !m -> Const (getConst (f (lookup k m)))
#-}
alterFWeird
:: (Functor f, Eq k, Hashable k)
=> f (Maybe v)
-> f (Maybe v)
-> (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterFWeird :: f (Maybe v)
-> f (Maybe v)
-> (Maybe v -> f (Maybe v))
-> k
-> HashMap k v
-> f (HashMap k v)
alterFWeird f (Maybe v)
_ f (Maybe v)
_ Maybe v -> f (Maybe v)
f = (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
forall (f :: * -> *) k v.
(Functor f, Eq k, Hashable k) =>
(Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterFEager Maybe v -> f (Maybe v)
f
{-# INLINE [0] alterFWeird #-}
alterFEager :: (Functor f, Eq k, Hashable k)
=> (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterFEager :: (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterFEager Maybe v -> f (Maybe v)
f !k
k !HashMap k v
m = ((Maybe v -> HashMap k v) -> f (Maybe v) -> f (HashMap k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe v -> f (Maybe v)
f Maybe v
mv) ((Maybe v -> HashMap k v) -> f (HashMap k v))
-> (Maybe v -> HashMap k v) -> f (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \Maybe v
fres ->
case Maybe v
fres of
Maybe v
Nothing -> case LookupRes v
lookupRes of
LookupRes v
Absent -> HashMap k v
m
Present v
_ Int
collPos -> Int -> Hash -> k -> HashMap k v -> HashMap k v
forall k v. Int -> Hash -> k -> HashMap k v -> HashMap k v
deleteKeyExists Int
collPos Hash
h k
k HashMap k v
m
Just v
v' -> case LookupRes v
lookupRes of
LookupRes v
Absent -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v -> HashMap k v
insertNewKey Hash
h k
k v
v' HashMap k v
m
Present v
v Int
collPos -> v
v' v -> HashMap k v -> HashMap k v
`seq`
if v
v v -> v -> Bool
forall a. a -> a -> Bool
`ptrEq` v
v'
then HashMap k v
m
else Int -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Int -> Hash -> k -> v -> HashMap k v -> HashMap k v
insertKeyExists Int
collPos Hash
h k
k v
v' HashMap k v
m
where !h :: Hash
h = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k
!lookupRes :: LookupRes v
lookupRes = Hash -> k -> HashMap k v -> LookupRes v
forall k v. Eq k => Hash -> k -> HashMap k v -> LookupRes v
lookupRecordCollision Hash
h k
k HashMap k v
m
!mv :: Maybe v
mv = case LookupRes v
lookupRes of
LookupRes v
Absent -> Maybe v
forall a. Maybe a
Nothing
Present v
v Int
_ -> v -> Maybe v
forall a. a -> Maybe a
Just v
v
{-# INLINABLE alterFEager #-}
#endif
unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> HashMap k v -> HashMap k v
-> HashMap k v
unionWith :: (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
unionWith v -> v -> v
f = (k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
unionWithKey ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f)
{-# INLINE unionWith #-}
unionWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> HashMap k v -> HashMap k v
-> HashMap k v
unionWithKey :: (k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
unionWithKey k -> v -> v -> v
f = Int -> HashMap k v -> HashMap k v -> HashMap k v
go Int
0
where
go :: Int -> HashMap k v -> HashMap k v -> HashMap k v
go !Int
_ HashMap k v
t1 HashMap k v
Empty = HashMap k v
t1
go Int
_ HashMap k v
Empty HashMap k v
t2 = HashMap k v
t2
go Int
s t1 :: HashMap k v
t1@(Leaf Hash
h1 l1 :: Leaf k v
l1@(L k
k1 v
v1)) t2 :: HashMap k v
t2@(Leaf Hash
h2 l2 :: Leaf k v
l2@(L k
k2 v
v2))
| Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 = if k
k1 k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k2
then Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h1 k
k1 (k -> v -> v -> v
f k
k1 v
v1 v
v2)
else Hash -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision Hash
h1 Leaf k v
l1 Leaf k v
l2
| Bool
otherwise = Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
go Int
s t1 :: HashMap k v
t1@(Leaf Hash
h1 (L k
k1 v
v1)) t2 :: HashMap k v
t2@(Collision Hash
h2 Array (Leaf k v)
ls2)
| Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h1 ((k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey k -> v -> v -> v
f k
k1 v
v1 Array (Leaf k v)
ls2)
| Bool
otherwise = Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
go Int
s t1 :: HashMap k v
t1@(Collision Hash
h1 Array (Leaf k v)
ls1) t2 :: HashMap k v
t2@(Leaf Hash
h2 (L k
k2 v
v2))
| Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h1 ((k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey ((v -> v -> v) -> v -> v -> v
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((v -> v -> v) -> v -> v -> v)
-> (k -> v -> v -> v) -> k -> v -> v -> v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> v -> v -> v
f) k
k2 v
v2 Array (Leaf k v)
ls1)
| Bool
otherwise = Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
go Int
s t1 :: HashMap k v
t1@(Collision Hash
h1 Array (Leaf k v)
ls1) t2 :: HashMap k v
t2@(Collision Hash
h2 Array (Leaf k v)
ls2)
| Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h1 ((k -> v -> v -> v)
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
updateOrConcatWithKey k -> v -> v -> v
f Array (Leaf k v)
ls1 Array (Leaf k v)
ls2)
| Bool
otherwise = Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
go Int
s (BitmapIndexed Hash
b1 Array (HashMap k v)
ary1) (BitmapIndexed Hash
b2 Array (HashMap k v)
ary2) =
let b' :: Hash
b' = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
b2
ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
b1 Hash
b2 Array (HashMap k v)
ary1 Array (HashMap k v)
ary2
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull Hash
b' Array (HashMap k v)
ary'
go Int
s (BitmapIndexed Hash
b1 Array (HashMap k v)
ary1) (Full Array (HashMap k v)
ary2) =
let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
b1 Hash
fullNodeMask Array (HashMap k v)
ary1 Array (HashMap k v)
ary2
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
go Int
s (Full Array (HashMap k v)
ary1) (BitmapIndexed Hash
b2 Array (HashMap k v)
ary2) =
let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
fullNodeMask Hash
b2 Array (HashMap k v)
ary1 Array (HashMap k v)
ary2
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
go Int
s (Full Array (HashMap k v)
ary1) (Full Array (HashMap k v)
ary2) =
let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey)) Hash
fullNodeMask Hash
fullNodeMask
Array (HashMap k v)
ary1 Array (HashMap k v)
ary2
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
go Int
s (BitmapIndexed Hash
b1 Array (HashMap k v)
ary1) HashMap k v
t2
| Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m2 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
0 = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.insert Array (HashMap k v)
ary1 Int
i HashMap k v
t2
b' :: Hash
b' = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m2
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull Hash
b' Array (HashMap k v)
ary'
| Bool
otherwise = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Int -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Int -> (e -> e) -> Array e
A.updateWith' Array (HashMap k v)
ary1 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st1 ->
Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st1 HashMap k v
t2
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b1 Array (HashMap k v)
ary'
where
h2 :: Hash
h2 = HashMap k v -> Hash
forall k v. HashMap k v -> Hash
leafHashCode HashMap k v
t2
m2 :: Hash
m2 = Hash -> Int -> Hash
mask Hash
h2 Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b1 Hash
m2
go Int
s HashMap k v
t1 (BitmapIndexed Hash
b2 Array (HashMap k v)
ary2)
| Hash
b2 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
0 = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Int -> e -> Array e
A.insert Array (HashMap k v)
ary2 Int
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
t1
b' :: Hash
b' = Hash
b2 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m1
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull Hash
b' Array (HashMap k v)
ary'
| Bool
otherwise = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Int -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Int -> (e -> e) -> Array e
A.updateWith' Array (HashMap k v)
ary2 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st2 ->
Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
t1 HashMap k v
st2
in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b2 Array (HashMap k v)
ary'
where
h1 :: Hash
h1 = HashMap k v -> Hash
forall k v. HashMap k v -> Hash
leafHashCode HashMap k v
t1
m1 :: Hash
m1 = Hash -> Int -> Hash
mask Hash
h1 Int
s
i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b2 Hash
m1
go Int
s (Full Array (HashMap k v)
ary1) HashMap k v
t2 =
let h2 :: Hash
h2 = HashMap k v -> Hash
forall k v. HashMap k v -> Hash
leafHashCode HashMap k v
t2
i :: Int
i = Hash -> Int -> Int
index Hash
h2 Int
s
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Int -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Int -> (e -> e) -> Array e
update16With' Array (HashMap k v)
ary1 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st1 -> Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st1 HashMap k v
t2
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
go Int
s HashMap k v
t1 (Full Array (HashMap k v)
ary2) =
let h1 :: Hash
h1 = HashMap k v -> Hash
forall k v. HashMap k v -> Hash
leafHashCode HashMap k v
t1
i :: Int
i = Hash -> Int -> Int
index Hash
h1 Int
s
ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Int -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Int -> (e -> e) -> Array e
update16With' Array (HashMap k v)
ary2 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st2 -> Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
t1 HashMap k v
st2
in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
leafHashCode :: HashMap k v -> Hash
leafHashCode (Leaf Hash
h Leaf k v
_) = Hash
h
leafHashCode (Collision Hash
h Array (Leaf k v)
_) = Hash
h
leafHashCode HashMap k v
_ = [Char] -> Hash
forall a. HasCallStack => [Char] -> a
error [Char]
"leafHashCode"
goDifferentHash :: Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
| Hash
m1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
m2 = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
m1 (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
t1 HashMap k v
t2)
| Hash
m1 Hash -> Hash -> Bool
forall a. Ord a => a -> a -> Bool
< Hash
m2 = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash
m1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m2) (HashMap k v -> HashMap k v -> Array (HashMap k v)
forall a. a -> a -> Array a
A.pair HashMap k v
t1 HashMap k v
t2)
| Bool
otherwise = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash
m1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m2) (HashMap k v -> HashMap k v -> Array (HashMap k v)
forall a. a -> a -> Array a
A.pair HashMap k v
t2 HashMap k v
t1)
where
m1 :: Hash
m1 = Hash -> Int -> Hash
mask Hash
h1 Int
s
m2 :: Hash
m2 = Hash -> Int -> Hash
mask Hash
h2 Int
s
{-# INLINE unionWithKey #-}
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey k -> v1 -> v2
f = HashMap k v1 -> HashMap k v2
go
where
go :: HashMap k v1 -> HashMap k v2
go HashMap k v1
Empty = HashMap k v2
forall k v. HashMap k v
Empty
go (Leaf Hash
h (L k
k v1
v)) = Hash -> k -> v2 -> HashMap k v2
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k (k -> v1 -> v2
f k
k v1
v)
go (BitmapIndexed Hash
b Array (HashMap k v1)
ary) = Hash -> Array (HashMap k v2) -> HashMap k v2
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v2) -> HashMap k v2)
-> Array (HashMap k v2) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ (HashMap k v1 -> HashMap k v2)
-> Array (HashMap k v1) -> Array (HashMap k v2)
forall a b. (a -> b) -> Array a -> Array b
A.map' HashMap k v1 -> HashMap k v2
go Array (HashMap k v1)
ary
go (Full Array (HashMap k v1)
ary) = Array (HashMap k v2) -> HashMap k v2
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v2) -> HashMap k v2)
-> Array (HashMap k v2) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ (HashMap k v1 -> HashMap k v2)
-> Array (HashMap k v1) -> Array (HashMap k v2)
forall a b. (a -> b) -> Array a -> Array b
A.map' HashMap k v1 -> HashMap k v2
go Array (HashMap k v1)
ary
go (Collision Hash
h Array (Leaf k v1)
ary) =
Hash -> Array (Leaf k v2) -> HashMap k v2
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Array (Leaf k v2) -> HashMap k v2)
-> Array (Leaf k v2) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ (Leaf k v1 -> Leaf k v2) -> Array (Leaf k v1) -> Array (Leaf k v2)
forall a b. (a -> b) -> Array a -> Array b
A.map' (\ (L k
k v1
v) -> let !v' :: v2
v' = k -> v1 -> v2
f k
k v1
v in k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k v2
v') Array (Leaf k v1)
ary
{-# INLINE mapWithKey #-}
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2
map v1 -> v2
f = (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
forall k v1 v2. (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey ((v1 -> v2) -> k -> v1 -> v2
forall a b. a -> b -> a
const v1 -> v2
f)
{-# INLINE map #-}
mapMaybeWithKey :: (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybeWithKey :: (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybeWithKey k -> v1 -> Maybe v2
f = (HashMap k v1 -> Maybe (HashMap k v2))
-> (Leaf k v1 -> Maybe (Leaf k v2)) -> HashMap k v1 -> HashMap k v2
forall k v1 v2.
(HashMap k v1 -> Maybe (HashMap k v2))
-> (Leaf k v1 -> Maybe (Leaf k v2)) -> HashMap k v1 -> HashMap k v2
filterMapAux HashMap k v1 -> Maybe (HashMap k v2)
onLeaf Leaf k v1 -> Maybe (Leaf k v2)
onColl
where onLeaf :: HashMap k v1 -> Maybe (HashMap k v2)
onLeaf (Leaf Hash
h (L k
k v1
v)) | Just v2
v' <- k -> v1 -> Maybe v2
f k
k v1
v = HashMap k v2 -> Maybe (HashMap k v2)
forall a. a -> Maybe a
Just (Hash -> k -> v2 -> HashMap k v2
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k v2
v')
onLeaf HashMap k v1
_ = Maybe (HashMap k v2)
forall a. Maybe a
Nothing
onColl :: Leaf k v1 -> Maybe (Leaf k v2)
onColl (L k
k v1
v) | Just v2
v' <- k -> v1 -> Maybe v2
f k
k v1
v = Leaf k v2 -> Maybe (Leaf k v2)
forall a. a -> Maybe a
Just (k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k v2
v')
| Bool
otherwise = Maybe (Leaf k v2)
forall a. Maybe a
Nothing
{-# INLINE mapMaybeWithKey #-}
mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybe v1 -> Maybe v2
f = (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
forall k v1 v2.
(k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybeWithKey ((v1 -> Maybe v2) -> k -> v1 -> Maybe v2
forall a b. a -> b -> a
const v1 -> Maybe v2
f)
{-# INLINE mapMaybe #-}
traverseWithKey
:: Applicative f
=> (k -> v1 -> f v2)
-> HashMap k v1 -> f (HashMap k v2)
traverseWithKey :: (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)
traverseWithKey k -> v1 -> f v2
f = HashMap k v1 -> f (HashMap k v2)
go
where
go :: HashMap k v1 -> f (HashMap k v2)
go HashMap k v1
Empty = HashMap k v2 -> f (HashMap k v2)
forall (f :: * -> *) a. Applicative f => a -> f a
pure HashMap k v2
forall k v. HashMap k v
Empty
go (Leaf Hash
h (L k
k v1
v)) = Hash -> k -> v2 -> HashMap k v2
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k (v2 -> HashMap k v2) -> f v2 -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> v1 -> f v2
f k
k v1
v
go (BitmapIndexed Hash
b Array (HashMap k v1)
ary) = Hash -> Array (HashMap k v2) -> HashMap k v2
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v2) -> HashMap k v2)
-> f (Array (HashMap k v2)) -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (HashMap k v1 -> f (HashMap k v2))
-> Array (HashMap k v1) -> f (Array (HashMap k v2))
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Array a -> f (Array b)
A.traverse' HashMap k v1 -> f (HashMap k v2)
go Array (HashMap k v1)
ary
go (Full Array (HashMap k v1)
ary) = Array (HashMap k v2) -> HashMap k v2
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v2) -> HashMap k v2)
-> f (Array (HashMap k v2)) -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (HashMap k v1 -> f (HashMap k v2))
-> Array (HashMap k v1) -> f (Array (HashMap k v2))
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Array a -> f (Array b)
A.traverse' HashMap k v1 -> f (HashMap k v2)
go Array (HashMap k v1)
ary
go (Collision Hash
h Array (Leaf k v1)
ary) =
Hash -> Array (Leaf k v2) -> HashMap k v2
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Array (Leaf k v2) -> HashMap k v2)
-> f (Array (Leaf k v2)) -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Leaf k v1 -> f (Leaf k v2))
-> Array (Leaf k v1) -> f (Array (Leaf k v2))
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Array a -> f (Array b)
A.traverse' (\ (L k
k v1
v) -> (k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k (v2 -> Leaf k v2) -> v2 -> Leaf k v2
forall a b. (a -> b) -> a -> b
$!) (v2 -> Leaf k v2) -> f v2 -> f (Leaf k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> v1 -> f v2
f k
k v1
v) Array (Leaf k v1)
ary
{-# INLINE traverseWithKey #-}
differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v
differenceWith :: (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v
differenceWith v -> w -> Maybe v
f HashMap k v
a HashMap k w
b = (HashMap k v -> k -> v -> HashMap k v)
-> HashMap k v -> HashMap k v -> HashMap k v
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' HashMap k v -> k -> v -> HashMap k v
go HashMap k v
forall k v. HashMap k v
empty HashMap k v
a
where
go :: HashMap k v -> k -> v -> HashMap k v
go HashMap k v
m k
k v
v = case k -> HashMap k w -> Maybe w
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
HM.lookup k
k HashMap k w
b of
Maybe w
Nothing -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k v
v HashMap k v
m
Just w
w -> HashMap k v -> (v -> HashMap k v) -> Maybe v -> HashMap k v
forall b a. b -> (a -> b) -> Maybe a -> b
maybe HashMap k v
m (\v
y -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k v
y HashMap k v
m) (v -> w -> Maybe v
f v
v w
w)
{-# INLINABLE differenceWith #-}
intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> HashMap k v1
-> HashMap k v2 -> HashMap k v3
intersectionWith :: (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3
intersectionWith v1 -> v2 -> v3
f HashMap k v1
a HashMap k v2
b = (HashMap k v3 -> k -> v1 -> HashMap k v3)
-> HashMap k v3 -> HashMap k v1 -> HashMap k v3
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' HashMap k v3 -> k -> v1 -> HashMap k v3
go HashMap k v3
forall k v. HashMap k v
empty HashMap k v1
a
where
go :: HashMap k v3 -> k -> v1 -> HashMap k v3
go HashMap k v3
m k
k v1
v = case k -> HashMap k v2 -> Maybe v2
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
HM.lookup k
k HashMap k v2
b of
Just v2
w -> k -> v3 -> HashMap k v3 -> HashMap k v3
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k (v1 -> v2 -> v3
f v1
v v2
w) HashMap k v3
m
Maybe v2
_ -> HashMap k v3
m
{-# INLINABLE intersectionWith #-}
intersectionWithKey :: (Eq k, Hashable k) => (k -> v1 -> v2 -> v3)
-> HashMap k v1 -> HashMap k v2 -> HashMap k v3
intersectionWithKey :: (k -> v1 -> v2 -> v3)
-> HashMap k v1 -> HashMap k v2 -> HashMap k v3
intersectionWithKey k -> v1 -> v2 -> v3
f HashMap k v1
a HashMap k v2
b = (HashMap k v3 -> k -> v1 -> HashMap k v3)
-> HashMap k v3 -> HashMap k v1 -> HashMap k v3
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' HashMap k v3 -> k -> v1 -> HashMap k v3
go HashMap k v3
forall k v. HashMap k v
empty HashMap k v1
a
where
go :: HashMap k v3 -> k -> v1 -> HashMap k v3
go HashMap k v3
m k
k v1
v = case k -> HashMap k v2 -> Maybe v2
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
HM.lookup k
k HashMap k v2
b of
Just v2
w -> k -> v3 -> HashMap k v3 -> HashMap k v3
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k (k -> v1 -> v2 -> v3
f k
k v1
v v2
w) HashMap k v3
m
Maybe v2
_ -> HashMap k v3
m
{-# INLINABLE intersectionWithKey #-}
fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList :: [(k, v)] -> HashMap k v
fromList = (HashMap k v -> (k, v) -> HashMap k v)
-> HashMap k v -> [(k, v)] -> HashMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl' (\ HashMap k v
m (k
k, !v
v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HM.unsafeInsert k
k v
v HashMap k v
m) HashMap k v
forall k v. HashMap k v
empty
{-# INLINABLE fromList #-}
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWith :: (v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWith v -> v -> v
f = (HashMap k v -> (k, v) -> HashMap k v)
-> HashMap k v -> [(k, v)] -> HashMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl' (\ HashMap k v
m (k
k, v
v) -> (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWith v -> v -> v
f k
k v
v HashMap k v
m) HashMap k v
forall k v. HashMap k v
empty
{-# INLINE fromListWith #-}
fromListWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWithKey :: (k -> v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWithKey k -> v -> v -> v
f = (HashMap k v -> (k, v) -> HashMap k v)
-> HashMap k v -> [(k, v)] -> HashMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl' (\ HashMap k v
m (k
k, v
v) -> (k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWithKey k -> v -> v -> v
f k
k v
v HashMap k v
m) HashMap k v
forall k v. HashMap k v
empty
{-# INLINE fromListWithKey #-}
updateWith :: Eq k => (v -> v) -> k -> A.Array (Leaf k v) -> A.Array (Leaf k v)
updateWith :: (v -> v) -> k -> Array (Leaf k v) -> Array (Leaf k v)
updateWith v -> v
f k
k0 Array (Leaf k v)
ary0 = k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
forall t.
Eq t =>
t -> Array (Leaf t v) -> Int -> Int -> Array (Leaf t v)
go k
k0 Array (Leaf k v)
ary0 Int
0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
where
go :: t -> Array (Leaf t v) -> Int -> Int -> Array (Leaf t v)
go !t
k !Array (Leaf t v)
ary !Int
i !Int
n
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = Array (Leaf t v)
ary
| Bool
otherwise = case Array (Leaf t v) -> Int -> Leaf t v
forall a. Array a -> Int -> a
A.index Array (Leaf t v)
ary Int
i of
(L t
kx v
y) | t
k t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
kx -> let !v' :: v
v' = v -> v
f v
y in Array (Leaf t v) -> Int -> Leaf t v -> Array (Leaf t v)
forall e. Array e -> Int -> e -> Array e
A.update Array (Leaf t v)
ary Int
i (t -> v -> Leaf t v
forall k v. k -> v -> Leaf k v
L t
k v
v')
| Bool
otherwise -> t -> Array (Leaf t v) -> Int -> Int -> Array (Leaf t v)
go t
k Array (Leaf t v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
n
{-# INLINABLE updateWith #-}
updateOrSnocWith :: Eq k => (v -> v -> v) -> k -> v -> A.Array (Leaf k v)
-> A.Array (Leaf k v)
updateOrSnocWith :: (v -> v -> v) -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWith v -> v -> v
f = (k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f)
{-# INLINABLE updateOrSnocWith #-}
updateOrSnocWithKey :: Eq k => (k -> v -> v -> v) -> k -> v -> A.Array (Leaf k v)
-> A.Array (Leaf k v)
updateOrSnocWithKey :: (k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey k -> v -> v -> v
f k
k0 v
v0 Array (Leaf k v)
ary0 = k -> v -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k0 v
v0 Array (Leaf k v)
ary0 Int
0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
where
go :: k -> v -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go !k
k v
v !Array (Leaf k v)
ary !Int
i !Int
n
| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall e. (forall s. ST s (MArray s e)) -> Array e
A.run ((forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v))
-> (forall s. ST s (MArray s (Leaf k v))) -> Array (Leaf k v)
forall a b. (a -> b) -> a -> b
$ do
MArray s (Leaf k v)
mary <- Int -> ST s (MArray s (Leaf k v))
forall s a. Int -> ST s (MArray s a)
A.new_ (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
Array (Leaf k v)
-> Int -> MArray s (Leaf k v) -> Int -> Int -> ST s ()
forall e s. Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
A.copy Array (Leaf k v)
ary Int
0 MArray s (Leaf k v)
mary Int
0 Int
n
let !l :: Leaf k v
l = v
v v -> Leaf k v -> Leaf k v
`seq` (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v)
MArray s (Leaf k v) -> Int -> Leaf k v -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (Leaf k v)
mary Int
n Leaf k v
l
MArray s (Leaf k v) -> ST s (MArray s (Leaf k v))
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s (Leaf k v)
mary
| Bool
otherwise = case Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
ary Int
i of
(L k
kx v
y) | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx -> let !v' :: v
v' = k -> v -> v -> v
f k
k v
v v
y in Array (Leaf k v) -> Int -> Leaf k v -> Array (Leaf k v)
forall e. Array e -> Int -> e -> Array e
A.update Array (Leaf k v)
ary Int
i (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v')
| Bool
otherwise -> k -> v -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k v
v Array (Leaf k v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
n
{-# INLINABLE updateOrSnocWithKey #-}
leaf :: Hash -> k -> v -> HashMap k v
leaf :: Hash -> k -> v -> HashMap k v
leaf Hash
h k
k = \ !v
v -> Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v)
{-# INLINE leaf #-}