{-# 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
    -- list conversion
  , 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

-- The key array is twice as long as the value array since
-- everything is stored as a range. Also, figure out how to
-- unpack these two arguments at some point.
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

-- Note: this is only correct when the function is a bijection.
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 -- keys a
  -> varr v -- values a
  -> karr k -- keys b
  -> varr v -- values b
  -> (karr k, varr v)
unionArrWith :: forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, 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
    -- In the go functon, ixDst is always at least one. Similarly,
    -- all key arguments are always greater than minBound.
    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
          -- here we know that hiA > loA
          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)

-- implementation copied from GHC.Show
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
')'