{-# LANGUAGE BangPatterns  #-}
{-# LANGUAGE CPP           #-}
{-# LANGUAGE LambdaCase    #-}
{-# LANGUAGE MagicHash     #-}
{-# LANGUAGE PatternGuards #-}
{-# LANGUAGE Trustworthy   #-}
{-# LANGUAGE UnboxedTuples #-}
{-# OPTIONS_HADDOCK not-home #-}

------------------------------------------------------------------------
-- |
-- Module      :  Data.HashMap.Strict
-- Copyright   :  2010-2012 Johan Tibell
-- License     :  BSD-style
-- Maintainer  :  johan.tibell@gmail.com
-- Portability :  portable
--
-- = WARNING
--
-- This module is considered __internal__.
--
-- The Package Versioning Policy __does not apply__.
--
-- The contents of this module may change __in any way whatsoever__
-- and __without any warning__ between minor versions of this package.
--
-- Authors importing this module are expected to track development
-- closely.
--
-- = Description
--
-- A map from /hashable/ keys to values.  A map cannot contain
-- duplicate keys; each key can map to at most one value.  A 'HashMap'
-- makes no guarantees as to the order of its elements.
--
-- The implementation is based on /hash array mapped tries/.  A
-- 'HashMap' is often faster than other tree-based set types,
-- especially when key comparison is expensive, as in the case of
-- strings.
--
-- Many operations have a average-case complexity of \(O(\log n)\).  The
-- implementation uses a large base (i.e. 32) so in practice these
-- operations are constant time.
module Data.HashMap.Internal.Strict
    (
      -- * Strictness properties
      -- $strictness

      HashMap

      -- * Construction
    , HM.empty
    , singleton

      -- * Basic interface
    , HM.null
    , HM.size
    , HM.member
    , HM.lookup
    , (HM.!?)
    , HM.findWithDefault
    , HM.lookupDefault
    , (HM.!)
    , insert
    , insertWith
    , HM.delete
    , adjust
    , update
    , alter
    , alterF
    , HM.isSubmapOf
    , HM.isSubmapOfBy

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

    -- ** Compose
    , HM.compose

      -- * Transformations
    , map
    , mapWithKey
    , traverseWithKey
    , HM.mapKeys

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

      -- * Folds
    , HM.foldMapWithKey
    , HM.foldr'
    , HM.foldl'
    , HM.foldrWithKey'
    , HM.foldlWithKey'
    , HM.foldr
    , HM.foldl
    , HM.foldrWithKey
    , HM.foldlWithKey

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

      -- * Conversions
    , HM.keys
    , HM.elems

      -- ** Lists
    , HM.toList
    , fromList
    , fromListWith
    , fromListWithKey
    ) where

import Control.Applicative   (Const (..))
import Control.Monad.ST      (runST)
import Data.Bits             ((.&.), (.|.))
import Data.Coerce           (coerce)
import Data.Functor.Identity (Identity (..))
-- See Note [Imports from Data.HashMap.Internal]
import Data.Hashable         (Hashable)
import Data.HashMap.Internal (Hash, HashMap (..), Leaf (..), LookupRes (..),
                              fullBitmap, hash, index, mask, nextShift, ptrEq,
                              sparseIndex)
import Prelude               hiding (lookup, map)

-- See Note [Imports from Data.HashMap.Internal]
import qualified Data.HashMap.Internal       as HM
import qualified Data.HashMap.Internal.Array as A
import qualified Data.List                   as List
import qualified GHC.Exts                    as Exts

{-
Note [Imports from Data.HashMap.Internal]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

It is very important for code in this module not to make mistakes about
the strictness properties of any utilities. Mistakes can easily lead to space
leaks, see e.g. #383.

Therefore nearly all functions imported from Data.HashMap.Internal should be
imported qualified. Only functions that do not manipulate HashMaps or their
values are exempted.
-}

-- $strictness
--
-- This module satisfies the following strictness properties:
--
-- 1. Key arguments are evaluated to WHNF;
--
-- 2. Keys and values are evaluated to WHNF before they are stored in
--    the map.

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

-- | \(O(1)\) Construct a map with a single element.
singleton :: (Hashable k) => k -> v -> HashMap k v
singleton :: forall k v. Hashable k => k -> v -> HashMap k v
singleton k
k !v
v = k -> v -> HashMap k v
forall k v. Hashable k => k -> v -> HashMap k v
HM.singleton k
k v
v

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

-- | \(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 :: forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
insert k
k !v
v = k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HM.insert k
k v
v
{-# INLINABLE insert #-}

-- | \(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
insertWith :: forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
insertWith v -> v -> v
f k
k0 v
v0 HashMap k v
m0 = Hash -> k -> v -> Shift -> HashMap k v -> HashMap k v
forall {a}.
Eq a =>
Hash -> a -> v -> Shift -> HashMap a v -> HashMap a v
go Hash
h0 k
k0 v
v0 Shift
0 HashMap k v
m0
  where
    h0 :: Hash
h0 = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k0
    go :: Hash -> a -> v -> Shift -> HashMap a v -> HashMap a v
go !Hash
h !a
k v
x !Shift
_ HashMap a v
Empty = Hash -> a -> v -> HashMap a v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h a
k v
x
    go Hash
h a
k v
x Shift
s t :: HashMap a v
t@(Leaf Hash
hy l :: Leaf a v
l@(L a
ky v
y))
        | Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h = if a
ky a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
k
                    then Hash -> a -> v -> HashMap a v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h a
k (v -> v -> v
f v
x v
y)
                    else v
x v -> HashMap a v -> HashMap a v
forall a b. a -> b -> b
`seq` Hash -> Leaf a v -> Leaf a v -> HashMap a v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
HM.collision Hash
h Leaf a v
l (a -> v -> Leaf a v
forall k v. k -> v -> Leaf k v
L a
k v
x)
        | Bool
otherwise = v
x v -> HashMap a v -> HashMap a v
forall a b. a -> b -> b
`seq` (forall s. ST s (HashMap a v)) -> HashMap a v
forall a. (forall s. ST s a) -> a
runST (Shift
-> Hash -> a -> v -> Hash -> HashMap a v -> ST s (HashMap a v)
forall k v s.
Shift
-> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
HM.two Shift
s Hash
h a
k v
x Hash
hy HashMap a v
t)
    go Hash
h a
k v
x Shift
s (BitmapIndexed Hash
b Array (HashMap a v)
ary)
        | Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
0 =
            let ary' :: Array (HashMap a v)
ary' = Array (HashMap a v) -> Shift -> HashMap a v -> Array (HashMap a v)
forall e. Array e -> Shift -> e -> Array e
A.insert Array (HashMap a v)
ary Shift
i (HashMap a v -> Array (HashMap a v))
-> HashMap a v -> Array (HashMap a v)
forall a b. (a -> b) -> a -> b
$! Hash -> a -> v -> HashMap a v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h a
k v
x
            in Hash -> Array (HashMap a v) -> HashMap a v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
HM.bitmapIndexedOrFull (Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
m) Array (HashMap a v)
ary'
        | Bool
otherwise =
            let st :: HashMap a v
st   = Array (HashMap a v) -> Shift -> HashMap a v
forall a. Array a -> Shift -> a
A.index Array (HashMap a v)
ary Shift
i
                st' :: HashMap a v
st'  = Hash -> a -> v -> Shift -> HashMap a v -> HashMap a v
go Hash
h a
k v
x (Shift -> Shift
nextShift Shift
s) HashMap a v
st
                ary' :: Array (HashMap a v)
ary' = Array (HashMap a v) -> Shift -> HashMap a v -> Array (HashMap a v)
forall e. Array e -> Shift -> e -> Array e
A.update Array (HashMap a v)
ary Shift
i (HashMap a v -> Array (HashMap a v))
-> HashMap a v -> Array (HashMap a v)
forall a b. (a -> b) -> a -> b
$! HashMap a v
st'
            in Hash -> Array (HashMap a v) -> HashMap a v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b Array (HashMap a v)
ary'
      where m :: Hash
m = Hash -> Shift -> Hash
mask Hash
h Shift
s
            i :: Shift
i = Hash -> Hash -> Shift
sparseIndex Hash
b Hash
m
    go Hash
h a
k v
x Shift
s (Full Array (HashMap a v)
ary) =
        let st :: HashMap a v
st   = Array (HashMap a v) -> Shift -> HashMap a v
forall a. Array a -> Shift -> a
A.index Array (HashMap a v)
ary Shift
i
            st' :: HashMap a v
st'  = Hash -> a -> v -> Shift -> HashMap a v -> HashMap a v
go Hash
h a
k v
x (Shift -> Shift
nextShift Shift
s) HashMap a v
st
            ary' :: Array (HashMap a v)
ary' = Array (HashMap a v) -> Shift -> HashMap a v -> Array (HashMap a v)
forall e. Array e -> Shift -> e -> Array e
HM.update32 Array (HashMap a v)
ary Shift
i (HashMap a v -> Array (HashMap a v))
-> HashMap a v -> Array (HashMap a v)
forall a b. (a -> b) -> a -> b
$! HashMap a v
st'
        in Array (HashMap a v) -> HashMap a v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap a v)
ary'
      where i :: Shift
i = Hash -> Shift -> Shift
index Hash
h Shift
s
    go Hash
h a
k v
x Shift
s t :: HashMap a v
t@(Collision Hash
hy Array (Leaf a v)
v)
        | Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy   = Hash -> Array (Leaf a v) -> HashMap a v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h ((v -> v -> v) -> a -> v -> Array (Leaf a v) -> Array (Leaf a v)
forall k v.
Eq k =>
(v -> v -> v) -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWith v -> v -> v
f a
k v
x Array (Leaf a v)
v)
        | Bool
otherwise = Hash -> a -> v -> Shift -> HashMap a v -> HashMap a v
go Hash
h a
k v
x Shift
s (HashMap a v -> HashMap a v) -> HashMap a v -> HashMap a v
forall a b. (a -> b) -> a -> b
$ Hash -> Array (HashMap a v) -> HashMap a v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Hash -> Shift -> Hash
mask Hash
hy Shift
s) (HashMap a v -> Array (HashMap a v)
forall a. a -> Array a
A.singleton HashMap a v
t)
{-# INLINABLE insertWith #-}

-- | In-place update version of insertWith
unsafeInsertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v
                 -> HashMap k v
unsafeInsertWith :: forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWith v -> v -> v
f k
k0 v
v0 HashMap k v
m0 = (k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWithKey ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f) k
k0 v
v0 HashMap k v
m0
{-# INLINABLE unsafeInsertWith #-}

unsafeInsertWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> k -> v -> HashMap k v
                    -> HashMap k v
unsafeInsertWithKey :: forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWithKey k -> v -> v -> v
f k
k0 v
v0 HashMap k v
m0 = (forall s. ST s (HashMap k v)) -> HashMap k v
forall a. (forall s. ST s a) -> a
runST (Hash -> k -> v -> Shift -> HashMap k v -> ST s (HashMap k v)
forall {s}.
Hash -> k -> v -> Shift -> HashMap k v -> ST s (HashMap k v)
go Hash
h0 k
k0 v
v0 Shift
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
h !k
k v
x !Shift
_ HashMap k v
Empty = HashMap k v -> ST s (HashMap k v)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k v
x
    go Hash
h k
k v
x Shift
s t :: HashMap k v
t@(Leaf Hash
hy l :: Leaf k v
l@(L k
ky v
y))
        | Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h = if k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k
                    then HashMap k v -> ST s (HashMap k v)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k (k -> v -> v -> v
f k
k v
x v
y)
                    else do
                        let l' :: Leaf k v
l' = v
x v -> Leaf k v -> Leaf k v
forall a b. a -> b -> b
`seq` k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
x
                        HashMap k v -> ST s (HashMap k v)
forall a. a -> ST s a
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
HM.collision Hash
h Leaf k v
l Leaf k v
l'
        | Bool
otherwise = v
x v -> ST s (HashMap k v) -> ST s (HashMap k v)
forall a b. a -> b -> b
`seq` Shift
-> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Shift
-> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
HM.two Shift
s Hash
h k
k v
x Hash
hy HashMap k v
t
    go Hash
h k
k v
x Shift
s t :: HashMap k v
t@(BitmapIndexed Hash
b Array (HashMap k v)
ary)
        | Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
0 = do
            Array (HashMap k v)
ary' <- Array (HashMap k v)
-> Shift -> HashMap k v -> ST s (Array (HashMap k v))
forall e s. Array e -> Shift -> e -> ST s (Array e)
A.insertM Array (HashMap k v)
ary Shift
i (HashMap k v -> ST s (Array (HashMap k v)))
-> HashMap k v -> ST s (Array (HashMap k v))
forall a b. (a -> b) -> a -> b
$! Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k v
x
            HashMap k v -> ST s (HashMap k v)
forall a. a -> ST s a
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
HM.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) -> Shift -> ST s (HashMap k v)
forall a s. Array a -> Shift -> ST s a
A.indexM Array (HashMap k v)
ary Shift
i
            HashMap k v
st' <- Hash -> k -> v -> Shift -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x (Shift -> Shift
nextShift Shift
s) HashMap k v
st
            Array (HashMap k v) -> Shift -> HashMap k v -> ST s ()
forall e s. Array e -> Shift -> e -> ST s ()
A.unsafeUpdateM Array (HashMap k v)
ary Shift
i HashMap k v
st'
            HashMap k v -> ST s (HashMap k v)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v
t
      where m :: Hash
m = Hash -> Shift -> Hash
mask Hash
h Shift
s
            i :: Shift
i = Hash -> Hash -> Shift
sparseIndex Hash
b Hash
m
    go Hash
h k
k v
x Shift
s t :: HashMap k v
t@(Full Array (HashMap k v)
ary) = do
        HashMap k v
st <- Array (HashMap k v) -> Shift -> ST s (HashMap k v)
forall a s. Array a -> Shift -> ST s a
A.indexM Array (HashMap k v)
ary Shift
i
        HashMap k v
st' <- Hash -> k -> v -> Shift -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x (Shift -> Shift
nextShift Shift
s) HashMap k v
st
        Array (HashMap k v) -> Shift -> HashMap k v -> ST s ()
forall e s. Array e -> Shift -> e -> ST s ()
A.unsafeUpdateM Array (HashMap k v)
ary Shift
i HashMap k v
st'
        HashMap k v -> ST s (HashMap k v)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return HashMap k v
t
      where i :: Shift
i = Hash -> Shift -> Shift
index Hash
h Shift
s
    go Hash
h k
k v
x Shift
s t :: HashMap k v
t@(Collision Hash
hy Array (Leaf k v)
v)
        | Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy   = HashMap k v -> ST s (HashMap k v)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return (HashMap k v -> ST s (HashMap k v))
-> HashMap k v -> ST s (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h ((k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey k -> v -> v -> v
f k
k v
x Array (Leaf k v)
v)
        | Bool
otherwise = Hash -> k -> v -> Shift -> HashMap k v -> ST s (HashMap k v)
go Hash
h k
k v
x Shift
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 -> Shift -> Hash
mask Hash
hy Shift
s) (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton HashMap k v
t)
{-# INLINABLE unsafeInsertWithKey #-}

-- | \(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
adjust :: forall k v.
(Eq k, Hashable k) =>
(v -> v) -> k -> HashMap k v -> HashMap k v
adjust v -> v
f k
k0 HashMap k v
m0 = Hash -> k -> Shift -> HashMap k v -> HashMap k v
forall {k}.
Eq k =>
Hash -> k -> Shift -> HashMap k v -> HashMap k v
go Hash
h0 k
k0 Shift
0 HashMap k v
m0
  where
    h0 :: Hash
h0 = k -> Hash
forall a. Hashable a => a -> Hash
hash k
k0
    go :: Hash -> k -> Shift -> HashMap k v -> HashMap k v
go !Hash
_ !k
_ !Shift
_ HashMap k v
Empty = HashMap k v
forall k v. HashMap k v
Empty
    go Hash
h k
k Shift
_ t :: HashMap k v
t@(Leaf Hash
hy (L k
ky v
y))
        | Hash
hy Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h Bool -> Bool -> Bool
&& k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k = Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k (v -> v
f v
y)
        | Bool
otherwise          = HashMap k v
t
    go Hash
h k
k Shift
s t :: HashMap k v
t@(BitmapIndexed Hash
b Array (HashMap k v)
ary)
        | Hash
b Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
0 = HashMap k v
t
        | Bool
otherwise = let st :: HashMap k v
st   = Array (HashMap k v) -> Shift -> HashMap k v
forall a. Array a -> Shift -> a
A.index Array (HashMap k v)
ary Shift
i
                          st' :: HashMap k v
st'  = Hash -> k -> Shift -> HashMap k v -> HashMap k v
go Hash
h k
k (Shift -> Shift
nextShift Shift
s) HashMap k v
st
                          ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Shift -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Shift -> e -> Array e
A.update Array (HashMap k v)
ary Shift
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
st'
                      in Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b Array (HashMap k v)
ary'
      where m :: Hash
m = Hash -> Shift -> Hash
mask Hash
h Shift
s
            i :: Shift
i = Hash -> Hash -> Shift
sparseIndex Hash
b Hash
m
    go Hash
h k
k Shift
s (Full Array (HashMap k v)
ary) =
        let i :: Shift
i    = Hash -> Shift -> Shift
index Hash
h Shift
s
            st :: HashMap k v
st   = Array (HashMap k v) -> Shift -> HashMap k v
forall a. Array a -> Shift -> a
A.index Array (HashMap k v)
ary Shift
i
            st' :: HashMap k v
st'  = Hash -> k -> Shift -> HashMap k v -> HashMap k v
go Hash
h k
k (Shift -> Shift
nextShift Shift
s) HashMap k v
st
            ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Shift -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Shift -> e -> Array e
HM.update32 Array (HashMap k v)
ary Shift
i (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! HashMap k v
st'
        in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
    go Hash
h k
k Shift
_ t :: HashMap k v
t@(Collision Hash
hy Array (Leaf k v)
v)
        | Hash
h Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
hy   = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h ((v -> v) -> k -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(v -> v) -> k -> Array (Leaf k v) -> Array (Leaf k v)
updateWith v -> v
f k
k Array (Leaf k v)
v)
        | Bool
otherwise = HashMap k v
t
{-# INLINABLE adjust #-}

-- | \(O(\log n)\)  The expression @('update' f k map)@ updates the value @x@ at @k@
-- (if it is in the map). If @(f 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 :: forall k a.
(Eq k, Hashable k) =>
(a -> Maybe a) -> k -> HashMap k a -> HashMap k a
update a -> Maybe a
f = (Maybe a -> Maybe a) -> k -> HashMap k a -> HashMap k a
forall k v.
(Eq k, Hashable k) =>
(Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
alter (Maybe a -> (a -> Maybe a) -> Maybe a
forall a b. Maybe a -> (a -> Maybe b) -> Maybe b
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
alter :: forall k v.
(Eq k, Hashable k) =>
(Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
alter Maybe v -> Maybe v
f k
k HashMap k v
m =
    let !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
HM.lookupRecordCollision Hash
h k
k HashMap k v
m
    in case Maybe v -> Maybe v
f (LookupRes v -> Maybe v
forall a. LookupRes a -> Maybe a
HM.lookupResToMaybe LookupRes v
lookupRes) of
        Maybe v
Nothing -> case LookupRes v
lookupRes of
            LookupRes v
Absent            -> HashMap k v
m
            Present v
_ Shift
collPos -> Shift -> Hash -> k -> HashMap k v -> HashMap k v
forall k v. Shift -> Hash -> k -> HashMap k v -> HashMap k v
HM.deleteKeyExists Shift
collPos Hash
h k
k HashMap k v
m
        Just !v
v' -> case LookupRes v
lookupRes of
            LookupRes v
Absent             -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v -> HashMap k v
HM.insertNewKey Hash
h k
k v
v' HashMap k v
m
            Present v
v Shift
collPos ->
                if v
v v -> v -> Bool
forall a. a -> a -> Bool
`ptrEq` v
v'
                    then HashMap k v
m
                    else Shift -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Shift -> Hash -> k -> v -> HashMap k v -> HashMap k v
HM.insertKeyExists Shift
collPos Hash
h 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/docs/Control-Lens-At.html#v:at Control.Lens.At>.
--
-- @since 0.2.10
alterF :: (Functor f, Eq k, Hashable k)
       => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
-- Special care is taken to only calculate the hash once. When we rewrite
-- with RULES, we also ensure that we only compare the key for equality
-- once. 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 :: forall (f :: * -> *) k v.
(Functor f, Eq k, Hashable k) =>
(Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterF Maybe v -> f (Maybe v)
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
HM.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
$ \case
    Maybe v
Nothing -> HashMap k v -> (v -> HashMap k v) -> Maybe v -> HashMap k v
forall b a. b -> (a -> b) -> Maybe a -> b
maybe HashMap k v
m (HashMap k v -> v -> HashMap k v
forall a b. a -> b -> a
const (Hash -> k -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> HashMap k v -> HashMap k v
HM.delete' Hash
h k
k HashMap k v
m)) Maybe v
mv
    Just !v
v' -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Eq k => Hash -> k -> v -> HashMap k v -> HashMap k v
HM.insert' Hash
h k
k v
v' HashMap k v
m

-- We rewrite this function unconditionally in RULES, but we expose
-- an unfolding just in case it's used in a context where the rules
-- don't fire.
{-# INLINABLE [0] alterF #-}

-- See notes in Data.HashMap.Internal
test_bottom :: a
test_bottom :: forall a. a
test_bottom = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.HashMap.alterF internal error: hit test_bottom"

bogus# :: (# #) -> (# a #)
bogus# :: forall a. (# #) -> (# a #)
bogus# (# #)
_ = [Char] -> (# a #)
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.HashMap.alterF internal error: hit bogus#"

impossibleAdjust :: a
impossibleAdjust :: forall a. a
impossibleAdjust = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.HashMap.alterF internal error: impossible adjust"

{-# RULES

-- See detailed notes on alterF rules in Data.HashMap.Internal.

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

"alterFconstant" forall (f :: Maybe a -> Identity (Maybe a)) x.
  alterFWeird x x f = \ !k !m ->
    Identity (case runIdentity x of {Nothing -> HM.delete k m; Just a -> insert k a m})

"alterFinsertWith" [1] forall (f :: Maybe a -> Identity (Maybe a)) x y.
  alterFWeird (coerce (Just x)) (coerce (Just y)) f =
    coerce (HM.insertModifying x (\mold -> case runIdentity (f (Just mold)) of
                                               Nothing -> bogus# (# #)
                                               Just !new -> (# new #)))

-- This rule is written a bit differently than the one for lazy
-- maps because the adjust here is strict. We could write it the
-- same general way anyway, but this seems simpler.
"alterFadjust" forall (f :: Maybe a -> Identity (Maybe a)) x.
  alterFWeird (coerce Nothing) (coerce (Just x)) f =
    coerce (adjust (\a -> case runIdentity (f (Just a)) of
                               Just a' -> a'
                               Nothing -> impossibleAdjust))

"alterFlookup" forall _ign1 _ign2 (f :: Maybe a -> Const r (Maybe a)) .
  alterFWeird _ign1 _ign2 f = \ !k !m -> Const (getConst (f (HM.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 :: forall (f :: * -> *) k v.
(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)
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 :: 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 !k
k !HashMap k v
m = ((Maybe v -> HashMap k v) -> f (Maybe v) -> f (HashMap k v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe v -> f (Maybe v)
f Maybe v
mv) ((Maybe v -> HashMap k v) -> f (HashMap k v))
-> (Maybe v -> HashMap k v) -> f (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \Maybe v
fres ->
  case Maybe v
fres of

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

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

      -- Key did exist, no collision
      Present v
_ Shift
collPos -> Shift -> Hash -> k -> HashMap k v -> HashMap k v
forall k v. Shift -> Hash -> k -> HashMap k v -> HashMap k v
HM.deleteKeyExists Shift
collPos Hash
h k
k HashMap k v
m

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

      -- Key did not exist before, insert v' under a new key
      LookupRes v
Absent -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v -> HashMap k v
HM.insertNewKey Hash
h k
k v
v' HashMap k v
m

      -- Key existed before, no hash collision
      Present v
v Shift
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 Shift -> Hash -> k -> v -> HashMap k v -> HashMap k v
forall k v. Shift -> Hash -> k -> v -> HashMap k v -> HashMap k v
HM.insertKeyExists Shift
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
HM.lookupRecordCollision Hash
h k
k HashMap k v
m
        !mv :: Maybe v
mv = LookupRes v -> Maybe v
forall a. LookupRes a -> Maybe a
HM.lookupResToMaybe LookupRes v
lookupRes
{-# INLINABLE alterFEager #-}

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

-- | \(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 => (v -> v -> v) -> HashMap k v -> HashMap k v
          -> HashMap k v
unionWith :: forall k v.
Eq k =>
(v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
unionWith v -> v -> v
f = (k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
forall k v.
Eq k =>
(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 => (k -> v -> v -> v) -> HashMap k v -> HashMap k v
          -> HashMap k v
unionWithKey :: forall k v.
Eq k =>
(k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
unionWithKey k -> v -> v -> v
f = Shift -> HashMap k v -> HashMap k v -> HashMap k v
go Shift
0
  where
    -- empty vs. anything
    go :: Shift -> HashMap k v -> HashMap k v -> HashMap k v
go !Shift
_ HashMap k v
t1 HashMap k v
Empty = HashMap k v
t1
    go Shift
_ HashMap k v
Empty HashMap k v
t2 = HashMap k v
t2
    -- leaf vs. leaf
    go Shift
s t1 :: HashMap k v
t1@(Leaf Hash
h1 l1 :: Leaf k v
l1@(L k
k1 v
v1)) t2 :: HashMap k v
t2@(Leaf Hash
h2 l2 :: Leaf k v
l2@(L k
k2 v
v2))
        | Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2  = if k
k1 k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k2
                      then Hash -> k -> v -> HashMap k v
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h1 k
k1 (k -> v -> v -> v
f k
k1 v
v1 v
v2)
                      else Hash -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> Leaf k v -> HashMap k v
HM.collision Hash
h1 Leaf k v
l1 Leaf k v
l2
        | Bool
otherwise = Shift -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
forall {k} {v}.
Shift -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Shift
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
    go Shift
s t1 :: HashMap k v
t1@(Leaf Hash
h1 (L k
k1 v
v1)) t2 :: HashMap k v
t2@(Collision Hash
h2 Array (Leaf k v)
ls2)
        | Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2  = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h1 ((k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey k -> v -> v -> v
f k
k1 v
v1 Array (Leaf k v)
ls2)
        | Bool
otherwise = Shift -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
forall {k} {v}.
Shift -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Shift
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
    go Shift
s t1 :: HashMap k v
t1@(Collision Hash
h1 Array (Leaf k v)
ls1) t2 :: HashMap k v
t2@(Leaf Hash
h2 (L k
k2 v
v2))
        | Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2  = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h1 ((k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey ((v -> v -> v) -> v -> v -> v
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((v -> v -> v) -> v -> v -> v)
-> (k -> v -> v -> v) -> k -> v -> v -> v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> v -> v -> v
f) k
k2 v
v2 Array (Leaf k v)
ls1)
        | Bool
otherwise = Shift -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
forall {k} {v}.
Shift -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Shift
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
    go Shift
s t1 :: HashMap k v
t1@(Collision Hash
h1 Array (Leaf k v)
ls1) t2 :: HashMap k v
t2@(Collision Hash
h2 Array (Leaf k v)
ls2)
        | Hash
h1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
h2  = Hash -> Array (Leaf k v) -> HashMap k v
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h1 ((k -> v -> v -> (# v #))
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> (# v #))
-> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
HM.updateOrConcatWithKey (\k
k v
a v
b -> let !v :: v
v = k -> v -> v -> v
f k
k v
a v
b in (# v
v #)) Array (Leaf k v)
ls1 Array (Leaf k v)
ls2)
        | Bool
otherwise = Shift -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
forall {k} {v}.
Shift -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Shift
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
    -- branch vs. branch
    go Shift
s (BitmapIndexed Hash
b1 Array (HashMap k v)
ary1) (BitmapIndexed Hash
b2 Array (HashMap k v)
ary2) =
        let b' :: Hash
b'   = Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.|. Hash
b2
            ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
HM.unionArrayBy (Shift -> HashMap k v -> HashMap k v -> HashMap k v
go (Shift -> Shift
nextShift Shift
s)) 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
HM.bitmapIndexedOrFull Hash
b' Array (HashMap k v)
ary'
    go Shift
s (BitmapIndexed Hash
b1 Array (HashMap k v)
ary1) (Full Array (HashMap k v)
ary2) =
        let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
HM.unionArrayBy (Shift -> HashMap k v -> HashMap k v -> HashMap k v
go (Shift -> Shift
nextShift Shift
s)) Hash
b1 Hash
fullBitmap 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 Shift
s (Full Array (HashMap k v)
ary1) (BitmapIndexed Hash
b2 Array (HashMap k v)
ary2) =
        let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
HM.unionArrayBy (Shift -> HashMap k v -> HashMap k v -> HashMap k v
go (Shift -> Shift
nextShift Shift
s)) Hash
fullBitmap 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 Shift
s (Full Array (HashMap k v)
ary1) (Full Array (HashMap k v)
ary2) =
        let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Hash
-> Hash
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Hash -> Hash -> Array a -> Array a -> Array a
HM.unionArrayBy (Shift -> HashMap k v -> HashMap k v -> HashMap k v
go (Shift -> Shift
nextShift Shift
s)) Hash
fullBitmap Hash
fullBitmap
                   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 Shift
s (BitmapIndexed Hash
b1 Array (HashMap k v)
ary1) HashMap k v
t2
        | Hash
b1 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m2 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
0 = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Shift -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Shift -> e -> Array e
A.insert Array (HashMap k v)
ary1 Shift
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
HM.bitmapIndexedOrFull Hash
b' Array (HashMap k v)
ary'
        | Bool
otherwise      = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Shift -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Shift -> (e -> e) -> Array e
A.updateWith' Array (HashMap k v)
ary1 Shift
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st1 ->
                                   Shift -> HashMap k v -> HashMap k v -> HashMap k v
go (Shift -> Shift
nextShift Shift
s) 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 -> Shift -> Hash
mask Hash
h2 Shift
s
          i :: Shift
i = Hash -> Hash -> Shift
sparseIndex Hash
b1 Hash
m2
    go Shift
s HashMap k v
t1 (BitmapIndexed Hash
b2 Array (HashMap k v)
ary2)
        | Hash
b2 Hash -> Hash -> Hash
forall a. Bits a => a -> a -> a
.&. Hash
m1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
0 = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v) -> Shift -> HashMap k v -> Array (HashMap k v)
forall e. Array e -> Shift -> e -> Array e
A.insert Array (HashMap k v)
ary2 Shift
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
HM.bitmapIndexedOrFull Hash
b' Array (HashMap k v)
ary'
        | Bool
otherwise      = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Shift -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Shift -> (e -> e) -> Array e
A.updateWith' Array (HashMap k v)
ary2 Shift
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st2 ->
                                   Shift -> HashMap k v -> HashMap k v -> HashMap k v
go (Shift -> Shift
nextShift Shift
s) 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 -> Shift -> Hash
mask Hash
h1 Shift
s
        i :: Shift
i = Hash -> Hash -> Shift
sparseIndex Hash
b2 Hash
m1
    go Shift
s (Full Array (HashMap k v)
ary1) HashMap k v
t2 =
        let h2 :: Hash
h2   = HashMap k v -> Hash
forall {k} {v}. HashMap k v -> Hash
leafHashCode HashMap k v
t2
            i :: Shift
i    = Hash -> Shift -> Shift
index Hash
h2 Shift
s
            ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Shift -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Shift -> (e -> e) -> Array e
HM.update32With' Array (HashMap k v)
ary1 Shift
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st1 -> Shift -> HashMap k v -> HashMap k v -> HashMap k v
go (Shift -> Shift
nextShift Shift
s) 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 Shift
s HashMap k v
t1 (Full Array (HashMap k v)
ary2) =
        let h1 :: Hash
h1   = HashMap k v -> Hash
forall {k} {v}. HashMap k v -> Hash
leafHashCode HashMap k v
t1
            i :: Shift
i    = Hash -> Shift -> Shift
index Hash
h1 Shift
s
            ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Shift -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Shift -> (e -> e) -> Array e
HM.update32With' Array (HashMap k v)
ary2 Shift
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st2 -> Shift -> HashMap k v -> HashMap k v -> HashMap k v
go (Shift -> Shift
nextShift Shift
s) HashMap k v
t1 HashMap k v
st2
        in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'

    leafHashCode :: HashMap k v -> Hash
leafHashCode (Leaf Hash
h Leaf k v
_) = Hash
h
    leafHashCode (Collision Hash
h Array (Leaf k v)
_) = Hash
h
    leafHashCode HashMap k v
_ = [Char] -> Hash
forall a. HasCallStack => [Char] -> a
error [Char]
"leafHashCode"

    goDifferentHash :: Shift -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Shift
s Hash
h1 Hash
h2 HashMap k v
t1 HashMap k v
t2
        | Hash
m1 Hash -> Hash -> Bool
forall a. Eq a => a -> a -> Bool
== Hash
m2  = Hash -> Array (HashMap k v) -> HashMap k v
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
m1 (HashMap k v -> Array (HashMap k v)
forall a. a -> Array a
A.singleton (HashMap k v -> Array (HashMap k v))
-> HashMap k v -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$! Shift -> Hash -> Hash -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash (Shift -> Shift
nextShift Shift
s) Hash
h1 Hash
h2 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 -> Shift -> Hash
mask Hash
h1 Shift
s
        m2 :: Hash
m2 = Hash -> Shift -> Hash
mask Hash
h2 Shift
s
{-# INLINE unionWithKey #-}

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

-- | \(O(n)\) Transform this map by applying a function to every value.
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey :: forall k v1 v2. (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey k -> v1 -> v2
f = HashMap k v1 -> HashMap k v2
go
  where
    go :: HashMap k v1 -> HashMap k v2
go HashMap k v1
Empty                 = HashMap k v2
forall k v. HashMap k v
Empty
    go (Leaf Hash
h (L k
k v1
v))      = Hash -> k -> v2 -> HashMap k v2
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k (k -> v1 -> v2
f k
k v1
v)
    go (BitmapIndexed Hash
b Array (HashMap k v1)
ary) = Hash -> Array (HashMap k v2) -> HashMap k v2
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v2) -> HashMap k v2)
-> Array (HashMap k v2) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ (HashMap k v1 -> HashMap k v2)
-> Array (HashMap k v1) -> Array (HashMap k v2)
forall a b. (a -> b) -> Array a -> Array b
A.map' HashMap k v1 -> HashMap k v2
go Array (HashMap k v1)
ary
    go (Full Array (HashMap k v1)
ary)            = Array (HashMap k v2) -> HashMap k v2
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v2) -> HashMap k v2)
-> Array (HashMap k v2) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ (HashMap k v1 -> HashMap k v2)
-> Array (HashMap k v1) -> Array (HashMap k v2)
forall a b. (a -> b) -> Array a -> Array b
A.map' HashMap k v1 -> HashMap k v2
go Array (HashMap k v1)
ary
    go (Collision Hash
h Array (Leaf k v1)
ary)     =
        Hash -> Array (Leaf k v2) -> HashMap k v2
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Array (Leaf k v2) -> HashMap k v2)
-> Array (Leaf k v2) -> HashMap k v2
forall a b. (a -> b) -> a -> b
$ (Leaf k v1 -> Leaf k v2) -> Array (Leaf k v1) -> Array (Leaf k v2)
forall a b. (a -> b) -> Array a -> Array b
A.map' (\ (L k
k v1
v) -> let !v' :: v2
v' = k -> v1 -> v2
f k
k v1
v in k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k v2
v') Array (Leaf k v1)
ary
{-# INLINE mapWithKey #-}

-- | \(O(n)\) Transform this map by applying a function to every value.
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2
map :: forall v1 v2 k. (v1 -> v2) -> HashMap k v1 -> HashMap k v2
map v1 -> v2
f = (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
forall k v1 v2. (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
mapWithKey ((v1 -> v2) -> k -> v1 -> v2
forall a b. a -> b -> a
const v1 -> v2
f)
{-# INLINE map #-}


------------------------------------------------------------------------
-- * 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 :: forall k v1 v2.
(k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybeWithKey k -> v1 -> Maybe v2
f = (HashMap k v1 -> Maybe (HashMap k v2))
-> (Leaf k v1 -> Maybe (Leaf k v2)) -> HashMap k v1 -> HashMap k v2
forall k v1 v2.
(HashMap k v1 -> Maybe (HashMap k v2))
-> (Leaf k v1 -> Maybe (Leaf k v2)) -> HashMap k v1 -> HashMap k v2
HM.filterMapAux HashMap k v1 -> Maybe (HashMap k v2)
onLeaf Leaf k v1 -> Maybe (Leaf k v2)
onColl
  where onLeaf :: HashMap k v1 -> Maybe (HashMap k v2)
onLeaf (Leaf Hash
h (L k
k v1
v)) | Just v2
v' <- k -> v1 -> Maybe v2
f k
k v1
v = HashMap k v2 -> Maybe (HashMap k v2)
forall a. a -> Maybe a
Just (Hash -> k -> v2 -> HashMap k v2
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k v2
v')
        onLeaf HashMap k v1
_ = Maybe (HashMap k v2)
forall a. Maybe a
Nothing

        onColl :: Leaf k v1 -> Maybe (Leaf k v2)
onColl (L k
k v1
v) | Just !v2
v' <- k -> v1 -> Maybe v2
f k
k v1
v = Leaf k v2 -> Maybe (Leaf k v2)
forall a. a -> Maybe a
Just (k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k v2
v')
                       | Bool
otherwise = Maybe (Leaf k v2)
forall a. Maybe a
Nothing
{-# INLINE mapMaybeWithKey #-}

-- | \(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 :: forall v1 v2 k. (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybe v1 -> Maybe v2
f = (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
forall k v1 v2.
(k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
mapMaybeWithKey ((v1 -> Maybe v2) -> k -> v1 -> Maybe v2
forall a b. a -> b -> a
const v1 -> Maybe v2
f)
{-# INLINE mapMaybe #-}

-- | \(O(n)\) Perform an 'Applicative' action for each key-value pair
-- in a 'HashMap' and produce a 'HashMap' of all the results. Each 'HashMap'
-- will be strict in all its values.
--
-- @
-- traverseWithKey f = fmap ('map' id) . "Data.HashMap.Lazy".'Data.HashMap.Lazy.traverseWithKey' f
-- @
--
-- 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 :: forall (f :: * -> *) k v1 v2.
Applicative f =>
(k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)
traverseWithKey k -> v1 -> f v2
f = HashMap k v1 -> f (HashMap k v2)
go
  where
    go :: HashMap k v1 -> f (HashMap k v2)
go HashMap k v1
Empty                 = HashMap k v2 -> f (HashMap k v2)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure HashMap k v2
forall k v. HashMap k v
Empty
    go (Leaf Hash
h (L k
k v1
v))      = Hash -> k -> v2 -> HashMap k v2
forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k (v2 -> HashMap k v2) -> f v2 -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> v1 -> f v2
f k
k v1
v
    go (BitmapIndexed Hash
b Array (HashMap k v1)
ary) = Hash -> Array (HashMap k v2) -> HashMap k v2
forall k v. Hash -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Hash
b (Array (HashMap k v2) -> HashMap k v2)
-> f (Array (HashMap k v2)) -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (HashMap k v1 -> f (HashMap k v2))
-> Array (HashMap k v1) -> f (Array (HashMap k v2))
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Array a -> f (Array b)
A.traverse' HashMap k v1 -> f (HashMap k v2)
go Array (HashMap k v1)
ary
    go (Full Array (HashMap k v1)
ary)            = Array (HashMap k v2) -> HashMap k v2
forall k v. Array (HashMap k v) -> HashMap k v
Full (Array (HashMap k v2) -> HashMap k v2)
-> f (Array (HashMap k v2)) -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (HashMap k v1 -> f (HashMap k v2))
-> Array (HashMap k v1) -> f (Array (HashMap k v2))
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Array a -> f (Array b)
A.traverse' HashMap k v1 -> f (HashMap k v2)
go Array (HashMap k v1)
ary
    go (Collision Hash
h Array (Leaf k v1)
ary)     =
        Hash -> Array (Leaf k v2) -> HashMap k v2
forall k v. Hash -> Array (Leaf k v) -> HashMap k v
Collision Hash
h (Array (Leaf k v2) -> HashMap k v2)
-> f (Array (Leaf k v2)) -> f (HashMap k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Leaf k v1 -> f (Leaf k v2))
-> Array (Leaf k v1) -> f (Array (Leaf k v2))
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Array a -> f (Array b)
A.traverse' (\ (L k
k v1
v) -> (k -> v2 -> Leaf k v2
forall k v. k -> v -> Leaf k v
L k
k (v2 -> Leaf k v2) -> v2 -> Leaf k v2
forall a b. (a -> b) -> a -> b
$!) (v2 -> Leaf k v2) -> f v2 -> f (Leaf k v2)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> v1 -> f v2
f k
k v1
v) Array (Leaf k v1)
ary
{-# INLINE traverseWithKey #-}

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

-- | \(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 :: forall k v w.
(Eq k, Hashable k) =>
(v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v
differenceWith v -> w -> Maybe v
f HashMap k v
a HashMap k w
b = (HashMap k v -> k -> v -> HashMap k v)
-> HashMap k v -> HashMap k v -> HashMap k v
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
HM.foldlWithKey' HashMap k v -> k -> v -> HashMap k v
go HashMap k v
forall k v. HashMap k v
HM.empty HashMap k v
a
  where
    go :: HashMap k v -> k -> v -> HashMap k v
go HashMap k v
m k
k v
v = case k -> HashMap k w -> Maybe w
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
HM.lookup k
k HashMap k w
b of
                 Maybe w
Nothing -> v
v v -> HashMap k v -> HashMap k v
forall a b. a -> b -> b
`seq` k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HM.unsafeInsert k
k v
v HashMap k v
m
                 Just w
w  -> HashMap k v -> (v -> HashMap k v) -> Maybe v -> HashMap k v
forall b a. b -> (a -> b) -> Maybe a -> b
maybe HashMap k v
m (\ !v
y -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HM.unsafeInsert k
k v
y HashMap k v
m) (v -> w -> Maybe v
f v
v w
w)
{-# INLINABLE differenceWith #-}

-- | \(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 => (v1 -> v2 -> v3) -> HashMap k v1
                 -> HashMap k v2 -> HashMap k v3
intersectionWith :: forall k v1 v2 v3.
Eq k =>
(v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3
intersectionWith v1 -> v2 -> v3
f = ((k -> v1 -> v2 -> v3)
 -> HashMap k v1 -> HashMap k v2 -> HashMap k v3)
-> (k -> v1 -> v2 -> v3)
-> HashMap k v1
-> HashMap k v2
-> HashMap k v3
forall a. a -> a
Exts.inline (k -> v1 -> v2 -> v3)
-> HashMap k v1 -> HashMap k v2 -> HashMap k v3
forall k v1 v2 v3.
Eq 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)
-> (k -> v1 -> v2 -> v3)
-> HashMap k v1
-> HashMap k v2
-> HashMap k v3
forall a b. (a -> b) -> a -> b
$ (v1 -> v2 -> v3) -> k -> v1 -> v2 -> v3
forall a b. a -> b -> a
const v1 -> v2 -> v3
f
{-# 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 => (k -> v1 -> v2 -> v3)
                    -> HashMap k v1 -> HashMap k v2 -> HashMap k v3
intersectionWithKey :: forall k v1 v2 v3.
Eq k =>
(k -> v1 -> v2 -> v3)
-> HashMap k v1 -> HashMap k v2 -> HashMap k v3
intersectionWithKey k -> v1 -> v2 -> v3
f = (k -> v1 -> v2 -> (# v3 #))
-> HashMap k v1 -> HashMap k v2 -> HashMap k v3
forall k v1 v2 v3.
Eq k =>
(k -> v1 -> v2 -> (# v3 #))
-> HashMap k v1 -> HashMap k v2 -> HashMap k v3
HM.intersectionWithKey# ((k -> v1 -> v2 -> (# v3 #))
 -> HashMap k v1 -> HashMap k v2 -> HashMap k v3)
-> (k -> v1 -> v2 -> (# v3 #))
-> HashMap k v1
-> HashMap k v2
-> HashMap k v3
forall a b. (a -> b) -> a -> b
$ \k
k v1
v1 v2
v2 -> let !v3 :: v3
v3 = k -> v1 -> v2 -> v3
f k
k v1
v1 v2
v2 in (# v3
v3 #)
{-# INLINABLE intersectionWithKey #-}

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

-- | \(O(n \log 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 :: forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
fromList = (HashMap k v -> (k, v) -> HashMap k v)
-> HashMap k v -> [(k, v)] -> HashMap k v
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\ HashMap k v
m (k
k, !v
v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HM.unsafeInsert k
k v
v HashMap k v
m) HashMap k v
forall k v. HashMap k v
HM.empty
{-# INLINABLE fromList #-}

-- | \(O(n \log n)\) Construct a map from a list of elements.  Uses
-- the provided function @f@ to merge duplicate entries with
-- @(f newVal oldVal)@.
--
-- === Examples
--
-- Given a list @xs@, create a map with the number of occurrences of each
-- element in @xs@:
--
-- > let xs = ['a', 'b', 'a']
-- > in fromListWith (+) [ (x, 1) | x <- xs ]
-- >
-- > = fromList [('a', 2), ('b', 1)]
--
-- Given a list of key-value pairs @xs :: [(k, v)]@, group all values by their
-- keys and return a @HashMap k [v]@.
--
-- > let xs = ('a', 1), ('b', 2), ('a', 3)]
-- > in fromListWith (++) [ (k, [v]) | (k, v) <- xs ]
-- >
-- > = fromList [('a', [3, 1]), ('b', [2])]
--
-- Note that the lists in the resulting map contain elements in reverse order
-- from their occurrences in the original list.
--
-- More generally, duplicate entries are accumulated as follows;
-- this matters when @f@ is not commutative or not associative.
--
-- > fromListWith f [(k, a), (k, b), (k, c), (k, d)]
-- > = fromList [(k, f d (f c (f b a)))]
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWith :: forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWith v -> v -> v
f = (HashMap k v -> (k, v) -> HashMap k v)
-> HashMap k v -> [(k, v)] -> HashMap k v
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\ HashMap k v
m (k
k, v
v) -> (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWith v -> v -> v
f k
k v
v HashMap k v
m) HashMap k v
forall k v. HashMap k v
HM.empty
{-# INLINE fromListWith #-}

-- | \(O(n \log n)\) Construct a map from a list of elements.  Uses
-- the provided function to merge duplicate entries.
--
-- === Examples
--
-- Given a list of key-value pairs where the keys are of different flavours, e.g:
--
-- > data Key = Div | Sub
--
-- and the values need to be combined differently when there are duplicates,
-- depending on the key:
--
-- > combine Div = div
-- > combine Sub = (-)
--
-- then @fromListWithKey@ can be used as follows:
--
-- > fromListWithKey combine [(Div, 2), (Div, 6), (Sub, 2), (Sub, 3)]
-- > = fromList [(Div, 3), (Sub, 1)]
--
-- More generally, duplicate entries are accumulated as follows;
--
-- > fromListWith f [(k, a), (k, b), (k, c), (k, d)]
-- > = fromList [(k, f k d (f k c (f k b a)))]
--
-- @since 0.2.11
fromListWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWithKey :: forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWithKey k -> v -> v -> v
f = (HashMap k v -> (k, v) -> HashMap k v)
-> HashMap k v -> [(k, v)] -> HashMap k v
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\ HashMap k v
m (k
k, v
v) -> (k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
unsafeInsertWithKey k -> v -> v -> v
f k
k v
v HashMap k v
m) HashMap k v
forall k v. HashMap k v
HM.empty
{-# INLINE fromListWithKey #-}

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

updateWith :: Eq k => (v -> v) -> k -> A.Array (Leaf k v) -> A.Array (Leaf k v)
updateWith :: forall k v.
Eq k =>
(v -> v) -> k -> Array (Leaf k v) -> Array (Leaf k v)
updateWith v -> v
f k
k0 Array (Leaf k v)
ary0 = k -> Array (Leaf k v) -> Shift -> Shift -> Array (Leaf k v)
forall {t}.
Eq t =>
t -> Array (Leaf t v) -> Shift -> Shift -> Array (Leaf t v)
go k
k0 Array (Leaf k v)
ary0 Shift
0 (Array (Leaf k v) -> Shift
forall a. Array a -> Shift
A.length Array (Leaf k v)
ary0)
  where
    go :: t -> Array (Leaf t v) -> Shift -> Shift -> Array (Leaf t v)
go !t
k !Array (Leaf t v)
ary !Shift
i !Shift
n
        | Shift
i Shift -> Shift -> Bool
forall a. Ord a => a -> a -> Bool
>= Shift
n    = Array (Leaf t v)
ary
        | Bool
otherwise = case Array (Leaf t v) -> Shift -> Leaf t v
forall a. Array a -> Shift -> a
A.index Array (Leaf t v)
ary Shift
i of
            (L t
kx v
y) | t
k t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
kx   -> let !v' :: v
v' = v -> v
f v
y in Array (Leaf t v) -> Shift -> Leaf t v -> Array (Leaf t v)
forall e. Array e -> Shift -> e -> Array e
A.update Array (Leaf t v)
ary Shift
i (t -> v -> Leaf t v
forall k v. k -> v -> Leaf k v
L t
k v
v')
                     | Bool
otherwise -> t -> Array (Leaf t v) -> Shift -> Shift -> Array (Leaf t v)
go t
k Array (Leaf t v)
ary (Shift
iShift -> Shift -> Shift
forall a. Num a => a -> a -> a
+Shift
1) Shift
n
{-# INLINABLE updateWith #-}

-- | Append the given key and value to the array. If the key is
-- already present, instead update the value of the key by applying
-- the given function to the new and old value (in that order). The
-- value is always evaluated to WHNF before being inserted into the
-- array.
updateOrSnocWith :: Eq k => (v -> v -> v) -> k -> v -> A.Array (Leaf k v)
                 -> A.Array (Leaf k v)
updateOrSnocWith :: forall k v.
Eq k =>
(v -> v -> v) -> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWith v -> v -> v
f = (k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
forall k v.
Eq k =>
(k -> v -> v -> v)
-> k -> v -> Array (Leaf k v) -> Array (Leaf k v)
updateOrSnocWithKey ((v -> v -> v) -> k -> v -> v -> v
forall a b. a -> b -> a
const v -> v -> v
f)
{-# INLINABLE updateOrSnocWith #-}

-- | Append the given key and value to the array. If the key is
-- already present, instead update the value of the key by applying
-- the given function to the new and old value (in that order). The
-- value is always evaluated to WHNF before being inserted into the
-- array.
updateOrSnocWithKey :: Eq k => (k -> v -> v -> v) -> k -> v -> A.Array (Leaf k v)
                 -> A.Array (Leaf k v)
updateOrSnocWithKey :: 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
k0 v
v0 Array (Leaf k v)
ary0 = k -> v -> Array (Leaf k v) -> Shift -> Shift -> Array (Leaf k v)
go k
k0 v
v0 Array (Leaf k v)
ary0 Shift
0 (Array (Leaf k v) -> Shift
forall a. Array a -> Shift
A.length Array (Leaf k v)
ary0)
  where
    go :: k -> v -> Array (Leaf k v) -> Shift -> Shift -> Array (Leaf k v)
go !k
k v
v !Array (Leaf k v)
ary !Shift
i !Shift
n
        -- Not found, append to the end.
        | Shift
i Shift -> Shift -> Bool
forall a. Ord a => a -> a -> Bool
>= Shift
n = Array (Leaf k v) -> Leaf k v -> Array (Leaf k v)
forall a. Array a -> a -> Array a
A.snoc Array (Leaf k v)
ary (Leaf k v -> Array (Leaf k v)) -> Leaf k v -> Array (Leaf k v)
forall a b. (a -> b) -> a -> b
$! k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k (v -> Leaf k v) -> v -> Leaf k v
forall a b. (a -> b) -> a -> b
$! v
v
        | Bool
otherwise = case Array (Leaf k v) -> Shift -> Leaf k v
forall a. Array a -> Shift -> a
A.index Array (Leaf k v)
ary Shift
i of
            (L k
kx v
y) | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
kx   -> let !v' :: v
v' = k -> v -> v -> v
f k
k v
v v
y in Array (Leaf k v) -> Shift -> Leaf k v -> Array (Leaf k v)
forall e. Array e -> Shift -> e -> Array e
A.update Array (Leaf k v)
ary Shift
i (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v')
                     | Bool
otherwise -> k -> v -> Array (Leaf k v) -> Shift -> Shift -> Array (Leaf k v)
go k
k v
v Array (Leaf k v)
ary (Shift
iShift -> Shift -> Shift
forall a. Num a => a -> a -> a
+Shift
1) Shift
n
{-# INLINABLE updateOrSnocWithKey #-}

------------------------------------------------------------------------
-- Smart constructors
--
-- These constructors make sure the value is in WHNF before it's
-- inserted into the constructor.

leaf :: Hash -> k -> v -> HashMap k v
leaf :: forall k v. Hash -> k -> v -> HashMap k v
leaf Hash
h k
k = \ !v
v -> Hash -> Leaf k v -> HashMap k v
forall k v. Hash -> Leaf k v -> HashMap k v
Leaf Hash
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v)
{-# INLINE leaf #-}