{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UnboxedTuples #-}

{-# OPTIONS_GHC -O2 -Wall #-}
module Data.Map.Internal
  ( Map
  , empty
  , singleton
  , null
  , map
  , mapWithKey
  , mapMaybe
  , mapMaybeP
  , mapMaybeWithKey
    -- * Folds
  , foldrWithKey
  , foldlWithKey'
  , foldrWithKey'
  , foldMapWithKey
  , foldMapWithKey'
    -- * Monadic Folds
  , foldlWithKeyM'
  , foldrWithKeyM'
  , foldlMapWithKeyM'
  , foldrMapWithKeyM'
    -- * Traversals
  , traverse
  , traverseWithKey
  , traverseWithKey_
    -- * Functions
  , append
  , appendWith
  , appendWithKey
  , appendRightBiased
  , intersectionWith
  , intersectionsWith
  , adjustMany
  , adjustManyInline
  , lookup
  , showsPrec
  , equals
  , compare
  , toList
  , concat
  , size
  , sizeKeys
  , keys
  , elems
  , restrict
  , rnf
    -- * List Conversion
  , fromListN
  , fromList
  , fromListAppend
  , fromListAppendN
  , fromSet
  , fromSetP
    -- * Array Conversion
  , unsafeFreezeZip
  , unsafeZipPresorted
  ) where

import Prelude hiding (compare,showsPrec,lookup,map,concat,null,traverse)

import Control.Applicative (liftA2)
import Control.DeepSeq (NFData)
import Control.Monad.Primitive (PrimMonad,PrimState)
import Control.Monad.ST (ST,runST)
import Data.List.NonEmpty (NonEmpty)
import Data.Primitive.Contiguous (ContiguousU,Mutable,Element)
import Data.Primitive.Sort (sortUniqueTaggedMutable)
import Data.Set.Internal (Set(..))

import qualified Data.Concatenation as C
import qualified Data.Primitive.Contiguous as I
import qualified Data.Semigroup as SG
import qualified Prelude as P

-- TODO: Do some sneakiness with UnliftedRep
data Map karr varr k v = Map !(karr k) !(varr v)

empty :: (ContiguousU karr, ContiguousU varr) => Map karr varr k v
empty :: forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, ContiguousU varr) =>
Map karr varr k v
empty = forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map forall (arr :: * -> *) a. Contiguous arr => arr a
I.empty forall (arr :: * -> *) a. Contiguous arr => arr a
I.empty

null :: ContiguousU varr => Map karr varr k v -> Bool
null :: forall (varr :: * -> *) (karr :: * -> *) k v.
ContiguousU varr =>
Map karr varr k v -> Bool
null (Map karr k
_ varr v
vals) = forall (arr :: * -> *) b. Contiguous arr => arr b -> Bool
I.null varr v
vals

singleton :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v) => k -> v -> Map karr varr k v
singleton :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
k -> v -> Map karr varr k v
singleton k
k v
v = forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map
  ( forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
      Mutable karr s k
arr <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
1
      forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
arr Int
0 k
k
      forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable karr s k
arr
  )
  ( forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
      Mutable varr s v
arr <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
1
      forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s v
arr Int
0 v
v
      forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable varr s v
arr
  )

equals :: (ContiguousU karr, Element karr k, Eq k, ContiguousU varr, Element varr v, Eq v) => Map karr varr k v -> Map karr varr k v -> Bool
equals :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Eq k, ContiguousU varr,
 Element varr v, Eq v) =>
Map karr varr k v -> Map karr varr k v -> Bool
equals (Map karr k
k1 varr v
v1) (Map karr k
k2 varr v
v2) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b, Eq b) =>
arr b -> arr b -> Bool
I.equals karr k
k1 karr k
k2 Bool -> Bool -> Bool
&& forall (arr :: * -> *) b.
(Contiguous arr, Element arr b, Eq b) =>
arr b -> arr b -> Bool
I.equals varr v
v1 varr v
v2

compare :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v, Ord v) => Map karr varr k v -> Map karr varr k v -> Ordering
compare :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Ord v) =>
Map karr varr k v -> Map karr varr k v -> Ordering
compare Map karr varr k v
m1 Map karr varr k v
m2 = forall a. Ord a => a -> a -> Ordering
P.compare (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
Map karr varr k v -> [(k, v)]
toList Map karr varr k v
m1) (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
Map karr varr k v -> [(k, v)]
toList Map karr varr k v
m2)

fromListWithN :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v) => (v -> v -> v) -> Int -> [(k,v)] -> Map karr varr k v
fromListWithN :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(v -> v -> v) -> Int -> [(k, v)] -> Map karr varr k v
fromListWithN v -> v -> v
combine Int
n [(k, v)]
xs =
  case [(k, v)]
xs of
    [] -> forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, ContiguousU varr) =>
Map karr varr k v
empty
    (k
k,v
v) : [(k, v)]
ys ->
      let ([(k, v)]
leftovers, Map karr varr k v
result) = forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(v -> v -> v)
-> Int -> k -> v -> [(k, v)] -> ([(k, v)], Map karr varr k v)
fromAscListWith v -> v -> v
combine (forall a. Ord a => a -> a -> a
max Int
1 Int
n) k
k v
v [(k, v)]
ys
       in forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(v -> v -> v) -> [Map karr varr k v] -> Map karr varr k v
concatWith v -> v -> v
combine (Map karr varr k v
result forall a. a -> [a] -> [a]
: forall a b. (a -> b) -> [a] -> [b]
P.map (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
k -> v -> Map karr varr k v
singleton) [(k, v)]
leftovers)

fromListN :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v)
  => Int
  -> [(k,v)]
  -> Map karr varr k v
{-# INLINABLE fromListN #-}
fromListN :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Int -> [(k, v)] -> Map karr varr k v
fromListN Int
n [(k, v)]
xs = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
  (Mutable karr s k
ks,Mutable varr s v
vs) <- forall s (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Int -> [(k, v)] -> ST s (Mutable karr s k, Mutable varr s v)
mutableArraysFromPairs (forall a. Ord a => a -> a -> a
max Int
n Int
1) [(k, v)]
xs
  forall (karr :: * -> *) k (varr :: * -> *) v s.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Mutable karr s k -> Mutable varr s v -> ST s (Map karr varr k v)
unsafeFreezeZip Mutable karr s k
ks Mutable varr s v
vs

mutableArraysFromPairs :: forall s karr varr k v. (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v)
  => Int -- must be at least one
  -> [(k,v)]
  -> ST s (Mutable karr s k, Mutable varr s v)
{-# INLINABLE mutableArraysFromPairs #-}
mutableArraysFromPairs :: forall s (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Int -> [(k, v)] -> ST s (Mutable karr s k, Mutable varr s v)
mutableArraysFromPairs Int
n [(k, v)]
xs = do
  let go :: Int -> Int -> Mutable karr s k -> Mutable varr s v -> [(k,v)] -> ST s (Int, Mutable karr s k, Mutable varr s v)
      go :: Int
-> Int
-> Mutable karr s k
-> Mutable varr s v
-> [(k, v)]
-> ST s (Int, Mutable karr s k, Mutable varr s v)
go !Int
ix !Int
_ !Mutable karr s k
ks !Mutable varr s v
vs [] = forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ix,Mutable karr s k
ks,Mutable varr s v
vs)
      go !Int
ix !Int
len !Mutable karr s k
ks !Mutable varr s v
vs ((k
k,v
v) : [(k, v)]
ys) = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
len
        then do
          forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
ks Int
ix k
k
          forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s v
vs Int
ix v
v
          Int
-> Int
-> Mutable karr s k
-> Mutable varr s v
-> [(k, v)]
-> ST s (Int, Mutable karr s k, Mutable varr s v)
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1) Int
len Mutable karr s k
ks Mutable varr s v
vs [(k, v)]
ys
        else do
          let len' :: Int
len' = Int
len forall a. Num a => a -> a -> a
* Int
2
          Mutable karr s k
ks' <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
len'
          Mutable varr s v
vs' <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
len'
          forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> MutableSliced arr (PrimState m) b -> m ()
I.copyMut Mutable karr s k
ks' Int
0 (forall (arr :: * -> *) a s.
(Contiguous arr, Element arr a) =>
Mutable arr s a -> Int -> Int -> MutableSliced arr s a
I.sliceMut Mutable karr s k
ks Int
0 Int
len)
          forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> MutableSliced arr (PrimState m) b -> m ()
I.copyMut Mutable varr s v
vs' Int
0 (forall (arr :: * -> *) a s.
(Contiguous arr, Element arr a) =>
Mutable arr s a -> Int -> Int -> MutableSliced arr s a
I.sliceMut Mutable varr s v
vs Int
0 Int
len)
          forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
ks' Int
ix k
k
          forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s v
vs' Int
ix v
v
          Int
-> Int
-> Mutable karr s k
-> Mutable varr s v
-> [(k, v)]
-> ST s (Int, Mutable karr s k, Mutable varr s v)
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1) Int
len' Mutable karr s k
ks' Mutable varr s v
vs' [(k, v)]
ys
  Mutable karr s k
ks0 <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
n
  Mutable varr s v
vs0 <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
n
  (Int
len,Mutable karr s k
ks',Mutable varr s v
vs') <- Int
-> Int
-> Mutable karr s k
-> Mutable varr s v
-> [(k, v)]
-> ST s (Int, Mutable karr s k, Mutable varr s v)
go Int
0 Int
n Mutable karr s k
ks0 Mutable varr s v
vs0 [(k, v)]
xs
  Mutable karr s k
ksFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr s k
ks' Int
len
  Mutable varr s v
vsFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable varr s v
vs' Int
len
  forall (m :: * -> *) a. Monad m => a -> m a
return (Mutable karr s k
ksFinal,Mutable varr s v
vsFinal)

fromList :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v) => [(k,v)] -> Map karr varr k v
fromList :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
[(k, v)] -> Map karr varr k v
fromList = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Int -> [(k, v)] -> Map karr varr k v
fromListN Int
8

fromListAppendN :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v, Semigroup v) => Int -> [(k,v)] -> Map karr varr k v
fromListAppendN :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Semigroup v) =>
Int -> [(k, v)] -> Map karr varr k v
fromListAppendN = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(v -> v -> v) -> Int -> [(k, v)] -> Map karr varr k v
fromListWithN forall a. Semigroup a => a -> a -> a
(SG.<>)

