{-# LANGUAGE BangPatterns        #-}
{-# LANGUAGE CPP                 #-}
{-# LANGUAGE LambdaCase          #-}
{-# LANGUAGE MagicHash           #-}
{-# LANGUAGE PatternGuards       #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# 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. 16 or 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.!)
    , HM.lookupKey
    , 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
    , differenceWithKey
    , HM.intersection
    , intersectionWith
    , intersectionWithKey
    , HM.disjoint

      -- * 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      (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 (..),
                              Shift, 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 :: Hashable k => k -> v -> HashMap k v -> HashMap k v
insert :: forall k v. 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. 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 :: Hashable k => (v -> v -> v) -> k -> v -> HashMap k v
           -> HashMap k v
insertWith :: forall k v.
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 = Word -> k -> v -> Int -> HashMap k v -> HashMap k v
forall {a}.
Eq a =>
Word -> a -> v -> Int -> HashMap a v -> HashMap a v
go Word
h0 k
k0 v
v0 Int
0 HashMap k v
m0
  where
    h0 :: Word
h0 = k -> Word
forall a. Hashable a => a -> Word
hash k
k0
    go :: Word -> a -> v -> Int -> HashMap a v -> HashMap a v
go !Word
h !a
k v
x !Int
_ HashMap a v
Empty = Word -> a -> v -> HashMap a v
forall k v. Word -> k -> v -> HashMap k v
leaf Word
h a
k v
x
    go Word
h a
k v
x Int
s t :: HashMap a v
t@(Leaf Word
hy l :: Leaf a v
l@(L a
ky v
y))
        | Word
hy Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
h = if a
ky a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
k
                    then Word -> a -> v -> HashMap a v
forall k v. Word -> k -> v -> HashMap k v
leaf Word
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` Word -> Leaf a v -> Leaf a v -> HashMap a v
forall k v. Word -> Leaf k v -> Leaf k v -> HashMap k v
HM.collision Word
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 (Int -> Word -> a -> v -> Word -> HashMap a v -> ST s (HashMap a v)
forall k v s.
Int -> Word -> k -> v -> Word -> HashMap k v -> ST s (HashMap k v)
HM.two Int
s Word
h a
k v
x Word
hy HashMap a v
t)
    go Word
h a
k v
x Int
s (BitmapIndexed Word
b Array (HashMap a v)
ary)
        | Word
b Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
m Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
0 =
            let ary' :: Array (HashMap a v)
ary' = Array (HashMap a v) -> Int -> HashMap a v -> Array (HashMap a v)
forall e. Array e -> Int -> e -> Array e
A.insert Array (HashMap a v)
ary Int
i (HashMap a v -> Array (HashMap a v))
-> HashMap a v -> Array (HashMap a v)
forall a b. (a -> b) -> a -> b
$! Word -> a -> v -> HashMap a v
forall k v. Word -> k -> v -> HashMap k v
leaf Word
h a
k v
x
            in Word -> Array (HashMap a v) -> HashMap a v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
HM.bitmapIndexedOrFull (Word
b Word -> Word -> Word
forall a. Bits a => a -> a -> a
.|. Word
m) Array (HashMap a v)
ary'
        | Bool
otherwise =
            case Array (HashMap a v) -> Int -> (# HashMap a v #)
forall a. Array a -> Int -> (# a #)
A.index# Array (HashMap a v)
ary Int
i of
              (# HashMap a v
st #) ->
                let !st' :: HashMap a v
st' = Word -> a -> v -> Int -> HashMap a v -> HashMap a v
go Word
h a
k v
x (Int -> Int
nextShift Int
s) HashMap a v
st
                    ary' :: Array (HashMap a v)
ary' = Array (HashMap a v) -> Int -> HashMap a v -> Array (HashMap a v)
forall e. Array e -> Int -> e -> Array e
A.update Array (HashMap a v)
ary Int
i HashMap a v
st'
                in Word -> Array (HashMap a v) -> HashMap a v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Word
b Array (HashMap a v)
ary'
      where m :: Word
m = Word -> Int -> Word
mask Word
h Int
s
            i :: Int
i = Word -> Word -> Int
sparseIndex Word
b Word
m
    go Word
h a
k v
x Int
s (Full Array (HashMap a v)
ary) =
        case Array (HashMap a v) -> Int -> (# HashMap a v #)
forall a. Array a -> Int -> (# a #)
A.index# Array (HashMap a v)
ary Int
i of
          (# HashMap a v
st #) ->
            let !st' :: HashMap a v
st' = Word -> a -> v -> Int -> HashMap a v -> HashMap a v
go Word
h a
k v
x (Int -> Int
nextShift Int
s) HashMap a v
st
                ary' :: Array (HashMap a v)
ary' = Array (HashMap a v) -> Int -> HashMap a v -> Array (HashMap a v)
forall e. Array e -> Int -> e -> Array e
HM.updateFullArray Array (HashMap a v)
ary Int
i 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 :: Int
i = Word -> Int -> Int
index Word
h Int
s
    go Word
h a
k v
x Int
s t :: HashMap a v
t@(Collision Word
hy Array (Leaf a v)
v)
        | Word
h Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
hy   = Word -> Array (Leaf a v) -> HashMap a v
forall k v. Word -> Array (Leaf k v) -> HashMap k v
Collision Word
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 = Word -> a -> v -> Int -> HashMap a v -> HashMap a v
go Word
h a
k v
x Int
s (HashMap a v -> HashMap a v) -> HashMap a v -> HashMap a v
forall a b. (a -> b) -> a -> b
$ Word -> Array (HashMap a v) -> HashMap a v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Word -> Int -> Word
mask Word
hy Int
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 :: Hashable k => (v -> v -> v) -> k -> v -> HashMap k v
                 -> HashMap k v
unsafeInsertWith :: forall k v.
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.
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 :: forall k v. Hashable k => (k -> v -> v -> v) -> k -> v -> HashMap k v
                    -> HashMap k v
unsafeInsertWithKey :: forall k v.
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 (Word -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
forall s.
Word -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Word
h0 k
k0 v
v0 Int
0 HashMap k v
m0)
  where
    h0 :: Word
h0 = k -> Word
forall a. Hashable a => a -> Word
hash k
k0
    go :: forall s. Hash -> k -> v -> Shift -> HashMap k v -> ST s (HashMap k v)
    go :: forall s.
Word -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go !Word
h !k
k v
x !Int
_ 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
$! Word -> k -> v -> HashMap k v
forall k v. Word -> k -> v -> HashMap k v
leaf Word
h k
k v
x
    go Word
h k
k v
x Int
s t :: HashMap k v
t@(Leaf Word
hy l :: Leaf k v
l@(L k
ky v
y))
        | Word
hy Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
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
$! Word -> k -> v -> HashMap k v
forall k v. Word -> k -> v -> HashMap k v
leaf Word
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
$! Word -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Word -> Leaf k v -> Leaf k v -> HashMap k v
HM.collision Word
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` Int -> Word -> k -> v -> Word -> HashMap k v -> ST s (HashMap k v)
forall k v s.
Int -> Word -> k -> v -> Word -> HashMap k v -> ST s (HashMap k v)
HM.two Int
s Word
h k
k v
x Word
hy HashMap k v
t
    go Word
h k
k v
x Int
s t :: HashMap k v
t@(BitmapIndexed Word
b Array (HashMap k v)
ary)
        | Word
b Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
m Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
0 = do
            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
$! Word -> k -> v -> HashMap k v
forall k v. Word -> k -> v -> HashMap k v
leaf Word
h k
k v
x
            return $! HM.bitmapIndexedOrFull (b .|. m) ary'
        | Bool
otherwise = do
            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
            st' <- go h k x (nextShift s) st
            A.unsafeUpdateM ary i st'
            return t
      where m :: Word
m = Word -> Int -> Word
mask Word
h Int
s
            i :: Int
i = Word -> Word -> Int
sparseIndex Word
b Word
m
    go Word
h k
k v
x Int
s t :: HashMap k v
t@(Full Array (HashMap k v)
ary) = do
        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
        st' <- go h k x (nextShift s) st
        A.unsafeUpdateM ary i st'
        return t
      where i :: Int
i = Word -> Int -> Int
index Word
h Int
s
    go Word
h k
k v
x Int
s t :: HashMap k v
t@(Collision Word
hy Array (Leaf k v)
v)
        | Word
h Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
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
$! Word -> Array (Leaf k v) -> HashMap k v
forall k v. Word -> Array (Leaf k v) -> HashMap k v
Collision Word
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 = Word -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
forall s.
Word -> k -> v -> Int -> HashMap k v -> ST s (HashMap k v)
go Word
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
$ Word -> Array (HashMap k v) -> HashMap k v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Word -> Int -> Word
mask Word
hy Int
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 :: Hashable k => (v -> v) -> k -> HashMap k v -> HashMap k v
adjust :: forall k v.
Hashable k =>
(v -> v) -> k -> HashMap k v -> HashMap k v
adjust v -> v
f k
k0 HashMap k v
m0 = Word -> k -> Int -> HashMap k v -> HashMap k v
forall {k}. Eq k => Word -> k -> Int -> HashMap k v -> HashMap k v
go Word
h0 k
k0 Int
0 HashMap k v
m0
  where
    h0 :: Word
h0 = k -> Word
forall a. Hashable a => a -> Word
hash k
k0
    go :: Word -> k -> Int -> HashMap k v -> HashMap k v
go !Word
_ !k
_ !Int
_ HashMap k v
Empty = HashMap k v
forall k v. HashMap k v
Empty
    go Word
h k
k Int
_ t :: HashMap k v
t@(Leaf Word
hy (L k
ky v
y))
        | Word
hy Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
h Bool -> Bool -> Bool
&& k
ky k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k = Word -> k -> v -> HashMap k v
forall k v. Word -> k -> v -> HashMap k v
leaf Word
h k
k (v -> v
f v
y)
        | Bool
otherwise          = HashMap k v
t
    go Word
h k
k Int
s t :: HashMap k v
t@(BitmapIndexed Word
b Array (HashMap k v)
ary)
        | Word
b Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
m Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
0 = HashMap k v
t
        | Bool
otherwise =
            case Array (HashMap k v) -> Int -> (# HashMap k v #)
forall a. Array a -> Int -> (# a #)
A.index# Array (HashMap k v)
ary Int
i of
              (# HashMap k v
st #) ->
                let !st' :: HashMap k v
st' = Word -> k -> Int -> HashMap k v -> HashMap k v
go Word
h k
k (Int -> Int
nextShift Int
s) 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
st'
                in Word -> Array (HashMap k v) -> HashMap k v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Word
b Array (HashMap k v)
ary'
      where m :: Word
m = Word -> Int -> Word
mask Word
h Int
s
            i :: Int
i = Word -> Word -> Int
sparseIndex Word
b Word
m
    go Word
h k
k Int
s (Full Array (HashMap k v)
ary) =
        case Array (HashMap k v) -> Int -> (# HashMap k v #)
forall a. Array a -> Int -> (# a #)
A.index# Array (HashMap k v)
ary Int
i of
          (# HashMap k v
st #) ->
            let !st' :: HashMap k v
st' = Word -> k -> Int -> HashMap k v -> HashMap k v
go Word
h k
k (Int -> Int
nextShift Int
s) 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
HM.updateFullArray Array (HashMap k v)
ary Int
i HashMap k v
st'
            in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
      where i :: Int
i = Word -> Int -> Int
index Word
h Int
s
    go Word
h k
k Int
_ t :: HashMap k v
t@(Collision Word
hy Array (Leaf k v)
v)
        | Word
h Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
hy   = Word -> Array (Leaf k v) -> HashMap k v
forall k v. Word -> Array (Leaf k v) -> HashMap k v
Collision Word
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 :: Hashable k => (a -> Maybe a) -> k -> HashMap k a -> HashMap k a
update :: forall k a.
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.
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 :: Hashable k => (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
alter :: forall k v.
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 :: Word
h = k -> Word
forall a. Hashable a => a -> Word
hash k
k
        !lookupRes :: LookupRes v
lookupRes = Word -> k -> HashMap k v -> LookupRes v
forall k v. Eq k => Word -> k -> HashMap k v -> LookupRes v
HM.lookupRecordCollision Word
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
_ Int
collPos -> Int -> Word -> k -> HashMap k v -> HashMap k v
forall k v. Int -> Word -> k -> HashMap k v -> HashMap k v
HM.deleteKeyExists Int
collPos Word
h k
k HashMap k v
m
        Just !v
v' -> case LookupRes v
lookupRes of
            LookupRes v
Absent             -> Word -> k -> v -> HashMap k v -> HashMap k v
forall k v. Word -> k -> v -> HashMap k v -> HashMap k v
HM.insertNewKey Word
h k
k v
v' HashMap k v
m
            Present v
v Int
collPos ->
                if v
v v -> v -> Bool
forall a. a -> a -> Bool
`ptrEq` v
v'
                    then HashMap k v
m
                    else Int -> Word -> k -> v -> HashMap k v -> HashMap k v
forall k v. Int -> Word -> k -> v -> HashMap k v -> HashMap k v
HM.insertKeyExists Int
collPos Word
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, 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, 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 :: Word
h = k -> Word
forall a. Hashable a => a -> Word
hash k
k
      mv :: Maybe v
mv = Word -> k -> HashMap k v -> Maybe v
forall k v. Eq k => Word -> k -> HashMap k v -> Maybe v
HM.lookup' Word
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 (Word -> k -> HashMap k v -> HashMap k v
forall k v. Eq k => Word -> k -> HashMap k v -> HashMap k v
HM.delete' Word
h k
k HashMap k v
m)) Maybe v
mv
    Just !v
v' -> Word -> k -> v -> HashMap k v -> HashMap k v
forall k v. Eq k => Word -> k -> v -> HashMap k v -> HashMap k v
HM.insert' Word
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, 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, 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, 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, Hashable k)
       => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)
alterFEager :: forall (f :: * -> *) k v.
(Functor f, 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
_ Int
collPos -> Int -> Word -> k -> HashMap k v -> HashMap k v
forall k v. Int -> Word -> k -> HashMap k v -> HashMap k v
HM.deleteKeyExists Int
collPos Word
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 -> Word -> k -> v -> HashMap k v -> HashMap k v
forall k v. Word -> k -> v -> HashMap k v -> HashMap k v
HM.insertNewKey Word
h k
k v
v' HashMap k v
m

      -- Key existed before, no hash collision
      Present v
v 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 -> Word -> k -> v -> HashMap k v -> HashMap k v
forall k v. Int -> Word -> k -> v -> HashMap k v -> HashMap k v
HM.insertKeyExists Int
collPos Word
h k
k v
v' HashMap k v
m

  where !h :: Word
h = k -> Word
forall a. Hashable a => a -> Word
hash k
k
        !lookupRes :: LookupRes v
lookupRes = Word -> k -> HashMap k v -> LookupRes v
forall k v. Eq k => Word -> k -> HashMap k v -> LookupRes v
HM.lookupRecordCollision Word
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 = Int -> HashMap k v -> HashMap k v -> HashMap k v
go Int
0
  where
    -- empty vs. anything
    go :: Int -> HashMap k v -> HashMap k v -> HashMap k v
go !Int
_ HashMap k v
t1 HashMap k v
Empty = HashMap k v
t1
    go Int
_ HashMap k v
Empty HashMap k v
t2 = HashMap k v
t2
    -- leaf vs. leaf
    go Int
s t1 :: HashMap k v
t1@(Leaf Word
h1 l1 :: Leaf k v
l1@(L k
k1 v
v1)) t2 :: HashMap k v
t2@(Leaf Word
h2 l2 :: Leaf k v
l2@(L k
k2 v
v2))
        | Word
h1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
h2  = if k
k1 k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k2
                      then Word -> k -> v -> HashMap k v
forall k v. Word -> k -> v -> HashMap k v
leaf Word
h1 k
k1 (k -> v -> v -> v
f k
k1 v
v1 v
v2)
                      else Word -> Leaf k v -> Leaf k v -> HashMap k v
forall k v. Word -> Leaf k v -> Leaf k v -> HashMap k v
HM.collision Word
h1 Leaf k v
l1 Leaf k v
l2
        | Bool
otherwise = Int -> Word -> Word -> HashMap k v -> HashMap k v -> HashMap k v
forall {k} {v}.
Int -> Word -> Word -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Word
h1 Word
h2 HashMap k v
t1 HashMap k v
t2
    go Int
s t1 :: HashMap k v
t1@(Leaf Word
h1 (L k
k1 v
v1)) t2 :: HashMap k v
t2@(Collision Word
h2 Array (Leaf k v)
ls2)
        | Word
h1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
h2  = Word -> Array (Leaf k v) -> HashMap k v
forall k v. Word -> Array (Leaf k v) -> HashMap k v
Collision Word
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 -> Word -> Word -> HashMap k v -> HashMap k v -> HashMap k v
forall {k} {v}.
Int -> Word -> Word -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Word
h1 Word
h2 HashMap k v
t1 HashMap k v
t2
    go Int
s t1 :: HashMap k v
t1@(Collision Word
h1 Array (Leaf k v)
ls1) t2 :: HashMap k v
t2@(Leaf Word
h2 (L k
k2 v
v2))
        | Word
h1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
h2  = Word -> Array (Leaf k v) -> HashMap k v
forall k v. Word -> Array (Leaf k v) -> HashMap k v
Collision Word
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 -> Word -> Word -> HashMap k v -> HashMap k v -> HashMap k v
forall {k} {v}.
Int -> Word -> Word -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Word
h1 Word
h2 HashMap k v
t1 HashMap k v
t2
    go Int
s t1 :: HashMap k v
t1@(Collision Word
h1 Array (Leaf k v)
ls1) t2 :: HashMap k v
t2@(Collision Word
h2 Array (Leaf k v)
ls2)
        | Word
h1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
h2  = Word -> Array (Leaf k v) -> HashMap k v
forall k v. Word -> Array (Leaf k v) -> HashMap k v
Collision Word
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 = Int -> Word -> Word -> HashMap k v -> HashMap k v -> HashMap k v
forall {k} {v}.
Int -> Word -> Word -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Word
h1 Word
h2 HashMap k v
t1 HashMap k v
t2
    -- branch vs. branch
    go Int
s (BitmapIndexed Word
b1 Array (HashMap k v)
ary1) (BitmapIndexed Word
b2 Array (HashMap k v)
ary2) =
        let b' :: Word
b'   = Word
b1 Word -> Word -> Word
forall a. Bits a => a -> a -> a
.|. Word
b2
            ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Word
-> Word
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Word -> Word -> Array a -> Array a -> Array a
HM.unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int -> Int
nextShift Int
s)) Word
b1 Word
b2 Array (HashMap k v)
ary1 Array (HashMap k v)
ary2
        in Word -> Array (HashMap k v) -> HashMap k v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
HM.bitmapIndexedOrFull Word
b' Array (HashMap k v)
ary'
    go Int
s (BitmapIndexed Word
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)
-> Word
-> Word
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Word -> Word -> Array a -> Array a -> Array a
HM.unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int -> Int
nextShift Int
s)) Word
b1 Word
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 Int
s (Full Array (HashMap k v)
ary1) (BitmapIndexed Word
b2 Array (HashMap k v)
ary2) =
        let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Word
-> Word
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Word -> Word -> Array a -> Array a -> Array a
HM.unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int -> Int
nextShift Int
s)) Word
fullBitmap Word
b2 Array (HashMap k v)
ary1 Array (HashMap k v)
ary2
        in Array (HashMap k v) -> HashMap k v
forall k v. Array (HashMap k v) -> HashMap k v
Full Array (HashMap k v)
ary'
    go Int
s (Full Array (HashMap k v)
ary1) (Full Array (HashMap k v)
ary2) =
        let ary' :: Array (HashMap k v)
ary' = (HashMap k v -> HashMap k v -> HashMap k v)
-> Word
-> Word
-> Array (HashMap k v)
-> Array (HashMap k v)
-> Array (HashMap k v)
forall a.
(a -> a -> a) -> Word -> Word -> Array a -> Array a -> Array a
HM.unionArrayBy (Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int -> Int
nextShift Int
s)) Word
fullBitmap Word
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 Int
s (BitmapIndexed Word
b1 Array (HashMap k v)
ary1) HashMap k v
t2
        | Word
b1 Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
m2 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
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' :: Word
b'   = Word
b1 Word -> Word -> Word
forall a. Bits a => a -> a -> a
.|. Word
m2
                           in Word -> Array (HashMap k v) -> HashMap k v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
HM.bitmapIndexedOrFull Word
b' Array (HashMap k v)
ary'
        | Bool
otherwise      = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Int -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Int -> (e -> e) -> Array e
A.updateWith' Array (HashMap k v)
ary1 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st1 ->
                                   Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int -> Int
nextShift Int
s) HashMap k v
st1 HashMap k v
t2
                           in Word -> Array (HashMap k v) -> HashMap k v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Word
b1 Array (HashMap k v)
ary'
        where
          h2 :: Word
h2 = HashMap k v -> Word
forall {k} {v}. HashMap k v -> Word
leafHashCode HashMap k v
t2
          m2 :: Word
m2 = Word -> Int -> Word
mask Word
h2 Int
s
          i :: Int
i = Word -> Word -> Int
sparseIndex Word
b1 Word
m2
    go Int
s HashMap k v
t1 (BitmapIndexed Word
b2 Array (HashMap k v)
ary2)
        | Word
b2 Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
m1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
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' :: Word
b'   = Word
b2 Word -> Word -> Word
forall a. Bits a => a -> a -> a
.|. Word
m1
                           in Word -> Array (HashMap k v) -> HashMap k v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
HM.bitmapIndexedOrFull Word
b' Array (HashMap k v)
ary'
        | Bool
otherwise      = let ary' :: Array (HashMap k v)
ary' = Array (HashMap k v)
-> Int -> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall e. Array e -> Int -> (e -> e) -> Array e
A.updateWith' Array (HashMap k v)
ary2 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st2 ->
                                   Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int -> Int
nextShift Int
s) HashMap k v
t1 HashMap k v
st2
                           in Word -> Array (HashMap k v) -> HashMap k v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Word
b2 Array (HashMap k v)
ary'
      where
        h1 :: Word
h1 = HashMap k v -> Word
forall {k} {v}. HashMap k v -> Word
leafHashCode HashMap k v
t1
        m1 :: Word
m1 = Word -> Int -> Word
mask Word
h1 Int
s
        i :: Int
i = Word -> Word -> Int
sparseIndex Word
b2 Word
m1
    go Int
s (Full Array (HashMap k v)
ary1) HashMap k v
t2 =
        let h2 :: Word
h2   = HashMap k v -> Word
forall {k} {v}. HashMap k v -> Word
leafHashCode HashMap k v
t2
            i :: Int
i    = Word -> Int -> Int
index Word
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
HM.updateFullArrayWith' Array (HashMap k v)
ary1 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st1 -> Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int -> Int
nextShift Int
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 Int
s HashMap k v
t1 (Full Array (HashMap k v)
ary2) =
        let h1 :: Word
h1   = HashMap k v -> Word
forall {k} {v}. HashMap k v -> Word
leafHashCode HashMap k v
t1
            i :: Int
i    = Word -> Int -> Int
index Word
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
HM.updateFullArrayWith' Array (HashMap k v)
ary2 Int
i ((HashMap k v -> HashMap k v) -> Array (HashMap k v))
-> (HashMap k v -> HashMap k v) -> Array (HashMap k v)
forall a b. (a -> b) -> a -> b
$ \HashMap k v
st2 -> Int -> HashMap k v -> HashMap k v -> HashMap k v
go (Int -> Int
nextShift Int
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 -> Word
leafHashCode (Leaf Word
h Leaf k v
_) = Word
h
    leafHashCode (Collision Word
h Array (Leaf k v)
_) = Word
h
    leafHashCode HashMap k v
_ = [Char] -> Word
forall a. HasCallStack => [Char] -> a
error [Char]
"leafHashCode"

    goDifferentHash :: Int -> Word -> Word -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash Int
s Word
h1 Word
h2 HashMap k v
t1 HashMap k v
t2
        | Word
m1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
m2  = Word -> Array (HashMap k v) -> HashMap k v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Word
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 -> Word -> Word -> HashMap k v -> HashMap k v -> HashMap k v
goDifferentHash (Int -> Int
nextShift Int
s) Word
h1 Word
h2 HashMap k v
t1 HashMap k v
t2)
        | Word
m1 Word -> Word -> Bool
forall a. Ord a => a -> a -> Bool
<  Word
m2  = Word -> Array (HashMap k v) -> HashMap k v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Word
m1 Word -> Word -> Word
forall a. Bits a => a -> a -> a
.|. Word
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 = Word -> Array (HashMap k v) -> HashMap k v
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed (Word
m1 Word -> Word -> Word
forall a. Bits a => a -> a -> a
.|. Word
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 :: Word
m1 = Word -> Int -> Word
mask Word
h1 Int
s
        m2 :: Word
m2 = Word -> Int -> Word
mask Word
h2 Int
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 Word
h (L k
k v1
v))      = Word -> k -> v2 -> HashMap k v2
forall k v. Word -> k -> v -> HashMap k v
leaf Word
h k
k (k -> v1 -> v2
f k
k v1
v)
    go (BitmapIndexed Word
b Array (HashMap k v1)
ary) = Word -> Array (HashMap k v2) -> HashMap k v2
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Word
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 Word
h Array (Leaf k v1)
ary)     =
        Word -> Array (Leaf k v2) -> HashMap k v2
forall k v. Word -> Array (Leaf k v) -> HashMap k v
Collision Word
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 Word
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 (Word -> k -> v2 -> HashMap k v2
forall k v. Word -> k -> v -> HashMap k v
leaf Word
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 Word
h (L k
k v1
v))      = Word -> k -> v2 -> HashMap k v2
forall k v. Word -> k -> v -> HashMap k v
leaf Word
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 Word
b Array (HashMap k v1)
ary) = Word -> Array (HashMap k v2) -> HashMap k v2
forall k v. Word -> Array (HashMap k v) -> HashMap k v
BitmapIndexed Word
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 Word
h Array (Leaf k v1)
ary)     =
        Word -> Array (Leaf k v2) -> HashMap k v2
