{-# LANGUAGE BangPatterns, CPP, DeriveDataTypeable, MagicHash #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE PatternGuards #-}
{-# LANGUAGE RoleAnnotations #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE LambdaCase #-}
#if __GLASGOW_HASKELL__ >= 802
{-# LANGUAGE TypeInType #-}
{-# LANGUAGE UnboxedSums #-}
#endif
{-# OPTIONS_GHC -fno-full-laziness -funbox-strict-fields #-}

module Data.HashMap.Base
    (
      HashMap(..)
    , Leaf(..)

      -- * Construction
    , empty
    , singleton

      -- * Basic interface
    , null
    , size
    , member
    , lookup
    , lookupDefault
    , (!)
    , insert
    , insertWith
    , unsafeInsert
    , delete
    , adjust
    , update
    , alter
    , alterF

      -- * Combine
      -- ** Union
    , union
    , unionWith
    , unionWithKey
    , unions

      -- * Transformations
    , map
    , mapWithKey
    , traverseWithKey

      -- * Difference and intersection
    , difference
    , differenceWith
    , intersection
    , intersectionWith
    , intersectionWithKey

      -- * Folds
    , foldl'
    , foldlWithKey'
    , foldr
    , foldrWithKey

      -- * Filter
    , mapMaybe
    , mapMaybeWithKey
    , filter
    , filterWithKey

      -- * Conversions
    , keys
    , elems

      -- ** Lists
    , toList
    , fromList
    , fromListWith

      -- Internals used by the strict version
    , Hash
    , Bitmap
    , bitmapIndexedOrFull
    , collision
    , hash
    , mask
    , index
    , bitsPerSubkey
    , fullNodeMask
    , sparseIndex
    , two
    , unionArrayBy
    , update16
    , update16M
    , update16With'
    , updateOrConcatWith
    , updateOrConcatWithKey
    , filterMapAux
    , equalKeys
    , equalKeys1
    , lookupRecordCollision
    , LookupRes(..)
    , insert'
    , delete'
    , lookup'
    , insertNewKey
    , insertKeyExists
    , deleteKeyExists
    , insertModifying
    , ptrEq
    , adjust#
    ) where

#if __GLASGOW_HASKELL__ < 710
import Control.Applicative ((<$>), Applicative(pure))
import Data.Monoid (Monoid(mempty, mappend))
import Data.Traversable (Traversable(..))
import Data.Word (Word)
#endif
#if __GLASGOW_HASKELL__ >= 711
import Data.Semigroup (Semigroup((<>)))
#endif
import Control.DeepSeq (NFData(rnf))
import Control.Monad.ST (ST)
import Data.Bits ((.&.), (.|.), complement, popCount)
import Data.Data hiding (Typeable)
import qualified Data.Foldable as Foldable
import qualified Data.List as L
import GHC.Exts ((==#), build, reallyUnsafePtrEquality#)
import Prelude hiding (filter, foldr, lookup, map, null, pred)
import Text.Read hiding (step)

import qualified Data.HashMap.Array as A
import qualified Data.Hashable as H
import Data.Hashable (Hashable)
import Data.HashMap.Unsafe (runST)
import Data.HashMap.UnsafeShift (unsafeShiftL, unsafeShiftR)
import Data.HashMap.List (isPermutationBy, unorderedCompare)
import Data.Typeable (Typeable)

import GHC.Exts (isTrue#)
import qualified GHC.Exts as Exts

#if MIN_VERSION_base(4,9,0)
import Data.Functor.Classes
#endif

#if MIN_VERSION_hashable(1,2,5)
import qualified Data.Hashable.Lifted as H
#endif

#if __GLASGOW_HASKELL__ >= 802
import GHC.Exts (TYPE, Int (..), Int#)
#endif

#if MIN_VERSION_base(4,8,0)
import Data.Functor.Identity (Identity (..))
#endif
import Control.Applicative (Const (..))
import Data.Coerce (coerce)

-- | A set of values.  A set cannot contain duplicate values.
------------------------------------------------------------------------

-- | Convenience function.  Compute a hash value for the given value.
hash :: H.Hashable a => a -> Hash
hash :: a -> Hash
hash = Int -> Hash
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Hash) -> (a -> Int) -> a -> Hash
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Int
forall a. Hashable a => a -> Int
H.hash

data Leaf k v = L !k v
  deriving (Leaf k v -> Leaf k v -> Bool
(Leaf k v -> Leaf k v -> Bool)
-> (Leaf k v -> Leaf k v -> Bool) -> Eq (Leaf k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. (Eq k, Eq v) => Leaf k v -> Leaf k v -> Bool
/= :: Leaf k v -> Leaf k v -> Bool
$c/= :: forall k v. (Eq k, Eq v) => Leaf k v -> Leaf k v -> Bool
== :: Leaf k v -> Leaf k v -> Bool
$c== :: forall k v. (Eq k, Eq v) => Leaf k v -> Leaf k v -> Bool
Eq)

instance (NFData k, NFData v) => NFData (Leaf k v) where
    rnf :: Leaf k v -> ()
rnf (L k :: k
k v :: v
v) = k -> ()
forall a. NFData a => a -> ()
rnf k
k () -> () -> ()
forall a b. a -> b -> b
`seq` v -> ()
forall a. NFData a => a -> ()
rnf v
v

-- Invariant: The length of the 1st argument to 'Full' is
-- 2^bitsPerSubkey

-- | A map from keys to values.  A map cannot contain duplicate keys;
-- each key can map to at most one value.
data HashMap k v
    = Empty
    | BitmapIndexed !Bitmap !(A.Array (HashMap k v))
    | Leaf !Hash !(Leaf k v)
    | Full !(A.Array (HashMap k v))
    | Collision !Hash !(A.Array (Leaf k v))
      deriving (Typeable)

type role HashMap nominal representational

instance (NFData k, NFData v) => NFData (HashMap k v) where
    rnf :: HashMap k v -> ()
rnf Empty                 = ()
    rnf (BitmapIndexed _ ary :: Array (HashMap k v)
ary) = Array (HashMap k v) -> ()
forall a. NFData a => a -> ()
rnf Array (HashMap k v)
ary
    rnf (Leaf _ l :: Leaf k v
l)            = Leaf k v -> ()
forall a. NFData a => a -> ()
rnf Leaf k v
l
    rnf (Full ary :: Array (HashMap k v)
ary)            = Array (HashMap k v) -> ()
forall a. NFData a => a -> ()
rnf Array (HashMap k v)
ary
    rnf (Collision _ ary :: Array (Leaf k v)
ary)     = Array (Leaf k v) -> ()
forall a. NFData a => a -> ()
rnf Array (Leaf k v)
ary

instance Functor (HashMap k) where
    fmap :: (a -> b) -> HashMap k a -> HashMap k b
fmap = (a -> b) -> HashMap k a -> HashMap k b
forall v1 v2 k. (v1 -> v2) -> HashMap k v1 -> HashMap k v2
map

instance Foldable.Foldable (HashMap k) where
    foldr :: (a -> b -> b) -> b -> HashMap k a -> b
foldr f :: a -> b -> b
f = (k -> a -> b -> b) -> b -> HashMap k a -> b
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey ((a -> b -> b) -> k -> a -> b -> b
forall a b. a -> b -> a
const a -> b -> b
f)

#if __GLASGOW_HASKELL__ >= 711
instance (Eq k, Hashable k) => Semigroup (HashMap k v) where
  <> :: HashMap k v -> HashMap k v -> HashMap k v
(<>) = HashMap k v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
HashMap k v -> HashMap k v -> HashMap k v
union
  {-# INLINE (<>) #-}
#endif

instance (Eq k, Hashable k) => Monoid (HashMap k v) where
  mempty :: HashMap k v
mempty = HashMap k v
forall k v. HashMap k v
empty
  {-# INLINE mempty #-}
#if __GLASGOW_HASKELL__ >= 711
  mappend :: HashMap k v -> HashMap k v -> HashMap k v
mappend = HashMap k v -> HashMap k v -> HashMap k v
forall a. Semigroup a => a -> a -> a
(<>)
#else
  mappend = union
#endif
  {-# INLINE mappend #-}

instance (Data k, Data v, Eq k, Hashable k) => Data (HashMap k v) where
    gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> HashMap k v -> c (HashMap k v)
gfoldl f :: forall d b. Data d => c (d -> b) -> d -> c b
f z :: forall g. g -> c g
z m :: HashMap k v
m   = ([(k, v)] -> HashMap k v) -> c ([(k, v)] -> HashMap k v)
forall g. g -> c g
z [(k, v)] -> HashMap k v
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList c ([(k, v)] -> HashMap k v) -> [(k, v)] -> c (HashMap k v)
forall d b. Data d => c (d -> b) -> d -> c b
`f` HashMap k v -> [(k, v)]
forall k v. HashMap k v -> [(k, v)]
toList HashMap k v
m
    toConstr :: HashMap k v -> Constr
toConstr _     = Constr
fromListConstr
    gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (HashMap k v)
gunfold k :: forall b r. Data b => c (b -> r) -> c r
k z :: forall r. r -> c r
z c :: Constr
c  = case Constr -> Int
constrIndex Constr
c of
        1 -> c ([(k, v)] -> HashMap k v) -> c (HashMap k v)
forall b r. Data b => c (b -> r) -> c r
k (([(k, v)] -> HashMap k v) -> c ([(k, v)] -> HashMap k v)
forall r. r -> c r
z [(k, v)] -> HashMap k v
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList)
        _ -> [Char] -> c (HashMap k v)
forall a. HasCallStack => [Char] -> a
error "gunfold"
    dataTypeOf :: HashMap k v -> DataType
dataTypeOf _   = DataType
hashMapDataType
    dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (HashMap k v))
dataCast2 f :: forall d e. (Data d, Data e) => c (t d e)
f    = c (t k v) -> Maybe (c (HashMap k v))
forall k1 k2 k3 (c :: k1 -> *) (t :: k2 -> k3 -> k1)
       (t' :: k2 -> k3 -> k1) (a :: k2) (b :: k3).
(Typeable t, Typeable t') =>
c (t a b) -> Maybe (c (t' a b))
gcast2 c (t k v)
forall d e. (Data d, Data e) => c (t d e)
f

fromListConstr :: Constr
fromListConstr :: Constr
fromListConstr = DataType -> [Char] -> [[Char]] -> Fixity -> Constr
mkConstr DataType
hashMapDataType "fromList" [] Fixity
Prefix

hashMapDataType :: DataType
hashMapDataType :: DataType
hashMapDataType = [Char] -> [Constr] -> DataType
mkDataType "Data.HashMap.Base.HashMap" [Constr
fromListConstr]

type Hash   = Word
type Bitmap = Word
type Shift  = Int

#if MIN_VERSION_base(4,9,0)
instance Show2 HashMap where
    liftShowsPrec2 :: (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> HashMap a b
-> ShowS
liftShowsPrec2 spk :: Int -> a -> ShowS
spk slk :: [a] -> ShowS
slk spv :: Int -> b -> ShowS
spv slv :: [b] -> ShowS
slv d :: Int
d m :: HashMap a b
m =
        (Int -> [(a, b)] -> ShowS) -> [Char] -> Int -> [(a, b)] -> ShowS
forall a. (Int -> a -> ShowS) -> [Char] -> Int -> a -> ShowS
showsUnaryWith ((Int -> (a, b) -> ShowS)
-> ([(a, b)] -> ShowS) -> Int -> [(a, b)] -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> (a, b) -> ShowS
sp [(a, b)] -> ShowS
sl) "fromList" Int
d (HashMap a b -> [(a, b)]
forall k v. HashMap k v -> [(k, v)]
toList HashMap a b
m)
      where
        sp :: Int -> (a, b) -> ShowS
sp = (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> (a, b)
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> f a b
-> ShowS
liftShowsPrec2 Int -> a -> ShowS
spk [a] -> ShowS
slk Int -> b -> ShowS
spv [b] -> ShowS
slv
        sl :: [(a, b)] -> ShowS
sl = (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [(a, b)]
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [f a b]
-> ShowS
liftShowList2 Int -> a -> ShowS
spk [a] -> ShowS
slk Int -> b -> ShowS
spv [b] -> ShowS
slv

instance Show k => Show1 (HashMap k) where
    liftShowsPrec :: (Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> HashMap k a -> ShowS
liftShowsPrec = (Int -> k -> ShowS)
-> ([k] -> ShowS)
-> (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> Int
-> HashMap k a
-> ShowS
forall (f :: * -> * -> *) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> f a b
-> ShowS
liftShowsPrec2 Int -> k -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec [k] -> ShowS
forall a. Show a => [a] -> ShowS
showList

instance (Eq k, Hashable k, Read k) => Read1 (HashMap k) where
    liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (HashMap k a)
liftReadsPrec rp :: Int -> ReadS a
rp rl :: ReadS [a]
rl = ([Char] -> ReadS (HashMap k a)) -> Int -> ReadS (HashMap k a)
forall a. ([Char] -> ReadS a) -> Int -> ReadS a
readsData (([Char] -> ReadS (HashMap k a)) -> Int -> ReadS (HashMap k a))
-> ([Char] -> ReadS (HashMap k a)) -> Int -> ReadS (HashMap k a)
forall a b. (a -> b) -> a -> b
$
        (Int -> ReadS [(k, a)])
-> [Char]
-> ([(k, a)] -> HashMap k a)
-> [Char]
-> ReadS (HashMap k a)
forall a t.
(Int -> ReadS a) -> [Char] -> (a -> t) -> [Char] -> ReadS t
readsUnaryWith ((Int -> ReadS (k, a)) -> ReadS [(k, a)] -> Int -> ReadS [(k, a)]
forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a)
liftReadsPrec Int -> ReadS (k, a)
rp' ReadS [(k, a)]
rl') "fromList" [(k, a)] -> HashMap k a
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList
      where
        rp' :: Int -> ReadS (k, a)
rp' = (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (k, a)
forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a)
liftReadsPrec Int -> ReadS a
rp ReadS [a]
rl
        rl' :: ReadS [(k, a)]
rl' = (Int -> ReadS a) -> ReadS [a] -> ReadS [(k, a)]
forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> ReadS [f a]
liftReadList Int -> ReadS a
rp ReadS [a]
rl
#endif

instance (Eq k, Hashable k, Read k, Read e) => Read (HashMap k e) where
    readPrec :: ReadPrec (HashMap k e)
readPrec = ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (HashMap k e) -> ReadPrec (HashMap k e))
-> ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a. Int -> ReadPrec a -> ReadPrec a
prec 10 (ReadPrec (HashMap k e) -> ReadPrec (HashMap k e))
-> ReadPrec (HashMap k e) -> ReadPrec (HashMap k e)
forall a b. (a -> b) -> a -> b
$ do
      Ident "fromList" <- ReadPrec Lexeme
lexP
      [(k, e)]
xs <- ReadPrec [(k, e)]
forall a. Read a => ReadPrec a
readPrec
      HashMap k e -> ReadPrec (HashMap k e)
forall (m :: * -> *) a. Monad m => a -> m a
return ([(k, e)] -> HashMap k e
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList [(k, e)]
xs)

    readListPrec :: ReadPrec [HashMap k e]
readListPrec = ReadPrec [HashMap k e]
forall a. Read a => ReadPrec [a]
readListPrecDefault

instance (Show k, Show v) => Show (HashMap k v) where
    showsPrec :: Int -> HashMap k v -> ShowS
showsPrec d :: Int
d m :: HashMap k v
m = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> 10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
      [Char] -> ShowS
showString "fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, v)] -> ShowS
forall a. Show a => a -> ShowS
shows (HashMap k v -> [(k, v)]
forall k v. HashMap k v -> [(k, v)]
toList HashMap k v
m)

instance Traversable (HashMap k) where
    traverse :: (a -> f b) -> HashMap k a -> f (HashMap k b)
traverse f :: a -> f b
f = (k -> a -> f b) -> HashMap k a -> f (HashMap k b)
forall (f :: * -> *) k v1 v2.
Applicative f =>
(k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)
traverseWithKey ((a -> f b) -> k -> a -> f b
forall a b. a -> b -> a
const a -> f b
f)
    {-# INLINABLE traverse #-}

#if MIN_VERSION_base(4,9,0)
instance Eq2 HashMap where
    liftEq2 :: (a -> b -> Bool)
-> (c -> d -> Bool) -> HashMap a c -> HashMap b d -> Bool
liftEq2 = (a -> b -> Bool)
-> (c -> d -> Bool) -> HashMap a c -> HashMap b d -> Bool
forall a b c d.
(a -> b -> Bool)
-> (c -> d -> Bool) -> HashMap a c -> HashMap b d -> Bool
equal2

instance Eq k => Eq1 (HashMap k) where
    liftEq :: (a -> b -> Bool) -> HashMap k a -> HashMap k b -> Bool
liftEq = (a -> b -> Bool) -> HashMap k a -> HashMap k b -> Bool
forall k v v'.
Eq k =>
(v -> v' -> Bool) -> HashMap k v -> HashMap k v' -> Bool
equal1
#endif

instance (Eq k, Eq v) => Eq (HashMap k v) where
    == :: HashMap k v -> HashMap k v -> Bool
(==) = (v -> v -> Bool) -> HashMap k v -> HashMap k v -> Bool
forall k v v'.
Eq k =>
(v -> v' -> Bool) -> HashMap k v -> HashMap k v' -> Bool
equal1 v -> v -> Bool
forall a. Eq a => a -> a -> Bool
(==)

-- We rely on there being no Empty constructors in the tree!
-- This ensures that two equal HashMaps will have the same
-- shape, modulo the order of entries in Collisions.
equal1 :: Eq k
       => (v -> v' -> Bool)
       -> HashMap k v -> HashMap k v' -> Bool
equal1 :: (v -> v' -> Bool) -> HashMap k v -> HashMap k v' -> Bool
equal1 eq :: v -> v' -> Bool
eq = HashMap k v -> HashMap k v' -> Bool
go
  where
    go :: HashMap k v -> HashMap k v' -> Bool
go Empty Empty = Bool
True
    go (BitmapIndexed bm1 :: Hash
bm1 ary1 :: Array (HashMap k v)
ary1) (BitmapIndexed bm2 :: Hash
bm2 ary2 :: Array (HashMap k v')
ary2)
      = Hash
bm1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
bm2 Bool -> Bool -> Bool
&& (HashMap k v -> HashMap k v' -> Bool)
-> Array (HashMap k v) -> Array (HashMap k v') -> Bool
forall a b. (a -> b -> Bool) -> Array a -> Array b -> Bool
A.sameArray1 HashMap k v -> HashMap k v' -> Bool
go Array (HashMap k v)
ary1 Array (HashMap k v')
ary2
    go (Leaf h1 :: Hash
h1 l1 :: Leaf k v
l1) (Leaf h2 :: Hash
h2 l2 :: Leaf k v'
l2) = Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 Bool -> Bool -> Bool
&& Leaf k v -> Leaf k v' -> Bool
leafEq Leaf k v
l1 Leaf k v'
l2
    go (Full ary1 :: Array (HashMap k v)
ary1) (Full ary2 :: Array (HashMap k v')
ary2) = (HashMap k v -> HashMap k v' -> Bool)
-> Array (HashMap k v) -> Array (HashMap k v') -> Bool
forall a b. (a -> b -> Bool) -> Array a -> Array b -> Bool
A.sameArray1 HashMap k v -> HashMap k v' -> Bool
go Array (HashMap k v)
ary1 Array (HashMap k v')
ary2
    go (Collision h1 :: Hash
h1 ary1 :: Array (Leaf k v)
ary1) (Collision h2 :: Hash
h2 ary2 :: Array (Leaf k v')
ary2)
      = Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 Bool -> Bool -> Bool
&& (Leaf k v -> Leaf k v' -> Bool)
-> [Leaf k v] -> [Leaf k v'] -> Bool
forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
isPermutationBy Leaf k v -> Leaf k v' -> Bool
leafEq (Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList Array (Leaf k v)
ary1) (Array (Leaf k v') -> [Leaf k v']
forall a. Array a -> [a]
A.toList Array (Leaf k v')
ary2)
    go _ _ = Bool
False

    leafEq :: Leaf k v -> Leaf k v' -> Bool
leafEq (L k1 :: k
k1 v1 :: v
v1) (L k2 :: k
k2 v2 :: v'
v2) = k
k1 k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k2 Bool -> Bool -> Bool
&& v -> v' -> Bool
eq v
v1 v'
v2

equal2 :: (k -> k' -> Bool) -> (v -> v' -> Bool)
      -> HashMap k v -> HashMap k' v' -> Bool
equal2 :: (k -> k' -> Bool)
-> (v -> v' -> Bool) -> HashMap k v -> HashMap k' v' -> Bool
equal2 eqk :: k -> k' -> Bool
eqk eqv :: v -> v' -> Bool
eqv t1 :: HashMap k v
t1 t2 :: HashMap k' v'
t2 = [HashMap k v] -> [HashMap k' v'] -> Bool
go (HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k v
t1 []) (HashMap k' v' -> [HashMap k' v'] -> [HashMap k' v']
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k' v'
t2 [])
  where
    -- If the two trees are the same, then their lists of 'Leaf's and
    -- 'Collision's read from left to right should be the same (modulo the
    -- order of elements in 'Collision').

    go :: [HashMap k v] -> [HashMap k' v'] -> Bool
go (Leaf k1 :: Hash
k1 l1 :: Leaf k v
l1 : tl1 :: [HashMap k v]
tl1) (Leaf k2 :: Hash
k2 l2 :: Leaf k' v'
l2 : tl2 :: [HashMap k' v']
tl2)
      | Hash
k1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
k2 Bool -> Bool -> Bool
&&
        Leaf k v -> Leaf k' v' -> Bool
leafEq Leaf k v
l1 Leaf k' v'
l2
      = [HashMap k v] -> [HashMap k' v'] -> Bool
go [HashMap k v]
tl1 [HashMap k' v']
tl2
    go (Collision k1 :: Hash
k1 ary1 :: Array (Leaf k v)
ary1 : tl1 :: [HashMap k v]
tl1) (Collision k2 :: Hash
k2 ary2 :: Array (Leaf k' v')
ary2 : tl2 :: [HashMap k' v']
tl2)
      | Hash
k1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
k2 Bool -> Bool -> Bool
&&
        Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Array (Leaf k' v') -> Int
forall a. Array a -> Int
A.length Array (Leaf k' v')
ary2 Bool -> Bool -> Bool
&&
        (Leaf k v -> Leaf k' v' -> Bool)
-> [Leaf k v] -> [Leaf k' v'] -> Bool
forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
isPermutationBy Leaf k v -> Leaf k' v' -> Bool
leafEq (Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList Array (Leaf k v)
ary1) (Array (Leaf k' v') -> [Leaf k' v']
forall a. Array a -> [a]
A.toList Array (Leaf k' v')
ary2)
      = [HashMap k v] -> [HashMap k' v'] -> Bool
go [HashMap k v]
tl1 [HashMap k' v']
tl2
    go [] [] = Bool
True
    go _  _  = Bool
False

    leafEq :: Leaf k v -> Leaf k' v' -> Bool
leafEq (L k :: k
k v :: v
v) (L k' :: k'
k' v' :: v'
v') = k -> k' -> Bool
eqk k
k k'
k' Bool -> Bool -> Bool
&& v -> v' -> Bool
eqv v
v v'
v'

#if MIN_VERSION_base(4,9,0)
instance Ord2 HashMap where
    liftCompare2 :: (a -> b -> Ordering)
-> (c -> d -> Ordering) -> HashMap a c -> HashMap b d -> Ordering
liftCompare2 = (a -> b -> Ordering)
-> (c -> d -> Ordering) -> HashMap a c -> HashMap b d -> Ordering
forall a b c d.
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> HashMap a c -> HashMap b d -> Ordering
cmp

instance Ord k => Ord1 (HashMap k) where
    liftCompare :: (a -> b -> Ordering) -> HashMap k a -> HashMap k b -> Ordering
liftCompare = (k -> k -> Ordering)
-> (a -> b -> Ordering) -> HashMap k a -> HashMap k b -> Ordering
forall a b c d.
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> HashMap a c -> HashMap b d -> Ordering
cmp k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
#endif

-- | The order is total.
--
-- /Note:/ Because the hash is not guaranteed to be stable across library
-- versions, OSes, or architectures, neither is an actual order of elements in
-- 'HashMap' or an result of `compare`.is stable.
instance (Ord k, Ord v) => Ord (HashMap k v) where
    compare :: HashMap k v -> HashMap k v -> Ordering
compare = (k -> k -> Ordering)
-> (v -> v -> Ordering) -> HashMap k v -> HashMap k v -> Ordering
forall a b c d.
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> HashMap a c -> HashMap b d -> Ordering
cmp k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare v -> v -> Ordering
forall a. Ord a => a -> a -> Ordering
compare

cmp :: (k -> k' -> Ordering) -> (v -> v' -> Ordering)
    -> HashMap k v -> HashMap k' v' -> Ordering
cmp :: (k -> k' -> Ordering)
-> (v -> v' -> Ordering)
-> HashMap k v
-> HashMap k' v'
-> Ordering
cmp cmpk :: k -> k' -> Ordering
cmpk cmpv :: v -> v' -> Ordering
cmpv t1 :: HashMap k v
t1 t2 :: HashMap k' v'
t2 = [HashMap k v] -> [HashMap k' v'] -> Ordering
go (HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k v
t1 []) (HashMap k' v' -> [HashMap k' v'] -> [HashMap k' v']
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k' v'
t2 [])
  where
    go :: [HashMap k v] -> [HashMap k' v'] -> Ordering
go (Leaf k1 :: Hash
k1 l1 :: Leaf k v
l1 : tl1 :: [HashMap k v]
tl1) (Leaf k2 :: Hash
k2 l2 :: Leaf k' v'
l2 : tl2 :: [HashMap k' v']
tl2)
      = Hash -> Hash -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Hash
k1 Hash
k2 Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
        Leaf k v -> Leaf k' v' -> Ordering
leafCompare Leaf k v
l1 Leaf k' v'
l2 Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
        [HashMap k v] -> [HashMap k' v'] -> Ordering
go [HashMap k v]
tl1 [HashMap k' v']
tl2
    go (Collision k1 :: Hash
k1 ary1 :: Array (Leaf k v)
ary1 : tl1 :: [HashMap k v]
tl1) (Collision k2 :: Hash
k2 ary2 :: Array (Leaf k' v')
ary2 : tl2 :: [HashMap k' v']
tl2)
      = Hash -> Hash -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Hash
k1 Hash
k2 Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
        Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary1) (Array (Leaf k' v') -> Int
forall a. Array a -> Int
A.length Array (Leaf k' v')
ary2) Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
        (Leaf k v -> Leaf k' v' -> Ordering)
-> [Leaf k v] -> [Leaf k' v'] -> Ordering
forall a b. (a -> b -> Ordering) -> [a] -> [b] -> Ordering
unorderedCompare Leaf k v -> Leaf k' v' -> Ordering
leafCompare (Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList Array (Leaf k v)
ary1) (Array (Leaf k' v') -> [Leaf k' v']
forall a. Array a -> [a]
A.toList Array (Leaf k' v')
ary2) Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend`
        [HashMap k v] -> [HashMap k' v'] -> Ordering
go [HashMap k v]
tl1 [HashMap k' v']
tl2
    go (Leaf _ _ : _) (Collision _ _ : _) = Ordering
LT
    go (Collision _ _ : _) (Leaf _ _ : _) = Ordering
GT
    go [] [] = Ordering
EQ
    go [] _  = Ordering
LT
    go _  [] = Ordering
GT
    go _ _ = [Char] -> Ordering
forall a. HasCallStack => [Char] -> a
error "cmp: Should never happend, toList' includes non Leaf / Collision"

    leafCompare :: Leaf k v -> Leaf k' v' -> Ordering
leafCompare (L k :: k
k v :: v
v) (L k' :: k'
k' v' :: v'
v') = k -> k' -> Ordering
cmpk k
k k'
k' Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend` v -> v' -> Ordering
cmpv v
v v'
v'

-- Same as 'equal' but doesn't compare the values.
equalKeys1 :: (k -> k' -> Bool) -> HashMap k v -> HashMap k' v' -> Bool
equalKeys1 :: (k -> k' -> Bool) -> HashMap k v -> HashMap k' v' -> Bool
equalKeys1 eq :: k -> k' -> Bool
eq t1 :: HashMap k v
t1 t2 :: HashMap k' v'
t2 = [HashMap k v] -> [HashMap k' v'] -> Bool
go (HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k v
t1 []) (HashMap k' v' -> [HashMap k' v'] -> [HashMap k' v']
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k' v'
t2 [])
  where
    go :: [HashMap k v] -> [HashMap k' v'] -> Bool
go (Leaf k1 :: Hash
k1 l1 :: Leaf k v
l1 : tl1 :: [HashMap k v]
tl1) (Leaf k2 :: Hash
k2 l2 :: Leaf k' v'
l2 : tl2 :: [HashMap k' v']
tl2)
      | Hash
k1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
k2 Bool -> Bool -> Bool
&& Leaf k v -> Leaf k' v' -> Bool
leafEq Leaf k v
l1 Leaf k' v'
l2
      = [HashMap k v] -> [HashMap k' v'] -> Bool
go [HashMap k v]
tl1 [HashMap k' v']
tl2
    go (Collision k1 :: Hash
k1 ary1 :: Array (Leaf k v)
ary1 : tl1 :: [HashMap k v]
tl1) (Collision k2 :: Hash
k2 ary2 :: Array (Leaf k' v')
ary2 : tl2 :: [HashMap k' v']
tl2)
      | Hash
k1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
k2 Bool -> Bool -> Bool
&& Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Array (Leaf k' v') -> Int
forall a. Array a -> Int
A.length Array (Leaf k' v')
ary2 Bool -> Bool -> Bool
&&
        (Leaf k v -> Leaf k' v' -> Bool)
-> [Leaf k v] -> [Leaf k' v'] -> Bool
forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
isPermutationBy Leaf k v -> Leaf k' v' -> Bool
leafEq (Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList Array (Leaf k v)
ary1) (Array (Leaf k' v') -> [Leaf k' v']
forall a. Array a -> [a]
A.toList Array (Leaf k' v')
ary2)
      = [HashMap k v] -> [HashMap k' v'] -> Bool
go [HashMap k v]
tl1 [HashMap k' v']
tl2
    go [] [] = Bool
True
    go _  _  = Bool
False

    leafEq :: Leaf k v -> Leaf k' v' -> Bool
leafEq (L k :: k
k _) (L k' :: k'
k' _) = k -> k' -> Bool
eq k
k k'
k'

-- Same as 'equal1' but doesn't compare the values.
equalKeys :: Eq k => HashMap k v -> HashMap k v' -> Bool
equalKeys :: HashMap k v -> HashMap k v' -> Bool
equalKeys = HashMap k v -> HashMap k v' -> Bool
forall k v v'. Eq k => HashMap k v -> HashMap k v' -> Bool
go
  where
    go :: Eq k => HashMap k v -> HashMap k v' -> Bool
    go :: HashMap k v -> HashMap k v' -> Bool
go Empty Empty = Bool
True
    go (BitmapIndexed bm1 :: Hash
bm1 ary1 :: Array (HashMap k v)
ary1) (BitmapIndexed bm2 :: Hash
bm2 ary2 :: Array (HashMap k v')
ary2)
      = Hash
bm1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
bm2 Bool -> Bool -> Bool
&& (HashMap k v -> HashMap k v' -> Bool)
-> Array (HashMap k v) -> Array (HashMap k v') -> Bool
forall a b. (a -> b -> Bool) -> Array a -> Array b -> Bool
A.sameArray1 HashMap k v -> HashMap k v' -> Bool
forall k v v'. Eq k => HashMap k v -> HashMap k v' -> Bool
go Array (HashMap k v)
ary1 Array (HashMap k v')
ary2
    go (Leaf h1 :: Hash
h1 l1 :: Leaf k v
l1) (Leaf h2 :: Hash
h2 l2 :: Leaf k v'
l2) = Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 Bool -> Bool -> Bool
&& Leaf k v -> Leaf k v' -> Bool
forall a v v. Eq a => Leaf a v -> Leaf a v -> Bool
leafEq Leaf k v
l1 Leaf k v'
l2
    go (Full ary1 :: Array (HashMap k v)
ary1) (Full ary2 :: Array (HashMap k v')
ary2) = (HashMap k v -> HashMap k v' -> Bool)
-> Array (HashMap k v) -> Array (HashMap k v') -> Bool
forall a b. (a -> b -> Bool) -> Array a -> Array b -> Bool
A.sameArray1 HashMap k v -> HashMap k v' -> Bool
forall k v v'. Eq k => HashMap k v -> HashMap k v' -> Bool
go Array (HashMap k v)
ary1 Array (HashMap k v')
ary2
    go (Collision h1 :: Hash
h1 ary1 :: Array (Leaf k v)
ary1) (Collision h2 :: Hash
h2 ary2 :: Array (Leaf k v')
ary2)
      = Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2 Bool -> Bool -> Bool
&& (Leaf k v -> Leaf k v' -> Bool)
-> [Leaf k v] -> [Leaf k v'] -> Bool
forall a b. (a -> b -> Bool) -> [a] -> [b] -> Bool
isPermutationBy Leaf k v -> Leaf k v' -> Bool
forall a v v. Eq a => Leaf a v -> Leaf a v -> Bool
leafEq (Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList Array (Leaf k v)
ary1) (Array (Leaf k v') -> [Leaf k v']
forall a. Array a -> [a]
A.toList Array (Leaf k v')
ary2)
    go _ _ = Bool
False

    leafEq :: Leaf a v -> Leaf a v -> Bool
leafEq (L k1 :: a
k1 _) (L k2 :: a
k2 _) = a
k1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
k2

#if MIN_VERSION_hashable(1,2,5)
instance H.Hashable2 HashMap where
    liftHashWithSalt2 :: (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> HashMap a b -> Int
liftHashWithSalt2 hk :: Int -> a -> Int
hk hv :: Int -> b -> Int
hv salt :: Int
salt hm :: HashMap a b
hm = Int -> [HashMap a b] -> Int
go Int
salt (HashMap a b -> [HashMap a b] -> [HashMap a b]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap a b
hm [])
      where
        -- go :: Int -> [HashMap k v] -> Int
        go :: Int -> [HashMap a b] -> Int
go s :: Int
s [] = Int
s
        go s :: Int
s (Leaf _ l :: Leaf a b
l : tl :: [HashMap a b]
tl)
          = Int
s Int -> Leaf a b -> Int
`hashLeafWithSalt` Leaf a b
l Int -> [HashMap a b] -> Int
`go` [HashMap a b]
tl
        -- For collisions we hashmix hash value
        -- and then array of values' hashes sorted
        go s :: Int
s (Collision h :: Hash
h a :: Array (Leaf a b)
a : tl :: [HashMap a b]
tl)
          = (Int
s Int -> Hash -> Int
forall a. Hashable a => Int -> a -> Int
`H.hashWithSalt` Hash
h) Int -> Array (Leaf a b) -> Int
`hashCollisionWithSalt` Array (Leaf a b)
a Int -> [HashMap a b] -> Int
`go` [HashMap a b]
tl
        go s :: Int
s (_ : tl :: [HashMap a b]
tl) = Int
s Int -> [HashMap a b] -> Int
`go` [HashMap a b]
tl

        -- hashLeafWithSalt :: Int -> Leaf k v -> Int
        hashLeafWithSalt :: Int -> Leaf a b -> Int
hashLeafWithSalt s :: Int
s (L k :: a
k v :: b
v) = (Int
s Int -> a -> Int
`hk` a
k) Int -> b -> Int
`hv` b
v

        -- hashCollisionWithSalt :: Int -> A.Array (Leaf k v) -> Int
        hashCollisionWithSalt :: Int -> Array (Leaf a b) -> Int
hashCollisionWithSalt s :: Int
s
          = (Int -> Int -> Int) -> Int -> [Int] -> Int
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl' Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
H.hashWithSalt Int
s ([Int] -> Int)
-> (Array (Leaf a b) -> [Int]) -> Array (Leaf a b) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Array (Leaf a b) -> [Int]
arrayHashesSorted Int
s

        -- arrayHashesSorted :: Int -> A.Array (Leaf k v) -> [Int]
        arrayHashesSorted :: Int -> Array (Leaf a b) -> [Int]
arrayHashesSorted s :: Int
s = [Int] -> [Int]
forall a. Ord a => [a] -> [a]
L.sort ([Int] -> [Int])
-> (Array (Leaf a b) -> [Int]) -> Array (Leaf a b) -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Leaf a b -> Int) -> [Leaf a b] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
L.map (Int -> Leaf a b -> Int
hashLeafWithSalt Int
s) ([Leaf a b] -> [Int])
-> (Array (Leaf a b) -> [Leaf a b]) -> Array (Leaf a b) -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Array (Leaf a b) -> [Leaf a b]
forall a. Array a -> [a]
A.toList

instance (Hashable k) => H.Hashable1 (HashMap k) where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> HashMap k a -> Int
liftHashWithSalt = (Int -> k -> Int) -> (Int -> a -> Int) -> Int -> HashMap k a -> Int
forall (t :: * -> * -> *) a b.
Hashable2 t =>
(Int -> a -> Int) -> (Int -> b -> Int) -> Int -> t a b -> Int
H.liftHashWithSalt2 Int -> k -> Int
forall a. Hashable a => Int -> a -> Int
H.hashWithSalt
#endif

instance (Hashable k, Hashable v) => Hashable (HashMap k v) where
    hashWithSalt :: Int -> HashMap k v -> Int
hashWithSalt salt :: Int
salt hm :: HashMap k v
hm = Int -> [HashMap k v] -> Int
go Int
salt (HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' HashMap k v
hm [])
      where
        go :: Int -> [HashMap k v] -> Int
        go :: Int -> [HashMap k v] -> Int
go s :: Int
s [] = Int
s
        go s :: Int
s (Leaf _ l :: Leaf k v
l : tl :: [HashMap k v]
tl)
          = Int
s Int -> Leaf k v -> Int
`hashLeafWithSalt` Leaf k v
l Int -> [HashMap k v] -> Int
`go` [HashMap k v]
tl
        -- For collisions we hashmix hash value
        -- and then array of values' hashes sorted
        go s :: Int
s (Collision h :: Hash
h a :: Array (Leaf k v)
a : tl :: [HashMap k v]
tl)
          = (Int
s Int -> Hash -> Int
forall a. Hashable a => Int -> a -> Int
`H.hashWithSalt` Hash
h) Int -> Array (Leaf k v) -> Int
`hashCollisionWithSalt` Array (Leaf k v)
a Int -> [HashMap k v] -> Int
`go` [HashMap k v]
tl
        go s :: Int
s (_ : tl :: [HashMap k v]
tl) = Int
s Int -> [HashMap k v] -> Int
`go` [HashMap k v]
tl

        hashLeafWithSalt :: Int -> Leaf k v -> Int
        hashLeafWithSalt :: Int -> Leaf k v -> Int
hashLeafWithSalt s :: Int
s (L k :: k
k v :: v
v) = Int
s Int -> k -> Int
forall a. Hashable a => Int -> a -> Int
`H.hashWithSalt` k
k Int -> v -> Int
forall a. Hashable a => Int -> a -> Int
`H.hashWithSalt` v
v

        hashCollisionWithSalt :: Int -> A.Array (Leaf k v) -> Int
        hashCollisionWithSalt :: Int -> Array (Leaf k v) -> Int
hashCollisionWithSalt s :: Int
s
          = (Int -> Int -> Int) -> Int -> [Int] -> Int
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl' Int -> Int -> Int
forall a. Hashable a => Int -> a -> Int
H.hashWithSalt Int
s ([Int] -> Int)
-> (Array (Leaf k v) -> [Int]) -> Array (Leaf k v) -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Array (Leaf k v) -> [Int]
arrayHashesSorted Int
s

        arrayHashesSorted :: Int -> A.Array (Leaf k v) -> [Int]
        arrayHashesSorted :: Int -> Array (Leaf k v) -> [Int]
arrayHashesSorted s :: Int
s = [Int] -> [Int]
forall a. Ord a => [a] -> [a]
L.sort ([Int] -> [Int])
-> (Array (Leaf k v) -> [Int]) -> Array (Leaf k v) -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Leaf k v -> Int) -> [Leaf k v] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
L.map (Int -> Leaf k v -> Int
hashLeafWithSalt Int
s) ([Leaf k v] -> [Int])
-> (Array (Leaf k v) -> [Leaf k v]) -> Array (Leaf k v) -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Array (Leaf k v) -> [Leaf k v]
forall a. Array a -> [a]
A.toList

  -- Helper to get 'Leaf's and 'Collision's as a list.
toList' :: HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' :: HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' (BitmapIndexed _ ary :: Array (HashMap k v)
ary) a :: [HashMap k v]
a = (HashMap k v -> [HashMap k v] -> [HashMap k v])
-> [HashMap k v] -> Array (HashMap k v) -> [HashMap k v]
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' [HashMap k v]
a Array (HashMap k v)
ary
toList' (Full ary :: Array (HashMap k v)
ary)            a :: [HashMap k v]
a = (HashMap k v -> [HashMap k v] -> [HashMap k v])
-> [HashMap k v] -> Array (HashMap k v) -> [HashMap k v]
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr HashMap k v -> [HashMap k v] -> [HashMap k v]
forall k v. HashMap k v -> [HashMap k v] -> [HashMap k v]
toList' [HashMap k v]
a Array (HashMap k v)
ary
toList' l :: HashMap k v
l@(Leaf _ _)          a :: [HashMap k v]
a = HashMap k v
l HashMap k v -> [HashMap k v] -> [HashMap k v]
forall a. a -> [a] -> [a]
: [HashMap k v]
a
toList' c :: HashMap k v
c@(Collision _ _)     a :: [HashMap k v]
a = HashMap k v
c HashMap k v -> [HashMap k v] -> [HashMap k v]
forall a. a -> [a] -> [a]
: [HashMap k v]
a
toList' Empty                 a :: [HashMap k v]
a = [HashMap k v]
a

-- Helper function to detect 'Leaf's and 'Collision's.
isLeafOrCollision :: HashMap k v -> Bool
isLeafOrCollision :: HashMap k v -> Bool
isLeafOrCollision (Leaf _ _)      = Bool
True
isLeafOrCollision (Collision _ _) = Bool
True
isLeafOrCollision _               = Bool
False

------------------------------------------------------------------------
-- * Construction

-- | /O(1)/ Construct an empty map.
empty :: HashMap k v
empty :: HashMap k v
empty = HashMap k v
forall k v. HashMap k v
Empty

-- | /O(1)/ Construct a map with a single element.
singleton :: (Hashable k) => k -> v -> HashMap k v
singleton :: k -> v -> HashMap k v
singleton k :: k
k v :: v
v = Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf (k -> Hash
forall a. Hashable a => a -> Hash
hash k
k) (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v)

------------------------------------------------------------------------
-- * Basic interface

-- | /O(1)/ Return 'True' if this map is empty, 'False' otherwise.
null :: HashMap k v -> Bool
null :: HashMap k v -> Bool
null Empty = Bool
True
null _   = Bool
False

-- | /O(n)/ Return the number of key-value mappings in this map.
size :: HashMap k v -> Int
size :: HashMap k v -> Int
size t :: HashMap k v
t = HashMap k v -> Int -> Int
forall k v. HashMap k v -> Int -> Int
go HashMap k v
t 0
  where
    go :: HashMap k v -> Int -> Int
go Empty                !Int
n = Int
n
    go (Leaf _ _)            n :: Int
n = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ 1
    go (BitmapIndexed _ ary :: Array (HashMap k v)
ary) n :: Int
n = (Int -> HashMap k v -> Int) -> Int -> Array (HashMap k v) -> Int
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' ((HashMap k v -> Int -> Int) -> Int -> HashMap k v -> Int
forall a b c. (a -> b -> c) -> b -> a -> c
flip HashMap k v -> Int -> Int
go) Int
n Array (HashMap k v)
ary
    go (Full ary :: Array (HashMap k v)
ary)            n :: Int
n = (Int -> HashMap k v -> Int) -> Int -> Array (HashMap k v) -> Int
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' ((HashMap k v -> Int -> Int) -> Int -> HashMap k v -> Int
forall a b c. (a -> b -> c) -> b -> a -> c
flip HashMap k v -> Int -> Int
go) Int
n Array (HashMap k v)
ary
    go (Collision _ ary :: Array (Leaf k v)
ary)     n :: Int
n = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary

-- | /O(log n)/ Return 'True' if the specified key is present in the
-- map, 'False' otherwise.
member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool
member :: k -> HashMap k a -> Bool
member k :: k
k m :: HashMap k a
m = case k -> HashMap k a -> Maybe a
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k a
m of
    Nothing -> Bool
False
    Just _  -> Bool
True
{-# INLINABLE member #-}

-- | /O(log n)/ Return the value to which the specified key is mapped,
-- or 'Nothing' if this map contains no mapping for the key.
lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
#if __GLASGOW_HASKELL__ >= 802
-- GHC does not yet perform a worker-wrapper transformation on
-- unboxed sums automatically. That seems likely to happen at some
-- point (possibly as early as GHC 8.6) but for now we do it manually.
lookup :: k -> HashMap k v -> Maybe v
lookup k :: k
k m :: HashMap k v
m = case k -> HashMap k v -> (# (# #) | v #)
forall k v.
(Eq k, Hashable k) =>
k -> HashMap k v -> (# (# #) | v #)
lookup# k
k HashMap k v
m of
  (# (# #) | #) -> Maybe v
forall a. Maybe a
Nothing
  (# | v
a #) -> v -> Maybe v
forall a. a -> Maybe a
Just v
a
{-# INLINE lookup #-}

lookup# :: (Eq k, Hashable k) => k -> HashMap k v -> (# (# #) | v #)
lookup# :: k -> HashMap k v -> (# (# #) | v #)
lookup# k :: k
k m :: HashMap k v
m = ((# #) -> (# (# #) | v #))
-> (v -> Int -> (# (# #) | v #))
-> Hash
-> k
-> HashMap k v
-> (# (# #) | v #)
forall r k v.
Eq k =>
((# #) -> r) -> (v -> Int -> r) -> Hash -> k -> HashMap k v -> r
lookupCont (\_ -> (# (# #) | #)) (\v :: v
v _i :: Int
_i -> (# | v
v #)) (k -> Hash
forall a. Hashable a => a -> Hash
hash k
k) k
k HashMap k v
m
{-# INLINABLE lookup# #-}

#else

lookup k m = lookupCont (\_ -> Nothing) (\v _i -> Just v) (hash k) k m
{-# INLINABLE lookup #-}
#endif

-- | lookup' is a version of lookup that takes the hash separately.
-- It is used to implement alterF.
lookup' :: Eq k => Hash -> k -> HashMap k v -> Maybe v
#if __GLASGOW_HASKELL__ >= 802
-- GHC does not yet perform a worker-wrapper transformation on
-- unboxed sums automatically. That seems likely to happen at some
-- point (possibly as early as GHC 8.6) but for now we do it manually.
-- lookup' would probably prefer to be implemented in terms of its own
-- lookup'#, but it's not important enough and we don't want too much
-- code.
lookup' :: Hash -> k -> HashMap k v -> Maybe v
lookup' h :: Hash
h k :: k
k m :: HashMap k v
m = case Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
forall k v.
Eq k =>
Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
lookupRecordCollision# Hash
h k
k HashMap k v
m of
  (# (# #) | #) -> Maybe v
forall a. Maybe a
Nothing
  (# | (# a :: v
a, _i :: Int#
_i #) #) -> v -> Maybe v
forall a. a -> Maybe a
Just v
a
{-# INLINE lookup' #-}
#else
lookup' h k m = lookupCont (\_ -> Nothing) (\v _i -> Just v) h k m
{-# INLINABLE lookup' #-}
#endif

-- The result of a lookup, keeping track of if a hash collision occured.
-- If a collision did not occur then it will have the Int value (-1).
data LookupRes a = Absent | Present a !Int

-- Internal helper for lookup. This version takes the precomputed hash so
-- that functions that make multiple calls to lookup and related functions
-- (insert, delete) only need to calculate the hash once.
--
-- It is used by 'alterF' so that hash computation and key comparison only needs
-- to be performed once. With this information you can use the more optimized
-- versions of insert ('insertNewKey', 'insertKeyExists') and delete
-- ('deleteKeyExists')
--
-- Outcomes:
--   Key not in map           => Absent
--   Key in map, no collision => Present v (-1)
--   Key in map, collision    => Present v position
lookupRecordCollision :: Eq k => Hash -> k -> HashMap k v -> LookupRes v
#if __GLASGOW_HASKELL__ >= 802
lookupRecordCollision :: Hash -> k -> HashMap k v -> LookupRes v
lookupRecordCollision h :: Hash
h k :: k
k m :: HashMap k v
m = case Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
forall k v.
Eq k =>
Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
lookupRecordCollision# Hash
h k
k HashMap k v
m of
  (# (# #) | #) -> LookupRes v
forall a. LookupRes a
Absent
  (# | (# a :: v
a, i :: Int#
i #) #) -> v -> Int -> LookupRes v
forall a. a -> Int -> LookupRes a
Present v
a (Int# -> Int
I# Int#
i) -- GHC will eliminate the I#
{-# INLINE lookupRecordCollision #-}

-- Why do we produce an Int# instead of an Int? Unfortunately, GHC is not
-- yet any good at unboxing things *inside* products, let alone sums. That
-- may be changing in GHC 8.6 or so (there is some work in progress), but
-- for now we use Int# explicitly here. We don't need to push the Int#
-- into lookupCont because inlining takes care of that.
lookupRecordCollision# :: Eq k => Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
lookupRecordCollision# :: Hash -> k -> HashMap k v -> (# (# #) | (# v, Int# #) #)
lookupRecordCollision# h :: Hash
h k :: k
k m :: HashMap k v
m =
    ((# #) -> (# (# #) | (# v, Int# #) #))
-> (v -> Int -> (# (# #) | (# v, Int# #) #))
-> Hash
-> k
-> HashMap k v
-> (# (# #) | (# v, Int# #) #)
forall r k v.
Eq k =>
((# #) -> r) -> (v -> Int -> r) -> Hash -> k -> HashMap k v -> r
lookupCont (\_ -> (# (# #) | #)) (\v :: v
v (I# i :: Int#
i) -> (# | (# v
v, Int#
i #) #)) Hash
h k
k HashMap k v
m
-- INLINABLE to specialize to the Eq instance.
{-# INLINABLE lookupRecordCollision# #-}

#else /* GHC < 8.2 so there are no unboxed sums */

lookupRecordCollision h k m = lookupCont (\_ -> Absent) Present h k m
{-# INLINABLE lookupRecordCollision #-}
#endif

-- A two-continuation version of lookupRecordCollision. This lets us
-- share source code between lookup and lookupRecordCollision without
-- risking any performance degradation.
--
-- The absent continuation has type @((# #) -> r)@ instead of just @r@
-- so we can be representation-polymorphic in the result type. Since
-- this whole thing is always inlined, we don't have to worry about
-- any extra CPS overhead.
lookupCont ::
#if __GLASGOW_HASKELL__ >= 802
  forall rep (r :: TYPE rep) k v.
#else
  forall r k v.
#endif
     Eq k
  => ((# #) -> r)    -- Absent continuation
  -> (v -> Int -> r) -- Present continuation
  -> Hash -- The hash of the key
  -> k -> HashMap k v -> r
lookupCont :: ((# #) -> r) -> (v -> Int -> r) -> Hash -> k -> HashMap k v -> r
lookupCont absent :: (# #) -> r
absent present :: v -> Int -> r
present !Hash
h0 !k
k0 !HashMap k v
m0 = Eq k => Hash -> k -> Int -> HashMap k v -> r
Hash -> k -> Int -> HashMap k v -> r
go Hash
h0 k
k0 0 HashMap k v
m0
  where
    go :: Eq k => Hash -> k -> Int -> HashMap k v -> r
    go :: Hash -> k -> Int -> HashMap k v -> r
go !Hash
_ !k
_ !Int
_ Empty = (# #) -> r
absent (# #)
    go h :: Hash
h k :: k
k _ (Leaf hx :: Hash
hx (L kx :: k
kx x :: v
x))
        | Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hx Bool -> Bool -> Bool
&& k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx = v -> Int -> r
present v
x (-1)
        | Bool
otherwise          = (# #) -> r
absent (# #)
    go h :: Hash
h k :: k
k s :: Int
s (BitmapIndexed b :: Hash
b v :: Array (HashMap k v)
v)
        | Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = (# #) -> r
absent (# #)
        | Bool
otherwise    =
            Eq k => Hash -> k -> Int -> HashMap k v -> r
Hash -> k -> Int -> HashMap k v -> r
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) (Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
v (Hash -> Hash -> Int
sparseIndex Hash
b Hash
m))
      where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
    go h :: Hash
h k :: k
k s :: Int
s (Full v :: Array (HashMap k v)
v) =
      Eq k => Hash -> k -> Int -> HashMap k v -> r
Hash -> k -> Int -> HashMap k v -> r
go Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) (Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
v (Hash -> Int -> Int
index Hash
h Int
s))
    go h :: Hash
h k :: k
k _ (Collision hx :: Hash
hx v :: Array (Leaf k v)
v)
        | Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hx   = ((# #) -> r) -> (v -> Int -> r) -> k -> Array (Leaf k v) -> r
forall r k v.
Eq k =>
((# #) -> r) -> (v -> Int -> r) -> k -> Array (Leaf k v) -> r
lookupInArrayCont (# #) -> r
absent v -> Int -> r
present k
k Array (Leaf k v)
v
        | Bool
otherwise = (# #) -> r
absent (# #)
{-# INLINE lookupCont #-}

-- | /O(log n)/ Return the value to which the specified key is mapped,
-- or the default value if this map contains no mapping for the key.
lookupDefault :: (Eq k, Hashable k)
              => v          -- ^ Default value to return.
              -> k -> HashMap k v -> v
lookupDefault :: v -> k -> HashMap k v -> v
lookupDefault def :: v
def k :: k
k t :: HashMap k v
t = case k -> HashMap k v -> Maybe v
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k v
t of
    Just v :: v
v -> v
v
    _      -> v
def
{-# INLINABLE lookupDefault #-}

-- | /O(log n)/ Return the value to which the specified key is mapped.
-- Calls 'error' if this map contains no mapping for the key.
(!) :: (Eq k, Hashable k) => HashMap k v -> k -> v
(!) m :: HashMap k v
m k :: k
k = case k -> HashMap k v -> Maybe v
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k v
m of
    Just v :: v
v  -> v
v
    Nothing -> [Char] -> v
forall a. HasCallStack => [Char] -> a
error "Data.HashMap.Base.(!): key not found"
{-# INLINABLE (!) #-}

infixl 9 !

-- | Create a 'Collision' value with two 'Leaf' values.
collision :: Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision :: Hash -> Leaf k v -> Leaf k v -> HashMap k v
collision h :: Hash
h !Leaf k v
e1 !Leaf k v
e2 =
    let v :: Array (Leaf k v)
v = (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 -> Leaf k v -> ST s (MArray s (Leaf k v))
forall a s. Int -> a -> ST s (MArray s a)
A.new 2 Leaf k v
e1
                       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 1 Leaf k v
e2
                       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
    in Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h Array (Leaf k v)
v
{-# INLINE collision #-}

-- | Create a 'BitmapIndexed' or 'Full' node.
bitmapIndexedOrFull :: Bitmap -> A.Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull :: Hash -> Array (HashMap k v) -> HashMap k v
bitmapIndexedOrFull b :: Hash
b ary :: Array (HashMap k v)
ary
    | Hash
b Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
fullNodeMask = Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary
    | Bool
otherwise         = 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
{-# INLINE bitmapIndexedOrFull #-}

-- | /O(log n)/ Associate the specified value with the specified
-- key in this map.  If this map previously contained a mapping for
-- the key, the old value is replaced.
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
k v :: v
v m :: HashMap k v
m = Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> v -> HashMap k v -> HashMap k v
insert' (k -> Hash
forall a. Hashable a => a -> Hash
hash k
k) k
k v
v HashMap k v
m
{-# INLINABLE insert #-}

insert' :: Eq k => Hash -> k -> v -> HashMap k v -> HashMap k v
insert' :: Hash -> k -> v -> HashMap k v -> HashMap k v
insert' h0 :: Hash
h0 k0 :: k
k0 v0 :: v
v0 m0 :: HashMap k v
m0 = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
forall k v.
Eq k =>
Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 v
v0 0 HashMap k v
m0
  where
    go :: Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go !Hash
h !k
k x :: v
x !Int
_ Empty = 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
x)
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Leaf hy :: Hash
hy l :: Leaf k v
l@(L ky :: k
ky y :: 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 if v
x v -> v -> Bool
forall a. a -> a -> Bool
`ptrEq` v
y
                         then HashMap k v
t
                         else 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
x)
                    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
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 = (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy k
ky v
y)
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: 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
== 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 -> 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
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
            in if HashMap k v
st' HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
`ptrEq` HashMap k v
st
               then HashMap k v
t
               else 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) -> 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
st')
      where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
            i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Full ary :: 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
        in if HashMap k v
st' HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
`ptrEq` HashMap k v
st
            then HashMap k v
t
            else Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full (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
st')
      where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Collision hy :: Hash
hy v :: 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
forall a b. a -> b -> a
const 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 insert' #-}

-- Insert optimized for the case when we know the key is not in the map.
--
-- It is only valid to call this when the key does not exist in the map.
--
-- We can skip:
--  - the key equality check on a Leaf
--  - check for its existence in the array for a hash collision
insertNewKey :: Hash -> k -> v -> HashMap k v -> HashMap k v
insertNewKey :: Hash -> k -> v -> HashMap k v -> HashMap k v
insertNewKey !Hash
h0 !k
k0 x0 :: v
x0 !HashMap k v
m0 = Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
forall k v. Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 v
x0 0 HashMap k v
m0
  where
    go :: Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go !Hash
h !k
k x :: v
x !Int
_ Empty = 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
x)
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s (Leaf hy :: Hash
hy l :: Leaf k v
l@(L ky :: k
ky y :: v
y))
      | Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h = 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 = (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy k
ky v
y)
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s (BitmapIndexed b :: Hash
b ary :: 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
== 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 -> 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
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
            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) -> 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
st')
      where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
            i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s (Full ary :: 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
        in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full (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
st')
      where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Collision hy :: Hash
hy v :: 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 (Leaf k v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v. Leaf k v -> Array (Leaf k v) -> Array (Leaf k v)
snocNewLeaf (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L 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)
      where
        snocNewLeaf :: Leaf k v -> A.Array (Leaf k v) -> A.Array (Leaf k v)
        snocNewLeaf :: Leaf k v -> Array (Leaf k v) -> Array (Leaf k v)
snocNewLeaf leaf :: Leaf k v
leaf ary :: Array (Leaf k v)
ary = (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
          let n :: Int
n = Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary
          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
+ 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 0 MArray s (Leaf k v)
mary 0 Int
n
          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
leaf
          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
{-# NOINLINE insertNewKey #-}


-- Insert optimized for the case when we know the key is in the map.
--
-- It is only valid to call this when the key exists in the map and you know the
-- hash collision position if there was one. This information can be obtained
-- from 'lookupRecordCollision'. If there is no collision pass (-1) as collPos
-- (first argument).
--
-- We can skip the key equality check on a Leaf because we know the leaf must be
-- for this key.
insertKeyExists :: Int -> Hash -> k -> v -> HashMap k v -> HashMap k v
insertKeyExists :: Int -> Hash -> k -> v -> HashMap k v -> HashMap k v
insertKeyExists !Int
collPos0 !Hash
h0 !k
k0 x0 :: v
x0 !HashMap k v
m0 = Int -> Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
forall k v.
Int -> Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Int
collPos0 Hash
h0 k
k0 v
x0 0 HashMap k v
m0
  where
    go :: Int -> Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go !Int
_collPos !Hash
h !k
k x :: v
x !Int
_s (Leaf _hy :: Hash
_hy _kx :: Leaf k v
_kx)
        = 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
x)
    go collPos :: Int
collPos h :: Hash
h k :: k
k x :: v
x s :: Int
s (BitmapIndexed b :: Hash
b ary :: 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
== 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 -> 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
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' = Int -> Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Int
collPos Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) 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) -> 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
st')
      where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
            i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
    go collPos :: Int
collPos h :: Hash
h k :: k
k x :: v
x s :: Int
s (Full ary :: 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' = Int -> Hash -> k -> v -> Int -> HashMap k v -> HashMap k v
go Int
collPos Hash
h k
k v
x (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) 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) -> 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
st')
      where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
    go collPos :: Int
collPos h :: Hash
h k :: k
k x :: v
x _s :: Int
_s (Collision _hy :: Hash
_hy v :: Array (Leaf k v)
v)
        | Int
collPos Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= 0 = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Int -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v. Int -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
setAtPosition Int
collPos k
k v
x Array (Leaf k v)
v)
        | Bool
otherwise = HashMap k v
forall k v. HashMap k v
Empty -- error "Internal error: go {collPos negative}"
    go _ _ _ _ _ Empty = HashMap k v
forall k v. HashMap k v
Empty -- error "Internal error: go Empty"

{-# NOINLINE insertKeyExists #-}

-- Replace the ith Leaf with Leaf k v.
--
-- This does not check that @i@ is within bounds of the array.
setAtPosition :: Int -> k -> v -> A.Array (Leaf k v) -> A.Array (Leaf k v)
setAtPosition :: Int -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
setAtPosition i :: Int
i k :: k
k x :: v
x ary :: Array (Leaf k v)
ary = 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
x)
{-# INLINE setAtPosition #-}


-- | In-place update version of insert
unsafeInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v
unsafeInsert :: k -> v -> HashMap k v -> HashMap k v
unsafeInsert k0 :: k
k0 v0 :: v
v0 m0 :: 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 k v s.
Eq k =>
Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Hash
h0 k
k0 v
v0 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 x :: v
x !Int
_ 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 -> 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
x)
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Leaf hy :: Hash
hy l :: Leaf k v
l@(L ky :: k
ky y :: 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 if v
x v -> v -> Bool
forall a. a -> a -> Bool
`ptrEq` v
y
                         then HashMap k v -> ST s (HashMap k v)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v
t
                         else 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 -> 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
x)
                    else 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 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
        | Bool
otherwise = Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy k
ky v
y
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: 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
== 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 -> 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
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 h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Full ary :: 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 h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Collision hy :: Hash
hy v :: 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 ((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
forall a b. a -> b -> a
const 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 unsafeInsert #-}

-- | Create a map from two key-value pairs which hashes don't collide.
two :: Shift -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
two :: Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
two = Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
go
  where
    go :: Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
go s :: Int
s h1 :: Hash
h1 k1 :: k
k1 v1 :: v
v1 h2 :: Hash
h2 k2 :: k
k2 v2 :: v
v2
        | Hash
bp1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
bp2 = do
            HashMap k v
st <- Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
go (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) Hash
h1 k
k1 v
v1 Hash
h2 k
k2 v
v2
            Array (HashMap k v)
ary <- HashMap k v -> ST s (Array (HashMap k v))
forall a s. a -> ST s (Array a)
A.singletonM HashMap k v
st
            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
BitmapIndexed Hash
bp1 Array (HashMap k v)
ary
        | Bool
otherwise  = do
            MArray s (HashMap k v)
mary <- Int -> HashMap k v -> ST s (MArray s (HashMap k v))
forall a s. Int -> a -> ST s (MArray s a)
A.new 2 (HashMap k v -> ST s (MArray s (HashMap k v)))
-> HashMap k v -> ST s (MArray s (HashMap k v))
forall a b. (a -> b) -> a -> b
$ Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h1 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k1 v
v1)
            MArray s (HashMap k v) -> Int -> HashMap k v -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (HashMap k v)
mary Int
idx2 (HashMap k v -> ST s ()) -> HashMap k v -> ST s ()
forall a b. (a -> b) -> a -> b
$ Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h2 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k2 v
v2)
            Array (HashMap k v)
ary <- MArray s (HashMap k v) -> ST s (Array (HashMap k v))
forall s a. MArray s a -> ST s (Array a)
A.unsafeFreeze MArray s (HashMap k v)
mary
            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
BitmapIndexed (Hash
bp1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
bp2) Array (HashMap k v)
ary
      where
        bp1 :: Hash
bp1  = Hash -> Int -> Hash
mask Hash
h1 Int
s
        bp2 :: Hash
bp2  = Hash -> Int -> Hash
mask Hash
h2 Int
s
        idx2 :: Int
idx2 | Hash -> Int -> Int
index Hash
h1 Int
s Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Hash -> Int -> Int
index Hash
h2 Int
s = 1
             | Bool
otherwise               = 0
{-# INLINE two #-}

-- | /O(log n)/ Associate the value with the key in this map.  If
-- this map previously contained a mapping for the key, the old value
-- is replaced by the result of applying the given function to the new
-- and old value.  Example:
--
-- > insertWith f k v map
-- >   where f new old = new + old
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v
            -> HashMap k v
-- We're not going to worry about allocating a function closure
-- to pass to insertModifying. See comments at 'adjust'.
insertWith :: (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
insertWith f :: v -> v -> v
f k :: k
k new :: v
new m :: HashMap k v
m = v -> (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
v -> (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
insertModifying v
new (\old :: v
old -> (# v -> v -> v
f v
new v
old #)) k
k HashMap k v
m
{-# INLINE insertWith #-}

-- | @insertModifying@ is a lot like insertWith; we use it to implement alterF.
-- It takes a value to insert when the key is absent and a function
-- to apply to calculate a new value when the key is present. Thanks
-- to the unboxed unary tuple, we avoid introducing any unnecessary
-- thunks in the tree.
insertModifying :: (Eq k, Hashable k) => v -> (v -> (# v #)) -> k -> HashMap k v
            -> HashMap k v
insertModifying :: v -> (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
insertModifying x :: v
x f :: v -> (# v #)
f k0 :: k
k0 m0 :: HashMap k v
m0 = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 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
h !k
k !Int
_ Empty = 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
x)
    go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(Leaf hy :: Hash
hy l :: Leaf k v
l@(L ky :: k
ky y :: 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 case v -> (# v #)
f v
y of
                      (# v' :: v
v' #) | v -> v -> Bool
forall a. a -> a -> Bool
ptrEq v
y v
v' -> HashMap k v
t
                               | Bool
otherwise -> 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'))
                    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
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 = (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy k
ky v
y)
    go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: 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
== 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 -> 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
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 -> 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 if HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
ptrEq HashMap k v
st HashMap k v
st'
               then HashMap k v
t
               else 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 h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(Full ary :: 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 -> 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 if HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
ptrEq HashMap k v
st HashMap k v
st'
           then HashMap k v
t
           else 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 h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(Collision hy :: Hash
hy v :: Array (Leaf k v)
v)
        | Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy   =
            let !v' :: Array (Leaf k v)
v' = v -> (v -> (# v #)) -> k -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
v -> (v -> (# v #)) -> k -> Array (Leaf k v) -> Array (Leaf k v)
insertModifyingArr v
x v -> (# v #)
f k
k Array (Leaf k v)
v
            in if Array (Leaf k v) -> Array (Leaf k v) -> Bool
forall a b. Array a -> Array b -> Bool
A.unsafeSameArray Array (Leaf k v)
v Array (Leaf k v)
v'
               then HashMap k v
t
               else Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h Array (Leaf k v)
v'
        | Bool
otherwise = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h k
k 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 insertModifying #-}

-- Like insertModifying for arrays; used to implement insertModifying
insertModifyingArr :: Eq k => v -> (v -> (# v #)) -> k -> A.Array (Leaf k v)
                 -> A.Array (Leaf k v)
insertModifyingArr :: v -> (v -> (# v #)) -> k -> Array (Leaf k v) -> Array (Leaf k v)
insertModifyingArr x :: v
x f :: v -> (# v #)
f k0 :: k
k0 ary0 :: Array (Leaf k v)
ary0 = k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k0 Array (Leaf k v)
ary0 0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
  where
    go :: k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go !k
k !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
            -- Not found, append to the end.
            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
+ 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 0 MArray s (Leaf k v)
mary 0 Int
n
            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 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
            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 kx :: k
kx y :: v
y) | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx   -> case v -> (# v #)
f v
y of
                                      (# y' :: v
y' #) -> if v -> v -> Bool
forall a. a -> a -> Bool
ptrEq v
y v
y'
                                                  then Array (Leaf k v)
ary
                                                  else 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
y')
                     | Bool
otherwise -> k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k Array (Leaf k v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
n
{-# INLINE insertModifyingArr #-}

-- | In-place update version of insertWith
unsafeInsertWith :: forall k v. (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 f :: v -> v -> v
f k0 :: k
k0 v0 :: v
v0 m0 :: 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 0 HashMap k v
m0)
  where
    h0 :: Hash
h0 = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k0
    go :: Hash -> k -> v -> Shift -> HashMap k v -> ST s (HashMap k v)
    go :: Hash -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go !Hash
h !k
k x :: v
x !Int
_ 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 -> 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
x)
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s (Leaf hy :: Hash
hy l :: Leaf k v
l@(L ky :: k
ky y :: 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 -> 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 -> v
f v
x v
y))
                    else 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 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x)
        | Bool
otherwise = Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
forall k v s.
Int -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
two Int
s Hash
h k
k v
x Hash
hy k
ky v
y
    go h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: 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
== 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 -> 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
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)
forall s.
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 h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Full ary :: 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)
forall s.
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 h :: Hash
h k :: k
k x :: v
x s :: Int
s t :: HashMap k v
t@(Collision hy :: Hash
hy v :: 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 ((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 -> ST s (HashMap k v)
forall s.
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 unsafeInsertWith #-}

-- | /O(log n)/ Remove the mapping for the specified key from this map
-- if present.
delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
delete :: k -> HashMap k v -> HashMap k v
delete k :: k
k m :: HashMap k v
m = Hash -> k -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> HashMap k v -> HashMap k v
delete' (k -> Hash
forall a. Hashable a => a -> Hash
hash k
k) k
k HashMap k v
m
{-# INLINABLE delete #-}

delete' :: Eq k => Hash -> k -> HashMap k v -> HashMap k v
delete' :: Hash -> k -> HashMap k v -> HashMap k v
delete' h0 :: Hash
h0 k0 :: k
k0 m0 :: HashMap k v
m0 = Hash -> k -> Int -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 0 HashMap k v
m0
  where
    go :: Hash -> k -> Int -> HashMap k v -> HashMap k v
go !Hash
_ !k
_ !Int
_ Empty = HashMap k v
forall k v. HashMap k v
Empty
    go h :: Hash
h k :: k
k _ t :: HashMap k v
t@(Leaf hy :: Hash
hy (L ky :: k
ky _))
        | 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 = HashMap k v
forall k v. HashMap k v
Empty
        | Bool
otherwise          = HashMap k v
t
    go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: 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
== 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
            in if HashMap k v
st' HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
`ptrEq` HashMap k v
st
                then HashMap k v
t
                else case HashMap k v
st' of
                Empty | Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 -> HashMap k v
forall k v. HashMap k v
Empty
                      | Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 2 ->
                          case (Int
i, Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary 0, Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary 1) of
                          (0, _, l :: HashMap k v
l) | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l -> HashMap k v
l
                          (1, l :: HashMap k v
l, _) | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l -> HashMap k v
l
                          _                               -> HashMap k v
bIndexed
                      | Bool
otherwise -> HashMap k v
bIndexed
                    where
                      bIndexed :: HashMap k v
bIndexed = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Bits a => a -> a
complement Hash
m) (Array (HashMap k v) -> Int -> Array (HashMap k v)
forall e. Array e -> Int -> Array e
A.delete Array (HashMap k v)
ary Int
i)
                l :: HashMap k v
l | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l Bool -> Bool -> Bool
&& Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 -> HashMap k v
l
                _ -> 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) -> 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
st')
      where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
            i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
    go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(Full ary :: 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 -> 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
        in if HashMap k v
st' HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
`ptrEq` HashMap k v
st
            then HashMap k v
t
            else case HashMap k v
st' of
            Empty ->
                let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> Array (HashMap k v)
forall e. Array e -> Int -> Array e
A.delete Array (HashMap k v)
ary Int
i
                    bm :: Hash
bm   = Hash
fullNodeMask Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Bits a => a -> a
complement (1 Hash -> Int -> Hash
`unsafeShiftL` Int
i)
                in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
bm Array (HashMap k v)
ary'
            _ -> Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full (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
st')
      where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
    go h :: Hash
h k :: k
k _ t :: HashMap k v
t@(Collision hy :: Hash
hy v :: Array (Leaf k v)
v)
        | Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy = case k -> Array (Leaf k v) -> Maybe Int
forall k v. Eq k => k -> Array (Leaf k v) -> Maybe Int
indexOf k
k Array (Leaf k v)
v of
            Just i :: Int
i
                | Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
v Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 2 ->
                    if Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0
                    then Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
v 1)
                    else Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
v 0)
                | Bool
otherwise -> Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Array (Leaf k v) -> Int -> Array (Leaf k v)
forall e. Array e -> Int -> Array e
A.delete Array (Leaf k v)
v Int
i)
            Nothing -> HashMap k v
t
        | Bool
otherwise = HashMap k v
t
{-# INLINABLE delete' #-}

-- | Delete optimized for the case when we know the key is in the map.
--
-- It is only valid to call this when the key exists in the map and you know the
-- hash collision position if there was one. This information can be obtained
-- from 'lookupRecordCollision'. If there is no collision pass (-1) as collPos.
--
-- We can skip:
--  - the key equality check on the leaf, if we reach a leaf it must be the key
deleteKeyExists :: Int -> Hash -> k -> HashMap k v -> HashMap k v
deleteKeyExists :: Int -> Hash -> k -> HashMap k v -> HashMap k v
deleteKeyExists !Int
collPos0 !Hash
h0 !k
k0 !HashMap k v
m0 = Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
forall k v. Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
go Int
collPos0 Hash
h0 k
k0 0 HashMap k v
m0
  where
    go :: Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
    go :: Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
go !Int
_collPos !Hash
_h !k
_k !Int
_s (Leaf _ _) = HashMap k v
forall k v. HashMap k v
Empty
    go collPos :: Int
collPos h :: Hash
h k :: k
k s :: Int
s (BitmapIndexed b :: Hash
b ary :: 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' = Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
forall k v. Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
go Int
collPos Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
            in case HashMap k v
st' of
                Empty | Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 -> HashMap k v
forall k v. HashMap k v
Empty
                      | Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 2 ->
                          case (Int
i, Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary 0, Array (HashMap k v) -> Int -> HashMap k v
forall a. Array a -> Int -> a
A.index Array (HashMap k v)
ary 1) of
                          (0, _, l :: HashMap k v
l) | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l -> HashMap k v
l
                          (1, l :: HashMap k v
l, _) | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l -> HashMap k v
l
                          _                               -> HashMap k v
bIndexed
                      | Bool
otherwise -> HashMap k v
bIndexed
                    where
                      bIndexed :: HashMap k v
bIndexed = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Bits a => a -> a
complement Hash
m) (Array (HashMap k v) -> Int -> Array (HashMap k v)
forall e. Array e -> Int -> Array e
A.delete Array (HashMap k v)
ary Int
i)
                l :: HashMap k v
l | HashMap k v -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v
l Bool -> Bool -> Bool
&& Array (HashMap k v) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v)
ary Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 1 -> HashMap k v
l
                _ -> 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) -> 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
st')
      where m :: Hash
m = Hash -> Int -> Hash
mask Hash
h Int
s
            i :: Int
i = Hash -> Hash -> Int
sparseIndex Hash
b Hash
m
    go collPos :: Int
collPos h :: Hash
h k :: k
k s :: Int
s (Full ary :: 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' = Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
forall k v. Int -> Hash -> k -> Int -> HashMap k v -> HashMap k v
go Int
collPos Hash
h k
k (Int
sInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
bitsPerSubkey) HashMap k v
st
        in case HashMap k v
st' of
            Empty ->
                let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Int -> Array (HashMap k v)
forall e. Array e -> Int -> Array e
A.delete Array (HashMap k v)
ary Int
i
                    bm :: Hash
bm   = Hash
fullNodeMask Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Bits a => a -> a
complement (1 Hash -> Int -> Hash
`unsafeShiftL` Int
i)
                in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
bm Array (HashMap k v)
ary'
            _ -> Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full (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
st')
      where i :: Int
i = Hash -> Int -> Int
index Hash
h Int
s
    go collPos :: Int
collPos h :: Hash
h _ _ (Collision _hy :: Hash
_hy v :: Array (Leaf k v)
v)
      | Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
v Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 2
      = if Int
collPos Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== 0
        then Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
v 1)
        else Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Array (Leaf k v) -> Int -> Leaf k v
forall a. Array a -> Int -> a
A.index Array (Leaf k v)
v 0)
      | Bool
otherwise = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Array (Leaf k v) -> Int -> Array (Leaf k v)
forall e. Array e -> Int -> Array e
A.delete Array (Leaf k v)
v Int
collPos)
    go !Int
_ !Hash
_ !k
_ !Int
_ Empty = HashMap k v
forall k v. HashMap k v
Empty -- error "Internal error: deleteKeyExists empty"
{-# NOINLINE deleteKeyExists #-}

-- | /O(log n)/ Adjust the value tied to a given key in this map only
-- if it is present. Otherwise, leave the map alone.
adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v
-- This operation really likes to leak memory, so using this
-- indirect implementation shouldn't hurt much. Furthermore, it allows
-- GHC to avoid a leak when the function is lazy. In particular,
--
--     adjust (const x) k m
-- ==> adjust# (\v -> (# const x v #)) k m
-- ==> adjust# (\_ -> (# x #)) k m
adjust :: (v -> v) -> k -> HashMap k v -> HashMap k v
adjust f :: v -> v
f k :: k
k m :: HashMap k v
m = (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(v -> (# v #)) -> k -> HashMap k v -> HashMap k v
adjust# (\v :: v
v -> (# v -> v
f v
v #)) k
k HashMap k v
m
{-# INLINE adjust #-}

-- | Much like 'adjust', but not inherently leaky.
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# f :: v -> (# v #)
f k0 :: k
k0 m0 :: HashMap k v
m0 = Hash -> k -> Int -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 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
_ Empty = HashMap k v
forall k v. HashMap k v
Empty
    go h :: Hash
h k :: k
k _ t :: HashMap k v
t@(Leaf hy :: Hash
hy (L ky :: k
ky y :: 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 = case v -> (# v #)
f v
y of
            (# y' :: v
y' #) | v -> v -> Bool
forall a. a -> a -> Bool
ptrEq v
y v
y' -> HashMap k v
t
                     | Bool
otherwise -> 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
y')
        | Bool
otherwise          = HashMap k v
t
    go h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(BitmapIndexed b :: Hash
b ary :: 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
== 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 if HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
ptrEq HashMap k v
st HashMap k v
st'
                         then HashMap k v
t
                         else 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 h :: Hash
h k :: k
k s :: Int
s t :: HashMap k v
t@(Full ary :: 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 if HashMap k v -> HashMap k v -> Bool
forall a. a -> a -> Bool
ptrEq HashMap k v
st HashMap k v
st'
           then HashMap k v
t
           else Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
    go h :: Hash
h k :: k
k _ t :: HashMap k v
t@(Collision hy :: Hash
hy v :: Array (Leaf k v)
v)
        | Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy   = let !v' :: Array (Leaf k v)
v' = (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
                      in if Array (Leaf k v) -> Array (Leaf k v) -> Bool
forall a b. Array a -> Array b -> Bool
A.unsafeSameArray Array (Leaf k v)
v Array (Leaf k v)
v'
                         then HashMap k v
t
                         else Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h Array (Leaf k v)
v'
        | Bool
otherwise = HashMap k v
t
{-# INLINABLE adjust# #-}

-- | /O(log n)/  The expression (@'update' f k map@) updates the value @x@ at @k@,
-- (if it is in the map). If (f k x) is @'Nothing', the element is deleted.
-- If it is (@'Just' y), the key k is bound to the new value y.
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 f :: 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 #-}


-- | /O(log n)/  The expression (@'alter' f k map@) alters the value @x@ at @k@, or
-- absence thereof. @alter@ can be used to insert, delete, or update a value in a
-- map. In short : @'lookup' k ('alter' f k m) = f ('lookup' k m)@.
alter :: (Eq k, Hashable k) => (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
-- TODO(m-renaud): Consider using specialized insert and delete for alter.
alter :: (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
alter f :: Maybe v -> Maybe v
f k :: k
k m :: 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
lookup k
k HashMap k v
m) of
    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
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 #-}

-- | /O(log n)/  The expression (@'alterF' f k map@) alters the value @x@ at
-- @k@, or absence thereof. @alterF@ can be used to insert, delete, or update
-- a value in a map.
--
-- Note: 'alterF' is a flipped version of the 'at' combinator from
-- <https://hackage.haskell.org/package/lens-4.15.4/docs/Control-Lens-At.html#v:at Control.Lens.At>.
--
-- @since 0.2.9
alterF :: (Functor f, Eq k, Hashable k)
       => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
-- We only calculate the hash once, but unless this is rewritten
-- by rules we may test for key equality multiple times.
-- We force the value of the map for consistency with the rewritten
-- version; otherwise someone could tell the difference using a lazy
-- @f@ and a functor that is similar to Const but not actually Const.
alterF :: (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterF f :: 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
$ \fres :: Maybe v
fres ->
    case Maybe v
fres of
      Nothing -> 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
      Just v' :: 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

-- We unconditionally rewrite alterF in RULES, but we expose an
-- unfolding just in case it's used in some way that prevents the
-- rule from firing.
{-# INLINABLE [0] alterF #-}

#if MIN_VERSION_base(4,8,0)
-- This is just a bottom value. See the comment on the "alterFWeird"
-- rule.
test_bottom :: a
test_bottom :: a
test_bottom = [Char] -> a
forall a. HasCallStack => [Char] -> a
error "Data.HashMap.alterF internal error: hit test_bottom"

-- We use this as an error result in RULES to ensure we don't get
-- any useless CallStack nonsense.
bogus# :: (# #) -> (# a #)
bogus# :: (# #) -> (# a #)
bogus# _ = [Char] -> (# a #)
forall a. HasCallStack => [Char] -> a
error "Data.HashMap.alterF internal error: hit bogus#"

{-# RULES
-- We probe the behavior of @f@ by applying it to Nothing and to
-- Just test_bottom. Based on the results, and how they relate to
-- each other, we choose the best implementation.

"alterFWeird" forall f. alterF f =
   alterFWeird (f Nothing) (f (Just test_bottom)) f

-- This rule covers situations where alterF is used to simply insert or
-- delete in Identity (most likely via Control.Lens.At). We recognize here
-- (through the repeated @x@ on the LHS) that
--
-- @f Nothing = f (Just bottom)@,
--
-- which guarantees that @f@ doesn't care what its argument is, so
-- we don't have to either.
--
-- Why only Identity? A variant of this rule is actually valid regardless of
-- the functor, but for some functors (e.g., []), it can lead to the
-- same keys being compared multiple times, which is bad if they're
-- ugly things like strings. This is unfortunate, since the rule is likely
-- a good idea for almost all realistic uses, but I don't like nasty
-- edge cases.
"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})

-- This rule handles the case where 'alterF' is used to do 'insertWith'-like
-- things. Whenever possible, GHC will get rid of the Maybe nonsense for us.
-- We delay this rule to stage 1 so alterFconstant has a chance to fire.
"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 #)))

-- Handle the case where someone uses 'alterF' instead of 'adjust'. This
-- rule is kind of picky; it will only work if the function doesn't
-- do anything between case matching on the Maybe and producing a result.
"alterFadjust" forall (f :: Maybe a -> Identity (Maybe a)) _y.
  alterFWeird (coerce Nothing) (coerce (Just _y)) f =
    coerce (adjust# (\x -> case runIdentity (f (Just x)) of
                               Just x' -> (# x' #)
                               Nothing -> bogus# (# #)))

-- The simple specialization to Const; in this case we can look up
-- the key without caring what position it's in. This is only a tiny
-- optimization.
"alterFlookup" forall _ign1 _ign2 (f :: Maybe a -> Const r (Maybe a)).
  alterFWeird _ign1 _ign2 f = \ !k !m -> Const (getConst (f (lookup k m)))
 #-}

-- This is a very unsafe version of alterF used for RULES. When calling
-- alterFWeird x y f, the following *must* hold:
--
-- x = f Nothing
-- y = f (Just _|_)
--
-- Failure to abide by these laws will make demons come out of your nose.
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)
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 #-}

-- | This is the default version of alterF that we use in most non-trivial
-- cases. It's called "eager" because it looks up the given key in the map
-- eagerly, whether or not the given function requires that information.
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 f :: Maybe v -> f (Maybe v)
f !k
k m :: 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
$ \fres :: Maybe v
fres ->
  case Maybe v
fres of

    ------------------------------
    -- Delete the key from the map.
    Nothing -> case LookupRes v
lookupRes of

      -- Key did not exist in the map to begin with, no-op
      Absent -> HashMap k v
m

      -- Key did exist
      Present _ collPos :: 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

    ------------------------------
    -- Update value
    Just v' :: v
v' -> case LookupRes v
lookupRes of

      -- Key did not exist before, insert v' under a new key
      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

      -- Key existed before
      Present v :: v
v collPos :: Int
collPos ->
        if v
v v -> v -> Bool
forall a. a -> a -> Bool
`ptrEq` v
v'
        -- If the value is identical, no-op
        then HashMap k v
m
        -- If the value changed, update the value.
        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
           Absent -> Maybe v
forall a. Maybe a
Nothing
           Present v :: v
v _ -> v -> Maybe v
forall a. a -> Maybe a
Just v
v
{-# INLINABLE alterFEager #-}
#endif


------------------------------------------------------------------------
-- * Combine

-- | /O(n+m)/ 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 :: (Eq k, Hashable k) => HashMap k v -> HashMap k v -> HashMap k v
union :: HashMap k v -> HashMap k v -> HashMap k v
union = (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
unionWith v -> v -> v
forall a b. a -> b -> a
const
{-# INLINABLE union #-}

-- | /O(n+m)/ The union of two maps.  If a key occurs in both maps,
-- the provided function (first argument) will be used to compute the
-- result.
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 f :: 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 #-}

-- | /O(n+m)/ 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 :: (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 f :: k -> v -> v -> v
f = Int -> HashMap k v -> HashMap k v -> HashMap k v
go 0
  where
    -- empty vs. anything
    go :: Int -> HashMap k v -> HashMap k v -> HashMap k v
go !Int
_ t1 :: HashMap k v
t1 Empty = HashMap k v
t1
    go _ Empty t2 :: HashMap k v
t2 = HashMap k v
t2
    -- leaf vs. leaf
    go s :: Int
s t1 :: HashMap k v
t1@(Leaf h1 :: Hash
h1 l1 :: Leaf k v
l1@(L k1 :: k
k1 v1 :: v
v1)) t2 :: HashMap k v
t2@(Leaf h2 :: Hash
h2 l2 :: Leaf k v
l2@(L k2 :: k
k2 v2 :: 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 -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h1 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L 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 s :: Int
s t1 :: HashMap k v
t1@(Leaf h1 :: Hash
h1 (L k1 :: k
k1 v1 :: v
v1)) t2 :: HashMap k v
t2@(Collision h2 :: Hash
h2 ls2 :: 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 s :: Int
s t1 :: HashMap k v
t1@(Collision h1 :: Hash
h1 ls1 :: Array (Leaf k v)
ls1) t2 :: HashMap k v
t2@(Leaf h2 :: Hash
h2 (L k2 :: k
k2 v2 :: 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 s :: Int
s t1 :: HashMap k v
t1@(Collision h1 :: Hash
h1 ls1 :: Array (Leaf k v)
ls1) t2 :: HashMap k v
t2@(Collision h2 :: Hash
h2 ls2 :: 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
    -- branch vs. branch
    go s :: Int
s (BitmapIndexed b1 :: Hash
b1 ary1 :: Array (HashMap k v)
ary1) (BitmapIndexed b2 :: Hash
b2 ary2 :: 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 s :: Int
s (BitmapIndexed b1 :: Hash
b1 ary1 :: Array (HashMap k v)
ary1) (Full ary2 :: 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 s :: Int
s (Full ary1 :: Array (HashMap k v)
ary1) (BitmapIndexed b2 :: Hash
b2 ary2 :: 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 s :: Int
s (Full ary1 :: Array (HashMap k v)
ary1) (Full ary2 :: 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'
    -- leaf vs. branch
    go s :: Int
s (BitmapIndexed b1 :: Hash
b1 ary1 :: Array (HashMap k v)
ary1) t2 :: 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
== 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
$ \st1 :: 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 s :: Int
s t1 :: HashMap k v
t1 (BitmapIndexed b2 :: Hash
b2 ary2 :: 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
== 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
$ \st2 :: 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 s :: Int
s (Full ary1 :: Array (HashMap k v)
ary1) t2 :: 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
$ \st1 :: 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 s :: Int
s t1 :: HashMap k v
t1 (Full ary2 :: 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
$ \st2 :: 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 h :: Hash
h _) = Hash
h
    leafHashCode (Collision h :: Hash
h _) = Hash
h
    leafHashCode _ = [Char] -> Hash
forall a. HasCallStack => [Char] -> a
error "leafHashCode"

    goDifferentHash :: Int -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash s :: Int
s h1 :: Hash
h1 h2 :: Hash
h2 t1 :: HashMap k v
t1 t2 :: 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 #-}

-- | Strict in the result of @f@.
unionArrayBy :: (a -> a -> a) -> Bitmap -> Bitmap -> A.Array a -> A.Array a
             -> A.Array a
unionArrayBy :: (a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
unionArrayBy f :: a -> a -> a
f b1 :: Hash
b1 b2 :: Hash
b2 ary1 :: Array a
ary1 ary2 :: Array a
ary2 = (forall s. ST s (MArray s a)) -> Array a
forall e. (forall s. ST s (MArray s e)) -> Array e
A.run ((forall s. ST s (MArray s a)) -> Array a)
-> (forall s. ST s (MArray s a)) -> Array a
forall a b. (a -> b) -> a -> b
$ do
    let b' :: Hash
b' = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
b2
    MArray s a
mary <- Int -> ST s (MArray s a)
forall s a. Int -> ST s (MArray s a)
A.new_ (Hash -> Int
forall a. Bits a => a -> Int
popCount Hash
b')
    -- iterate over nonzero bits of b1 .|. b2
    -- it would be nice if we could shift m by more than 1 each time
    let ba :: Hash
ba = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
b2
        go :: Int -> Int -> Int -> Hash -> ST s ()
go !Int
i !Int
i1 !Int
i2 !Hash
m
            | Hash
m Hash -> Hash -> Bool
forall a. Ord a => a -> a -> Bool
> Hash
b'        = () -> ST s ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
            | Hash
b' Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = Int -> Int -> Int -> Hash -> ST s ()
go Int
i Int
i1 Int
i2 (Hash
m Hash -> Int -> Hash
`unsafeShiftL` 1)
            | Hash
ba Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
/= 0 = do
                a
x1 <- Array a -> Int -> ST s a
forall a s. Array a -> Int -> ST s a
A.indexM Array a
ary1 Int
i1
                a
x2 <- Array a -> Int -> ST s a
forall a s. Array a -> Int -> ST s a
A.indexM Array a
ary2 Int
i2
                MArray s a -> Int -> a -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s a
mary Int
i (a -> ST s ()) -> a -> ST s ()
forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
x1 a
x2
                Int -> Int -> Int -> Hash -> ST s ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i1Int -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Hash
m Hash -> Int -> Hash
`unsafeShiftL` 1)
            | Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
/= 0 = do
                MArray s a -> Int -> a -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s a
mary Int
i (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Array a -> Int -> ST s a
forall a s. Array a -> Int -> ST s a
A.indexM Array a
ary1 Int
i1
                Int -> Int -> Int -> Hash -> ST s ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i1Int -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i2  ) (Hash
m Hash -> Int -> Hash
`unsafeShiftL` 1)
            | Bool
otherwise     = do
                MArray s a -> Int -> a -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s a
mary Int
i (a -> ST s ()) -> ST s a -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Array a -> Int -> ST s a
forall a s. Array a -> Int -> ST s a
A.indexM Array a
ary2 Int
i2
                Int -> Int -> Int -> Hash -> ST s ()
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i1  ) (Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Hash
m Hash -> Int -> Hash
`unsafeShiftL` 1)
    Int -> Int -> Int -> Hash -> ST s ()
go 0 0 0 (Hash
b' Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Num a => a -> a
negate Hash
b') -- XXX: b' must be non-zero
    MArray s a -> ST s (MArray s a)
forall (m :: * -> *) a. Monad m => a -> m a
return MArray s a
mary
    -- TODO: For the case where b1 .&. b2 == b1, i.e. when one is a
    -- subset of the other, we could use a slightly simpler algorithm,
    -- where we copy one array, and then update.
{-# INLINE unionArrayBy #-}

-- TODO: Figure out the time complexity of 'unions'.

-- | Construct a set containing all elements from a list of sets.
unions :: (Eq k, Hashable k) => [HashMap k v] -> HashMap k v
unions :: [HashMap k v] -> HashMap k v
unions = (HashMap k v -> HashMap k v -> HashMap k v)
-> HashMap k v -> [HashMap k v] -> HashMap k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl' HashMap k v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
HashMap k v -> HashMap k v -> HashMap k v
union HashMap k v
forall k v. HashMap k v
empty
{-# INLINE unions #-}

------------------------------------------------------------------------
-- * Transformations

-- | /O(n)/ Transform this map by applying a function to every value.
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey f :: k -> v1 -> v2
f = HashMap k v1 -> HashMap k v2
go
  where
    go :: HashMap k v1 -> HashMap k v2
go Empty = HashMap k v2
forall k v. HashMap k v
Empty
    go (Leaf h :: Hash
h (L k :: k
k v :: v1
v)) = Hash -> Leaf k v2 -> HashMap k v2
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Leaf k v2 -> HashMap k v2) -> Leaf k v2 -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k (k -> v1 -> v2
f k
k v1
v)
    go (BitmapIndexed b :: Hash
b ary :: 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 ary :: 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
    -- Why map strictly over collision arrays? Because there's no
    -- point suspending the O(1) work this does for each leaf.
    go (Collision h :: Hash
h ary :: 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
k v :: v1
v) -> k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k (k -> v1 -> v2
f k
k v1
v)) Array (Leaf k v1)
ary
{-# INLINE mapWithKey #-}

-- | /O(n)/ Transform this map by applying a function to every value.
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2
map f :: 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 #-}

-- TODO: We should be able to use mutation to create the new
-- 'HashMap'.

-- | /O(n)/ Perform an 'Applicative' action for each key-value pair
-- in a 'HashMap' and produce a 'HashMap' of all the results.
--
-- Note: the order in which the actions occur is unspecified. In particular,
-- when the map contains hash collisions, the order in which the actions
-- associated with the keys involved will depend in an unspecified way on
-- their insertion order.
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 f :: k -> v1 -> f v2
f = HashMap k v1 -> f (HashMap k v2)
go
  where
    go :: HashMap k v1 -> f (HashMap k v2)
go 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 h :: Hash
h (L k :: k
k v :: v1
v))      = Hash -> Leaf k v2 -> HashMap k v2
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (Leaf k v2 -> HashMap k v2)
-> (v2 -> Leaf k v2) -> v2 -> HashMap k v2
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L 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 b :: Hash
b ary :: 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 ary :: 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 h :: Hash
h ary :: 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
k v :: v1
v) -> k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k (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 #-}

------------------------------------------------------------------------
-- * Difference and intersection

-- | /O(n*log m)/ Difference of two maps. Return elements of the first map
-- not existing in the second.
difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v
difference :: HashMap k v -> HashMap k w -> HashMap k v
difference a :: HashMap k v
a b :: 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 m :: HashMap k v
m k :: k
k v :: v
v = case k -> HashMap k w -> Maybe w
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k w
b of
                 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
                 _       -> HashMap k v
m
{-# INLINABLE difference #-}

-- | /O(n*log m)/ 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 :: (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 f :: v -> w -> Maybe v
f a :: HashMap k v
a b :: 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 m :: HashMap k v
m k :: k
k v :: v
v = case k -> HashMap k w -> Maybe w
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k w
b of
                 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
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 (\y :: 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 #-}

-- | /O(n*log m)/ Intersection of two maps. Return elements of the first
-- map for keys existing in the second.
intersection :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v
intersection :: HashMap k v -> HashMap k w -> HashMap k v
intersection a :: HashMap k v
a b :: 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 m :: HashMap k v
m k :: k
k v :: v
v = case k -> HashMap k w -> Maybe w
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k w
b of
                 Just _ -> 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
                 _      -> HashMap k v
m
{-# INLINABLE intersection #-}

-- | /O(n+m)/ 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 :: (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 f :: v1 -> v2 -> v3
f a :: HashMap k v1
a b :: 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 m :: HashMap k v3
m k :: k
k v :: v1
v = case k -> HashMap k v2 -> Maybe v2
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k v2
b of
                 Just w :: 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
                 _      -> HashMap k v3
m
{-# INLINABLE intersectionWith #-}

-- | /O(n+m)/ 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 :: (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 f :: k -> v1 -> v2 -> v3
f a :: HashMap k v1
a b :: 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 m :: HashMap k v3
m k :: k
k v :: v1
v = case k -> HashMap k v2 -> Maybe v2
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
lookup k
k HashMap k v2
b of
                 Just w :: 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
                 _      -> HashMap k v3
m
{-# INLINABLE intersectionWithKey #-}

------------------------------------------------------------------------
-- * Folds

-- | /O(n)/ Reduce this map by applying a binary operator to all
-- elements, using the given starting value (typically the
-- left-identity of the operator).  Each application of the operator
-- is evaluated before using the result in the next application. 
-- This function is strict in the starting value.
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a
foldl' f :: a -> v -> a
f = (a -> k -> v -> a) -> a -> HashMap k v -> a
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' (\ z :: a
z _ v :: v
v -> a -> v -> a
f a
z v
v)
{-# INLINE foldl' #-}

-- | /O(n)/ Reduce this map by applying a binary operator to all
-- elements, using the given starting value (typically the
-- left-identity of the operator).  Each application of the operator
-- is evaluated before using the result in the next application.  
-- This function is strict in the starting value.
foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey' f :: a -> k -> v -> a
f = a -> HashMap k v -> a
go
  where
    go :: a -> HashMap k v -> a
go !a
z Empty                = a
z
    go z :: a
z (Leaf _ (L k :: k
k v :: v
v))      = a -> k -> v -> a
f a
z k
k v
v
    go z :: a
z (BitmapIndexed _ ary :: Array (HashMap k v)
ary) = (a -> HashMap k v -> a) -> a -> Array (HashMap k v) -> a
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' a -> HashMap k v -> a
go a
z Array (HashMap k v)
ary
    go z :: a
z (Full ary :: Array (HashMap k v)
ary)            = (a -> HashMap k v -> a) -> a -> Array (HashMap k v) -> a
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' a -> HashMap k v -> a
go a
z Array (HashMap k v)
ary
    go z :: a
z (Collision _ ary :: Array (Leaf k v)
ary)     = (a -> Leaf k v -> a) -> a -> Array (Leaf k v) -> a
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' (\ z' :: a
z' (L k :: k
k v :: v
v) -> a -> k -> v -> a
f a
z' k
k v
v) a
z Array (Leaf k v)
ary
{-# INLINE foldlWithKey' #-}

-- | /O(n)/ Reduce this map by applying a binary operator to all
-- elements, using the given starting value (typically the
-- right-identity of the operator).
foldr :: (v -> a -> a) -> a -> HashMap k v -> a
foldr :: (v -> a -> a) -> a -> HashMap k v -> a
foldr f :: v -> a -> a
f = (k -> v -> a -> a) -> a -> HashMap k v -> a
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey ((v -> a -> a) -> k -> v -> a -> a
forall a b. a -> b -> a
const v -> a -> a
f)
{-# INLINE foldr #-}

-- | /O(n)/ Reduce this map by applying a binary operator to all
-- elements, using the given starting value (typically the
-- right-identity of the operator).
foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey f :: k -> v -> a -> a
f = a -> HashMap k v -> a
go
  where
    go :: a -> HashMap k v -> a
go z :: a
z Empty                 = a
z
    go z :: a
z (Leaf _ (L k :: k
k v :: v
v))      = k -> v -> a -> a
f k
k v
v a
z
    go z :: a
z (BitmapIndexed _ ary :: Array (HashMap k v)
ary) = (HashMap k v -> a -> a) -> a -> Array (HashMap k v) -> a
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr ((a -> HashMap k v -> a) -> HashMap k v -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> HashMap k v -> a
go) a
z Array (HashMap k v)
ary
    go z :: a
z (Full ary :: Array (HashMap k v)
ary)            = (HashMap k v -> a -> a) -> a -> Array (HashMap k v) -> a
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr ((a -> HashMap k v -> a) -> HashMap k v -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> HashMap k v -> a
go) a
z Array (HashMap k v)
ary
    go z :: a
z (Collision _ ary :: Array (Leaf k v)
ary)     = (Leaf k v -> a -> a) -> a -> Array (Leaf k v) -> a
forall a b. (a -> b -> b) -> b -> Array a -> b
A.foldr (\ (L k :: k
k v :: v
v) z' :: a
z' -> k -> v -> a -> a
f k
k v
v a
z') a
z Array (Leaf k v)
ary
{-# INLINE foldrWithKey #-}

------------------------------------------------------------------------
-- * Filter

-- | /O(n)/ Transform this map by applying a function to every value
--   and retaining only some of them.
mapMaybeWithKey :: (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybeWithKey :: (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybeWithKey f :: 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 h :: Hash
h (L k :: k
k v :: v1
v)) | Just v' :: 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 -> Leaf k v2 -> HashMap k v2
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k v2
v'))
        onLeaf _ = Maybe (HashMap k v2)
forall a. Maybe a
Nothing

        onColl :: Leaf k v1 -> Maybe (Leaf k v2)
onColl (L k :: k
k v :: v1
v) | Just v' :: 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 #-}

-- | /O(n)/ Transform this map by applying a function to every value
--   and retaining only some of them.
mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybe f :: 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 #-}

-- | /O(n)/ Filter this map by retaining only elements satisfying a
-- predicate.
filterWithKey :: forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v
filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v
filterWithKey pred :: k -> v -> Bool
pred = (HashMap k v -> Maybe (HashMap k v))
-> (Leaf k v -> Maybe (Leaf k v)) -> HashMap k v -> HashMap k v
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 v -> Maybe (HashMap k v)
onLeaf Leaf k v -> Maybe (Leaf k v)
onColl
  where onLeaf :: HashMap k v -> Maybe (HashMap k v)
onLeaf t :: HashMap k v
t@(Leaf _ (L k :: k
k v :: v
v)) | k -> v -> Bool
pred k
k v
v = HashMap k v -> Maybe (HashMap k v)
forall a. a -> Maybe a
Just HashMap k v
t
        onLeaf _ = Maybe (HashMap k v)
forall a. Maybe a
Nothing

        onColl :: Leaf k v -> Maybe (Leaf k v)
onColl el :: Leaf k v
el@(L k :: k
k v :: v
v) | k -> v -> Bool
pred k
k v
v = Leaf k v -> Maybe (Leaf k v)
forall a. a -> Maybe a
Just Leaf k v
el
        onColl _ = Maybe (Leaf k v)
forall a. Maybe a
Nothing
{-# INLINE filterWithKey #-}


-- | Common implementation for 'filterWithKey' and 'mapMaybeWithKey',
--   allowing the former to former to reuse terms.
filterMapAux :: 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))
-> (Leaf k v1 -> Maybe (Leaf k v2)) -> HashMap k v1 -> HashMap k v2
filterMapAux onLeaf :: HashMap k v1 -> Maybe (HashMap k v2)
onLeaf onColl :: Leaf k v1 -> Maybe (Leaf k v2)
onColl = HashMap k v1 -> HashMap k v2
go
  where
    go :: HashMap k v1 -> HashMap k v2
go Empty = HashMap k v2
forall k v. HashMap k v
Empty
    go t :: HashMap k v1
t@Leaf{}
        | Just t' :: HashMap k v2
t' <- HashMap k v1 -> Maybe (HashMap k v2)
onLeaf HashMap k v1
t = HashMap k v2
t'
        | Bool
otherwise = HashMap k v2
forall k v. HashMap k v
Empty
    go (BitmapIndexed b :: Hash
b ary :: Array (HashMap k v1)
ary) = Array (HashMap k v1) -> Hash -> HashMap k v2
filterA Array (HashMap k v1)
ary Hash
b
    go (Full ary :: Array (HashMap k v1)
ary) = Array (HashMap k v1) -> Hash -> HashMap k v2
filterA Array (HashMap k v1)
ary Hash
fullNodeMask
    go (Collision h :: Hash
h ary :: Array (Leaf k v1)
ary) = Array (Leaf k v1) -> Hash -> HashMap k v2
filterC Array (Leaf k v1)
ary Hash
h

    filterA :: Array (HashMap k v1) -> Hash -> HashMap k v2
filterA ary0 :: Array (HashMap k v1)
ary0 b0 :: Hash
b0 =
        let !n :: Int
n = Array (HashMap k v1) -> Int
forall a. Array a -> Int
A.length Array (HashMap k v1)
ary0
        in (forall s. ST s (HashMap k v2)) -> HashMap k v2
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (HashMap k v2)) -> HashMap k v2)
-> (forall s. ST s (HashMap k v2)) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ do
            MArray s (HashMap k v2)
mary <- Int -> ST s (MArray s (HashMap k v2))
forall s a. Int -> ST s (MArray s a)
A.new_ Int
n
            Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
forall s.
Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
step Array (HashMap k v1)
ary0 MArray s (HashMap k v2)
mary Hash
b0 0 0 1 Int
n
      where
        step :: A.Array (HashMap k v1) -> A.MArray s (HashMap k v2)
             -> Bitmap -> Int -> Int -> Bitmap -> Int
             -> ST s (HashMap k v2)
        step :: Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
step !Array (HashMap k v1)
ary !MArray s (HashMap k v2)
mary !Hash
b i :: Int
i !Int
j !Hash
bi n :: Int
n
            | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n = case Int
j of
                0 -> HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v2
forall k v. HashMap k v
Empty
                1 -> do
                    HashMap k v2
ch <- MArray s (HashMap k v2) -> Int -> ST s (HashMap k v2)
forall s a. MArray s a -> Int -> ST s a
A.read MArray s (HashMap k v2)
mary 0
                    case HashMap k v2
ch of
                      t :: HashMap k v2
t | HashMap k v2 -> Bool
forall k a. HashMap k a -> Bool
isLeafOrCollision HashMap k v2
t -> HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v2
t
                      _                       -> 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)
-> ST s (Array (HashMap k v2)) -> ST s (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MArray s (HashMap k v2) -> Int -> ST s (Array (HashMap k v2))
forall s a. MArray s a -> Int -> ST s (Array a)
A.trim MArray s (HashMap k v2)
mary 1
                _ -> do
                    Array (HashMap k v2)
ary2 <- MArray s (HashMap k v2) -> Int -> ST s (Array (HashMap k v2))
forall s a. MArray s a -> Int -> ST s (Array a)
A.trim MArray s (HashMap k v2)
mary Int
j
                    HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v2 -> ST s (HashMap k v2))
-> HashMap k v2 -> ST s (HashMap k v2)
forall a b. (a -> b) -> a -> b
$! if Int
j Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
maxChildren
                              then Array (HashMap k v2) -> HashMap k v2
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v2)
ary2
                              else 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)
ary2
            | Hash
bi Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
b Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== 0 = Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
forall s.
Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
step Array (HashMap k v1)
ary MArray s (HashMap k v2)
mary Hash
b Int
i Int
j (Hash
bi Hash -> Int -> Hash
`unsafeShiftL` 1) Int
n
            | Bool
otherwise = case HashMap k v1 -> HashMap k v2
go (Array (HashMap k v1) -> Int -> HashMap k v1
forall a. Array a -> Int -> a
A.index Array (HashMap k v1)
ary Int
i) of
                Empty -> Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
forall s.
Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
step Array (HashMap k v1)
ary MArray s (HashMap k v2)
mary (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash -> Hash
forall a. Bits a => a -> a
complement Hash
bi) (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
j
                         (Hash
bi Hash -> Int -> Hash
`unsafeShiftL` 1) Int
n
                t :: HashMap k v2
t     -> do MArray s (HashMap k v2) -> Int -> HashMap k v2 -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (HashMap k v2)
mary Int
j HashMap k v2
t
                            Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
forall s.
Array (HashMap k v1)
-> MArray s (HashMap k v2)
-> Hash
-> Int
-> Int
-> Hash
-> Int
-> ST s (HashMap k v2)
step Array (HashMap k v1)
ary MArray s (HashMap k v2)
mary Hash
b (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Hash
bi Hash -> Int -> Hash
`unsafeShiftL` 1) Int
n

    filterC :: Array (Leaf k v1) -> Hash -> HashMap k v2
filterC ary0 :: Array (Leaf k v1)
ary0 h :: Hash
h =
        let !n :: Int
n = Array (Leaf k v1) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v1)
ary0
        in (forall s. ST s (HashMap k v2)) -> HashMap k v2
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (HashMap k v2)) -> HashMap k v2)
-> (forall s. ST s (HashMap k v2)) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ do
            MArray s (Leaf k v2)
mary <- Int -> ST s (MArray s (Leaf k v2))
forall s a. Int -> ST s (MArray s a)
A.new_ Int
n
            Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
forall s.
Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
step Array (Leaf k v1)
ary0 MArray s (Leaf k v2)
mary 0 0 Int
n
      where
        step :: A.Array (Leaf k v1) -> A.MArray s (Leaf k v2)
             -> Int -> Int -> Int
             -> ST s (HashMap k v2)
        step :: Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
step !Array (Leaf k v1)
ary !MArray s (Leaf k v2)
mary i :: Int
i !Int
j n :: Int
n
            | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = case Int
j of
                0 -> HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v2
forall k v. HashMap k v
Empty
                1 -> do Leaf k v2
l <- MArray s (Leaf k v2) -> Int -> ST s (Leaf k v2)
forall s a. MArray s a -> Int -> ST s a
A.read MArray s (Leaf k v2)
mary 0
                        HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v2 -> ST s (HashMap k v2))
-> HashMap k v2 -> ST s (HashMap k v2)
forall a b. (a -> b) -> a -> b
$! Hash -> Leaf k v2 -> HashMap k v2
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h Leaf k v2
l
                _ | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j -> do Array (Leaf k v2)
ary2 <- MArray s (Leaf k v2) -> ST s (Array (Leaf k v2))
forall s a. MArray s a -> ST s (Array a)
A.unsafeFreeze MArray s (Leaf k v2)
mary
                                 HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v2 -> ST s (HashMap k v2))
-> HashMap k v2 -> ST s (HashMap k v2)
forall a b. (a -> b) -> a -> b
$! 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)
ary2
                  | Bool
otherwise -> do Array (Leaf k v2)
ary2 <- MArray s (Leaf k v2) -> Int -> ST s (Array (Leaf k v2))
forall s a. MArray s a -> Int -> ST s (Array a)
A.trim MArray s (Leaf k v2)
mary Int
j
                                    HashMap k v2 -> ST s (HashMap k v2)
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v2 -> ST s (HashMap k v2))
-> HashMap k v2 -> ST s (HashMap k v2)
forall a b. (a -> b) -> a -> b
$! 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)
ary2
            | Just el :: Leaf k v2
el <- Leaf k v1 -> Maybe (Leaf k v2)
onColl (Leaf k v1 -> Maybe (Leaf k v2)) -> Leaf k v1 -> Maybe (Leaf k v2)
forall a b. (a -> b) -> a -> b
$! Array (Leaf k v1) -> Int -> Leaf k v1
forall a. Array a -> Int -> a
A.index Array (Leaf k v1)
ary Int
i
                = MArray s (Leaf k v2) -> Int -> Leaf k v2 -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s (Leaf k v2)
mary Int
j Leaf k v2
el ST s () -> ST s (HashMap k v2) -> ST s (HashMap k v2)
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
forall s.
Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
step Array (Leaf k v1)
ary MArray s (Leaf k v2)
mary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
jInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
n
            | Bool
otherwise = Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
forall s.
Array (Leaf k v1)
-> MArray s (Leaf k v2) -> Int -> Int -> Int -> ST s (HashMap k v2)
step Array (Leaf k v1)
ary MArray s (Leaf k v2)
mary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
j Int
n
{-# INLINE filterMapAux #-}

-- | /O(n)/ Filter this map by retaining only elements which values
-- satisfy a predicate.
filter :: (v -> Bool) -> HashMap k v -> HashMap k v
filter :: (v -> Bool) -> HashMap k v -> HashMap k v
filter p :: v -> Bool
p = (k -> v -> Bool) -> HashMap k v -> HashMap k v
forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v
filterWithKey (\_ v :: v
v -> v -> Bool
p v
v)
{-# INLINE filter #-}

------------------------------------------------------------------------
-- * Conversions

-- TODO: Improve fusion rules by modelled them after the Prelude ones
-- on lists.

-- | /O(n)/ Return a list of this map's keys.  The list is produced
-- lazily.
keys :: HashMap k v -> [k]
keys :: HashMap k v -> [k]
keys = ((k, v) -> k) -> [(k, v)] -> [k]
forall a b. (a -> b) -> [a] -> [b]
L.map (k, v) -> k
forall a b. (a, b) -> a
fst ([(k, v)] -> [k])
-> (HashMap k v -> [(k, v)]) -> HashMap k v -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap k v -> [(k, v)]
forall k v. HashMap k v -> [(k, v)]
toList
{-# INLINE keys #-}

-- | /O(n)/ Return a list of this map's values.  The list is produced
-- lazily.
elems :: HashMap k v -> [v]
elems :: HashMap k v -> [v]
elems = ((k, v) -> v) -> [(k, v)] -> [v]
forall a b. (a -> b) -> [a] -> [b]
L.map (k, v) -> v
forall a b. (a, b) -> b
snd ([(k, v)] -> [v])
-> (HashMap k v -> [(k, v)]) -> HashMap k v -> [v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap k v -> [(k, v)]
forall k v. HashMap k v -> [(k, v)]
toList
{-# INLINE elems #-}

------------------------------------------------------------------------
-- ** Lists

-- | /O(n)/ Return a list of this map's elements.  The list is
-- produced lazily. The order of its elements is unspecified.
toList :: HashMap k v -> [(k, v)]
toList :: HashMap k v -> [(k, v)]
toList t :: HashMap k v
t = (forall b. ((k, v) -> b -> b) -> b -> b) -> [(k, v)]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\ c :: (k, v) -> b -> b
c z :: b
z -> (k -> v -> b -> b) -> b -> HashMap k v -> b
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey (((k, v) -> b -> b) -> k -> v -> b -> b
forall a b c. ((a, b) -> c) -> a -> b -> c
curry (k, v) -> b -> b
c) b
z HashMap k v
t)
{-# INLINE toList #-}

-- | /O(n)/ Construct a map with the supplied mappings.  If the list
-- contains duplicate mappings, the later mappings take precedence.
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' (\ m :: HashMap k v
m (k :: k
k, v :: 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
unsafeInsert k
k v
v HashMap k v
m) HashMap k v
forall k v. HashMap k v
empty
{-# INLINABLE fromList #-}

-- | /O(n*log n)/ Construct a map from a list of elements.  Uses
-- the provided function to merge duplicate entries.
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWith :: (v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWith f :: 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' (\ m :: HashMap k v
m (k :: k
k, v :: 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 #-}

------------------------------------------------------------------------
-- Array operations

-- | /O(n)/ Look up the value associated with the given key in an
-- array.
lookupInArrayCont ::
#if __GLASGOW_HASKELL__ >= 802
  forall rep (r :: TYPE rep) k v.
#else
  forall r k v.
#endif
  Eq k => ((# #) -> r) -> (v -> Int -> r) -> k -> A.Array (Leaf k v) -> r
lookupInArrayCont :: ((# #) -> r) -> (v -> Int -> r) -> k -> Array (Leaf k v) -> r
lookupInArrayCont absent :: (# #) -> r
absent present :: v -> Int -> r
present k0 :: k
k0 ary0 :: Array (Leaf k v)
ary0 = k -> Array (Leaf k v) -> Int -> Int -> r
Eq k => k -> Array (Leaf k v) -> Int -> Int -> r
go k
k0 Array (Leaf k v)
ary0 0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
  where
    go :: Eq k => k -> A.Array (Leaf k v) -> Int -> Int -> r
    go :: k -> Array (Leaf k v) -> Int -> Int -> r
go !k
k !Array (Leaf k v)
ary !Int
i !Int
n
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = (# #) -> r
absent (# #)
        | 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 kx :: k
kx v :: v
v)
                | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx   -> v -> Int -> r
present v
v Int
i
                | Bool
otherwise -> k -> Array (Leaf k v) -> Int -> Int -> r
Eq k => k -> Array (Leaf k v) -> Int -> Int -> r
go k
k Array (Leaf k v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
n
{-# INLINE lookupInArrayCont #-}

-- | /O(n)/ Lookup the value associated with the given key in this
-- array.  Returns 'Nothing' if the key wasn't found.
indexOf :: Eq k => k -> A.Array (Leaf k v) -> Maybe Int
indexOf :: k -> Array (Leaf k v) -> Maybe Int
indexOf k0 :: k
k0 ary0 :: Array (Leaf k v)
ary0 = k -> Array (Leaf k v) -> Int -> Int -> Maybe Int
forall t v.
Eq t =>
t -> Array (Leaf t v) -> Int -> Int -> Maybe Int
go k
k0 Array (Leaf k v)
ary0 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 -> Maybe Int
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    = Maybe Int
forall a. Maybe a
Nothing
        | 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 kx :: t
kx _)
                | t
k t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
kx   -> Int -> Maybe Int
forall a. a -> Maybe a
Just Int
i
                | Bool
otherwise -> t -> Array (Leaf t v) -> Int -> Int -> Maybe Int
go t
k Array (Leaf t v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) Int
n
{-# INLINABLE indexOf #-}

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# f :: v -> (# v #)
f k0 :: k
k0 ary0 :: Array (Leaf k v)
ary0 = k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k0 Array (Leaf k v)
ary0 0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
  where
    go :: k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go !k
k !Array (Leaf k v)
ary !Int
i !Int
n
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = Array (Leaf k v)
ary
        | 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 kx :: k
kx y :: v
y) | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx -> case v -> (# v #)
f v
y of
                          (# y' :: v
y' #)
                             | v -> v -> Bool
forall a. a -> a -> Bool
ptrEq v
y v
y' -> Array (Leaf k v)
ary
                             | Bool
otherwise -> 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
y')
                     | Bool
otherwise -> k -> Array (Leaf k v) -> Int -> Int -> Array (Leaf k v)
go k
k Array (Leaf k v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+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 f :: 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 f :: k -> v -> v -> v
f k0 :: k
k0 v0 :: v
v0 ary0 :: 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 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
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
            -- Not found, append to the end.
            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
+ 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 0 MArray s (Leaf k v)
mary 0 Int
n
            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 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v)
            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 kx :: k
kx y :: v
y) | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx   -> 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 (k -> v -> v -> v
f k
k v
v v
y))
                     | 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
+1) Int
n
{-# INLINABLE updateOrSnocWithKey #-}

updateOrConcatWith :: Eq k => (v -> v -> v) -> A.Array (Leaf k v) -> A.Array (Leaf k v) -> A.Array (Leaf k v)
updateOrConcatWith :: (v -> v -> v)
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
updateOrConcatWith f :: v -> v -> v
f = (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 ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f)
{-# INLINABLE updateOrConcatWith #-}

updateOrConcatWithKey :: Eq k => (k -> v -> v -> v) -> A.Array (Leaf k v) -> A.Array (Leaf k v) -> A.Array (Leaf k v)
updateOrConcatWithKey :: (k -> v -> v -> v)
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
updateOrConcatWithKey f :: k -> v -> v -> v
f ary1 :: Array (Leaf k v)
ary1 ary2 :: Array (Leaf k v)
ary2 = (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
    -- TODO: instead of mapping and then folding, should we traverse?
    -- We'll have to be careful to avoid allocating pairs or similar.

    -- first: look up the position of each element of ary2 in ary1
    let indices :: Array (Maybe Int)
indices = (Leaf k v -> Maybe Int) -> Array (Leaf k v) -> Array (Maybe Int)
forall a b. (a -> b) -> Array a -> Array b
A.map' (\(L k :: k
k _) -> k -> Array (Leaf k v) -> Maybe Int
forall k v. Eq k => k -> Array (Leaf k v) -> Maybe Int
indexOf k
k Array (Leaf k v)
ary1) Array (Leaf k v)
ary2
    -- that tells us how large the overlap is:
    -- count number of Nothing constructors
    let nOnly2 :: Int
nOnly2 = (Int -> Maybe Int -> Int) -> Int -> Array (Maybe Int) -> Int
forall b a. (b -> a -> b) -> b -> Array a -> b
A.foldl' (\n :: Int
n -> Int -> (Int -> Int) -> Maybe Int -> Int
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int -> Int -> Int
forall a b. a -> b -> a
const Int
n)) 0 Array (Maybe Int)
indices
    let n1 :: Int
n1 = Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary1
    let n2 :: Int
n2 = Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary2
    -- copy over all elements from ary1
    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
n1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
nOnly2)
    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)
ary1 0 MArray s (Leaf k v)
mary 0 Int
n1
    -- append or update all elements from ary2
    let go :: Int -> Int -> ST s ()
go !Int
iEnd !Int
i2
          | Int
i2 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n2 = () -> ST s ()
forall (m :: * -> *) a. Monad m => a -> m a
return ()
          | Bool
otherwise = case Array (Maybe Int) -> Int -> Maybe Int
forall a. Array a -> Int -> a
A.index Array (Maybe Int)
indices Int
i2 of
               Just i1 :: Int
i1 -> do -- key occurs in both arrays, store combination in position i1
                             L k :: k
k v1 :: v
v1 <- Array (Leaf k v) -> Int -> ST s (Leaf k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (Leaf k v)
ary1 Int
i1
                             L _ v2 :: v
v2 <- Array (Leaf k v) -> Int -> ST s (Leaf k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (Leaf k v)
ary2 Int
i2
                             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
i1 (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k (k -> v -> v -> v
f k
k v
v1 v
v2))
                             Int -> Int -> ST s ()
go Int
iEnd (Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+1)
               Nothing -> do -- key is only in ary2, append to end
                             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
iEnd (Leaf k v -> ST s ()) -> ST s (Leaf k v) -> ST s ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Array (Leaf k v) -> Int -> ST s (Leaf k v)
forall a s. Array a -> Int -> ST s a
A.indexM Array (Leaf k v)
ary2 Int
i2
                             Int -> Int -> ST s ()
go (Int
iEndInt -> Int -> Int
forall a. Num a => a -> a -> a
+1) (Int
i2Int -> Int -> Int
forall a. Num a => a -> a -> a
+1)
    Int -> Int -> ST s ()
go Int
n1 0
    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
{-# INLINABLE updateOrConcatWithKey #-}

------------------------------------------------------------------------
-- Manually unrolled loops

-- | /O(n)/ Update the element at the given position in this array.
update16 :: A.Array e -> Int -> e -> A.Array e
update16 :: Array e -> Int -> e -> Array e
update16 ary :: Array e
ary idx :: Int
idx b :: e
b = (forall s. ST s (Array e)) -> Array e
forall a. (forall s. ST s a) -> a
runST (Array e -> Int -> e -> ST s (Array e)
forall e s. Array e -> Int -> e -> ST s (Array e)
update16M Array e
ary Int
idx e
b)
{-# INLINE update16 #-}

-- | /O(n)/ Update the element at the given position in this array.
update16M :: A.Array e -> Int -> e -> ST s (A.Array e)
update16M :: Array e -> Int -> e -> ST s (Array e)
update16M ary :: Array e
ary idx :: Int
idx b :: e
b = do
    MArray s e
mary <- Array e -> ST s (MArray s e)
forall e s. Array e -> ST s (MArray s e)
clone16 Array e
ary
    MArray s e -> Int -> e -> ST s ()
forall s a. MArray s a -> Int -> a -> ST s ()
A.write MArray s e
mary Int
idx e
b
    MArray s e -> ST s (Array e)
forall s a. MArray s a -> ST s (Array a)
A.unsafeFreeze MArray s e
mary
{-# INLINE update16M #-}

-- | /O(n)/ Update the element at the given position in this array, by applying a function to it.
update16With' :: A.Array e -> Int -> (e -> e) -> A.Array e
update16With' :: Array e -> Int -> (e -> e) -> Array e
update16With' ary :: Array e
ary idx :: Int
idx f :: e -> e
f
  | (# x :: e
x #) <- Array e -> Int -> (# e #)
forall a. Array a -> Int -> (# a #)
A.index# Array e
ary Int
idx
  = Array e -> Int -> e -> Array e
forall e. Array e -> Int -> e -> Array e
update16 Array e
ary Int
idx (e -> Array e) -> e -> Array e
forall a b. (a -> b) -> a -> b
$! e -> e
f e
x
{-# INLINE update16With' #-}

-- | Unsafely clone an array of 16 elements.  The length of the input
-- array is not checked.
clone16 :: A.Array e -> ST s (A.MArray s e)
clone16 :: Array e -> ST s (MArray s e)
clone16 ary :: Array e
ary =
    Array e -> Int -> Int -> ST s (MArray s e)
forall e s. Array e -> Int -> Int -> ST s (MArray s e)
A.thaw Array e
ary 0 16

------------------------------------------------------------------------
-- Bit twiddling

bitsPerSubkey :: Int
bitsPerSubkey :: Int
bitsPerSubkey = 4

maxChildren :: Int
maxChildren :: Int
maxChildren = Hash -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Hash -> Int) -> Hash -> Int
forall a b. (a -> b) -> a -> b
$ 1 Hash -> Int -> Hash
`unsafeShiftL` Int
bitsPerSubkey

subkeyMask :: Bitmap
subkeyMask :: Hash
subkeyMask = 1 Hash -> Int -> Hash
`unsafeShiftL` Int
bitsPerSubkey Hash -> Hash -> Hash
forall a. Num a => a -> a -> a
- 1

sparseIndex :: Bitmap -> Bitmap -> Int
sparseIndex :: Hash -> Hash -> Int
sparseIndex b :: Hash
b m :: Hash
m = Hash -> Int
forall a. Bits a => a -> Int
popCount (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. (Hash
m Hash -> Hash -> Hash
forall a. Num a => a -> a -> a
- 1))

mask :: Word -> Shift -> Bitmap
mask :: Hash -> Int -> Hash
mask w :: Hash
w s :: Int
s = 1 Hash -> Int -> Hash
`unsafeShiftL` Hash -> Int -> Int
index Hash
w Int
s
{-# INLINE mask #-}

-- | Mask out the 'bitsPerSubkey' bits used for indexing at this level
-- of the tree.
index :: Hash -> Shift -> Int
index :: Hash -> Int -> Int
index w :: Hash
w s :: Int
s = Hash -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Hash -> Int) -> Hash -> Int
forall a b. (a -> b) -> a -> b
$ (Hash -> Int -> Hash
unsafeShiftR Hash
w Int
s) Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
subkeyMask
{-# INLINE index #-}

-- | A bitmask with the 'bitsPerSubkey' least significant bits set.
fullNodeMask :: Bitmap
fullNodeMask :: Hash
fullNodeMask = Hash -> Hash
forall a. Bits a => a -> a
complement (Hash -> Hash
forall a. Bits a => a -> a
complement 0 Hash -> Int -> Hash
`unsafeShiftL` Int
maxChildren)
{-# INLINE fullNodeMask #-}

-- | Check if two the two arguments are the same value.  N.B. This
-- function might give false negatives (due to GC moving objects.)
ptrEq :: a -> a -> Bool
ptrEq :: a -> a -> Bool
ptrEq x :: a
x y :: a
y = Int# -> Bool
isTrue# (a -> a -> Int#
forall a. a -> a -> Int#
reallyUnsafePtrEquality# a
x a
y Int# -> Int# -> Int#
==# 1#)
{-# INLINE ptrEq #-}

------------------------------------------------------------------------
-- IsList instance
instance (Eq k, Hashable k) => Exts.IsList (HashMap k v) where
    type Item (HashMap k v) = (k, v)
    fromList :: [Item (HashMap k v)] -> HashMap k v
fromList = [Item (HashMap k v)] -> HashMap k v
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList
    toList :: HashMap k v -> [Item (HashMap k v)]
toList   = HashMap k v -> [Item (HashMap k v)]
forall k v. HashMap k v -> [(k, v)]
toList