{-# 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
, foldrWithKey
, foldlWithKey'
, foldrWithKey'
, foldMapWithKey
, foldMapWithKey'
, foldlWithKeyM'
, foldrWithKeyM'
, foldlMapWithKeyM'
, foldrMapWithKeyM'
, traverse
, traverseWithKey
, traverseWithKey_
, append
, appendWith
, appendWithKey
, appendRightBiased
, intersectionWith
, intersectionsWith
, adjustMany
, adjustManyInline
, lookup
, showsPrec
, equals
, compare
, toList
, concat
, size
, sizeKeys
, keys
, elems
, restrict
, rnf
, fromListN
, fromList
, fromListAppend
, fromListAppendN
, fromSet
, fromSetP
, 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
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
-> [(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
-> k
-> v
-> [(k,v)]
-> ([(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)
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)
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)
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)
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)
-> 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)
-> 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
-> varr v
-> karr k
-> varr v
-> (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
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
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 #-}
unsafeZipPresorted :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v)
=> karr k
-> varr v
-> 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' #-}
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
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
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
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) ())