forall k v. Word -> Array (Leaf k v) -> HashMap k v
Collision Word
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 :: Hashable k => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v
differenceWith :: forall k v w.
Hashable k =>
(v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v
differenceWith v -> w -> Maybe v
f = (k -> v -> w -> Maybe v)
-> HashMap k v -> HashMap k w -> HashMap k v
forall k v w.
Eq k =>
(k -> v -> w -> Maybe v)
-> HashMap k v -> HashMap k w -> HashMap k v
HM.differenceWithKey ((k -> v -> w -> Maybe v)
 -> HashMap k v -> HashMap k w -> HashMap k v)
-> (k -> v -> w -> Maybe v)
-> HashMap k v
-> HashMap k w
-> HashMap k v
forall a b. (a -> b) -> a -> b
$
  \k
_k v
vA w
vB -> case v -> w -> Maybe v
f v
vA w
vB of
     Maybe v
Nothing -> Maybe v
forall a. Maybe a
Nothing
     x :: Maybe v
x@(Just v
v) -> v
v v -> Maybe v -> Maybe v
forall a b. a -> b -> b
`seq` Maybe v
x
{-# INLINE differenceWith #-}

-- | \(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@.
--
-- @since 0.2.21
differenceWithKey :: Eq k => (k -> v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v
differenceWithKey :: forall k v w.
Eq k =>
(k -> v -> w -> Maybe v)
-> HashMap k v -> HashMap k w -> HashMap k v
differenceWithKey k -> v -> w -> Maybe v
f = (k -> v -> w -> Maybe v)
-> HashMap k v -> HashMap k w -> HashMap k v
forall k v w.
Eq k =>
(k -> v -> w -> Maybe v)
-> HashMap k v -> HashMap k w -> HashMap k v
HM.differenceWithKey ((k -> v -> w -> Maybe v)
 -> HashMap k v -> HashMap k w -> HashMap k v)
-> (k -> v -> w -> Maybe v)
-> HashMap k v
-> HashMap k w
-> HashMap k v
forall a b. (a -> b) -> a -> b
$
  \k
k v
vA w
vB -> case k -> v -> w -> Maybe v
f k
k v
vA w
vB of
     Maybe v
Nothing -> Maybe v
forall a. Maybe a
Nothing
     x :: Maybe v
x@(Just v
v) -> v
v v -> Maybe v -> Maybe v
forall a b. a -> b -> b
`seq` Maybe v
x
{-# INLINE differenceWithKey #-}

-- | \(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 :: Hashable k => [(k, v)] -> HashMap k v
fromList :: forall k v. 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. 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 :: Hashable k => (v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWith :: forall k v. 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.
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 :: Hashable k => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v
fromListWithKey :: forall k v.
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.
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) -> Int -> Int -> Array (Leaf k v)
forall {t}.
Eq t =>
t -> Array (Leaf t v) -> Int -> Int -> Array (Leaf t v)
go k
k0 Array (Leaf k v)
ary0 Int
0 (Array (Leaf k v) -> Int
forall a. Array a -> Int
A.length Array (Leaf k v)
ary0)
  where
    go :: t -> Array (Leaf t v) -> Int -> Int -> Array (Leaf t v)
go !t
k !Array (Leaf t v)
ary !Int
i !Int
n
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n    = Array (Leaf t v)
ary
        | Bool
otherwise = case Array (Leaf t v) -> Int -> (# Leaf t v #)
forall a. Array a -> Int -> (# a #)
A.index# Array (Leaf t v)
ary Int
i of
            (# L t
kx v
y #) | t
k t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
kx   -> let !v' :: v
v' = v -> v
f v
y in Array (Leaf t v) -> Int -> Leaf t v -> Array (Leaf t v)
forall e. Array e -> Int -> e -> Array e
A.update Array (Leaf t v)
ary Int
i (t -> v -> Leaf t v
forall k v. k -> v -> Leaf k v
L t
k v
v')
                         | Bool
otherwise -> t -> Array (Leaf t v) -> Int -> Int -> Array (Leaf t v)
go t
k Array (Leaf t v)
ary (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
n
{-# INLINABLE updateWith #-}

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

------------------------------------------------------------------------
-- 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. Word -> k -> v -> HashMap k v
leaf Word
h k
k = \ !v
v -> Word -> Leaf k v -> HashMap k v
forall k v. Word -> Leaf k v -> HashMap k v
Leaf Word
h (k -> v -> Leaf k v
forall k v. k -> v -> Leaf k v
L k
k v
v)
{-# INLINE leaf #-}