fromListAppend :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v, Semigroup v) => [(k,v)] -> Map karr varr k v
fromListAppend :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Semigroup v) =>
[(k, v)] -> Map karr varr k v
fromListAppend = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Semigroup v) =>
Int -> [(k, v)] -> Map karr varr k v
fromListAppendN Int
1

fromAscListWith :: forall karr varr k v. (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v)
  => (v -> v -> v)
  -> Int -- initial size of buffer, must be 1 or higher
  -> k -- first key
  -> v -- first value
  -> [(k,v)] -- elements
  -> ([(k,v)], Map karr varr k v)
fromAscListWith :: forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(v -> v -> v)
-> Int -> k -> v -> [(k, v)] -> ([(k, v)], Map karr varr k v)
fromAscListWith v -> v -> v
combine !Int
n !k
k0 !v
v0 [(k, v)]
xs0 = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
  Mutable karr s k
keys0 <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
n
  Mutable varr s v
vals0 <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
n
  forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
keys0 Int
0 k
k0
  forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s v
vals0 Int
0 v
v0
  let go :: forall s. Int -> k -> Int -> Mutable karr s k -> Mutable varr s v -> [(k,v)] -> ST s ([(k,v)], Map karr varr k v)
      go :: forall s.
Int
-> k
-> Int
-> Mutable karr s k
-> Mutable varr s v
-> [(k, v)]
-> ST s ([(k, v)], Map karr varr k v)
go !Int
ix !k
_ !Int
sz !Mutable karr s k
theKeys !Mutable varr s v
vals [] = if Int
ix forall a. Eq a => a -> a -> Bool
== Int
sz
        then do
          karr k
arrKeys <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable karr s k
theKeys
          varr v
arrVals <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable varr s v
vals
          forall (m :: * -> *) a. Monad m => a -> m a
return ([],forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
arrKeys varr v
arrVals)
        else do
          Mutable karr s k
keys' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr s k
theKeys Int
ix
          karr k
arrKeys <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable karr s k
keys'
          Mutable varr s v
vals' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable varr s v
vals Int
ix
          varr v
arrVals <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable varr s v
vals'
          forall (m :: * -> *) a. Monad m => a -> m a
return ([],forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
arrKeys varr v
arrVals)
      go !Int
ix !k
old !Int
sz !Mutable karr s k
theKeys !Mutable varr s v
vals ((k
k,v
v) : [(k, v)]
xs) = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
sz
        then case forall a. Ord a => a -> a -> Ordering
P.compare k
k k
old of
          Ordering
GT -> do
            forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
theKeys Int
ix k
k
            forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s v
vals Int
ix v
v
            forall s.
Int
-> k
-> Int
-> Mutable karr s k
-> Mutable varr s v
-> [(k, v)]
-> ST s ([(k, v)], Map karr varr k v)
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1) k
k Int
sz Mutable karr s k
theKeys Mutable varr s v
vals [(k, v)]
xs
          Ordering
EQ -> do
            v
oldVal <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> m b
I.read Mutable varr s v
vals (Int
ix forall a. Num a => a -> a -> a
- Int
1)
            let !newVal :: v
newVal = v -> v -> v
combine v
oldVal v
v
            forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s v
vals (Int
ix forall a. Num a => a -> a -> a
- Int
1) v
newVal
            forall s.
Int
-> k
-> Int
-> Mutable karr s k
-> Mutable varr s v
-> [(k, v)]
-> ST s ([(k, v)], Map karr varr k v)
go Int
ix k
k Int
sz Mutable karr s k
theKeys Mutable varr s v
vals [(k, v)]
xs
          Ordering
LT -> do
            Mutable karr s k
keys' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr s k
theKeys Int
ix
            karr k
arrKeys <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable karr s k
keys'
            Mutable varr s v
vals' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable varr s v
vals Int
ix
            varr v
arrVals <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable varr s v
vals'
            forall (m :: * -> *) a. Monad m => a -> m a
return ((k
k,v
v) forall a. a -> [a] -> [a]
: [(k, v)]
xs,forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
arrKeys varr v
arrVals)
        else do
          let sz' :: Int
sz' = Int
sz forall a. Num a => a -> a -> a
* Int
2
          Mutable karr s k
keys' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr s k
theKeys Int
sz'
          Mutable varr s v
vals' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable varr s v
vals Int
sz'
          forall s.
Int
-> k
-> Int
-> Mutable karr s k
-> Mutable varr s v
-> [(k, v)]
-> ST s ([(k, v)], Map karr varr k v)
go Int
ix k
old Int
sz' Mutable karr s k
keys' Mutable varr s v
vals' ((k
k,v
v) forall a. a -> [a] -> [a]
: [(k, v)]
xs)
  forall s.
Int
-> k
-> Int
-> Mutable karr s k
-> Mutable varr s v
-> [(k, v)]
-> ST s ([(k, v)], Map karr varr k v)
go Int
1 k
k0 Int
n Mutable karr s k
keys0 Mutable varr s v
vals0 [(k, v)]
xs0


map :: (ContiguousU varr, ContiguousU warr, Element varr v, Element warr w)
  => (v -> w)
  -> Map karr varr k v
  -> Map karr warr k w
map :: forall (varr :: * -> *) (warr :: * -> *) v w (karr :: * -> *) k.
(ContiguousU varr, ContiguousU warr, Element varr v,
 Element warr w) =>
(v -> w) -> Map karr varr k v -> Map karr warr k w
map v -> w
f (Map karr k
k varr v
v) = forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
k (forall (arr1 :: * -> *) b (arr2 :: * -> *) c.
(Contiguous arr1, Element arr1 b, Contiguous arr2,
 Element arr2 c) =>
(b -> c) -> arr1 b -> arr2 c
I.map v -> w
f varr v
v)

