{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE MagicHash #-}
{-# OPTIONS_GHC -O2 -Wall #-}
module Data.Diet.Map.Strict.Internal
( Map
, empty
, singleton
, map
, append
, lookup
, concat
, equals
, showsPrec
, liftShowsPrec2
, fromListN
, fromList
, fromListAppend
, fromListAppendN
, toList
) where
import Prelude hiding (lookup,showsPrec,concat,map)
import Control.Applicative (liftA2)
import Control.Monad.ST (ST,runST)
import Data.Semigroup (Semigroup)
import Data.Foldable (foldl')
import Text.Show (showListWith)
import Data.Primitive.Contiguous (ContiguousU,Element,Mutable)
import qualified Data.List as L
import qualified Data.Semigroup as SG
import qualified Prelude as P
import qualified Data.Primitive.Contiguous as I
import qualified Data.Concatenation as C
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
map :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v, Element varr w) => (v -> w) -> Map karr varr k v -> Map karr varr k w
map :: forall (karr :: * -> *) k (varr :: * -> *) v w.
(ContiguousU karr, Element karr k, ContiguousU varr,
Element varr v, Element varr w) =>
(v -> w) -> Map karr varr k v -> Map karr varr 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)
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
fromListN :: (ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr, Element varr v, Eq v) => Int -> [(k,k,v)] -> Map karr varr k v
fromListN :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
Int -> [(k, k, v)] -> Map karr varr k v
fromListN = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
(v -> v -> v) -> Int -> [(k, k, v)] -> Map karr varr k v
fromListWithN (\v
_ v
a -> v
a)
fromList :: (ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr, Element varr v, Eq v) => [(k,k,v)] -> Map karr varr k v
fromList :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
[(k, k, v)] -> Map karr varr k v
fromList = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
Int -> [(k, k, v)] -> Map karr varr k v
fromListN Int
1
fromListAppendN :: (ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr, Element varr v, Semigroup v, Eq v) => Int -> [(k,k,v)] -> Map karr varr k v
fromListAppendN :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Semigroup v, Eq v) =>
Int -> [(k, k, v)] -> Map karr varr k v
fromListAppendN = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
(v -> v -> v) -> Int -> [(k, k, v)] -> Map karr varr k v
fromListWithN forall a. Semigroup a => a -> a -> a
(SG.<>)
fromListAppend :: (ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr, Element varr v, Semigroup v, Eq v) => [(k,k,v)] -> Map karr varr k v
fromListAppend :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Semigroup v, Eq v) =>
[(k, k, v)] -> Map karr varr k v
fromListAppend = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Semigroup v, Eq v) =>
Int -> [(k, k, v)] -> Map karr varr k v
fromListAppendN Int
1
fromListWithN :: (ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr, Element varr v, Eq v) => (v -> v -> v) -> Int -> [(k,k,v)] -> Map karr varr k v
fromListWithN :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
(v -> v -> v) -> Int -> [(k, k, v)] -> Map karr varr k v
fromListWithN v -> v -> v
combine Int
_ [(k, k, v)]
xs =
forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
(v -> v -> v) -> [Map karr varr k v] -> Map karr varr k v
concatWith v -> v -> v
combine (forall a b. (a -> b) -> [a] -> [b]
P.map (\(k
lo,k
hi,v
v) -> forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
Element varr v) =>
k -> k -> v -> Map karr varr k v
singleton k
lo k
hi v
v) [(k, k, v)]
xs)
concat :: (ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr, Element varr v, Semigroup v, Eq v) => [Map karr varr k v] -> Map karr varr k v
concat :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Semigroup v, Eq v) =>
[Map karr varr k v] -> Map karr varr k v
concat = forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
(v -> v -> v) -> [Map karr varr k v] -> Map karr varr k v
concatWith forall a. Semigroup a => a -> a -> a
(SG.<>)
singleton :: forall karr varr k v. (ContiguousU karr, Element karr k,Ord k,ContiguousU varr, Element varr v) => k -> k -> v -> Map karr varr k v
singleton :: forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
Element varr v) =>
k -> k -> v -> Map karr varr k v
singleton !k
lo !k
hi !v
v = if k
lo forall a. Ord a => a -> a -> Bool
<= k
hi
then 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 :: 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
2
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
lo
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
1 k
hi
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 :: 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
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
)
else forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, ContiguousU varr) =>
Map karr varr k v
empty
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 :: 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
keys 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 if Int
end forall a. Eq a => a -> a -> Bool
== Int
start
then
let !valLo :: k
valLo = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keys (Int
2 forall a. Num a => a -> a -> a
* Int
start)
!valHi :: k
valHi = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keys (Int
2 forall a. Num a => a -> a -> a
* Int
start forall a. Num a => a -> a -> a
+ Int
1)
in if k
a forall a. Ord a => a -> a -> Bool
>= k
valLo Bool -> Bool -> Bool
&& k
a forall a. Ord a => a -> a -> Bool
<= k
valHi
then case forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vals Int
start of
(# v
v #) -> forall a. a -> Maybe a
Just v
v
else forall a. Maybe a
Nothing
else 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 forall a. Num a => a -> a -> a
+ Int
1) Int
2
!valLo :: k
valLo = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keys (Int
2 forall a. Num a => a -> a -> a
* Int
mid)
in case forall a. Ord a => a -> a -> Ordering
P.compare k
a k
valLo 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
v #) -> forall a. a -> Maybe a
Just v
v
Ordering
GT -> Int -> Int -> Maybe v
go Int
mid Int
end
{-# INLINEABLE lookup #-}
append :: (ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr, Element varr v, Semigroup v, Eq 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, Ord k, Enum k, ContiguousU varr,
Element varr v, Semigroup v, Eq 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, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
(v -> v -> v)
-> karr k -> varr v -> karr k -> varr v -> (karr k, varr v)
unionArrWith forall a. Semigroup a => a -> a -> a
(SG.<>) 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, Ord k, Enum k, ContiguousU varr, Element varr v, Eq v) => (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, Ord k, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
(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, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
(v -> v -> v)
-> karr k -> varr v -> karr k -> varr v -> (karr k, varr v)
unionArrWith 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
unionArrWith :: forall karr varr k v. (ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr, Element varr v, Eq v)
=> (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, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
(v -> v -> v)
-> karr k -> varr v -> karr k -> varr v -> (karr k, varr v)
unionArrWith 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 s. ST s (karr k, varr v)
action
where
action :: forall s. ST s (karr k, varr v)
action :: forall s. ST s (karr k, varr v)
action = 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 (forall a. Ord a => a -> a -> a
max Int
szA Int
szB forall a. Num a => a -> a -> a
* Int
8)
!(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 (forall a. Ord a => a -> a -> a
max Int
szA Int
szB forall a. Num a => a -> a -> a
* Int
4)
let writeKeyRange :: Int -> k -> k -> ST s ()
writeKeyRange :: Int -> k -> k -> ST s ()
writeKeyRange !Int
ix !k
lo !k
hi = 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
2 forall a. Num a => a -> a -> a
* Int
ix) k
lo
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
2 forall a. Num a => a -> a -> a
* Int
ix forall a. Num a => a -> a -> a
+ Int
1) k
hi
writeDstHiKey :: Int -> k -> ST s ()
writeDstHiKey :: Int -> k -> ST s ()
writeDstHiKey !Int
ix !k
hi = 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
2 forall a. Num a => a -> a -> a
* Int
ix forall a. Num a => a -> a -> a
+ Int
1) k
hi
writeDstValue :: Int -> v -> ST s ()
writeDstValue :: Int -> v -> ST s ()
writeDstValue !Int
ix !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
valsDst Int
ix v
v
readDstHiKey :: Int -> ST s k
readDstHiKey :: Int -> ST s k
readDstHiKey !Int
ix = forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> m b
I.read Mutable karr s k
keysDst (Int
2 forall a. Num a => a -> a -> a
* Int
ix forall a. Num a => a -> a -> a
+ Int
1)
readDstVal :: Int -> ST s v
readDstVal :: Int -> ST s v
readDstVal !Int
ix = 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
valsDst Int
ix
indexLoKeyA :: Int -> k
indexLoKeyA :: Int -> k
indexLoKeyA !Int
ix = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keysA (Int
ix forall a. Num a => a -> a -> a
* Int
2)
indexLoKeyB :: Int -> k
indexLoKeyB :: Int -> k
indexLoKeyB !Int
ix = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keysB (Int
ix forall a. Num a => a -> a -> a
* Int
2)
indexHiKeyA :: Int -> k
indexHiKeyA :: Int -> k
indexHiKeyA !Int
ix = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keysA (Int
ix forall a. Num a => a -> a -> a
* Int
2 forall a. Num a => a -> a -> a
+ Int
1)
indexHiKeyB :: Int -> k
indexHiKeyB :: Int -> k
indexHiKeyB !Int
ix = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keysB (Int
ix forall a. Num a => a -> a -> a
* Int
2 forall a. Num a => a -> a -> a
+ Int
1)
indexValueA :: Int -> v
indexValueA :: Int -> v
indexValueA !Int
ix = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index varr v
valsA Int
ix
indexValueB :: Int -> v
indexValueB :: Int -> v
indexValueB !Int
ix = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index varr v
valsB Int
ix
let go :: Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go :: Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go !Int
ixA !k
loA !k
hiA !v
valA !Int
ixB !k
loB !k
hiB !v
valB !Int
ixDst = do
k
prevHi <- Int -> ST s k
readDstHiKey (Int
ixDst forall a. Num a => a -> a -> a
- Int
1)
v
prevVal <- Int -> ST s v
readDstVal (Int
ixDst forall a. Num a => a -> a -> a
- Int
1)
case forall a. Ord a => a -> a -> Ordering
compare k
loA k
loB of
Ordering
LT -> do
let (k
upper,Int
ixA') = if k
hiA forall a. Ord a => a -> a -> Bool
< k
loB
then (k
hiA,Int
ixA forall a. Num a => a -> a -> a
+ Int
1)
else (forall a. Enum a => a -> a
pred k
loB,Int
ixA)
Int
ixDst' <- if forall a. Enum a => a -> a
pred k
loA forall a. Eq a => a -> a -> Bool
== k
prevHi Bool -> Bool -> Bool
&& v
valA forall a. Eq a => a -> a -> Bool
== v
prevVal
then do
Int -> k -> ST s ()
writeDstHiKey (Int
ixDst forall a. Num a => a -> a -> a
- Int
1) k
upper
forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
else do
Int -> k -> k -> ST s ()
writeKeyRange Int
ixDst k
loA k
upper
Int -> v -> ST s ()
writeDstValue Int
ixDst v
valA
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
if Int
ixA' forall a. Ord a => a -> a -> Bool
< Int
szA
then do
let (k
loA',k
hiA') = if k
hiA forall a. Ord a => a -> a -> Bool
< k
loB
then (Int -> k
indexLoKeyA Int
ixA',Int -> k
indexHiKeyA Int
ixA')
else (k
loB,k
hiA)
Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
ixA' k
loA' k
hiA' (Int -> v
indexValueA Int
ixA') Int
ixB k
loB k
hiB v
valB Int
ixDst'
else Int -> k -> k -> v -> Int -> ST s Int
copyB Int
ixB k
loB k
hiB v
valB Int
ixDst'
Ordering
GT -> do
let (k
upper,Int
ixB') = if k
hiB forall a. Ord a => a -> a -> Bool
< k
loA
then (k
hiB,Int
ixB forall a. Num a => a -> a -> a
+ Int
1)
else (forall a. Enum a => a -> a
pred k
loA,Int
ixB)
Int
ixDst' <- if forall a. Enum a => a -> a
pred k
loB forall a. Eq a => a -> a -> Bool
== k
prevHi Bool -> Bool -> Bool
&& v
valB forall a. Eq a => a -> a -> Bool
== v
prevVal
then do
Int -> k -> ST s ()
writeDstHiKey (Int
ixDst forall a. Num a => a -> a -> a
- Int
1) k
upper
forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
else do
Int -> k -> k -> ST s ()
writeKeyRange Int
ixDst k
loB k
upper
Int -> v -> ST s ()
writeDstValue Int
ixDst v
valB
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
if Int
ixB' forall a. Ord a => a -> a -> Bool
< Int
szB
then do
let (k
loB',k
hiB') = if k
hiB forall a. Ord a => a -> a -> Bool
< k
loA
then (Int -> k
indexLoKeyB Int
ixB',Int -> k
indexHiKeyB Int
ixB')
else (k
loA,k
hiB)
Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
ixA k
loA k
hiA v
valA Int
ixB' k
loB' k
hiB' (Int -> v
indexValueB Int
ixB') Int
ixDst'
else Int -> k -> k -> v -> Int -> ST s Int
copyA Int
ixA k
loA k
hiA v
valA Int
ixDst'
Ordering
EQ -> do
let valCombination :: v
valCombination = v -> v -> v
combine v
valA v
valB
case forall a. Ord a => a -> a -> Ordering
compare k
hiA k
hiB of
Ordering
LT -> do
Int
ixDst' <- if forall a. Enum a => a -> a
pred k
loA forall a. Eq a => a -> a -> Bool
== k
prevHi Bool -> Bool -> Bool
&& v
valCombination forall a. Eq a => a -> a -> Bool
== v
prevVal
then do
Int -> k -> ST s ()
writeDstHiKey (Int
ixDst forall a. Num a => a -> a -> a
- Int
1) k
hiA
forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
else do
Int -> k -> k -> ST s ()
writeKeyRange Int
ixDst k
loA k
hiA
Int -> v -> ST s ()
writeDstValue Int
ixDst v
valCombination
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
let ixA' :: Int
ixA' = Int
ixA forall a. Num a => a -> a -> a
+ Int
1
loB' :: k
loB' = forall a. Enum a => a -> a
succ k
hiA
if Int
ixA' forall a. Ord a => a -> a -> Bool
< Int
szA
then Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
ixA' (Int -> k
indexLoKeyA Int
ixA') (Int -> k
indexHiKeyA Int
ixA') (Int -> v
indexValueA Int
ixA') Int
ixB k
loB' k
hiB v
valB Int
ixDst'
else Int -> k -> k -> v -> Int -> ST s Int
copyB Int
ixB k
loB' k
hiB v
valB Int
ixDst'
Ordering
GT -> do
Int
ixDst' <- if forall a. Enum a => a -> a
pred k
loB forall a. Eq a => a -> a -> Bool
== k
prevHi Bool -> Bool -> Bool
&& v
valCombination forall a. Eq a => a -> a -> Bool
== v
prevVal
then do
Int -> k -> ST s ()
writeDstHiKey (Int
ixDst forall a. Num a => a -> a -> a
- Int
1) k
hiB
forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
else do
Int -> k -> k -> ST s ()
writeKeyRange Int
ixDst k
loB k
hiB
Int -> v -> ST s ()
writeDstValue Int
ixDst v
valCombination
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
let ixB' :: Int
ixB' = Int
ixB forall a. Num a => a -> a -> a
+ Int
1
loA' :: k
loA' = forall a. Enum a => a -> a
succ k
hiB
if Int
ixB' forall a. Ord a => a -> a -> Bool
< Int
szB
then Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
ixA k
loA' k
hiA v
valA Int
ixB' (Int -> k
indexLoKeyB Int
ixB') (Int -> k
indexHiKeyB Int
ixB') (Int -> v
indexValueB Int
ixB') Int
ixDst'
else Int -> k -> k -> v -> Int -> ST s Int
copyA Int
ixA k
loA' k
hiA v
valA Int
ixDst'
Ordering
EQ -> do
Int
ixDst' <- if forall a. Enum a => a -> a
pred k
loB forall a. Eq a => a -> a -> Bool
== k
prevHi Bool -> Bool -> Bool
&& v
valCombination forall a. Eq a => a -> a -> Bool
== v
prevVal
then do
Int -> k -> ST s ()
writeDstHiKey (Int
ixDst forall a. Num a => a -> a -> a
- Int
1) k
hiB
forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
else do
Int -> k -> k -> ST s ()
writeKeyRange Int
ixDst k
loB k
hiB
Int -> v -> ST s ()
writeDstValue Int
ixDst v
valCombination
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
let ixA' :: Int
ixA' = Int
ixA forall a. Num a => a -> a -> a
+ Int
1
ixB' :: Int
ixB' = Int
ixB forall a. Num a => a -> a -> a
+ Int
1
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 Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
ixA' (Int -> k
indexLoKeyA Int
ixA') (Int -> k
indexHiKeyA Int
ixA') (Int -> v
indexValueA Int
ixA') Int
ixB' (Int -> k
indexLoKeyB Int
ixB') (Int -> k
indexHiKeyB Int
ixB') (Int -> v
indexValueB Int
ixB') Int
ixDst'
else Int -> k -> k -> v -> Int -> ST s Int
copyA Int
ixA' (Int -> k
indexLoKeyA Int
ixA') (Int -> k
indexHiKeyA Int
ixA') (Int -> v
indexValueA Int
ixA') Int
ixDst'
else if Int
ixB' forall a. Ord a => a -> a -> Bool
< Int
szB
then Int -> k -> k -> v -> Int -> ST s Int
copyB Int
ixB' (Int -> k
indexLoKeyB Int
ixB') (Int -> k
indexHiKeyB Int
ixB') (Int -> v
indexValueB Int
ixB') Int
ixDst'
else forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst'
copyB :: Int -> k -> k -> v -> Int -> ST s Int
copyB :: Int -> k -> k -> v -> Int -> ST s Int
copyB !Int
ixB !k
loB !k
hiB v
valB !Int
ixDst = do
k
prevHi <- Int -> ST s k
readDstHiKey (Int
ixDst forall a. Num a => a -> a -> a
- Int
1)
v
prevVal <- Int -> ST s v
readDstVal (Int
ixDst forall a. Num a => a -> a -> a
- Int
1)
Int
ixDst' <- if forall a. Enum a => a -> a
pred k
loB forall a. Eq a => a -> a -> Bool
== k
prevHi Bool -> Bool -> Bool
&& v
valB forall a. Eq a => a -> a -> Bool
== v
prevVal
then do
Int -> k -> ST s ()
writeDstHiKey (Int
ixDst forall a. Num a => a -> a -> a
- Int
1) k
hiB
forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
else do
Int -> k -> k -> ST s ()
writeKeyRange Int
ixDst k
loB k
hiB
Int -> v -> ST s ()
writeDstValue Int
ixDst v
valB
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
let ixB' :: Int
ixB' = Int
ixB forall a. Num a => a -> a -> a
+ Int
1
remaining :: Int
remaining = 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 karr s k
keysDst (Int
ixDst' forall a. Num a => a -> a -> a
* Int
2) (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
I.slice karr k
keysB (Int
ixB' forall a. Num a => a -> a -> a
* Int
2) (Int
remaining forall a. Num a => a -> a -> a
* Int
2))
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
remaining)
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst' forall a. Num a => a -> a -> a
+ Int
remaining)
copyA :: Int -> k -> k -> v -> Int -> ST s Int
copyA :: Int -> k -> k -> v -> Int -> ST s Int
copyA !Int
ixA !k
loA !k
hiA !v
valA !Int
ixDst = do
k
prevHi <- Int -> ST s k
readDstHiKey (Int
ixDst forall a. Num a => a -> a -> a
- Int
1)
v
prevVal <- Int -> ST s v
readDstVal (Int
ixDst forall a. Num a => a -> a -> a
- Int
1)
Int
ixDst' <- if forall a. Enum a => a -> a
pred k
loA forall a. Eq a => a -> a -> Bool
== k
prevHi Bool -> Bool -> Bool
&& v
valA forall a. Eq a => a -> a -> Bool
== v
prevVal
then do
Int -> k -> ST s ()
writeDstHiKey (Int
ixDst forall a. Num a => a -> a -> a
- Int
1) k
hiA
forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
else do
Int -> k -> k -> ST s ()
writeKeyRange Int
ixDst k
loA k
hiA
Int -> v -> ST s ()
writeDstValue Int
ixDst v
valA
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
let ixA' :: Int
ixA' = Int
ixA forall a. Num a => a -> a -> a
+ Int
1
remaining :: Int
remaining = 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 karr s k
keysDst (Int
ixDst' forall a. Num a => a -> a -> a
* Int
2) (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
I.slice karr k
keysA (Int
ixA' forall a. Num a => a -> a -> a
* Int
2) (Int
remaining forall a. Num a => a -> a -> a
* Int
2))
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
remaining)
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst' forall a. Num a => a -> a -> a
+ Int
remaining)
let !loA0 :: k
loA0 = Int -> k
indexLoKeyA Int
0
!loB0 :: k
loB0 = Int -> k
indexLoKeyB Int
0
!hiA0 :: k
hiA0 = Int -> k
indexHiKeyA Int
0
!hiB0 :: k
hiB0 = Int -> k
indexHiKeyB Int
0
valA0 :: v
valA0 = Int -> v
indexValueA Int
0
valB0 :: v
valB0 = Int -> v
indexValueB Int
0
Int
total <- case forall a. Ord a => a -> a -> Ordering
compare k
loA0 k
loB0 of
Ordering
LT -> if k
hiA0 forall a. Ord a => a -> a -> Bool
< k
loB0
then do
Int -> k -> k -> ST s ()
writeKeyRange Int
0 k
loA0 k
hiA0
Int -> v -> ST s ()
writeDstValue Int
0 v
valA0
if Int
1 forall a. Ord a => a -> a -> Bool
< Int
szA
then Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
1 (Int -> k
indexLoKeyA Int
1) (Int -> k
indexHiKeyA Int
1) (Int -> v
indexValueA Int
1) Int
0 k
loB0 k
hiB0 v
valB0 Int
1
else Int -> k -> k -> v -> Int -> ST s Int
copyB Int
0 k
loB0 k
hiB0 v
valB0 Int
1
else do
let !upperA :: k
upperA = forall a. Enum a => a -> a
pred k
loB0
Int -> k -> k -> ST s ()
writeKeyRange Int
0 k
loA0 k
upperA
Int -> v -> ST s ()
writeDstValue Int
0 v
valA0
Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
0 k
loB0 k
hiA0 v
valA0 Int
0 k
loB0 k
hiB0 v
valB0 Int
1
Ordering
EQ -> case forall a. Ord a => a -> a -> Ordering
compare k
hiA0 k
hiB0 of
Ordering
LT -> do
Int -> k -> k -> ST s ()
writeKeyRange Int
0 k
loA0 k
hiA0
Int -> v -> ST s ()
writeDstValue Int
0 (v -> v -> v
combine v
valA0 v
valB0)
if Int
1 forall a. Ord a => a -> a -> Bool
< Int
szA
then Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
1 (Int -> k
indexLoKeyA Int
1) (Int -> k
indexHiKeyA Int
1) (Int -> v
indexValueA Int
1) Int
0 (forall a. Enum a => a -> a
succ k
hiA0) k
hiB0 v
valB0 Int
1
else Int -> k -> k -> v -> Int -> ST s Int
copyB Int
0 (forall a. Enum a => a -> a
succ k
hiA0) k
hiB0 v
valB0 Int
1
Ordering
GT -> do
Int -> k -> k -> ST s ()
writeKeyRange Int
0 k
loB0 k
hiB0
Int -> v -> ST s ()
writeDstValue Int
0 (v -> v -> v
combine v
valA0 v
valB0)
if Int
1 forall a. Ord a => a -> a -> Bool
< Int
szB
then Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
0 (forall a. Enum a => a -> a
succ k
hiB0) k
hiA0 v
valA0 Int
1 (Int -> k
indexLoKeyB Int
1) (Int -> k
indexHiKeyB Int
1) (Int -> v
indexValueB Int
1) Int
1
else Int -> k -> k -> v -> Int -> ST s Int
copyA Int
0 (forall a. Enum a => a -> a
succ k
hiB0) k
hiA0 v
valA0 Int
1
Ordering
EQ -> do
Int -> k -> k -> ST s ()
writeKeyRange Int
0 k
loA0 k
hiA0
Int -> v -> ST s ()
writeDstValue Int
0 (v -> v -> v
combine v
valA0 v
valB0)
if Int
1 forall a. Ord a => a -> a -> Bool
< Int
szA
then if Int
1 forall a. Ord a => a -> a -> Bool
< Int
szB
then Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
1 (Int -> k
indexLoKeyA Int
1) (Int -> k
indexHiKeyA Int
1) (Int -> v
indexValueA Int
1) Int
1 (Int -> k
indexLoKeyB Int
1) (Int -> k
indexHiKeyB Int
1) (Int -> v
indexValueB Int
1) Int
1
else Int -> k -> k -> v -> Int -> ST s Int
copyA Int
1 (Int -> k
indexLoKeyA Int
1) (Int -> k
indexHiKeyA Int
1) (Int -> v
indexValueA Int
1) Int
1
else if Int
1 forall a. Ord a => a -> a -> Bool
< Int
szB
then Int -> k -> k -> v -> Int -> ST s Int
copyB Int
1 (Int -> k
indexLoKeyB Int
1) (Int -> k
indexHiKeyB Int
1) (Int -> v
indexValueB Int
1) Int
1
else forall (m :: * -> *) a. Monad m => a -> m a
return Int
1
Ordering
GT -> if k
hiB0 forall a. Ord a => a -> a -> Bool
< k
loA0
then do
Int -> k -> k -> ST s ()
writeKeyRange Int
0 k
loB0 k
hiB0
Int -> v -> ST s ()
writeDstValue Int
0 v
valB0
if Int
1 forall a. Ord a => a -> a -> Bool
< Int
szB
then Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
0 k
loA0 k
hiA0 v
valA0 Int
1 (Int -> k
indexLoKeyB Int
1) (Int -> k
indexHiKeyB Int
1) (Int -> v
indexValueB Int
1) Int
1
else Int -> k -> k -> v -> Int -> ST s Int
copyA Int
0 k
loA0 k
hiA0 v
valA0 Int
1
else do
let !upperB :: k
upperB = forall a. Enum a => a -> a
pred k
loA0
Int -> k -> k -> ST s ()
writeKeyRange Int
0 k
loB0 k
upperB
Int -> v -> ST s ()
writeDstValue Int
0 v
valB0
Int -> k -> k -> v -> Int -> k -> k -> v -> Int -> ST s Int
go Int
0 k
loA0 k
hiA0 v
valA0 Int
0 k
loA0 k
hiB0 v
valB0 Int
1
!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 forall a. Num a => a -> a -> a
* Int
2)
!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)
concatWith :: forall karr varr k v. (ContiguousU karr, Element karr k, Ord k, Enum k, ContiguousU varr, Element varr v, Eq 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, Enum k, ContiguousU varr,
Element varr v, Eq 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, Ord k, Enum k, ContiguousU varr,
Element varr v, Eq v) =>
(v -> v -> v)
-> Map karr varr k v -> Map karr varr k v -> Map karr varr k v
appendWith v -> v -> v
combine)
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
vals) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
I.size varr v
vals
toList :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v) => Map karr varr k v -> [(k,k,v)]
toList :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
Element varr v) =>
Map karr varr k v -> [(k, k, v)]
toList = forall (karr :: * -> *) k (varr :: * -> *) v b.
(ContiguousU karr, Element karr k, ContiguousU varr,
Element varr v) =>
(k -> k -> v -> b -> b) -> b -> Map karr varr k v -> b
foldrWithKey (\k
lo k
hi v
v [(k, k, v)]
xs -> (k
lo,k
hi,v
v) forall a. a -> [a] -> [a]
: [(k, k, v)]
xs) []
foldrWithKey :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v) => (k -> 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 -> k -> v -> b -> b) -> b -> Map karr varr k v -> b
foldrWithKey k -> k -> v -> b -> b
f b
z (Map karr k
keys 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 !lo :: k
lo = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keys (Int
i forall a. Num a => a -> a -> a
* Int
2)
!hi :: k
hi = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
I.index karr k
keys (Int
i forall a. Num a => a -> a -> a
* Int
2 forall a. Num a => a -> a -> a
+ Int
1)
!(# v
v #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
I.index# varr v
vals Int
i
in k -> k -> v -> b -> b
f k
lo k
hi v
v (Int -> b
go (Int
i forall a. Num a => a -> a -> a
+ Int
1))
in Int -> b
go Int
0
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, k, v)]
toList Map karr varr k v
xs)
liftShowsPrec2 :: (ContiguousU karr, Element karr k, ContiguousU varr, Element varr v) => (Int -> k -> ShowS) -> ([k] -> ShowS) -> (Int -> v -> ShowS) -> ([v] -> ShowS) -> Int -> Map karr varr k v -> ShowS
liftShowsPrec2 :: forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
Element varr v) =>
(Int -> k -> ShowS)
-> ([k] -> ShowS)
-> (Int -> v -> ShowS)
-> ([v] -> ShowS)
-> Int
-> Map karr varr k v
-> ShowS
liftShowsPrec2 Int -> k -> ShowS
showsPrecK [k] -> ShowS
_ Int -> v -> ShowS
showsPrecV [v] -> ShowS
_ 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. (a -> ShowS) -> [a] -> ShowS
showListWith (\(k
a,k
b,v
c) -> [ShowS] -> ShowS
show_tuple [Int -> k -> ShowS
showsPrecK Int
0 k
a, Int -> k -> ShowS
showsPrecK Int
0 k
b, Int -> v -> ShowS
showsPrecV Int
0 v
c]) (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
Element varr v) =>
Map karr varr k v -> [(k, k, v)]
toList Map karr varr k v
xs)
show_tuple :: [ShowS] -> ShowS
show_tuple :: [ShowS] -> ShowS
show_tuple [ShowS]
ss = forall a. a -> a
id
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
'('
forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldr1 (\ShowS
s ShowS
r -> ShowS
s forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
',' forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
r) [ShowS]
ss
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
')'