    {-# 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. 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.!)
        , 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.updateFullArray 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
                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
                return $! HM.bitmapIndexedOrFull (b .|. m) ary'
            | Bool
    otherwise = do
                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
                st' <- go h k x (nextShift s) st
                A.unsafeUpdateM ary i st'
                return 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
            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
            st' <- go h k x (nextShift s) st
            A.unsafeUpdateM ary i st'
            return 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.updateFullArray 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.updateFullArrayWith' 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.updateFullArrayWith' 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 #-}