-- | /O(n)/ Map over the elements with access to their corresponding keys.
mapWithKey :: forall karr varr k v w. (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Element varr w)
  => (k -> v -> w)
  -> Map karr varr k v
  -> Map karr varr k w
{-# INLINEABLE mapWithKey #-}
mapWithKey :: forall (karr :: * -> *) (varr :: * -> *) k v w.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(k -> v -> w) -> Map karr varr k v -> Map karr varr k w
mapWithKey k -> v -> w
f (Map karr k
ks varr v
vs) = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
  let !sz :: Int
sz = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs
  !(Mutable karr s k
karr :: Mutable karr s k) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
sz
  !(Mutable varr s w
varr :: Mutable varr s w) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
sz
  let go :: Int -> ST s Int
go !Int
ix = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
sz
        then do
          k
k <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM karr k
ks Int
ix
          v
a <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM varr v
vs Int
ix
          forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s w
varr Int
ix (k -> v -> w
f k
k v
a)
          forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
karr Int
ix k
k
          Int -> ST s Int
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1)
        else forall (m :: * -> *) a. Monad m => a -> m a
return Int
ix
  Int
dstLen <- Int -> ST s Int
go Int
0
  karr k
ksFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr s k
karr Int
dstLen forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
  varr w
vsFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable varr s w
varr Int
dstLen forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
  forall (m :: * -> *) a. Monad m => a -> m a
return (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
ksFinal varr w
vsFinal)

-- | /O(n)/ Drop elements for which the predicate returns 'Nothing'.
mapMaybe :: forall karr varr k v w. (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Element varr w)
  => (v -> Maybe w)
  -> Map karr varr k v
  -> Map karr varr k w
{-# INLINE mapMaybe #-}
mapMaybe :: forall (karr :: * -> *) (varr :: * -> *) k v w.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(v -> Maybe w) -> Map karr varr k v -> Map karr varr k w
mapMaybe v -> Maybe w
f (Map karr k
ks varr v
vs) = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
  let !sz :: Int
sz = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs
  !(Mutable karr s k
karr :: Mutable karr s k) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
sz
  !(Mutable varr s w
varr :: Mutable varr s w) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
sz
  let go :: Int -> Int -> ST s Int
go !Int
ixSrc !Int
ixDst = if Int
ixSrc forall a. Ord a => a -> a -> Bool
< Int
sz
        then do
          v
a <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM varr v
vs Int
ixSrc
          case v -> Maybe w
f v
a of
            Maybe w
Nothing -> Int -> Int -> ST s Int
go (Int
ixSrc forall a. Num a => a -> a -> a
+ Int
1) Int
ixDst
            Just w
b -> do
              forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s w
varr Int
ixDst w
b
              forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
karr Int
ixDst forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM karr k
ks Int
ixSrc
              Int -> Int -> ST s Int
go (Int
ixSrc forall a. Num a => a -> a -> a
+ Int
1) (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
        else forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
  Int
dstLen <- Int -> Int -> ST s Int
go Int
0 Int
0
  karr k
ksFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr s k
karr Int
dstLen forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
  varr w
vsFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable varr s w
varr Int
dstLen forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
  forall (m :: * -> *) a. Monad m => a -> m a
return (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
ksFinal varr w
vsFinal)

-- | /O(n)/ Drop elements for which the predicate returns 'Nothing'.
mapMaybeP :: forall karr varr m k v w. (PrimMonad m, ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Element varr w)
  => (v -> m (Maybe w))
  -> Map karr varr k v
  -> m (Map karr varr k w)
{-# INLINE mapMaybeP #-}
mapMaybeP :: forall (karr :: * -> *) (varr :: * -> *) (m :: * -> *) k v w.
(PrimMonad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(v -> m (Maybe w)) -> Map karr varr k v -> m (Map karr varr k w)
mapMaybeP v -> m (Maybe w)
f (Map karr k
ks varr v
vs) = do
  let !sz :: Int
sz = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs
  !(Mutable karr (PrimState m) k
karr :: Mutable karr (PrimState m) k) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
sz
  !(Mutable varr (PrimState m) w
varr :: Mutable varr (PrimState m) w) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
sz
  let go :: Int -> Int -> m Int
go !Int
ixSrc !Int
ixDst = if Int
ixSrc forall a. Ord a => a -> a -> Bool
< Int
sz
        then do
          v
a <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM varr v
vs Int
ixSrc
          v -> m (Maybe w)
f v
a forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
            Maybe w
Nothing -> Int -> Int -> m Int
go (Int
ixSrc forall a. Num a => a -> a -> a
+ Int
1) Int
ixDst
            Just w
b -> do
              forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr (PrimState m) w
varr Int
ixDst w
b
              forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr (PrimState m) k
karr Int
ixDst forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM karr k
ks Int
ixSrc
              Int -> Int -> m Int
go (Int
ixSrc forall a. Num a => a -> a -> a
+ Int
1) (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
        else forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
  Int
dstLen <- Int -> Int -> m Int
go Int
0 Int
0
  karr k
ksFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr (PrimState m) k
karr Int
dstLen forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
  varr w
vsFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable varr (PrimState m) w
varr Int
dstLen forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
  forall (m :: * -> *) a. Monad m => a -> m a
return (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
ksFinal varr w
vsFinal)

-- | /O(n)/ Drop elements for which the predicate returns 'Nothing'.
mapMaybeWithKey :: forall karr varr k v w. (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Element varr w)
  => (k -> v -> Maybe w)
  -> Map karr varr k v
  -> Map karr varr k w
{-# INLINEABLE mapMaybeWithKey #-}
mapMaybeWithKey :: forall (karr :: * -> *) (varr :: * -> *) k v w.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(k -> v -> Maybe w) -> Map karr varr k v -> Map karr varr k w
mapMaybeWithKey k -> v -> Maybe w
f (Map karr k
ks varr v
vs) = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
  let !sz :: Int
sz = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs
  !(Mutable karr s k
karr :: Mutable karr s k) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
sz
  !(Mutable varr s w
varr :: Mutable varr s w) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
sz
  let go :: Int -> Int -> ST s Int
go !Int
ixSrc !Int
ixDst = if Int
ixSrc forall a. Ord a => a -> a -> Bool
< Int
sz
        then do
          k
k <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM karr k
ks Int
ixSrc
          v
a <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM varr v
vs Int
ixSrc
          case k -> v -> Maybe w
f k
k v
a of
            Maybe w
Nothing -> Int -> Int -> ST s Int
go (Int
ixSrc forall a. Num a => a -> a -> a
+ Int
1) Int
ixDst
            Just !w
b -> do
              forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s w
varr Int
ixDst w
b
              forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
karr Int
ixDst k
k
              Int -> Int -> ST s Int
go (Int
ixSrc forall a. Num a => a -> a -> a
+ Int
1) (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
        else forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
  Int
dstLen <- Int -> Int -> ST s Int
go Int
0 Int
0
  karr k
ksFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr s k
karr Int
dstLen forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
  varr w
vsFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable varr s w
varr Int
dstLen forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
  forall (m :: * -> *) a. Monad m => a -> m a
return (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
ksFinal varr w
vsFinal)

showsPrec :: (ContiguousU karr, Element karr k, Show k, ContiguousU varr, Element varr v, Show v) => Int -> Map karr varr k v -> ShowS
showsPrec :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Show k, ContiguousU varr,
 Element varr v, Show v) =>
Int -> Map karr varr k v -> ShowS
showsPrec Int
p Map karr varr k v
xs = Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
10) forall a b. (a -> b) -> a -> b
$
  String -> ShowS
showString String
"fromList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => a -> ShowS
shows (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
Map karr varr k v -> [(k, v)]
toList Map karr varr k v
xs)

toList :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v) => Map karr varr k v -> [(k,v)]
toList :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
Map karr varr k v -> [(k, v)]
toList = forall (karr :: * -> *) k (varr :: * -> *) v b.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> b -> b) -> b -> Map karr varr k v -> b
foldrWithKey (\k
k v
v [(k, v)]
xs -> (k
k,v
v) forall a. a -> [a] -> [a]
: [(k, v)]
xs) []

foldrWithKey :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v)
  => (k -> v -> b -> b)
  -> b
  -> Map karr varr k v
  -> b
foldrWithKey :: forall (karr :: * -> *) k (varr :: * -> *) v b.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> b -> b) -> b -> Map karr varr k v -> b
foldrWithKey k -> v -> b -> b
f b
z (Map karr k
theKeys varr v
vals) =
  let !sz :: Int
sz = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vals
      go :: Int -> b
go !Int
i
        | Int
i forall a. Eq a => a -> a -> Bool
== Int
sz = b
z
        | Bool
otherwise =
            let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
theKeys Int
i
                !(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vals Int
i
             in k -> v -> b -> b
f k
k v
v (Int -> b
go (Int
i forall a. Num a => a -> a -> a
+ Int
1))
   in Int -> b
go Int
0

foldMapWithKey :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Monoid m)
  => (k -> v -> m)
  -> Map karr varr k v
  -> m
foldMapWithKey :: forall (karr :: * -> *) k (varr :: * -> *) v m.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid m) =>
(k -> v -> m) -> Map karr varr k v -> m
foldMapWithKey k -> v -> m
f (Map karr k
theKeys varr v
vals) =
  let !sz :: Int
sz = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vals
      go :: Int -> m
go !Int
i
        | Int
i forall a. Eq a => a -> a -> Bool
== Int
sz = forall a. Monoid a => a
mempty
        | Bool
otherwise =
            let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
theKeys Int
i
                !(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vals Int
i
             in forall a. Monoid a => a -> a -> a
mappend (k -> v -> m
f k
k v
v) (Int -> m
go (Int
i forall a. Num a => a -> a -> a
+ Int
1))
   in Int -> m
go Int
0

adjustMany :: forall karr varr m k v a. (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, PrimMonad m, Ord k)
  => ((k -> (v -> m v) -> m ()) -> m a) -- Callback that takes a modify function
  -> Map karr varr k v
  -> m (Map karr varr k v, a)
{-# INLINABLE adjustMany #-}
adjustMany :: forall (karr :: * -> *) (varr :: * -> *) (m :: * -> *) k v a.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, PrimMonad m, Ord k) =>
((k -> (v -> m v) -> m ()) -> m a)
-> Map karr varr k v -> m (Map karr varr k v, a)
adjustMany (k -> (v -> m v) -> m ()) -> m a
f (Map karr k
theKeys varr v
theVals) = do
  Mutable varr (PrimState m) v
mvals <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Sliced arr b -> m (Mutable arr (PrimState m) b)
I.thaw (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
I.slice varr v
theVals Int
0 (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
theVals))
  let g :: k -> (v -> m v) -> m ()
      g :: k -> (v -> m v) -> m ()
g !k
k v -> m v
updateVal =
        let go :: Int -> Int -> m ()
go !Int
start !Int
end = if Int
end forall a. Ord a => a -> a -> Bool
< Int
start
              then forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
              else
                let !mid :: Int
mid = forall a. Integral a => a -> a -> a
div (Int
end forall a. Num a => a -> a -> a
+ Int
start) Int
2
                    !(# k
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
theKeys Int
mid
                 in case forall a. Ord a => a -> a -> Ordering
P.compare k
k k
v of
                      Ordering
LT -> Int -> Int -> m ()
go Int
start (Int
mid forall a. Num a => a -> a -> a
- Int
1)
                      Ordering
EQ -> do
                        v
r <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> m b
I.read Mutable varr (PrimState m) v
mvals Int
mid
                        v
r' <- v -> m v
updateVal v
r
                        forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr (PrimState m) v
mvals Int
mid v
r'
                      Ordering
GT -> Int -> Int -> m ()
go (Int
mid forall a. Num a => a -> a -> a
+ Int
1) Int
end
         in Int -> Int -> m ()
go Int
0 (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
theVals forall a. Num a => a -> a -> a
- Int
1)
  a
r <- (k -> (v -> m v) -> m ()) -> m a
f k -> (v -> m v) -> m ()
g
  varr v
rvals <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable varr (PrimState m) v
mvals
  forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
theKeys varr v
rvals, a
r)

adjustManyInline :: forall karr varr m k v a. (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, PrimMonad m, Ord k)
  => ((k -> (v -> m v) -> m ()) -> m a) -- Callback that takes a modify function
  -> Map karr varr k v
  -> m (Map karr varr k v, a)
{-# INLINE adjustManyInline #-}
adjustManyInline :: forall (karr :: * -> *) (varr :: * -> *) (m :: * -> *) k v a.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, PrimMonad m, Ord k) =>
((k -> (v -> m v) -> m ()) -> m a)
-> Map karr varr k v -> m (Map karr varr k v, a)
adjustManyInline (k -> (v -> m v) -> m ()) -> m a
f (Map karr k
theKeys varr v
theVals) = do
  Mutable varr (PrimState m) v
mvals <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Sliced arr b -> m (Mutable arr (PrimState m) b)
I.thaw (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
I.slice varr v
theVals Int
0 (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
theVals))
  let g :: k -> (v -> m v) -> m ()
      g :: k -> (v -> m v) -> m ()
g !k
k v -> m v
updateVal =
        let go :: Int -> Int -> m ()
go !Int
start !Int
end = if Int
end forall a. Ord a => a -> a -> Bool
< Int
start
              then forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
              else
                let !mid :: Int
mid = forall a. Integral a => a -> a -> a
div (Int
end forall a. Num a => a -> a -> a
+ Int
start) Int
2
                    !(# k
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
theKeys Int
mid
                 in case forall a. Ord a => a -> a -> Ordering
P.compare k
k k
v of
                      Ordering
LT -> Int -> Int -> m ()
go Int
start (Int
mid forall a. Num a => a -> a -> a
- Int
1)
                      Ordering
EQ -> do
                        v
r <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> m b
I.read Mutable varr (PrimState m) v
mvals Int
mid
                        v
r' <- v -> m v
updateVal v
r
                        forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr (PrimState m) v
mvals Int
mid v
r'
                      Ordering
GT -> Int -> Int -> m ()
go (Int
mid forall a. Num a => a -> a -> a
+ Int
1) Int
end
         in Int -> Int -> m ()
go Int
0 (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
theVals forall a. Num a => a -> a -> a
- Int
1)
  a
r <- (k -> (v -> m v) -> m ()) -> m a
f k -> (v -> m v) -> m ()
g
  varr v
rvals <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable varr (PrimState m) v
mvals
  forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
theKeys varr v
rvals, a
r)

concat :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v, Semigroup v) => [Map karr varr k v] -> Map karr varr k v
concat :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Semigroup v) =>
[Map karr varr k v] -> Map karr varr k v
concat = forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(v -> v -> v) -> [Map karr varr k v] -> Map karr varr k v
concatWith forall a. Semigroup a => a -> a -> a
(SG.<>)

concatWith :: forall karr varr k v. (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v)
  => (v -> v -> v)
  -> [Map karr varr k v]
  -> Map karr varr k v
concatWith :: forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(v -> v -> v) -> [Map karr varr k v] -> Map karr varr k v
concatWith v -> v -> v
combine = forall m. (m -> Int) -> m -> (m -> m -> m) -> [m] -> m
C.concatSized forall (varr :: * -> *) v (karr :: * -> *) k.
(ContiguousU varr, Element varr v) =>
Map karr varr k v -> Int
size forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, ContiguousU varr) =>
Map karr varr k v
empty (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k) =>
(v -> v -> v)
-> Map karr varr k v -> Map karr varr k v -> Map karr varr k v
appendWith v -> v -> v
combine)

intersectionsWith :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Ord k)
  => (v -> v -> v)
  -> NonEmpty (Map karr varr k v)
  -> Map karr varr k v
intersectionsWith :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k) =>
(v -> v -> v) -> NonEmpty (Map karr varr k v) -> Map karr varr k v
intersectionsWith v -> v -> v
f = forall m. (m -> Int) -> (m -> m -> m) -> NonEmpty m -> m
C.concatSized1 forall (varr :: * -> *) v (karr :: * -> *) k.
(ContiguousU varr, Element varr v) =>
Map karr varr k v -> Int
size (forall k v w x (karr :: * -> *) (varr :: * -> *) (warr :: * -> *)
       (xarr :: * -> *).
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, ContiguousU warr, Element warr w, ContiguousU xarr,
 Element xarr x, Ord k) =>
(v -> w -> x)
-> Map karr varr k v -> Map karr warr k w -> Map karr xarr k x
intersectionWith v -> v -> v
f)

appendRightBiased :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Ord k) => Map karr varr k v -> Map karr varr k v -> Map karr varr k v
appendRightBiased :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k) =>
Map karr varr k v -> Map karr varr k v -> Map karr varr k v
appendRightBiased = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k) =>
(v -> v -> v)
-> Map karr varr k v -> Map karr varr k v -> Map karr varr k v
appendWith forall a b. a -> b -> a
const

appendWithKey :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Ord k)
  => (k -> v -> v -> v) -> Map karr varr k v -> Map karr varr k v -> Map karr varr k v
appendWithKey :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k) =>
(k -> v -> v -> v)
-> Map karr varr k v -> Map karr varr k v -> Map karr varr k v
appendWithKey k -> v -> v -> v
combine (Map karr k
ksA varr v
vsA) (Map karr k
ksB varr v
vsB) =
  case forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(k -> v -> v -> v)
-> karr k -> varr v -> karr k -> varr v -> (karr k, varr v)
unionArrWith k -> v -> v -> v
combine karr k
ksA varr v
vsA karr k
ksB varr v
vsB of
    (karr k
k,varr v
v) -> forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
k varr v
v
  
appendWith :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Ord k)
  => (v -> v -> v) -> Map karr varr k v -> Map karr varr k v -> Map karr varr k v
appendWith :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k) =>
(v -> v -> v)
-> Map karr varr k v -> Map karr varr k v -> Map karr varr k v
appendWith v -> v -> v
combine (Map karr k
ksA varr v
vsA) (Map karr k
ksB varr v
vsB) =
  case forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(k -> v -> v -> v)
-> karr k -> varr v -> karr k -> varr v -> (karr k, varr v)
unionArrWith (\k
_ v
x v
y -> v -> v -> v
combine v
x v
y) karr k
ksA varr v
vsA karr k
ksB varr v
vsB of
    (karr k
k,varr v
v) -> forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
k varr v
v
  
append :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Ord k, Semigroup v)
  => Map karr varr k v -> Map karr varr k v -> Map karr varr k v
append :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k, Semigroup v) =>
Map karr varr k v -> Map karr varr k v -> Map karr varr k v
append (Map karr k
ksA varr v
vsA) (Map karr k
ksB varr v
vsB) =
  case forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(k -> v -> v -> v)
-> karr k -> varr v -> karr k -> varr v -> (karr k, varr v)
unionArrWith (\k
_ v
x v
y -> v
x forall a. Semigroup a => a -> a -> a
SG.<> v
y) karr k
ksA varr v
vsA karr k
ksB varr v
vsB of
    (karr k
k,varr v
v) -> forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
k varr v
v
  
intersectionWith :: forall k v w x karr varr warr xarr.
     (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, ContiguousU warr, Element warr w, ContiguousU xarr, Element xarr x, Ord k)
  => (v -> w -> x)
  -> Map karr varr k v
  -> Map karr warr k w
  -> Map karr xarr k x
intersectionWith :: forall k v w x (karr :: * -> *) (varr :: * -> *) (warr :: * -> *)
       (xarr :: * -> *).
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, ContiguousU warr, Element warr w, ContiguousU xarr,
 Element xarr x, Ord k) =>
(v -> w -> x)
-> Map karr varr k v -> Map karr warr k w -> Map karr xarr k x
intersectionWith v -> w -> x
f s1 :: Map karr varr k v
s1@(Map karr k
karr1 varr v
varr1) s2 :: Map karr warr k w
s2@(Map karr k
karr2 warr w
varr2)
  | Int
sz1 forall a. Eq a => a -> a -> Bool
== Int
0 = forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, ContiguousU varr) =>
Map karr varr k v
empty
  | Int
sz2 forall a. Eq a => a -> a -> Bool
== Int
0 = forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, ContiguousU varr) =>
Map karr varr k v
empty
  | Bool
otherwise = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
      let maxSz :: Int
maxSz = forall a. Ord a => a -> a -> a
min Int
sz1 Int
sz2
      Mutable karr s k
kdst <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
maxSz
      Mutable xarr s x
vdst <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
maxSz
      let go :: Int -> Int -> Int -> ST s Int
go !Int
ix1 !Int
ix2 !Int
dstIx = if Int
ix2 forall a. Ord a => a -> a -> Bool
< Int
sz2 Bool -> Bool -> Bool
&& Int
ix1 forall a. Ord a => a -> a -> Bool
< Int
sz1
            then do
              k
k1 <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM karr k
karr1 Int
ix1
              k
k2 <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM karr k
karr2 Int
ix2
              case forall a. Ord a => a -> a -> Ordering
P.compare k
k1 k
k2 of
                Ordering
EQ -> do
                  v
v1 <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM varr v
varr1 Int
ix1
                  w
v2 <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM warr w
varr2 Int
ix2
                  forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
kdst Int
dstIx k
k1
                  forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable xarr s x
vdst Int
dstIx (v -> w -> x
f v
v1 w
v2)
                  Int -> Int -> Int -> ST s Int
go (Int
ix1 forall a. Num a => a -> a -> a
+ Int
1) (Int
ix2 forall a. Num a => a -> a -> a
+ Int
1) (Int
dstIx forall a. Num a => a -> a -> a
+ Int
1)
                Ordering
LT -> Int -> Int -> Int -> ST s Int
go (Int
ix1 forall a. Num a => a -> a -> a
+ Int
1) Int
ix2 Int
dstIx
                Ordering
GT -> Int -> Int -> Int -> ST s Int
go Int
ix1 (Int
ix2 forall a. Num a => a -> a -> a
+ Int
1) Int
dstIx
            else forall (m :: * -> *) a. Monad m => a -> m a
return Int
dstIx
      Int
dstSz <- Int -> Int -> Int -> ST s Int
go Int
0 Int
0 Int
0
      karr k
kdstFrozen <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr s k
kdst Int
dstSz forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
      xarr x
vdstFrozen <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable xarr s x
vdst Int
dstSz forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
      forall (m :: * -> *) a. Monad m => a -> m a
return (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
kdstFrozen xarr x
vdstFrozen)
  where
    !sz1 :: Int
sz1 = forall (varr :: * -> *) v (karr :: * -> *) k.
(ContiguousU varr, Element varr v) =>
Map karr varr k v -> Int
size Map karr varr k v
s1
    !sz2 :: Int
sz2 = forall (varr :: * -> *) v (karr :: * -> *) k.
(ContiguousU varr, Element varr v) =>
Map karr varr k v -> Int
size Map karr warr k w
s2

unionArrWith :: forall karr varr k v. (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v)
  => (k -> v -> v -> v)
  -> karr k -- keys a
  -> varr v -- values a
  -> karr k -- keys b
  -> varr v -- values b
  -> (karr k, varr v)
unionArrWith :: forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
(k -> v -> v -> v)
-> karr k -> varr v -> karr k -> varr v -> (karr k, varr v)
unionArrWith k -> v -> v -> v
combine karr k
keysA varr v
valsA karr k
keysB varr v
valsB
  | forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
valsA forall a. Ord a => a -> a -> Bool
< Int
1 = (karr k
keysB,varr v
valsB)
  | forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
valsB forall a. Ord a => a -> a -> Bool
< Int
1 = (karr k
keysA,varr v
valsA)
  | Bool
otherwise = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
      let !szA :: Int
szA = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
valsA
          !szB :: Int
szB = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
valsB
      !(Mutable karr s k
keysDst :: Mutable karr s k) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new (Int
szA forall a. Num a => a -> a -> a
+ Int
szB)
      !(Mutable varr s v
valsDst :: Mutable varr s v) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new (Int
szA forall a. Num a => a -> a -> a
+ Int
szB)
      let go :: Int -> Int -> Int -> ST s Int
go !Int
ixA !Int
ixB !Int
ixDst = if Int
ixA forall a. Ord a => a -> a -> Bool
< Int
szA
            then if Int
ixB forall a. Ord a => a -> a -> Bool
< Int
szB
              then do
                let !keyA :: k
keyA = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keysA Int
ixA
                    !keyB :: k
keyB = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keysB Int
ixB
                    !(# v
valA #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
valsA Int
ixA
                    !(# v
valB #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
valsB Int
ixB
                case forall a. Ord a => a -> a -> Ordering
P.compare k
keyA k
keyB of
                  Ordering
EQ -> do
                    forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
keysDst Int
ixDst k
keyA
                    let r :: v
r = k -> v -> v -> v
combine k
keyA v
valA v
valB
                    forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s v
valsDst Int
ixDst v
r
                    Int -> Int -> Int -> ST s Int
go (Int
ixA forall a. Num a => a -> a -> a
+ Int
1) (Int
ixB forall a. Num a => a -> a -> a
+ Int
1) (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
                  Ordering
LT -> do
                    forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
keysDst Int
ixDst k
keyA
                    forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s v
valsDst Int
ixDst v
valA
                    Int -> Int -> Int -> ST s Int
go (Int
ixA forall a. Num a => a -> a -> a
+ Int
1) Int
ixB (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
                  Ordering
GT -> do
                    forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
keysDst Int
ixDst k
keyB
                    forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s v
valsDst Int
ixDst v
valB
                    Int -> Int -> Int -> ST s Int
go Int
ixA (Int
ixB forall a. Num a => a -> a -> a
+ Int
1) (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
              else do
                forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> Sliced arr b -> m ()
I.copy Mutable karr s k
keysDst Int
ixDst (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
I.slice karr k
keysA Int
ixA (Int
szA forall a. Num a => a -> a -> a
- Int
ixA))
                forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> Sliced arr b -> m ()
I.copy Mutable varr s v
valsDst Int
ixDst (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
I.slice varr v
valsA Int
ixA (Int
szA forall a. Num a => a -> a -> a
- Int
ixA))
                forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ (Int
szA forall a. Num a => a -> a -> a
- Int
ixA))
            else if Int
ixB forall a. Ord a => a -> a -> Bool
< Int
szB
              then do
                forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> Sliced arr b -> m ()
I.copy Mutable karr s k
keysDst Int
ixDst (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
I.slice karr k
keysB Int
ixB (Int
szB forall a. Num a => a -> a -> a
- Int
ixB))
                forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> Sliced arr b -> m ()
I.copy Mutable varr s v
valsDst Int
ixDst (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
I.slice varr v
valsB Int
ixB (Int
szB forall a. Num a => a -> a -> a
- Int
ixB))
                forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ (Int
szB forall a. Num a => a -> a -> a
- Int
ixB))
              else forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
      !Int
total <- Int -> Int -> Int -> ST s Int
go Int
0 Int
0 Int
0
      !Mutable karr s k
keysFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr s k
keysDst Int
total
      !Mutable varr s v
valsFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable varr s v
valsDst Int
total
      forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (,) (forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable karr s k
keysFinal) (forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable varr s v
valsFinal)
 
lookup :: forall karr varr k v.
     (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v)
  => k
  -> Map karr varr k v
  -> Maybe v
{-# INLINEABLE lookup #-}
lookup :: forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
k -> Map karr varr k v -> Maybe v
lookup k
a (Map karr k
arr varr v
vals) = Int -> Int -> Maybe v
go Int
0 (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vals forall a. Num a => a -> a -> a
- Int
1) where
  go :: Int -> Int -> Maybe v
  go :: Int -> Int -> Maybe v
go !Int
start !Int
end = if Int
end forall a. Ord a => a -> a -> Bool
< Int
start
    then forall a. Maybe a
Nothing
    else
      let !mid :: Int
mid = forall a. Integral a => a -> a -> a
div (Int
end forall a. Num a => a -> a -> a
+ Int
start) Int
2
          !(# k
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
arr Int
mid
       in case forall a. Ord a => a -> a -> Ordering
P.compare k
a k
v of
            Ordering
LT -> Int -> Int -> Maybe v
go Int
start (Int
mid forall a. Num a => a -> a -> a
- Int
1)
            Ordering
EQ -> case forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vals Int
mid of
              (# v
r #) -> forall a. a -> Maybe a
Just v
r
            Ordering
GT -> Int -> Int -> Maybe v
go (Int
mid forall a. Num a => a -> a -> a
+ Int
1) Int
end

size :: (ContiguousU varr, Element varr v) => Map karr varr k v -> Int
size :: forall (varr :: * -> *) v (karr :: * -> *) k.
(ContiguousU varr, Element varr v) =>
Map karr varr k v -> Int
size (Map karr k
_ varr v
arr) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
arr

-- This may have less constraints than size
sizeKeys :: (ContiguousU karr, Element karr k) => Map karr varr k v -> Int
sizeKeys :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k) =>
Map karr varr k v -> Int
sizeKeys (Map karr k
arr varr v
_) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size karr k
arr

-- | Sort and deduplicate the key array, preserving the last value associated
-- with each key. The argument arrays may not be reused after being passed
-- to this function. This function is only unsafe because of the requirement
-- that the arguments not be reused. If the arrays do not match in size, the
-- larger one will be truncated to the length of the shorter one.
unsafeFreezeZip :: (ContiguousU karr, Element karr k, Ord k, ContiguousU varr, Element varr v)
  => Mutable karr s k
  -> Mutable varr s v
  -> ST s (Map karr varr k v)
unsafeFreezeZip :: forall (karr :: * -> *) k (varr :: * -> *) v s.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Mutable karr s k -> Mutable varr s v -> ST s (Map karr varr k v)
unsafeFreezeZip Mutable karr s k
keys0 Mutable varr s v
vals0 = do
  (Mutable karr s k
keys1,Mutable varr s v
vals1) <- forall (karr :: * -> *) k (varr :: * -> *) v s.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Mutable karr s k
-> Mutable varr s v -> ST s (Mutable karr s k, Mutable varr s v)
sortUniqueTaggedMutable Mutable karr s k
keys0 Mutable varr s v
vals0
  karr k
keys2 <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable karr s k
keys1
  varr v
vals2 <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze Mutable varr s v
vals1
  forall (m :: * -> *) a. Monad m => a -> m a
return (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
keys2 varr v
vals2)
{-# INLINEABLE unsafeFreezeZip #-}

-- | There are two preconditions:
--
-- * The array of keys is sorted
-- * The array of keys and the array of values have the same length.
--
-- If either of these conditions is not met, this function will introduce
-- undefined behavior or segfaults.
unsafeZipPresorted :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v)
  => karr k -- array of keys, must already be sorted
  -> varr v -- array of values
  -> Map karr varr k v
unsafeZipPresorted :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
karr k -> varr v -> Map karr varr k v
unsafeZipPresorted = forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map

foldlWithKeyM' :: forall karr varr k v m b. (Monad m, ContiguousU karr, Element karr k, ContiguousU varr, Element varr v)
  => (b -> k -> v -> m b)
  -> b
  -> Map karr varr k v
  -> m b
foldlWithKeyM' :: forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(b -> k -> v -> m b) -> b -> Map karr varr k v -> m b
foldlWithKeyM' b -> k -> v -> m b
f b
b0 (Map karr k
ks varr v
vs) = Int -> b -> m b
go Int
0 b
b0
  where
  !len :: Int
len = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs
  go :: Int -> b -> m b
  go :: Int -> b -> m b
go !Int
ix !b
acc = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
len
    then
      let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
ks Int
ix
          !(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vs Int
ix
       in b -> k -> v -> m b
f b
acc k
k v
v forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Int -> b -> m b
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1)
    else forall (m :: * -> *) a. Monad m => a -> m a
return b
acc
{-# INLINEABLE foldlWithKeyM' #-}

foldrWithKeyM' :: forall karr varr k v m b. (Monad m, ContiguousU karr, Element karr k, ContiguousU varr, Element varr v)
  => (k -> v -> b -> m b)
  -> b
  -> Map karr varr k v
  -> m b
foldrWithKeyM' :: forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> b -> m b) -> b -> Map karr varr k v -> m b
foldrWithKeyM' k -> v -> b -> m b
f b
b0 (Map karr k
ks varr v
vs) = Int -> b -> m b
go (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs forall a. Num a => a -> a -> a
- Int
1) b
b0
  where
  go :: Int -> b -> m b
  go :: Int -> b -> m b
go !Int
ix !b
acc = if Int
ix forall a. Ord a => a -> a -> Bool
>= Int
0
    then
      let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
ks Int
ix
          !(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vs Int
ix
       in k -> v -> b -> m b
f k
k v
v b
acc forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Int -> b -> m b
go (Int
ix forall a. Num a => a -> a -> a
- Int
1)
    else forall (m :: * -> *) a. Monad m => a -> m a
return b
acc
{-# INLINEABLE foldrWithKeyM' #-}

foldlMapWithKeyM' :: forall karr varr k v m b. (Monad m, ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Monoid b)
  => (k -> v -> m b)
  -> Map karr varr k v
  -> m b
foldlMapWithKeyM' :: forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid b) =>
(k -> v -> m b) -> Map karr varr k v -> m b
foldlMapWithKeyM' k -> v -> m b
f (Map karr k
ks varr v
vs) = Int -> b -> m b
go Int
0 forall a. Monoid a => a
mempty
  where
  !len :: Int
len = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs
  go :: Int -> b -> m b
  go :: Int -> b -> m b
go !Int
ix !b
accl = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
len
    then
      let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
ks Int
ix
          !(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vs Int
ix
       in do
         b
accr <- k -> v -> m b
f k
k v
v
         Int -> b -> m b
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1) (forall a. Monoid a => a -> a -> a
mappend b
accl b
accr)
    else forall (m :: * -> *) a. Monad m => a -> m a
return b
accl
{-# INLINEABLE foldlMapWithKeyM' #-}

traverse :: (Applicative m, ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Element varr w)
  => (v -> m w)
  -> Map karr varr k v
  -> m (Map karr varr k w)
{-# INLINEABLE traverse #-}
traverse :: forall (m :: * -> *) (karr :: * -> *) k (varr :: * -> *) v w.
(Applicative m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(v -> m w) -> Map karr varr k v -> m (Map karr varr k w)
traverse v -> m w
f (Map karr k
theKeys varr v
theVals) =
  forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
theKeys) (forall (arr1 :: * -> *) (arr2 :: * -> *) a b (f :: * -> *).
(Contiguous arr1, Contiguous arr2, Element arr1 a, Element arr2 b,
 Applicative f) =>
(a -> f b) -> arr1 a -> f (arr2 b)
I.traverse v -> m w
f varr v
theVals)

traverseWithKey :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Element varr v', Applicative f)
  => (k -> v -> f v')
  -> Map karr varr k v
  -> f (Map karr varr k v')
{-# INLINEABLE traverseWithKey #-}
traverseWithKey :: forall (karr :: * -> *) k (varr :: * -> *) v v' (f :: * -> *).
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr v', Applicative f) =>
(k -> v -> f v') -> Map karr varr k v -> f (Map karr varr k v')
traverseWithKey k -> v -> f v'
f (Map karr k
theKeys varr v
theVals) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
theKeys)
  forall a b. (a -> b) -> a -> b
$ forall (arr1 :: * -> *) (arr2 :: * -> *) a b (f :: * -> *).
(Contiguous arr1, Contiguous arr2, Element arr1 a, Element arr2 b,
 Applicative f) =>
(Int -> a -> f b) -> arr1 a -> f (arr2 b)
I.itraverse (\Int
i v
v -> k -> v -> f v'
f (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
theKeys Int
i) v
v) varr v
theVals

traverseWithKey_ :: forall karr varr k v m b. (Applicative m, ContiguousU karr, Element karr k, ContiguousU varr, Element varr v)
  => (k -> v -> m b)
  -> Map karr varr k v
  -> m ()
traverseWithKey_ :: forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Applicative m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> m b) -> Map karr varr k v -> m ()
traverseWithKey_ k -> v -> m b
f (Map karr k
ks varr v
vs) = Int -> m ()
go Int
0
  where
  !len :: Int
len = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs
  go :: Int -> m ()
  go :: Int -> m ()
go !Int
ix = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
len
    then
      let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
ks Int
ix
          !(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vs Int
ix
       in k -> v -> m b
f k
k v
v forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> Int -> m ()
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1)
    else forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
{-# INLINEABLE traverseWithKey_ #-}

foldrMapWithKeyM' :: forall karr varr k v m b. (Monad m, ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Monoid b)
  => (k -> v -> m b)
  -> Map karr varr k v
  -> m b
foldrMapWithKeyM' :: forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid b) =>
(k -> v -> m b) -> Map karr varr k v -> m b
foldrMapWithKeyM' k -> v -> m b
f (Map karr k
ks varr v
vs) = Int -> b -> m b
go (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs forall a. Num a => a -> a -> a
- Int
1) forall a. Monoid a => a
mempty
  where
  go :: Int -> b -> m b
  go :: Int -> b -> m b
go !Int
ix !b
accr = if Int
ix forall a. Ord a => a -> a -> Bool
>= Int
0
    then
      let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
ks Int
ix
          !(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vs Int
ix
       in do
         b
accl <- k -> v -> m b
f k
k v
v
         Int -> b -> m b
go (Int
ix forall a. Num a => a -> a -> a
- Int
1) (forall a. Monoid a => a -> a -> a
mappend b
accl b
accr)
    else forall (m :: * -> *) a. Monad m => a -> m a
return b
accr
{-# INLINEABLE foldrMapWithKeyM' #-}

foldMapWithKey' :: forall karr varr k v m. (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Monoid m)
  => (k -> v -> m)
  -> Map karr varr k v
  -> m
foldMapWithKey' :: forall (karr :: * -> *) (varr :: * -> *) k v m.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid m) =>
(k -> v -> m) -> Map karr varr k v -> m
foldMapWithKey' k -> v -> m
f (Map karr k
ks varr v
vs) = Int -> m -> m
go Int
0 forall a. Monoid a => a
mempty
  where
  !len :: Int
len = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs
  go :: Int -> m -> m
  go :: Int -> m -> m
go !Int
ix !m
accl = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
len
    then 
      let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
ks Int
ix
          !(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vs Int
ix
       in Int -> m -> m
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1) (forall a. Monoid a => a -> a -> a
mappend m
accl (k -> v -> m
f k
k v
v))
    else m
accl
{-# INLINEABLE foldMapWithKey' #-}

foldlWithKey' :: forall karr varr k v b. (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v)
  => (b -> k -> v -> b) 
  -> b
  -> Map karr varr k v
  -> b
foldlWithKey' :: forall (karr :: * -> *) (varr :: * -> *) k v b.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(b -> k -> v -> b) -> b -> Map karr varr k v -> b
foldlWithKey' b -> k -> v -> b
f b
b0 (Map karr k
ks varr v
vs) = Int -> b -> b
go Int
0 b
b0
  where
  !len :: Int
len = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs
  go :: Int -> b -> b
  go :: Int -> b -> b
go !Int
ix !b
acc = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
len
    then 
      let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
ks Int
ix
          !(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vs Int
ix
       in Int -> b -> b
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1) (b -> k -> v -> b
f b
acc k
k v
v)
    else b
acc
{-# INLINEABLE foldlWithKey' #-}

foldrWithKey' :: forall karr varr k v b. (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v)
  => (k -> v -> b -> b)
  -> b
  -> Map karr varr k v
  -> b
foldrWithKey' :: forall (karr :: * -> *) (varr :: * -> *) k v b.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> b -> b) -> b -> Map karr varr k v -> b
foldrWithKey' k -> v -> b -> b
f b
b0 (Map karr k
ks varr v
vs) = Int -> b -> b
go (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs forall a. Num a => a -> a -> a
- Int
1) b
b0
  where
  go :: Int -> b -> b
  go :: Int -> b -> b
go !Int
ix !b
acc = if Int
ix forall a. Ord a => a -> a -> Bool
>= Int
0
    then
      let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
ks Int
ix
          !(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vs Int
ix
       in Int -> b -> b
go (Int
ix forall a. Num a => a -> a -> a
- Int
1) (k -> v -> b -> b
f k
k v
v b
acc)
    else b
acc
{-# INLINEABLE foldrWithKey' #-}

-- The algorithm used here is good when the subset is small, but
-- when the subset is large, it is worse that just walking the map.
restrict :: forall karr varr k v. (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Ord k)
  => Map karr varr k v
  -> Set karr k
  -> Map karr varr k v
restrict :: forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k) =>
Map karr varr k v -> Set karr k -> Map karr varr k v
restrict m :: Map karr varr k v
m@(Map karr k
ks varr v
vs) (Set karr k
rs)
  | forall (arr :: * -> *) a. ContiguousU arr => arr a -> arr a -> Bool
I.same karr k
ks karr k
rs = Map karr varr k v
m
  | Bool
otherwise = Int -> Map karr varr k v
stage1 Int
0
  where
  szMap :: Int
szMap = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vs
  szSet :: Int
szSet = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size karr k
rs
  szMin :: Int
szMin = forall a. Ord a => a -> a -> a
min Int
szMap Int
szSet
  -- Locate the first difference between the two. This stage is useful
  -- because, in the case that the subset perfectly matches the keys,
  -- we do not need to do any copying.
  stage1 :: Int -> Map karr varr k v
  stage1 :: Int -> Map karr varr k v
stage1 !Int
ix = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
szMin
    then
      let !(# k
k #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
ks Int
ix
          !(# k
r #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# karr k
rs Int
ix
       in if k
k forall a. Eq a => a -> a -> Bool
== k
r
            then Int -> Map karr varr k v
stage1 (Int
ix forall a. Num a => a -> a -> a
+ Int
1)
            else Int -> Map karr varr k v
stage2 Int
ix
    else if Int
szMin forall a. Eq a => a -> a -> Bool
== Int
szMap
      then Map karr varr k v
m
      else forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
rs varr v
vs
  -- In stage two, we walk the map and the set with possibly differing
  -- indices, writing each matching key (along with its value) into
  -- the result map.
  stage2 :: Int -> Map karr varr k v
  stage2 :: Int -> Map karr varr k v
stage2 !Int
ix = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
    Mutable karr s k
ksMut <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
szMin
    Mutable varr s v
vsMut <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
I.new Int
szMin
    forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> Sliced arr b -> m ()
I.copy Mutable karr s k
ksMut Int
0 (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
I.slice karr k
ks Int
0 Int
ix)
    forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> Sliced arr b -> m ()
I.copy Mutable varr s v
vsMut Int
0 (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
I.slice varr v
vs Int
0 Int
ix)
    let -- TODO: Turn this into a galloping search. It would
        -- probably be worth trying this out on
        -- Data.Set.Internal.intersection first.
        go :: Int -> Int -> Int -> ST s Int
go !Int
ixRes !Int
ixm !Int
ixs = if Int
ixm forall a. Ord a => a -> a -> Bool
< Int
szMin Bool -> Bool -> Bool
&& Int
ixs forall a. Ord a => a -> a -> Bool
< Int
szMin
          then do
            k
k <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM karr k
ks Int
ixm
            k
r <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM karr k
rs Int
ixs
            case forall a. Ord a => a -> a -> Ordering
P.compare k
k k
r of
              Ordering
EQ -> do
                forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable karr s k
ksMut Int
ixRes k
k
                forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
I.write Mutable varr s v
vsMut Int
ixRes forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
I.indexM varr v
vs Int
ixm
                Int -> Int -> Int -> ST s Int
go (Int
ixRes forall a. Num a => a -> a -> a
+ Int
1) (Int
ixm forall a. Num a => a -> a -> a
+ Int
1) (Int
ixs forall a. Num a => a -> a -> a
+ Int
1)
              Ordering
LT -> Int -> Int -> Int -> ST s Int
go Int
ixRes (Int
ixm forall a. Num a => a -> a -> a
+ Int
1) Int
ixs
              Ordering
GT -> Int -> Int -> Int -> ST s Int
go Int
ixRes Int
ixm (Int
ixs forall a. Num a => a -> a -> a
+ Int
1)
          else forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixRes
    Int
total <- Int -> Int -> Int -> ST s Int
go Int
ix Int
ix Int
ix
    karr k
ks' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable karr s k
ksMut Int
total forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
    varr v
vs' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
I.resize Mutable varr s v
vsMut Int
total forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
I.unsafeFreeze
    forall (m :: * -> *) a. Monad m => a -> m a
return (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
ks' varr v
vs')
{-# INLINEABLE restrict #-}

fromSet :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v)
  => (k -> v)
  -> Set karr k
  -> Map karr varr k v
fromSet :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v) -> Set karr k -> Map karr varr k v
fromSet k -> v
f (Set karr k
arr) = forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
arr (forall (arr1 :: * -> *) b (arr2 :: * -> *) c.
(Contiguous arr1, Element arr1 b, Contiguous arr2,
 Element arr2 c) =>
(b -> c) -> arr1 b -> arr2 c
I.map k -> v
f karr k
arr)
{-# INLINE fromSet #-}

fromSetP :: (PrimMonad m, ContiguousU karr, Element karr k, ContiguousU varr, Element varr v)
  => (k -> m v)
  -> Set karr k
  -> m (Map karr varr k v)
fromSetP :: forall (m :: * -> *) (karr :: * -> *) k (varr :: * -> *) v.
(PrimMonad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> m v) -> Set karr k -> m (Map karr varr k v)
fromSetP k -> m v
f (Set karr k
arr) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (karr :: * -> *) (varr :: * -> *) k v.
karr k -> varr v -> Map karr varr k v
Map karr k
arr) (forall (m :: * -> *) (arr1 :: * -> *) a (arr2 :: * -> *) b.
(PrimMonad m, Contiguous arr1, Element arr1 a, Contiguous arr2,
 Element arr2 b) =>
(a -> m b) -> arr1 a -> m (arr2 b)
I.traverseP k -> m v
f karr k
arr)
{-# INLINE fromSetP #-}

keys :: Map karr varr k v -> Set karr k
keys :: forall (karr :: * -> *) (varr :: * -> *) k v.
Map karr varr k v -> Set karr k
keys (Map karr k
k varr v
_) = forall (arr :: * -> *) a. arr a -> Set arr a
Set karr k
k

elems :: Map karr varr k v -> varr v
elems :: forall (karr :: * -> *) (varr :: * -> *) k v.
Map karr varr k v -> varr v
elems (Map karr k
_ varr v
v) = varr v
v

rnf :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, NFData k, NFData v)
  => Map karr varr k v
  -> ()
rnf :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, NFData k, NFData v) =>
Map karr varr k v -> ()
rnf (Map karr k
k varr v
v) = seq :: forall a b. a -> b -> b
seq (forall (arr :: * -> *) a.
(Contiguous arr, NFData a, Element arr a) =>
arr a -> ()
I.rnf karr k
k) (seq :: forall a b. a -> b -> b
seq (forall (arr :: * -> *) a.
(Contiguous arr, NFData a, Element arr a) =>
arr a -> ()
I.rnf varr v
v) ())