{-# LANGUAGE CPP #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE UndecidableInstances #-}
module Data.Dependent.Map
    ( DMap

    -- * Operators
    , (!), (\\)

    -- * Query
    , null
    , size
    , member
    , notMember
    , lookup
    , findWithDefault

    -- * Construction
    , empty
    , singleton

    -- ** Insertion
    , insert
    , insertWith
    , insertWith'
    , insertWithKey
    , insertWithKey'
    , insertLookupWithKey
    , insertLookupWithKey'

    -- ** Delete\/Update
    , delete
    , adjust
    , adjustWithKey
    , adjustWithKey'
    , update
    , updateWithKey
    , updateLookupWithKey
    , alter
    , alterF

    -- * Combine

    -- ** Union
    , union
    , unionWithKey
    , unions
    , unionsWithKey

    -- ** Difference
    , difference
    , differenceWithKey

    -- ** Intersection
    , intersection
    , intersectionWithKey

    -- * Traversal
    -- ** Map
    , map
    , ffor
    , mapWithKey
    , fforWithKey
    , traverseWithKey_
    , forWithKey_
    , traverseWithKey
    , forWithKey
    , mapAccumLWithKey
    , mapAccumRWithKey
    , mapKeysWith
    , mapKeysMonotonic

    -- ** Fold
    , foldWithKey
    , foldrWithKey
    , foldlWithKey
    -- , foldlWithKey'

    -- * Conversion
    , keys
    , assocs

    -- ** Lists
    , toList
    , fromList
    , fromListWithKey

    -- ** Ordered lists
    , toAscList
    , toDescList
    , fromAscList
    , fromAscListWithKey
    , fromDistinctAscList

    -- * Filter
    , filter
    , filterWithKey
    , partitionWithKey

    , mapMaybe
    , mapMaybeWithKey
    , mapEitherWithKey

    , split
    , splitLookup

    -- * Submap
    , isSubmapOf, isSubmapOfBy
    , isProperSubmapOf, isProperSubmapOfBy

    -- * Indexed
    , lookupIndex
    , findIndex
    , elemAt
    , updateAt
    , deleteAt

    -- * Min\/Max
    , findMin
    , findMax
    , lookupMin
    , lookupMax
    , deleteMin
    , deleteMax
    , deleteFindMin
    , deleteFindMax
    , updateMinWithKey
    , updateMaxWithKey
    , minViewWithKey
    , maxViewWithKey

    -- * Debugging
    , showTree
    , showTreeWith
    , valid
    ) where

import Prelude hiding (null, lookup, map)
import qualified Prelude
import Data.Constraint.Extras (Has', has')
import Data.Dependent.Sum (DSum((:=>)))
import Data.GADT.Compare (GCompare, GEq, GOrdering(..), gcompare, geq)
import Data.GADT.Show (GRead, GShow)
import Data.Maybe (isJust)
import Data.Some (Some, mkSome)
import Data.Typeable ((:~:)(Refl))
import Text.Read (Lexeme(Ident), lexP, parens, prec, readListPrec,
                  readListPrecDefault, readPrec)

#if !MIN_VERSION_base(4,11,0)
import Data.Semigroup (Semigroup, (<>))
#endif

import Data.Dependent.Map.Internal
import Data.Dependent.Map.PtrEquality (ptrEq)

instance (GCompare k) => Monoid (DMap k f) where
    mempty :: DMap k f
mempty  = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
empty
    mappend :: DMap k f -> DMap k f -> DMap k f
mappend = DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
DMap k f -> DMap k f -> DMap k f
union
    mconcat :: [DMap k f] -> DMap k f
mconcat = [DMap k f] -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
[DMap k f] -> DMap k f
unions

instance (GCompare k) => Semigroup (DMap k f) where
  <> :: DMap k f -> DMap k f -> DMap k f
(<>) = DMap k f -> DMap k f -> DMap k f
forall a. Monoid a => a -> a -> a
mappend

{--------------------------------------------------------------------
  Operators
--------------------------------------------------------------------}
infixl 9 \\,! -- \\ at the end of the line means line continuation

-- | /O(log n)/. Find the value at a key.
-- Calls 'error' when the element can not be found.
--
-- > fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
-- > fromList [(5,'a'), (3,'b')] ! 5 == 'a'

(!) :: GCompare k => DMap k f -> k v -> f v
(!) DMap k f
m k v
k    = k v -> DMap k f -> f v
forall k (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
k v -> DMap k f -> f v
find k v
k DMap k f
m

-- | Same as 'difference'.
(\\) :: GCompare k => DMap k f -> DMap k f -> DMap k f
DMap k f
m1 \\ :: DMap k f -> DMap k f -> DMap k f
\\ DMap k f
m2 = DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
DMap k f -> DMap k g -> DMap k f
difference DMap k f
m1 DMap k f
m2

-- #if __GLASGOW_HASKELL__
--
-- {--------------------------------------------------------------------
--   A Data instance
-- --------------------------------------------------------------------}
--
-- -- This instance preserves data abstraction at the cost of inefficiency.
-- -- We omit reflection services for the sake of data abstraction.
--
-- instance (Data k, Data a, GCompare k) => Data (DMap k) where
--   gfoldl f z m   = z fromList `f` toList m
--   toConstr _     = error "toConstr"
--   gunfold _ _    = error "gunfold"
--   dataTypeOf _   = mkNoRepType "Data.Map.Map"
--   dataCast2 f    = gcast2 f
--
-- #endif

{--------------------------------------------------------------------
  Query
--------------------------------------------------------------------}

-- | /O(log n)/. Is the key a member of the map? See also 'notMember'.
member :: GCompare k => k a -> DMap k f -> Bool
member :: k a -> DMap k f -> Bool
member k a
k = Maybe (f a) -> Bool
forall a. Maybe a -> Bool
isJust (Maybe (f a) -> Bool)
-> (DMap k f -> Maybe (f a)) -> DMap k f -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k a -> DMap k f -> Maybe (f a)
forall k1 (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
k2 v -> DMap k2 f -> Maybe (f v)
lookup k a
k

-- | /O(log n)/. Is the key not a member of the map? See also 'member'.
notMember :: GCompare k => k v -> DMap k f -> Bool
notMember :: k v -> DMap k f -> Bool
notMember k v
k DMap k f
m = Bool -> Bool
not (k v -> DMap k f -> Bool
forall k (k :: k -> *) (a :: k) (f :: k -> *).
GCompare k =>
k a -> DMap k f -> Bool
member k v
k DMap k f
m)

-- | /O(log n)/. Find the value at a key.
-- Calls 'error' when the element can not be found.
-- Consider using 'lookup' when elements may not be present.
find :: GCompare k => k v -> DMap k f -> f v
find :: k v -> DMap k f -> f v
find k v
k DMap k f
m = case k v -> DMap k f -> Maybe (f v)
forall k1 (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
k2 v -> DMap k2 f -> Maybe (f v)
lookup k v
k DMap k f
m of
    Maybe (f v)
Nothing -> [Char] -> f v
forall a. HasCallStack => [Char] -> a
error [Char]
"DMap.find: element not in the map"
    Just f v
v  -> f v
v

-- | /O(log n)/. The expression @('findWithDefault' def k map)@ returns
-- the value at key @k@ or returns default value @def@
-- when the key is not in the map.
findWithDefault :: GCompare k => f v -> k v -> DMap k f -> f v
findWithDefault :: f v -> k v -> DMap k f -> f v
findWithDefault f v
def k v
k DMap k f
m = case k v -> DMap k f -> Maybe (f v)
forall k1 (k2 :: k1 -> *) (f :: k1 -> *) (v :: k1).
GCompare k2 =>
k2 v -> DMap k2 f -> Maybe (f v)
lookup k v
k DMap k f
m of
    Maybe (f v)
Nothing -> f v
def
    Just f v
v  -> f v
v

{--------------------------------------------------------------------
  Insertion
--------------------------------------------------------------------}

-- | /O(log n)/. Insert a new key and value in the map.
-- If the key is already present in the map, the associated value is
-- replaced with the supplied value. 'insert' is equivalent to
-- @'insertWith' 'const'@.
insert :: forall k f v. GCompare k => k v -> f v -> DMap k f -> DMap k f
insert :: k v -> f v -> DMap k f -> DMap k f
insert k v
kx f v
x = k v
kx k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
`seq` DMap k f -> DMap k f
go
    where
        go :: DMap k f -> DMap k f
        go :: DMap k f -> DMap k f
go DMap k f
Tip = k v -> f v -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k v
kx f v
x
        go t :: DMap k f
t@(Bin Int
sz k v
ky f v
y DMap k f
l DMap k f
r) = case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
kx k v
ky of
            GOrdering v v
GLT -> let !l' :: DMap k f
l' = DMap k f -> DMap k f
go DMap k f
l
                   in if DMap k f
l' DMap k f -> DMap k f -> Bool
forall a. a -> a -> Bool
`ptrEq` DMap k f
l
                      then DMap k f
t
                      else k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y DMap k f
l' DMap k f
r
            GOrdering v v
GGT -> let !r' :: DMap k f
r' = DMap k f -> DMap k f
go DMap k f
r
                   in if DMap k f
r' DMap k f -> DMap k f -> Bool
forall a. a -> a -> Bool
`ptrEq` DMap k f
r
                      then DMap k f
t
                      else k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y DMap k f
l DMap k f
r'
            GOrdering v v
GEQ
              | k v
kx k v -> k v -> Bool
forall a. a -> a -> Bool
`ptrEq` k v
k v
ky Bool -> Bool -> Bool
&& f v
x f v -> f v -> Bool
forall a. a -> a -> Bool
`ptrEq` f v
f v
y -> DMap k f
t
              | Bool
otherwise -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sz k v
kx f v
x DMap k f
l DMap k f
r

-- | /O(log n)/. Insert a new key and value in the map if the key
-- is not already present. If the key is already present, @insertR@
-- does nothing.
insertR :: forall k f v. GCompare k => k v -> f v -> DMap k f -> DMap k f
insertR :: k v -> f v -> DMap k f -> DMap k f
insertR k v
kx f v
x = k v
kx k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
`seq` DMap k f -> DMap k f
go
    where
        go :: DMap k f -> DMap k f
        go :: DMap k f -> DMap k f
go DMap k f
Tip = k v -> f v -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k v
kx f v
x
        go t :: DMap k f
t@(Bin Int
sz k v
ky f v
y DMap k f
l DMap k f
r) = case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
kx k v
ky of
            GOrdering v v
GLT -> let !l' :: DMap k f
l' = DMap k f -> DMap k f
go DMap k f
l
                   in if DMap k f
l' DMap k f -> DMap k f -> Bool
forall a. a -> a -> Bool
`ptrEq` DMap k f
l
                      then DMap k f
t
                      else k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y DMap k f
l' DMap k f
r
            GOrdering v v
GGT -> let !r' :: DMap k f
r' = DMap k f -> DMap k f
go DMap k f
r
                   in if DMap k f
r' DMap k f -> DMap k f -> Bool
forall a. a -> a -> Bool
`ptrEq` DMap k f
r
                   then DMap k f
t
                   else k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y DMap k f
l DMap k f
r'
            GOrdering v v
GEQ -> DMap k f
t

-- | /O(log n)/. Insert with a function, combining new value and old value.
-- @'insertWith' f key value mp@
-- will insert the entry @key :=> value@ into @mp@ if key does
-- not exist in the map. If the key does exist, the function will
-- insert the entry @key :=> f new_value old_value@.
insertWith :: GCompare k => (f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWith :: (f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWith f v -> f v -> f v
f = (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWithKey (\k v
_ f v
x' f v
y' -> f v -> f v -> f v
f f v
x' f v
y')

-- | Same as 'insertWith', but the combining function is applied strictly.
-- This is often the most desirable behavior.
insertWith' :: GCompare k => (f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWith' :: (f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWith' f v -> f v -> f v
f = (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWithKey' (\k v
_ f v
x' f v
y' -> f v -> f v -> f v
f f v
x' f v
y')

-- | /O(log n)/. Insert with a function, combining key, new value and old value.
-- @'insertWithKey' f key value mp@
-- will insert the entry @key :=> value@ into @mp@ if key does
-- not exist in the map. If the key does exist, the function will
-- insert the entry @key :=> f key new_value old_value@.
-- Note that the key passed to f is the same key passed to 'insertWithKey'.
insertWithKey :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWithKey :: (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWithKey k v -> f v -> f v -> f v
f k v
kx f v
x = k v
kx k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
`seq` DMap k f -> DMap k f
go
  where
    go :: DMap k f -> DMap k f
    go :: DMap k f -> DMap k f
go DMap k f
Tip = k v -> f v -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k v
kx f v
x
    go (Bin Int
sy k v
ky f v
y DMap k f
l DMap k f
r) =
        case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
kx k v
ky of
            GOrdering v v
GLT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y (DMap k f -> DMap k f
go DMap k f
l) DMap k f
r
            GOrdering v v
GGT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y DMap k f
l (DMap k f -> DMap k f
go DMap k f
r)
            GOrdering v v
GEQ -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sy k v
kx (k v -> f v -> f v -> f v
f k v
kx f v
x f v
f v
y) DMap k f
l DMap k f
r

-- | Same as 'insertWithKey', but the combining function is applied strictly.
insertWithKey' :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWithKey' :: (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWithKey' k v -> f v -> f v -> f v
f k v
kx f v
x = k v
kx k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
`seq` DMap k f -> DMap k f
go
  where
    go :: DMap k f -> DMap k f
    go :: DMap k f -> DMap k f
go DMap k f
Tip = k v -> f v -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k v
kx (f v -> DMap k f) -> f v -> DMap k f
forall a b. (a -> b) -> a -> b
$! f v
x
    go (Bin Int
sy k v
ky f v
y DMap k f
l DMap k f
r) =
        case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
kx k v
ky of
            GOrdering v v
GLT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y (DMap k f -> DMap k f
go DMap k f
l) DMap k f
r
            GOrdering v v
GGT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y DMap k f
l (DMap k f -> DMap k f
go DMap k f
r)
            GOrdering v v
GEQ -> let x' :: f v
x' = k v -> f v -> f v -> f v
f k v
kx f v
x f v
f v
y in f v -> DMap k f -> DMap k f
seq f v
x' (Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sy k v
kx f v
x' DMap k f
l DMap k f
r)

-- | /O(log n)/. Combines insert operation with old value retrieval.
-- The expression (@'insertLookupWithKey' f k x map@)
-- is a pair where the first element is equal to (@'lookup' k map@)
-- and the second element equal to (@'insertWithKey' f k x map@).
insertLookupWithKey :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f
                    -> (Maybe (f v), DMap k f)
insertLookupWithKey :: (k v -> f v -> f v -> f v)
-> k v -> f v -> DMap k f -> (Maybe (f v), DMap k f)
insertLookupWithKey k v -> f v -> f v -> f v
f k v
kx f v
x = k v
kx k v
-> (DMap k f -> (Maybe (f v), DMap k f))
-> DMap k f
-> (Maybe (f v), DMap k f)
`seq` DMap k f -> (Maybe (f v), DMap k f)
go
  where
    go :: DMap k f -> (Maybe (f v), DMap k f)
    go :: DMap k f -> (Maybe (f v), DMap k f)
go DMap k f
Tip = (Maybe (f v)
forall a. Maybe a
Nothing, k v -> f v -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k v
kx f v
x)
    go (Bin Int
sy k v
ky f v
y DMap k f
l DMap k f
r) =
        case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
kx k v
ky of
            GOrdering v v
GLT -> let (Maybe (f v)
found, DMap k f
l') = DMap k f -> (Maybe (f v), DMap k f)
go DMap k f
l
                  in (Maybe (f v)
found, k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y DMap k f
l' DMap k f
r)
            GOrdering v v
GGT -> let (Maybe (f v)
found, DMap k f
r') = DMap k f -> (Maybe (f v), DMap k f)
go DMap k f
r
                  in (Maybe (f v)
found, k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y DMap k f
l DMap k f
r')
            GOrdering v v
GEQ -> (f v -> Maybe (f v)
forall a. a -> Maybe a
Just f v
y, Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sy k v
kx (k v -> f v -> f v -> f v
f k v
kx f v
x f v
f v
y) DMap k f
l DMap k f
r)

-- | /O(log n)/. A strict version of 'insertLookupWithKey'.
insertLookupWithKey' :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f
                     -> (Maybe (f v), DMap k f)
insertLookupWithKey' :: (k v -> f v -> f v -> f v)
-> k v -> f v -> DMap k f -> (Maybe (f v), DMap k f)
insertLookupWithKey' k v -> f v -> f v -> f v
f k v
kx f v
x = k v
kx k v
-> (DMap k f -> (Maybe (f v), DMap k f))
-> DMap k f
-> (Maybe (f v), DMap k f)
`seq` DMap k f -> (Maybe (f v), DMap k f)
go
  where
    go :: DMap k f -> (Maybe (f v), DMap k f)
    go :: DMap k f -> (Maybe (f v), DMap k f)
go DMap k f
Tip = f v
x f v -> (Maybe (f v), DMap k f) -> (Maybe (f v), DMap k f)
`seq` (Maybe (f v)
forall a. Maybe a
Nothing, k v -> f v -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k v
kx f v
x)
    go (Bin Int
sy k v
ky f v
y DMap k f
l DMap k f
r) =
        case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
kx k v
ky of
            GOrdering v v
GLT -> let (Maybe (f v)
found, DMap k f
l') = DMap k f -> (Maybe (f v), DMap k f)
go DMap k f
l
                  in (Maybe (f v)
found, k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y DMap k f
l' DMap k f
r)
            GOrdering v v
GGT -> let (Maybe (f v)
found, DMap k f
r') = DMap k f -> (Maybe (f v), DMap k f)
go DMap k f
r
                  in (Maybe (f v)
found, k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
ky f v
y DMap k f
l DMap k f
r')
            GOrdering v v
GEQ -> let x' :: f v
x' = k v -> f v -> f v -> f v
f k v
kx f v
x f v
f v
y in f v
x' f v -> (Maybe (f v), DMap k f) -> (Maybe (f v), DMap k f)
`seq` (f v -> Maybe (f v)
forall a. a -> Maybe a
Just f v
y, Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sy k v
kx f v
x' DMap k f
l DMap k f
r)

{--------------------------------------------------------------------
  Deletion
  [delete] is the inlined version of [deleteWith (\k x -> Nothing)]
--------------------------------------------------------------------}

-- | /O(log n)/. Delete a key and its value from the map. When the key is not
-- a member of the map, the original map is returned.
delete :: forall k f v. GCompare k => k v -> DMap k f -> DMap k f
delete :: k v -> DMap k f -> DMap k f
delete k v
k = k v
k k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
`seq` DMap k f -> DMap k f
go
  where
    go :: DMap k f -> DMap k f
    go :: DMap k f -> DMap k f
go DMap k f
Tip = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r) =
        case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
            GOrdering v v
GLT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x (DMap k f -> DMap k f
go DMap k f
l) DMap k f
r
            GOrdering v v
GGT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x DMap k f
l (DMap k f -> DMap k f
go DMap k f
r)
            GOrdering v v
GEQ -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
glue DMap k f
l DMap k f
r

-- | /O(log n)/. Update a value at a specific key with the result of the provided function.
-- When the key is not
-- a member of the map, the original map is returned.
adjust :: GCompare k => (f v -> f v) -> k v -> DMap k f -> DMap k f
adjust :: (f v -> f v) -> k v -> DMap k f -> DMap k f
adjust f v -> f v
f = (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
(k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
adjustWithKey (\k v
_ f v
x -> f v -> f v
f f v
x)

-- | /O(log n)/. Adjust a value at a specific key. When the key is not
-- a member of the map, the original map is returned.
adjustWithKey :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
adjustWithKey :: (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
adjustWithKey k v -> f v -> f v
f0 !k v
k0 = (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
(k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
go k v -> f v -> f v
f0 k v
k0
  where
    go :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    go :: (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
go k v -> f v -> f v
_f k v
_k DMap k f
Tip = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go k v -> f v -> f v
f k v
k (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
r) =
      case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
        GOrdering v v
GLT -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
x ((k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
(k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
go k v -> f v -> f v
f k v
k DMap k f
l) DMap k f
r
        GOrdering v v
GGT -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
x DMap k f
l ((k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
(k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
go k v -> f v -> f v
f k v
k DMap k f
r)
        GOrdering v v
GEQ -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx (k v -> f v -> f v
f k v
k v
kx f v
f v
x) DMap k f
l DMap k f
r

-- | /O(log n)/. A strict version of 'adjustWithKey'.
adjustWithKey' :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
adjustWithKey' :: (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
adjustWithKey' k v -> f v -> f v
f0 !k v
k0 = (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
(k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
go k v -> f v -> f v
f0 k v
k0
  where
    go :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
    go :: (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
go k v -> f v -> f v
_f k v
_k DMap k f
Tip = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go k v -> f v -> f v
f k v
k (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
r) =
      case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
        GOrdering v v
GLT -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
x ((k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
(k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
go k v -> f v -> f v
f k v
k DMap k f
l) DMap k f
r
        GOrdering v v
GGT -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
x DMap k f
l ((k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
GCompare k =>
(k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
go k v -> f v -> f v
f k v
k DMap k f
r)
        GOrdering v v
GEQ -> let !x' :: f v
x' = k v -> f v -> f v
f k v
k v
kx f v
f v
x in Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
f v
x' DMap k f
l DMap k f
r

-- | /O(log n)/. The expression (@'update' f k map@) updates the value @x@
-- at @k@ (if it is in the map). If (@f x@) is 'Nothing', the element is
-- deleted. If it is (@'Just' y@), the key @k@ is bound to the new value @y@.
update :: GCompare k => (f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
update :: (f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
update f v -> Maybe (f v)
f = (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
updateWithKey (\k v
_ f v
x -> f v -> Maybe (f v)
f f v
x)

-- | /O(log n)/. The expression (@'updateWithKey' f k map@) updates the
-- value @x@ at @k@ (if it is in the map). If (@f k x@) is 'Nothing',
-- the element is deleted. If it is (@'Just' y@), the key @k@ is bound
-- to the new value @y@.
updateWithKey :: forall k f v. GCompare k => (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
updateWithKey :: (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
updateWithKey k v -> f v -> Maybe (f v)
f k v
k = k v
k k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
`seq` DMap k f -> DMap k f
go
  where
    go :: DMap k f -> DMap k f
    go :: DMap k f -> DMap k f
go DMap k f
Tip = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
r) =
        case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
           GOrdering v v
GLT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x (DMap k f -> DMap k f
go DMap k f
l) DMap k f
r
           GOrdering v v
GGT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x DMap k f
l (DMap k f -> DMap k f
go DMap k f
r)
           GOrdering v v
GEQ -> case k v -> f v -> Maybe (f v)
f k v
k v
kx f v
f v
x of
                   Just f v
x' -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
f v
x' DMap k f
l DMap k f
r
                   Maybe (f v)
Nothing -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
glue DMap k f
l DMap k f
r

-- | /O(log n)/. Lookup and update. See also 'updateWithKey'.
-- The function returns changed value, if it is updated.
-- Returns the original key value if the map entry is deleted.
updateLookupWithKey :: forall k f v. GCompare k => (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> (Maybe (f v), DMap k f)
updateLookupWithKey :: (k v -> f v -> Maybe (f v))
-> k v -> DMap k f -> (Maybe (f v), DMap k f)
updateLookupWithKey k v -> f v -> Maybe (f v)
f k v
k = k v
k k v
-> (DMap k f -> (Maybe (f v), DMap k f))
-> DMap k f
-> (Maybe (f v), DMap k f)
`seq` DMap k f -> (Maybe (f v), DMap k f)
go
 where
   go :: DMap k f -> (Maybe (f v), DMap k f)
   go :: DMap k f -> (Maybe (f v), DMap k f)
go DMap k f
Tip = (Maybe (f v)
forall a. Maybe a
Nothing,DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip)
   go (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
r) =
          case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
               GOrdering v v
GLT -> let (Maybe (f v)
found,DMap k f
l') = DMap k f -> (Maybe (f v), DMap k f)
go DMap k f
l in (Maybe (f v)
found,k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x DMap k f
l' DMap k f
r)
               GOrdering v v
GGT -> let (Maybe (f v)
found,DMap k f
r') = DMap k f -> (Maybe (f v), DMap k f)
go DMap k f
r in (Maybe (f v)
found,k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x DMap k f
l DMap k f
r')
               GOrdering v v
GEQ -> case k v -> f v -> Maybe (f v)
f k v
k v
kx f v
f v
x of
                       Just f v
x' -> (f v -> Maybe (f v)
forall a. a -> Maybe a
Just f v
x',Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
f v
x' DMap k f
l DMap k f
r)
                       Maybe (f v)
Nothing -> (f v -> Maybe (f v)
forall a. a -> Maybe a
Just f v
x,DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
glue DMap k f
l DMap k f
r)

-- | /O(log n)/. The expression (@'alter' f k map@) alters the value @x@ at @k@, or absence thereof.
-- 'alter' can be used to insert, delete, or update a value in a 'Map'.
-- In short : @'lookup' k ('alter' f k m) = f ('lookup' k m)@.
alter :: forall k f v. GCompare k => (Maybe (f v) -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
alter :: (Maybe (f v) -> Maybe (f v)) -> k v -> DMap k f -> DMap k f
alter Maybe (f v) -> Maybe (f v)
f k v
k = k v
k k v -> (DMap k f -> DMap k f) -> DMap k f -> DMap k f
`seq` DMap k f -> DMap k f
go
  where
    go :: DMap k f -> DMap k f
    go :: DMap k f -> DMap k f
go DMap k f
Tip = case Maybe (f v) -> Maybe (f v)
f Maybe (f v)
forall a. Maybe a
Nothing of
               Maybe (f v)
Nothing -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
               Just f v
x  -> k v -> f v -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k v
k f v
x

    go (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
r) = case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
               GOrdering v v
GLT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x (DMap k f -> DMap k f
go DMap k f
l) DMap k f
r
               GOrdering v v
GGT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x DMap k f
l (DMap k f -> DMap k f
go DMap k f
r)
               GOrdering v v
GEQ -> case Maybe (f v) -> Maybe (f v)
f (f v -> Maybe (f v)
forall a. a -> Maybe a
Just f v
x) of
                       Just f v
x' -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
f v
x' DMap k f
l DMap k f
r
                       Maybe (f v)
Nothing -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
glue DMap k f
l DMap k f
r

-- | Works the same as 'alter' except the new value is returned in some 'Functor' @f@.
-- In short : @(\v' -> alter (const v') k dm) <$> f (lookup k dm)@
alterF :: forall k f v g. (GCompare  k, Functor f) => k v -> (Maybe (g v) -> f (Maybe (g v))) -> DMap k g -> f (DMap k g)
alterF :: k v -> (Maybe (g v) -> f (Maybe (g v))) -> DMap k g -> f (DMap k g)
alterF k v
k Maybe (g v) -> f (Maybe (g v))
f = DMap k g -> f (DMap k g)
go
  where
    go :: DMap k g -> f (DMap k g)
    go :: DMap k g -> f (DMap k g)
go DMap k g
Tip = DMap k g -> (g v -> DMap k g) -> Maybe (g v) -> DMap k g
forall b a. b -> (a -> b) -> Maybe a -> b
maybe DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip (k v -> g v -> DMap k g
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k v
k) (Maybe (g v) -> DMap k g) -> f (Maybe (g v)) -> f (DMap k g)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (g v) -> f (Maybe (g v))
f Maybe (g v)
forall a. Maybe a
Nothing

    go (Bin Int
sx k v
kx g v
x DMap k g
l DMap k g
r) = case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
      GOrdering v v
GLT -> (\DMap k g
l' -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx g v
x DMap k g
l' DMap k g
r) (DMap k g -> DMap k g) -> f (DMap k g) -> f (DMap k g)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> DMap k g -> f (DMap k g)
go DMap k g
l
      GOrdering v v
GGT -> (\DMap k g
r' -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx g v
x DMap k g
l DMap k g
r') (DMap k g -> DMap k g) -> f (DMap k g) -> f (DMap k g)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> DMap k g -> f (DMap k g)
go DMap k g
r
      GOrdering v v
GEQ -> DMap k g -> (g v -> DMap k g) -> Maybe (g v) -> DMap k g
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (DMap k g -> DMap k g -> DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
glue DMap k g
l DMap k g
r) (\g v
x' -> Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx g v
x' DMap k g
l DMap k g
r) (Maybe (g v) -> DMap k g) -> f (Maybe (g v)) -> f (DMap k g)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (g v) -> f (Maybe (g v))
f (g v -> Maybe (g v)
forall a. a -> Maybe a
Just g v
x)

{--------------------------------------------------------------------
  Indexing
--------------------------------------------------------------------}

-- | /O(log n)/. Return the /index/ of a key. The index is a number from
-- /0/ up to, but not including, the 'size' of the map. Calls 'error' when
-- the key is not a 'member' of the map.
findIndex :: GCompare k => k v -> DMap k f -> Int
findIndex :: k v -> DMap k f -> Int
findIndex k v
k DMap k f
t
  = case k v -> DMap k f -> Maybe Int
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> DMap k f -> Maybe Int
lookupIndex k v
k DMap k f
t of
      Maybe Int
Nothing  -> [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Map.findIndex: element is not in the map"
      Just Int
idx -> Int
idx

-- | /O(log n)/. Lookup the /index/ of a key. The index is a number from
-- /0/ up to, but not including, the 'size' of the map.
lookupIndex :: forall k f v. GCompare k => k v -> DMap k f -> Maybe Int
lookupIndex :: k v -> DMap k f -> Maybe Int
lookupIndex k v
k = k v
k k v -> (DMap k f -> Maybe Int) -> DMap k f -> Maybe Int
`seq` Int -> DMap k f -> Maybe Int
go Int
0
  where
    go :: Int -> DMap k f -> Maybe Int
    go :: Int -> DMap k f -> Maybe Int
go !Int
idx DMap k f
Tip  = Int
idx Int -> Maybe Int -> Maybe Int
`seq` Maybe Int
forall a. Maybe a
Nothing
    go !Int
idx (Bin Int
_ k v
kx f v
_ DMap k f
l DMap k f
r)
      = case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
          GOrdering v v
GLT -> Int -> DMap k f -> Maybe Int
go Int
idx DMap k f
l
          GOrdering v v
GGT -> Int -> DMap k f -> Maybe Int
go (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
+ DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) DMap k f
r
          GOrdering v v
GEQ -> Int -> Maybe Int
forall a. a -> Maybe a
Just (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
+ DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
l)

-- | /O(log n)/. Retrieve an element by /index/. Calls 'error' when an
-- invalid index is used.
elemAt :: Int -> DMap k f -> DSum k f
elemAt :: Int -> DMap k f -> DSum k f
elemAt Int
_ DMap k f
Tip = [Char] -> DSum k f
forall a. HasCallStack => [Char] -> a
error [Char]
"Map.elemAt: index out of range"
elemAt Int
i (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r)
  = case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
i Int
sizeL of
      Ordering
LT -> Int -> DMap k f -> DSum k f
forall k (k :: k -> *) (f :: k -> *). Int -> DMap k f -> DSum k f
elemAt Int
i DMap k f
l
      Ordering
GT -> Int -> DMap k f -> DSum k f
forall k (k :: k -> *) (f :: k -> *). Int -> DMap k f -> DSum k f
elemAt (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
sizeLInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) DMap k f
r
      Ordering
EQ -> k v
kx k v -> f v -> DSum k f
forall k (tag :: k -> *) (f :: k -> *) (a :: k).
tag a -> f a -> DSum tag f
:=> f v
x
  where
    sizeL :: Int
sizeL = DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
l

-- | /O(log n)/. Update the element at /index/. Does nothing when an
-- invalid index is used.
updateAt :: (forall v. k v -> f v -> Maybe (f v)) -> Int -> DMap k f -> DMap k f
updateAt :: (forall (v :: k). k v -> f v -> Maybe (f v))
-> Int -> DMap k f -> DMap k f
updateAt forall (v :: k). k v -> f v -> Maybe (f v)
f Int
i0 DMap k f
t = Int
i0 Int -> DMap k f -> DMap k f
`seq` Int -> DMap k f -> DMap k f
go Int
i0 DMap k f
t
 where
    go :: Int -> DMap k f -> DMap k f
go Int
_ DMap k f
Tip  = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go Int
i (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
r) = case Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Int
i Int
sizeL of
      Ordering
LT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x (Int -> DMap k f -> DMap k f
go Int
i DMap k f
l) DMap k f
r
      Ordering
GT -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x DMap k f
l (Int -> DMap k f -> DMap k f
go (Int
iInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
sizeLInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) DMap k f
r)
      Ordering
EQ -> case k v -> f v -> Maybe (f v)
forall (v :: k). k v -> f v -> Maybe (f v)
f k v
kx f v
x of
              Just f v
x' -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
x' DMap k f
l DMap k f
r
              Maybe (f v)
Nothing -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
glue DMap k f
l DMap k f
r
      where
        sizeL :: Int
sizeL = DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
l

-- | /O(log n)/. Delete the element at /index/.
-- Defined as (@'deleteAt' i map = 'updateAt' (\k x -> 'Nothing') i map@).
deleteAt :: Int -> DMap k f -> DMap k f
deleteAt :: Int -> DMap k f -> DMap k f
deleteAt Int
i DMap k f
m
  = (forall (v :: k). k v -> f v -> Maybe (f v))
-> Int -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> Maybe (f v))
-> Int -> DMap k f -> DMap k f
updateAt (\k v
_ f v
_ -> Maybe (f v)
forall a. Maybe a
Nothing) Int
i DMap k f
m


{--------------------------------------------------------------------
  Minimal, Maximal
--------------------------------------------------------------------}

-- | /O(log n)/. The minimal key of the map. Calls 'error' is the map is empty.
findMin :: DMap k f -> DSum k f
findMin :: DMap k f -> DSum k f
findMin DMap k f
m = case DMap k f -> Maybe (DSum k f)
forall k (k :: k -> *) (f :: k -> *). DMap k f -> Maybe (DSum k f)
lookupMin DMap k f
m of
  Just DSum k f
x -> DSum k f
x
  Maybe (DSum k f)
Nothing -> [Char] -> DSum k f
forall a. HasCallStack => [Char] -> a
error [Char]
"Map.findMin: empty map has no minimal element"

lookupMin :: DMap k f -> Maybe (DSum k f)
lookupMin :: DMap k f -> Maybe (DSum k f)
lookupMin DMap k f
m = case DMap k f
m of
      DMap k f
Tip -> Maybe (DSum k f)
forall a. Maybe a
Nothing
      Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
_ -> DSum k f -> Maybe (DSum k f)
forall a. a -> Maybe a
Just (DSum k f -> Maybe (DSum k f)) -> DSum k f -> Maybe (DSum k f)
forall a b. (a -> b) -> a -> b
$! k v -> f v -> DMap k f -> DSum k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
k v -> f v -> DMap k f -> DSum k f
go k v
kx f v
x DMap k f
l
  where
    go :: k v -> f v -> DMap k f -> DSum k f
    go :: k v -> f v -> DMap k f -> DSum k f
go k v
kx f v
x DMap k f
Tip = k v
kx k v -> f v -> DSum k f
forall k (tag :: k -> *) (f :: k -> *) (a :: k).
tag a -> f a -> DSum tag f
:=> f v
x
    go k v
_  f v
_ (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
_) = k v -> f v -> DMap k f -> DSum k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
k v -> f v -> DMap k f -> DSum k f
go k v
kx f v
x DMap k f
l

-- | /O(log n)/. The maximal key of the map. Calls 'error' is the map is empty.
findMax :: DMap k f -> DSum k f
findMax :: DMap k f -> DSum k f
findMax DMap k f
m = case DMap k f -> Maybe (DSum k f)
forall k (k :: k -> *) (f :: k -> *). DMap k f -> Maybe (DSum k f)
lookupMax DMap k f
m of
  Just DSum k f
x -> DSum k f
x
  Maybe (DSum k f)
Nothing -> [Char] -> DSum k f
forall a. HasCallStack => [Char] -> a
error [Char]
"Map.findMax: empty map has no maximal element"

lookupMax :: DMap k f -> Maybe (DSum k f)
lookupMax :: DMap k f -> Maybe (DSum k f)
lookupMax DMap k f
m = case DMap k f
m of
      DMap k f
Tip -> Maybe (DSum k f)
forall a. Maybe a
Nothing
      Bin Int
_ k v
kx f v
x DMap k f
_ DMap k f
r -> DSum k f -> Maybe (DSum k f)
forall a. a -> Maybe a
Just (DSum k f -> Maybe (DSum k f)) -> DSum k f -> Maybe (DSum k f)
forall a b. (a -> b) -> a -> b
$! k v -> f v -> DMap k f -> DSum k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
k v -> f v -> DMap k f -> DSum k f
go k v
kx f v
x DMap k f
r
  where
    go :: k v -> f v -> DMap k f -> DSum k f
    go :: k v -> f v -> DMap k f -> DSum k f
go k v
kx f v
x DMap k f
Tip = k v
kx k v -> f v -> DSum k f
forall k (tag :: k -> *) (f :: k -> *) (a :: k).
tag a -> f a -> DSum tag f
:=> f v
x
    go k v
_  f v
_ (Bin Int
_ k v
kx f v
x DMap k f
_ DMap k f
r) = k v -> f v -> DMap k f -> DSum k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
k v -> f v -> DMap k f -> DSum k f
go k v
kx f v
x DMap k f
r

-- | /O(log n)/. Delete the minimal key. Returns an empty map if the map is empty.
deleteMin :: DMap k f -> DMap k f
deleteMin :: DMap k f -> DMap k f
deleteMin (Bin Int
_ k v
_  f v
_ DMap k f
Tip DMap k f
r)  = DMap k f
r
deleteMin (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r)    = k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x (DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *). DMap k f -> DMap k f
deleteMin DMap k f
l) DMap k f
r
deleteMin DMap k f
Tip                 = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip

-- | /O(log n)/. Delete the maximal key. Returns an empty map if the map is empty.
deleteMax :: DMap k f -> DMap k f
deleteMax :: DMap k f -> DMap k f
deleteMax (Bin Int
_ k v
_  f v
_ DMap k f
l DMap k f
Tip)  = DMap k f
l
deleteMax (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r)    = k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x DMap k f
l (DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *). DMap k f -> DMap k f
deleteMax DMap k f
r)
deleteMax DMap k f
Tip                 = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip

-- | /O(log n)/. Update the value at the minimal key.
updateMinWithKey :: (forall v. k v -> f v -> Maybe (f v)) -> DMap k f -> DMap k f
updateMinWithKey :: (forall (v :: k). k v -> f v -> Maybe (f v))
-> DMap k f -> DMap k f
updateMinWithKey forall (v :: k). k v -> f v -> Maybe (f v)
f = DMap k f -> DMap k f
go
 where
    go :: DMap k f -> DMap k f
go (Bin Int
sx k v
kx f v
x DMap k f
Tip DMap k f
r) = case k v -> f v -> Maybe (f v)
forall (v :: k). k v -> f v -> Maybe (f v)
f k v
kx f v
x of
                                  Maybe (f v)
Nothing -> DMap k f
r
                                  Just f v
x' -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
x' DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip DMap k f
r
    go (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r)    = k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x (DMap k f -> DMap k f
go DMap k f
l) DMap k f
r
    go DMap k f
Tip                 = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip

-- | /O(log n)/. Update the value at the maximal key.
updateMaxWithKey :: (forall v. k v -> f v -> Maybe (f v)) -> DMap k f -> DMap k f
updateMaxWithKey :: (forall (v :: k). k v -> f v -> Maybe (f v))
-> DMap k f -> DMap k f
updateMaxWithKey forall (v :: k). k v -> f v -> Maybe (f v)
f = DMap k f -> DMap k f
go
 where
    go :: DMap k f -> DMap k f
go (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
Tip) = case k v -> f v -> Maybe (f v)
forall (v :: k). k v -> f v -> Maybe (f v)
f k v
kx f v
x of
                              Maybe (f v)
Nothing -> DMap k f
l
                              Just f v
x' -> Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx f v
x' DMap k f
l DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r)    = k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
balance k v
kx f v
x DMap k f
l (DMap k f -> DMap k f
go DMap k f
r)
    go DMap k f
Tip                 = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip

{--------------------------------------------------------------------
  Union.
--------------------------------------------------------------------}

-- | The union of a list of maps:
--   (@'unions' == 'Prelude.foldl' 'union' 'empty'@).
unions :: GCompare k => [DMap k f] -> DMap k f
unions :: [DMap k f] -> DMap k f
unions [DMap k f]
ts
  = (DMap k f -> DMap k f -> DMap k f)
-> DMap k f -> [DMap k f] -> DMap k f
forall a b. (a -> b -> a) -> a -> [b] -> a
foldlStrict DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
DMap k f -> DMap k f -> DMap k f
union DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
empty [DMap k f]
ts

-- | The union of a list of maps, with a combining operation:
--   (@'unionsWithKey' f == 'Prelude.foldl' ('unionWithKey' f) 'empty'@).
unionsWithKey :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> [DMap k f] -> DMap k f
unionsWithKey :: (forall (v :: k). k v -> f v -> f v -> f v)
-> [DMap k f] -> DMap k f
unionsWithKey forall (v :: k). k v -> f v -> f v -> f v
f [DMap k f]
ts
  = (DMap k f -> DMap k f -> DMap k f)
-> DMap k f -> [DMap k f] -> DMap k f
forall a b. (a -> b -> a) -> a -> [b] -> a
foldlStrict ((forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DMap k f -> DMap k f
unionWithKey forall (v :: k). k v -> f v -> f v -> f v
f) DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
empty [DMap k f]
ts

-- | /O(m*log(n\/m + 1)), m <= n/.
-- The expression (@'union' t1 t2@) takes the left-biased union of @t1@ and @t2@.
-- It prefers @t1@ when duplicate keys are encountered,
-- i.e. (@'union' == 'unionWith' 'const'@).
union :: GCompare k => DMap k f -> DMap k f -> DMap k f
union :: DMap k f -> DMap k f -> DMap k f
union DMap k f
t1 DMap k f
Tip  = DMap k f
t1
union DMap k f
t1 (Bin Int
_ k v
kx f v
x DMap k f
Tip DMap k f
Tip) = k v -> f v -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> f v -> DMap k f -> DMap k f
insertR k v
kx f v
x DMap k f
t1
union DMap k f
Tip DMap k f
t2  = DMap k f
t2
union (Bin Int
_ k v
kx f v
x DMap k f
Tip DMap k f
Tip) DMap k f
t2 = k v -> f v -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> f v -> DMap k f -> DMap k f
insert k v
kx f v
x DMap k f
t2
union t1 :: DMap k f
t1@(Bin Int
_ k v
k1 f v
x1 DMap k f
l1 DMap k f
r1) DMap k f
t2 = case k v -> DMap k f -> (DMap k f, DMap k f)
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> DMap k f -> (DMap k f, DMap k f)
split k v
k1 DMap k f
t2 of
  (DMap k f
l2, DMap k f
r2)
    | DMap k f
l1 DMap k f -> DMap k f -> Bool
forall a. a -> a -> Bool
`ptrEq` DMap k f
l1l2 Bool -> Bool -> Bool
&& DMap k f
r1 DMap k f -> DMap k f -> Bool
forall a. a -> a -> Bool
`ptrEq` DMap k f
r1r2 -> DMap k f
t1
    | Bool
otherwise -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
k1 f v
x1 DMap k f
l1l2 DMap k f
r1r2
    where !l1l2 :: DMap k f
l1l2 = DMap k f
l1 DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
DMap k f -> DMap k f -> DMap k f
`union` DMap k f
l2
          !r1r2 :: DMap k f
r1r2 = DMap k f
r1 DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
DMap k f -> DMap k f -> DMap k f
`union` DMap k f
r2

{--------------------------------------------------------------------
  Union with a combining function
--------------------------------------------------------------------}

-- | /O(n+m)/.
-- Union with a combining function.
unionWithKey :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> DMap k f -> DMap k f -> DMap k f
unionWithKey :: (forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DMap k f -> DMap k f
unionWithKey forall (v :: k). k v -> f v -> f v -> f v
_ DMap k f
t1 DMap k f
Tip  = DMap k f
t1
unionWithKey forall (v :: k). k v -> f v -> f v -> f v
_ DMap k f
Tip DMap k f
t2  = DMap k f
t2
unionWithKey forall (v :: k). k v -> f v -> f v -> f v
f (Bin Int
_ k v
k1 f v
x1 DMap k f
l1 DMap k f
r1) DMap k f
t2 = case k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
splitLookup k v
k1 DMap k f
t2 of
  (DMap k f
l2, Maybe (f v)
mx2, DMap k f
r2) -> case Maybe (f v)
mx2 of
      Maybe (f v)
Nothing -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
k1 f v
x1 DMap k f
l1l2 DMap k f
r1r2
      Just f v
x2 -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
k1 (k v -> f v -> f v -> f v
forall (v :: k). k v -> f v -> f v -> f v
f k v
k1 f v
x1 f v
x2) DMap k f
l1l2 DMap k f
r1r2
    where !l1l2 :: DMap k f
l1l2 = (forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DMap k f -> DMap k f
unionWithKey forall (v :: k). k v -> f v -> f v -> f v
f DMap k f
l1 DMap k f
l2
          !r1r2 :: DMap k f
r1r2 = (forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DMap k f -> DMap k f
unionWithKey forall (v :: k). k v -> f v -> f v -> f v
f DMap k f
r1 DMap k f
r2

{--------------------------------------------------------------------
  Difference
--------------------------------------------------------------------}

-- | /O(m * log (n\/m + 1)), m <= n/. Difference of two maps.
-- Return elements of the first map not existing in the second map.
difference :: GCompare k => DMap k f -> DMap k g -> DMap k f
difference :: DMap k f -> DMap k g -> DMap k f
difference DMap k f
Tip DMap k g
_   = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
difference DMap k f
t1 DMap k g
Tip  = DMap k f
t1
difference DMap k f
t1 (Bin Int
_ k v
k2 g v
_x2 DMap k g
l2 DMap k g
r2) = case k v -> DMap k f -> (DMap k f, DMap k f)
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> DMap k f -> (DMap k f, DMap k f)
split k v
k2 DMap k f
t1 of
  (DMap k f
l1, DMap k f
r1)
    | DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
t1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
l1l2 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
r1r2 -> DMap k f
t1
    | Bool
otherwise -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
merge DMap k f
l1l2 DMap k f
r1r2
    where
      !l1l2 :: DMap k f
l1l2 = DMap k f
l1 DMap k f -> DMap k g -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
DMap k f -> DMap k g -> DMap k f
`difference` DMap k g
l2
      !r1r2 :: DMap k f
r1r2 = DMap k f
r1 DMap k f -> DMap k g -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
DMap k f -> DMap k g -> DMap k f
`difference` DMap k g
r2

-- | /O(n+m)/. Difference with a combining function. When two equal keys are
-- encountered, the combining function is applied to the key and both values.
-- If it returns 'Nothing', the element is discarded (proper set difference). If
-- it returns (@'Just' y@), the element is updated with a new value @y@.
differenceWithKey :: GCompare k => (forall v. k v -> f v -> g v -> Maybe (f v)) -> DMap k f -> DMap k g -> DMap k f
differenceWithKey :: (forall (v :: k). k v -> f v -> g v -> Maybe (f v))
-> DMap k f -> DMap k g -> DMap k f
differenceWithKey forall (v :: k). k v -> f v -> g v -> Maybe (f v)
_ DMap k f
Tip DMap k g
_   = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
differenceWithKey forall (v :: k). k v -> f v -> g v -> Maybe (f v)
_ DMap k f
t1 DMap k g
Tip  = DMap k f
t1
differenceWithKey forall (v :: k). k v -> f v -> g v -> Maybe (f v)
f (Bin Int
_ k v
k1 f v
x1 DMap k f
l1 DMap k f
r1) DMap k g
t2 = case k v -> DMap k g -> (DMap k g, Maybe (g v), DMap k g)
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
splitLookup k v
k1 DMap k g
t2 of
  (DMap k g
l2, Maybe (g v)
mx2, DMap k g
r2) -> case Maybe (g v)
mx2 of
      Maybe (g v)
Nothing -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
k1 f v
x1 DMap k f
l1l2 DMap k f
r1r2
      Just g v
x2 -> case k v -> f v -> g v -> Maybe (f v)
forall (v :: k). k v -> f v -> g v -> Maybe (f v)
f k v
k1 f v
x1 g v
x2 of
        Maybe (f v)
Nothing -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
merge DMap k f
l1l2 DMap k f
r1r2
        Just f v
x1x2 -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
k1 f v
x1x2 DMap k f
l1l2 DMap k f
r1r2
    where !l1l2 :: DMap k f
l1l2 = (forall (v :: k). k v -> f v -> g v -> Maybe (f v))
-> DMap k f -> DMap k g -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> g v -> Maybe (f v))
-> DMap k f -> DMap k g -> DMap k f
differenceWithKey forall (v :: k). k v -> f v -> g v -> Maybe (f v)
f DMap k f
l1 DMap k g
l2
          !r1r2 :: DMap k f
r1r2 = (forall (v :: k). k v -> f v -> g v -> Maybe (f v))
-> DMap k f -> DMap k g -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> g v -> Maybe (f v))
-> DMap k f -> DMap k g -> DMap k f
differenceWithKey forall (v :: k). k v -> f v -> g v -> Maybe (f v)
f DMap k f
r1 DMap k g
r2

{--------------------------------------------------------------------
  Intersection
--------------------------------------------------------------------}

-- | /O(m * log (n\/m + 1), m <= n/. Intersection of two maps.
-- Return data in the first map for the keys existing in both maps.
-- (@'intersection' m1 m2 == 'intersectionWith' 'const' m1 m2@).
intersection :: GCompare k => DMap k f -> DMap k f -> DMap k f
intersection :: DMap k f -> DMap k f -> DMap k f
intersection DMap k f
Tip DMap k f
_ = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
intersection DMap k f
_ DMap k f
Tip = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
intersection t1 :: DMap k f
t1@(Bin Int
s1 k v
k1 f v
x1 DMap k f
l1 DMap k f
r1) DMap k f
t2 =
  let !(DMap k f
l2, Bool
found, DMap k f
r2) = k v -> DMap k f -> (DMap k f, Bool, DMap k f)
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> DMap k f -> (DMap k f, Bool, DMap k f)
splitMember k v
k1 DMap k f
t2
      !l1l2 :: DMap k f
l1l2 = DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
DMap k f -> DMap k f -> DMap k f
intersection DMap k f
l1 DMap k f
l2
      !r1r2 :: DMap k f
r1r2 = DMap k f -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
DMap k f -> DMap k f -> DMap k f
intersection DMap k f
r1 DMap k f
r2
  in if Bool
found
     then if DMap k f
l1l2 DMap k f -> DMap k f -> Bool
forall a. a -> a -> Bool
`ptrEq` DMap k f
l1 Bool -> Bool -> Bool
&& DMap k f
r1r2 DMap k f -> DMap k f -> Bool
forall a. a -> a -> Bool
`ptrEq` DMap k f
r1
          then DMap k f
t1
          else k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
k1 f v
x1 DMap k f
l1l2 DMap k f
r1r2
     else DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
merge DMap k f
l1l2 DMap k f
r1r2

-- | /O(m * log (n\/m + 1), m <= n/. Intersection with a combining function.
intersectionWithKey :: GCompare k => (forall v. k v -> f v -> g v -> h v) -> DMap k f -> DMap k g -> DMap k h
intersectionWithKey :: (forall (v :: k). k v -> f v -> g v -> h v)
-> DMap k f -> DMap k g -> DMap k h
intersectionWithKey forall (v :: k). k v -> f v -> g v -> h v
_ DMap k f
Tip DMap k g
_ = DMap k h
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
intersectionWithKey forall (v :: k). k v -> f v -> g v -> h v
_ DMap k f
_ DMap k g
Tip = DMap k h
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
intersectionWithKey forall (v :: k). k v -> f v -> g v -> h v
f (Bin Int
s1 k v
k1 f v
x1 DMap k f
l1 DMap k f
r1) DMap k g
t2 =
  let !(DMap k g
l2, Maybe (g v)
found, DMap k g
r2) = k v -> DMap k g -> (DMap k g, Maybe (g v), DMap k g)
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
splitLookup k v
k1 DMap k g
t2
      !l1l2 :: DMap k h
l1l2 = (forall (v :: k). k v -> f v -> g v -> h v)
-> DMap k f -> DMap k g -> DMap k h
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> g v -> h v)
-> DMap k f -> DMap k g -> DMap k h
intersectionWithKey forall (v :: k). k v -> f v -> g v -> h v
f DMap k f
l1 DMap k g
l2
      !r1r2 :: DMap k h
r1r2 = (forall (v :: k). k v -> f v -> g v -> h v)
-> DMap k f -> DMap k g -> DMap k h
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> g v -> h v)
-> DMap k f -> DMap k g -> DMap k h
intersectionWithKey forall (v :: k). k v -> f v -> g v -> h v
f DMap k f
r1 DMap k g
r2
  in case Maybe (g v)
found of
       Maybe (g v)
Nothing -> DMap k h -> DMap k h -> DMap k h
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
merge DMap k h
l1l2 DMap k h
r1r2
       Just g v
x2 -> k v -> h v -> DMap k h -> DMap k h -> DMap k h
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
k1 (k v -> f v -> g v -> h v
forall (v :: k). k v -> f v -> g v -> h v
f k v
k1 f v
x1 g v
x2) DMap k h
l1l2 DMap k h
r1r2

{--------------------------------------------------------------------
  Submap
--------------------------------------------------------------------}
-- | /O(n+m)/.
-- This function is defined as (@'isSubmapOf' = 'isSubmapOfBy' 'eqTagged')@).
--
isSubmapOf
  :: forall k f
  .  (GCompare k, Has' Eq k f)
  => DMap k f -> DMap k f -> Bool
isSubmapOf :: DMap k f -> DMap k f -> Bool
isSubmapOf DMap k f
m1 DMap k f
m2 = (forall (v :: k). k v -> k v -> f v -> f v -> Bool)
-> DMap k f -> DMap k f -> Bool
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
isSubmapOfBy (\k v
k k v
_ f v
x0 f v
x1 -> k v -> (Eq (f v) => Bool) -> Bool
forall k k' (c :: k -> Constraint) (g :: k' -> k) (f :: k' -> *)
       (a :: k') r.
Has' c f g =>
f a -> (c (g a) => r) -> r
has' @Eq @f k v
k (f v
x0 f v -> f v -> Bool
forall a. Eq a => a -> a -> Bool
== f v
x1)) DMap k f
m1 DMap k f
m2

{- | /O(n+m)/.
 The expression (@'isSubmapOfBy' f t1 t2@) returns 'True' if
 all keys in @t1@ are in tree @t2@, and when @f@ returns 'True' when
 applied to their respective keys and values.
-}
isSubmapOfBy :: GCompare k => (forall v. k v -> k v -> f v -> g v -> Bool) -> DMap k f -> DMap k g -> Bool
isSubmapOfBy :: (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
isSubmapOfBy forall (v :: k). k v -> k v -> f v -> g v -> Bool
f DMap k f
t1 DMap k g
t2
  = (DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
t1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= DMap k g -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k g
t2) Bool -> Bool -> Bool
&& ((forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
submap' forall (v :: k). k v -> k v -> f v -> g v -> Bool
f DMap k f
t1 DMap k g
t2)

submap' :: GCompare k => (forall v. k v -> k v -> f v -> g v -> Bool) -> DMap k f -> DMap k g -> Bool
submap' :: (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
submap' forall (v :: k). k v -> k v -> f v -> g v -> Bool
_ DMap k f
Tip DMap k g
_ = Bool
True
submap' forall (v :: k). k v -> k v -> f v -> g v -> Bool
_ DMap k f
_ DMap k g
Tip = Bool
False
submap' forall (v :: k). k v -> k v -> f v -> g v -> Bool
f (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r) DMap k g
t
  = case Maybe (k v, g v)
found of
      Maybe (k v, g v)
Nothing -> Bool
False
      Just (k v
ky, g v
y)  -> k v -> k v -> f v -> g v -> Bool
forall (v :: k). k v -> k v -> f v -> g v -> Bool
f k v
kx k v
ky f v
x g v
y Bool -> Bool -> Bool
&& (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
submap' forall (v :: k). k v -> k v -> f v -> g v -> Bool
f DMap k f
l DMap k g
lt Bool -> Bool -> Bool
&& (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
submap' forall (v :: k). k v -> k v -> f v -> g v -> Bool
f DMap k f
r DMap k g
gt
  where
    (DMap k g
lt,Maybe (k v, g v)
found,DMap k g
gt) = k v -> DMap k g -> (DMap k g, Maybe (k v, g v), DMap k g)
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> DMap k f -> (DMap k f, Maybe (k v, f v), DMap k f)
splitLookupWithKey k v
kx DMap k g
t

-- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal).
-- Defined as (@'isProperSubmapOf' = 'isProperSubmapOfBy' 'eqTagged'@).
isProperSubmapOf
  :: forall k f
  .  (GCompare k, Has' Eq k f)
  => DMap k f -> DMap k f -> Bool
isProperSubmapOf :: DMap k f -> DMap k f -> Bool
isProperSubmapOf DMap k f
m1 DMap k f
m2
  = (forall (v :: k). k v -> k v -> f v -> f v -> Bool)
-> DMap k f -> DMap k f -> Bool
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
isProperSubmapOfBy (\k v
k k v
_ f v
x0 f v
x1 -> k v -> (Eq (f v) => Bool) -> Bool
forall k k' (c :: k -> Constraint) (g :: k' -> k) (f :: k' -> *)
       (a :: k') r.
Has' c f g =>
f a -> (c (g a) => r) -> r
has' @Eq @f k v
k (f v
x0 f v -> f v -> Bool
forall a. Eq a => a -> a -> Bool
== f v
x1)) DMap k f
m1 DMap k f
m2

{- | /O(n+m)/. Is this a proper submap? (ie. a submap but not equal).
 The expression (@'isProperSubmapOfBy' f m1 m2@) returns 'True' when
 @m1@ and @m2@ are not equal,
 all keys in @m1@ are in @m2@, and when @f@ returns 'True' when
 applied to their respective keys and values.
-}
isProperSubmapOfBy :: GCompare k => (forall v. k v -> k v -> f v -> g v -> Bool) -> DMap k f -> DMap k g -> Bool
isProperSubmapOfBy :: (forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
isProperSubmapOfBy forall (v :: k). k v -> k v -> f v -> g v -> Bool
f DMap k f
t1 DMap k g
t2
  = (DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
t1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< DMap k g -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k g
t2) Bool -> Bool -> Bool
&& ((forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> k v -> f v -> g v -> Bool)
-> DMap k f -> DMap k g -> Bool
submap' forall (v :: k). k v -> k v -> f v -> g v -> Bool
f DMap k f
t1 DMap k g
t2)

{--------------------------------------------------------------------
  Filter and partition
--------------------------------------------------------------------}

-- | /O(n)/. Filter all keys\/values that satisfy the predicate.
filterWithKey :: GCompare k => (forall v. k v -> f v -> Bool) -> DMap k f -> DMap k f
filterWithKey :: (forall (v :: k). k v -> f v -> Bool) -> DMap k f -> DMap k f
filterWithKey forall (v :: k). k v -> f v -> Bool
p = DMap k f -> DMap k f
go
  where
    go :: DMap k f -> DMap k f
go DMap k f
Tip = DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go t :: DMap k f
t@(Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r)
      | k v -> f v -> Bool
forall (v :: k). k v -> f v -> Bool
p k v
kx f v
x    = if DMap k f
l' DMap k f -> DMap k f -> Bool
forall a. a -> a -> Bool
`ptrEq` DMap k f
l Bool -> Bool -> Bool
&& DMap k f
r' DMap k f -> DMap k f -> Bool
forall a. a -> a -> Bool
`ptrEq` DMap k f
r
                    then DMap k f
t
                    else k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
l' DMap k f
r'
      | Bool
otherwise = DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
merge DMap k f
l' DMap k f
r'
      where !l' :: DMap k f
l' = DMap k f -> DMap k f
go DMap k f
l
            !r' :: DMap k f
r' = DMap k f -> DMap k f
go DMap k f
r

-- | /O(n)/. Partition the map according to a predicate. The first
-- map contains all elements that satisfy the predicate, the second all
-- elements that fail the predicate. See also 'split'.
partitionWithKey :: GCompare k => (forall v. k v -> f v -> Bool) -> DMap k f -> (DMap k f, DMap k f)
partitionWithKey :: (forall (v :: k). k v -> f v -> Bool)
-> DMap k f -> (DMap k f, DMap k f)
partitionWithKey forall (v :: k). k v -> f v -> Bool
p0 DMap k f
m0 = (DMap k f :*: DMap k f) -> (DMap k f, DMap k f)
forall a b. (a :*: b) -> (a, b)
toPair ((forall (v :: k). k v -> f v -> Bool)
-> DMap k f -> DMap k f :*: DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Bool)
-> DMap k f -> DMap k f :*: DMap k f
go forall (v :: k). k v -> f v -> Bool
p0 DMap k f
m0)
  where
    go :: GCompare k => (forall v. k v -> f v -> Bool) -> DMap k f -> (DMap k f :*: DMap k f)
    go :: (forall (v :: k). k v -> f v -> Bool)
-> DMap k f -> DMap k f :*: DMap k f
go forall (v :: k). k v -> f v -> Bool
_ DMap k f
Tip = (DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip DMap k f -> DMap k f -> DMap k f :*: DMap k f
forall a b. a -> b -> a :*: b
:*: DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip)
    go forall (v :: k). k v -> f v -> Bool
p (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r)
      | k v -> f v -> Bool
forall (v :: k). k v -> f v -> Bool
p k v
kx f v
x    = (k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
l1 DMap k f
r1 DMap k f -> DMap k f -> DMap k f :*: DMap k f
forall a b. a -> b -> a :*: b
:*: DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
merge DMap k f
l2 DMap k f
r2)
      | Bool
otherwise = (DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
merge DMap k f
l1 DMap k f
r1 DMap k f -> DMap k f -> DMap k f :*: DMap k f
forall a b. a -> b -> a :*: b
:*: k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
l2 DMap k f
r2)
      where
        (DMap k f
l1 :*: DMap k f
l2) = (forall (v :: k). k v -> f v -> Bool)
-> DMap k f -> DMap k f :*: DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Bool)
-> DMap k f -> DMap k f :*: DMap k f
go forall (v :: k). k v -> f v -> Bool
p DMap k f
l
        (DMap k f
r1 :*: DMap k f
r2) = (forall (v :: k). k v -> f v -> Bool)
-> DMap k f -> DMap k f :*: DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Bool)
-> DMap k f -> DMap k f :*: DMap k f
go forall (v :: k). k v -> f v -> Bool
p DMap k f
r

-- | /O(n)/. Map values and collect the 'Just' results.
mapMaybe :: GCompare k => (forall v. f v -> Maybe (g v)) -> DMap k f -> DMap k g
mapMaybe :: (forall (v :: k). f v -> Maybe (g v)) -> DMap k f -> DMap k g
mapMaybe forall (v :: k). f v -> Maybe (g v)
f = (forall (v :: k). k v -> f v -> Maybe (g v))
-> DMap k f -> DMap k g
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Maybe (g v))
-> DMap k f -> DMap k g
mapMaybeWithKey ((f v -> Maybe (g v)) -> k v -> f v -> Maybe (g v)
forall a b. a -> b -> a
const f v -> Maybe (g v)
forall (v :: k). f v -> Maybe (g v)
f)

-- | /O(n)/. Map keys\/values and collect the 'Just' results.
mapMaybeWithKey :: GCompare k => (forall v. k v -> f v -> Maybe (g v)) -> DMap k f -> DMap k g
mapMaybeWithKey :: (forall (v :: k). k v -> f v -> Maybe (g v))
-> DMap k f -> DMap k g
mapMaybeWithKey forall (v :: k). k v -> f v -> Maybe (g v)
f = DMap k f -> DMap k g
go
  where
    go :: DMap k f -> DMap k g
go DMap k f
Tip = DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r) = case k v -> f v -> Maybe (g v)
forall (v :: k). k v -> f v -> Maybe (g v)
f k v
kx f v
x of
        Just g v
y  -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx g v
y (DMap k f -> DMap k g
go DMap k f
l) (DMap k f -> DMap k g
go DMap k f
r)
        Maybe (g v)
Nothing -> DMap k g -> DMap k g -> DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
merge (DMap k f -> DMap k g
go DMap k f
l) (DMap k f -> DMap k g
go DMap k f
r)

-- | /O(n)/. Map keys\/values and separate the 'Left' and 'Right' results.
mapEitherWithKey :: GCompare k =>
  (forall v. k v -> f v -> Either (g v) (h v)) -> DMap k f -> (DMap k g, DMap k h)
mapEitherWithKey :: (forall (v :: k). k v -> f v -> Either (g v) (h v))
-> DMap k f -> (DMap k g, DMap k h)
mapEitherWithKey forall (v :: k). k v -> f v -> Either (g v) (h v)
f0 = (DMap k g :*: DMap k h) -> (DMap k g, DMap k h)
forall a b. (a :*: b) -> (a, b)
toPair ((DMap k g :*: DMap k h) -> (DMap k g, DMap k h))
-> (DMap k f -> DMap k g :*: DMap k h)
-> DMap k f
-> (DMap k g, DMap k h)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall (v :: k). k v -> f v -> Either (g v) (h v))
-> DMap k f -> DMap k g :*: DMap k h
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Either (g v) (h v))
-> DMap k f -> DMap k g :*: DMap k h
go forall (v :: k). k v -> f v -> Either (g v) (h v)
f0
  where
    go :: GCompare k
       => (forall v. k v -> f v -> Either (g v) (h v))
       -> DMap k f -> (DMap k g :*: DMap k h)
    go :: (forall (v :: k). k v -> f v -> Either (g v) (h v))
-> DMap k f -> DMap k g :*: DMap k h
go forall (v :: k). k v -> f v -> Either (g v) (h v)
_ DMap k f
Tip = (DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip DMap k g -> DMap k h -> DMap k g :*: DMap k h
forall a b. a -> b -> a :*: b
:*: DMap k h
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip)
    go forall (v :: k). k v -> f v -> Either (g v) (h v)
f (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r) = case k v -> f v -> Either (g v) (h v)
forall (v :: k). k v -> f v -> Either (g v) (h v)
f k v
kx f v
x of
      Left g v
y  -> (k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx g v
y DMap k g
l1 DMap k g
r1 DMap k g -> DMap k h -> DMap k g :*: DMap k h
forall a b. a -> b -> a :*: b
:*: DMap k h -> DMap k h -> DMap k h
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
merge DMap k h
l2 DMap k h
r2)
      Right h v
z -> (DMap k g -> DMap k g -> DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *).
DMap k2 f -> DMap k2 f -> DMap k2 f
merge DMap k g
l1 DMap k g
r1 DMap k g -> DMap k h -> DMap k g :*: DMap k h
forall a b. a -> b -> a :*: b
:*: k v -> h v -> DMap k h -> DMap k h -> DMap k h
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx h v
z DMap k h
l2 DMap k h
r2)
      where
        (DMap k g
l1,DMap k h
l2) = (forall (v :: k). k v -> f v -> Either (g v) (h v))
-> DMap k f -> (DMap k g, DMap k h)
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Either (g v) (h v))
-> DMap k f -> (DMap k g, DMap k h)
mapEitherWithKey forall (v :: k). k v -> f v -> Either (g v) (h v)
f DMap k f
l
        (DMap k g
r1,DMap k h
r2) = (forall (v :: k). k v -> f v -> Either (g v) (h v))
-> DMap k f -> (DMap k g, DMap k h)
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *) (h :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> Either (g v) (h v))
-> DMap k f -> (DMap k g, DMap k h)
mapEitherWithKey forall (v :: k). k v -> f v -> Either (g v) (h v)
f DMap k f
r

{--------------------------------------------------------------------
  Mapping
--------------------------------------------------------------------}

-- | /O(n)/. Map a function over all values in the map.
map :: (forall v. f v -> g v) -> DMap k f -> DMap k g
map :: (forall (v :: k). f v -> g v) -> DMap k f -> DMap k g
map forall (v :: k). f v -> g v
f = DMap k f -> DMap k g
go
  where
    go :: DMap k f -> DMap k g
go DMap k f
Tip = DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
r) = Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx (f v -> g v
forall (v :: k). f v -> g v
f f v
x) (DMap k f -> DMap k g
go DMap k f
l) (DMap k f -> DMap k g
go DMap k f
r)

-- | /O(n)/.
-- @'ffor' == 'flip' 'map'@ except we cannot actually use
-- 'flip' because of the lack of impredicative types.
ffor :: DMap k f -> (forall v. f v -> g v) -> DMap k g
ffor :: DMap k f -> (forall (v :: k). f v -> g v) -> DMap k g
ffor DMap k f
m forall (v :: k). f v -> g v
f = (forall (v :: k). f v -> g v) -> DMap k f -> DMap k g
forall k (f :: k -> *) (g :: k -> *) (k :: k -> *).
(forall (v :: k). f v -> g v) -> DMap k f -> DMap k g
map forall (v :: k). f v -> g v
f DMap k f
m

-- | /O(n)/. Map a function over all values in the map.
mapWithKey :: (forall v. k v -> f v -> g v) -> DMap k f -> DMap k g
mapWithKey :: (forall (v :: k). k v -> f v -> g v) -> DMap k f -> DMap k g
mapWithKey forall (v :: k). k v -> f v -> g v
f = DMap k f -> DMap k g
go
  where
    go :: DMap k f -> DMap k g
go DMap k f
Tip = DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
r) = Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx (k v -> f v -> g v
forall (v :: k). k v -> f v -> g v
f k v
kx f v
x) (DMap k f -> DMap k g
go DMap k f
l) (DMap k f -> DMap k g
go DMap k f
r)

-- | /O(n)/.
-- @'fforWithKey' == 'flip' 'mapWithKey'@ except we cannot actually use
-- 'flip' because of the lack of impredicative types.
fforWithKey :: DMap k f -> (forall v. k v -> f v -> g v) -> DMap k g
fforWithKey :: DMap k f -> (forall (v :: k). k v -> f v -> g v) -> DMap k g
fforWithKey DMap k f
m forall (v :: k). k v -> f v -> g v
f = (forall (v :: k). k v -> f v -> g v) -> DMap k f -> DMap k g
forall k (k :: k -> *) (f :: k -> *) (g :: k -> *).
(forall (v :: k). k v -> f v -> g v) -> DMap k f -> DMap k g
mapWithKey forall (v :: k). k v -> f v -> g v
f DMap k f
m

-- | /O(n)/.
-- @'traverseWithKey' f m == 'fromList' <$> 'traverse' (\(k, v) -> (,) k <$> f k v) ('toList' m)@
-- That is, behaves exactly like a regular 'traverse' except that the traversing
-- function also has access to the key associated with a value.
traverseWithKey_ :: Applicative t => (forall v. k v -> f v -> t ()) -> DMap k f -> t ()
traverseWithKey_ :: (forall (v :: k). k v -> f v -> t ()) -> DMap k f -> t ()
traverseWithKey_ forall (v :: k). k v -> f v -> t ()
f = DMap k f -> t ()
go
  where
    go :: DMap k f -> t ()
go DMap k f
Tip = () -> t ()
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
    go (Bin Int
1 k v
k f v
v DMap k f
_ DMap k f
_) = k v -> f v -> t ()
forall (v :: k). k v -> f v -> t ()
f k v
k f v
v
    go (Bin Int
s k v
k f v
v DMap k f
l DMap k f
r) = DMap k f -> t ()
go DMap k f
l t () -> t () -> t ()
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> k v -> f v -> t ()
forall (v :: k). k v -> f v -> t ()
f k v
k f v
v t () -> t () -> t ()
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> DMap k f -> t ()
go DMap k f
r

-- | /O(n)/.
-- @'forWithKey' == 'flip' 'traverseWithKey'@ except we cannot actually use
-- 'flip' because of the lack of impredicative types.
forWithKey_ :: Applicative t => DMap k f -> (forall v. k v -> f v -> t ()) -> t ()
forWithKey_ :: DMap k f -> (forall (v :: k). k v -> f v -> t ()) -> t ()
forWithKey_ DMap k f
m forall (v :: k). k v -> f v -> t ()
f = (forall (v :: k). k v -> f v -> t ()) -> DMap k f -> t ()
forall k (t :: * -> *) (k :: k -> *) (f :: k -> *).
Applicative t =>
(forall (v :: k). k v -> f v -> t ()) -> DMap k f -> t ()
traverseWithKey_ forall (v :: k). k v -> f v -> t ()
f DMap k f
m

-- | /O(n)/.
-- @'traverseWithKey' f m == 'fromList' <$> 'traverse' (\(k, v) -> (,) k <$> f k v) ('toList' m)@
-- That is, behaves exactly like a regular 'traverse' except that the traversing
-- function also has access to the key associated with a value.
traverseWithKey :: Applicative t => (forall v. k v -> f v -> t (g v)) -> DMap k f -> t (DMap k g)
traverseWithKey :: (forall (v :: k). k v -> f v -> t (g v))
-> DMap k f -> t (DMap k g)
traverseWithKey forall (v :: k). k v -> f v -> t (g v)
f = DMap k f -> t (DMap k g)
go
  where
    go :: DMap k f -> t (DMap k g)
go DMap k f
Tip = DMap k g -> t (DMap k g)
forall (f :: * -> *) a. Applicative f => a -> f a
pure DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go (Bin Int
1 k v
k f v
v DMap k f
_ DMap k f
_) = (\g v
v' -> Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
1 k v
k g v
v' DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip) (g v -> DMap k g) -> t (g v) -> t (DMap k g)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k v -> f v -> t (g v)
forall (v :: k). k v -> f v -> t (g v)
f k v
k f v
v
    go (Bin Int
s k v
k f v
v DMap k f
l DMap k f
r) = (g v -> DMap k g -> DMap k g -> DMap k g)
-> DMap k g -> g v -> DMap k g -> DMap k g
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
s k v
k) (DMap k g -> g v -> DMap k g -> DMap k g)
-> t (DMap k g) -> t (g v -> DMap k g -> DMap k g)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> DMap k f -> t (DMap k g)
go DMap k f
l t (g v -> DMap k g -> DMap k g)
-> t (g v) -> t (DMap k g -> DMap k g)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> k v -> f v -> t (g v)
forall (v :: k). k v -> f v -> t (g v)
f k v
k f v
v t (DMap k g -> DMap k g) -> t (DMap k g) -> t (DMap k g)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> DMap k f -> t (DMap k g)
go DMap k f
r

-- | /O(n)/.
-- @'forWithKey' == 'flip' 'traverseWithKey'@ except we cannot actually use
-- 'flip' because of the lack of impredicative types.
forWithKey :: Applicative t => DMap k f -> (forall v. k v -> f v -> t (g v)) -> t (DMap k g)
forWithKey :: DMap k f
-> (forall (v :: k). k v -> f v -> t (g v)) -> t (DMap k g)
forWithKey DMap k f
m forall (v :: k). k v -> f v -> t (g v)
f = (forall (v :: k). k v -> f v -> t (g v))
-> DMap k f -> t (DMap k g)
forall k (t :: * -> *) (k :: k -> *) (f :: k -> *) (g :: k -> *).
Applicative t =>
(forall (v :: k). k v -> f v -> t (g v))
-> DMap k f -> t (DMap k g)
traverseWithKey forall (v :: k). k v -> f v -> t (g v)
f DMap k f
m

-- | /O(n)/. The function 'mapAccumLWithKey' threads an accumulating
-- argument through the map in ascending order of keys.
mapAccumLWithKey :: (forall v. a -> k v -> f v -> (a, g v)) -> a -> DMap k f -> (a, DMap k g)
mapAccumLWithKey :: (forall (v :: k). a -> k v -> f v -> (a, g v))
-> a -> DMap k f -> (a, DMap k g)
mapAccumLWithKey forall (v :: k). a -> k v -> f v -> (a, g v)
f = a -> DMap k f -> (a, DMap k g)
go
  where
    go :: a -> DMap k f -> (a, DMap k g)
go a
a DMap k f
Tip               = (a
a,DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip)
    go a
a (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
r) =
                 let (a
a1,DMap k g
l') = a -> DMap k f -> (a, DMap k g)
go a
a DMap k f
l
                     (a
a2,g v
x') = a -> k v -> f v -> (a, g v)
forall (v :: k). a -> k v -> f v -> (a, g v)
f a
a1 k v
kx f v
x
                     (a
a3,DMap k g
r') = a -> DMap k f -> (a, DMap k g)
go a
a2 DMap k f
r
                 in (a
a3,Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx g v
x' DMap k g
l' DMap k g
r')

-- | /O(n)/. The function 'mapAccumRWithKey' threads an accumulating
-- argument through the map in descending order of keys.
mapAccumRWithKey :: (forall v. a -> k v -> f v -> (a, g v)) -> a -> DMap k f -> (a, DMap k g)
mapAccumRWithKey :: (forall (v :: k). a -> k v -> f v -> (a, g v))
-> a -> DMap k f -> (a, DMap k g)
mapAccumRWithKey forall (v :: k). a -> k v -> f v -> (a, g v)
f = a -> DMap k f -> (a, DMap k g)
go
  where
    go :: a -> DMap k f -> (a, DMap k g)
go a
a DMap k f
Tip = (a
a,DMap k g
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip)
    go a
a (Bin Int
sx k v
kx f v
x DMap k f
l DMap k f
r) =
                 let (a
a1,DMap k g
r') = a -> DMap k f -> (a, DMap k g)
go a
a DMap k f
r
                     (a
a2,g v
x') = a -> k v -> f v -> (a, g v)
forall (v :: k). a -> k v -> f v -> (a, g v)
f a
a1 k v
kx f v
x
                     (a
a3,DMap k g
l') = a -> DMap k f -> (a, DMap k g)
go a
a2 DMap k f
l
                 in (a
a3,Int -> k v -> g v -> DMap k g -> DMap k g -> DMap k g
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sx k v
kx g v
x' DMap k g
l' DMap k g
r')

-- | /O(n*log n)/.
-- @'mapKeysWith' c f s@ is the map obtained by applying @f@ to each key of @s@.
--
-- The size of the result may be smaller if @f@ maps two or more distinct
-- keys to the same new key.  In this case the associated values will be
-- combined using @c@.
mapKeysWith :: GCompare k2 => (forall v. k2 v -> f v -> f v -> f v) -> (forall v. k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
mapKeysWith :: (forall (v :: k). k2 v -> f v -> f v -> f v)
-> (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
mapKeysWith forall (v :: k). k2 v -> f v -> f v -> f v
c forall (v :: k). k1 v -> k2 v
f = (forall (v :: k). k2 v -> f v -> f v -> f v)
-> [DSum k2 f] -> DMap k2 f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> [DSum k f] -> DMap k f
fromListWithKey forall (v :: k). k2 v -> f v -> f v -> f v
c ([DSum k2 f] -> DMap k2 f)
-> (DMap k1 f -> [DSum k2 f]) -> DMap k1 f -> DMap k2 f
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (DSum k1 f -> DSum k2 f) -> [DSum k1 f] -> [DSum k2 f]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map DSum k1 f -> DSum k2 f
fFirst ([DSum k1 f] -> [DSum k2 f])
-> (DMap k1 f -> [DSum k1 f]) -> DMap k1 f -> [DSum k2 f]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DMap k1 f -> [DSum k1 f]
forall k (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
toList
    where fFirst :: DSum k1 f -> DSum k2 f
fFirst (k1 a
x :=> f a
y) = (k1 a -> k2 a
forall (v :: k). k1 v -> k2 v
f k1 a
x k2 a -> f a -> DSum k2 f
forall k (tag :: k -> *) (f :: k -> *) (a :: k).
tag a -> f a -> DSum tag f
:=> f a
y)


-- | /O(n)/.
-- @'mapKeysMonotonic' f s == 'mapKeys' f s@, but works only when @f@
-- is strictly monotonic.
-- That is, for any values @x@ and @y@, if @x@ < @y@ then @f x@ < @f y@.
-- /The precondition is not checked./
-- Semi-formally, we have:
--
-- > and [x < y ==> f x < f y | x <- ls, y <- ls]
-- >                     ==> mapKeysMonotonic f s == mapKeys f s
-- >     where ls = keys s
--
-- This means that @f@ maps distinct original keys to distinct resulting keys.
-- This function has better performance than 'mapKeys'.
mapKeysMonotonic :: (forall v. k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
mapKeysMonotonic :: (forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
mapKeysMonotonic forall (v :: k). k1 v -> k2 v
_ DMap k1 f
Tip = DMap k2 f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
mapKeysMonotonic forall (v :: k). k1 v -> k2 v
f (Bin Int
sz k1 v
k f v
x DMap k1 f
l DMap k1 f
r) =
    Int -> k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
forall k (k :: k -> *) (v :: k) (f :: k -> *).
Int -> k v -> f v -> DMap k f -> DMap k f -> DMap k f
Bin Int
sz (k1 v -> k2 v
forall (v :: k). k1 v -> k2 v
f k1 v
k) f v
x ((forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
forall k (k1 :: k -> *) (k2 :: k -> *) (f :: k -> *).
(forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
mapKeysMonotonic forall (v :: k). k1 v -> k2 v
f DMap k1 f
l) ((forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
forall k (k1 :: k -> *) (k2 :: k -> *) (f :: k -> *).
(forall (v :: k). k1 v -> k2 v) -> DMap k1 f -> DMap k2 f
mapKeysMonotonic forall (v :: k). k1 v -> k2 v
f DMap k1 f
r)

{--------------------------------------------------------------------
  Folds
--------------------------------------------------------------------}

-- | /O(n)/. Fold the keys and values in the map, such that
-- @'foldWithKey' f z == 'Prelude.foldr' ('uncurry' f) z . 'toAscList'@.
--
-- This is identical to 'foldrWithKey', and you should use that one instead of
-- this one.  This name is kept for backward compatibility.
foldWithKey :: (forall v. k v -> f v -> b -> b) -> b -> DMap k f -> b
foldWithKey :: (forall (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
foldWithKey = (forall (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
forall k (k :: k -> *) (f :: k -> *) b.
(forall (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
foldrWithKey
{-# DEPRECATED foldWithKey "Use foldrWithKey instead" #-}

-- | /O(n)/. Post-order fold.  The function will be applied from the lowest
-- value to the highest.
foldrWithKey :: (forall v. k v -> f v -> b -> b) -> b -> DMap k f -> b
foldrWithKey :: (forall (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
foldrWithKey forall (v :: k). k v -> f v -> b -> b
f = b -> DMap k f -> b
go
  where
    go :: b -> DMap k f -> b
go b
z DMap k f
Tip              = b
z
    go b
z (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r) = b -> DMap k f -> b
go (k v -> f v -> b -> b
forall (v :: k). k v -> f v -> b -> b
f k v
kx f v
x (b -> DMap k f -> b
go b
z DMap k f
r)) DMap k f
l

-- | /O(n)/. Pre-order fold.  The function will be applied from the highest
-- value to the lowest.
foldlWithKey :: (forall v. b -> k v -> f v -> b) -> b -> DMap k f -> b
foldlWithKey :: (forall (v :: k). b -> k v -> f v -> b) -> b -> DMap k f -> b
foldlWithKey forall (v :: k). b -> k v -> f v -> b
f = b -> DMap k f -> b
go
  where
    go :: b -> DMap k f -> b
go b
z DMap k f
Tip              = b
z
    go b
z (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r) = b -> DMap k f -> b
go (b -> k v -> f v -> b
forall (v :: k). b -> k v -> f v -> b
f (b -> DMap k f -> b
go b
z DMap k f
l) k v
kx f v
x) DMap k f
r

{-
-- | /O(n)/. A strict version of 'foldlWithKey'.
foldlWithKey' :: (b -> k -> a -> b) -> b -> DMap k -> b
foldlWithKey' f = go
  where
    go z Tip              = z
    go z (Bin _ kx x l r) = z `seq` go (f (go z l) kx x) r
-}

{--------------------------------------------------------------------
  List variations
--------------------------------------------------------------------}

-- | /O(n)/. Return all keys of the map in ascending order.
--
-- > keys (fromList [(5,"a"), (3,"b")]) == [3,5]
-- > keys empty == []

keys  :: DMap k f -> [Some k]
keys :: DMap k f -> [Some k]
keys DMap k f
m
  = [k a -> Some k
forall k (tag :: k -> *) (a :: k). tag a -> Some tag
mkSome k a
k | (k a
k :=> f a
_) <- DMap k f -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
assocs DMap k f
m]

-- | /O(n)/. Return all key\/value pairs in the map in ascending key order.
assocs :: DMap k f -> [DSum k f]
assocs :: DMap k f -> [DSum k f]
assocs DMap k f
m
  = DMap k f -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
toList DMap k f
m

{--------------------------------------------------------------------
  Lists
  use [foldlStrict] to reduce demand on the control-stack
--------------------------------------------------------------------}

-- | /O(n*log n)/. Build a map from a list of key\/value pairs. See also 'fromAscList'.
-- If the list contains more than one value for the same key, the last value
-- for the key is retained.
fromList :: GCompare k => [DSum k f] -> DMap k f
fromList :: [DSum k f] -> DMap k f
fromList [DSum k f]
xs
  = (DMap k f -> DSum k f -> DMap k f)
-> DMap k f -> [DSum k f] -> DMap k f
forall a b. (a -> b -> a) -> a -> [b] -> a
foldlStrict DMap k f -> DSum k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
DMap k f -> DSum k f -> DMap k f
ins DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
empty [DSum k f]
xs
  where
    ins :: GCompare k => DMap k f -> DSum k f -> DMap k f
    ins :: DMap k f -> DSum k f -> DMap k f
ins DMap k f
t (k a
k :=> f a
x) = k a -> f a -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
k v -> f v -> DMap k f -> DMap k f
insert k a
k f a
x DMap k f
t

-- | /O(n*log n)/. Build a map from a list of key\/value pairs with a combining function. See also 'fromAscListWithKey'.
fromListWithKey :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> [DSum k f] -> DMap k f
fromListWithKey :: (forall (v :: k). k v -> f v -> f v -> f v)
-> [DSum k f] -> DMap k f
fromListWithKey forall (v :: k). k v -> f v -> f v -> f v
f [DSum k f]
xs
  = (DMap k f -> DSum k f -> DMap k f)
-> DMap k f -> [DSum k f] -> DMap k f
forall a b. (a -> b -> a) -> a -> [b] -> a
foldlStrict ((forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DSum k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DSum k f -> DMap k f
ins forall (v :: k). k v -> f v -> f v -> f v
f) DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
empty [DSum k f]
xs
  where
    ins :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> DMap k f -> DSum k f -> DMap k f
    ins :: (forall (v :: k). k v -> f v -> f v -> f v)
-> DMap k f -> DSum k f -> DMap k f
ins forall (v :: k). k v -> f v -> f v -> f v
f DMap k f
t (k a
k :=> f a
x) = (k a -> f a -> f a -> f a) -> k a -> f a -> DMap k f -> DMap k f
forall k (k :: k -> *) (f :: k -> *) (v :: k).
GCompare k =>
(k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f
insertWithKey k a -> f a -> f a -> f a
forall (v :: k). k v -> f v -> f v -> f v
f k a
k f a
x DMap k f
t

-- | /O(n)/. Convert to a list of key\/value pairs.
toList :: DMap k f -> [DSum k f]
toList :: DMap k f -> [DSum k f]
toList DMap k f
t      = DMap k f -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
toAscList DMap k f
t

-- | /O(n)/. Convert to an ascending list.
toAscList :: DMap k f -> [DSum k f]
toAscList :: DMap k f -> [DSum k f]
toAscList DMap k f
t   = (forall (v :: k). k v -> f v -> [DSum k f] -> [DSum k f])
-> [DSum k f] -> DMap k f -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *) b.
(forall (v :: k). k v -> f v -> b -> b) -> b -> DMap k f -> b
foldrWithKey (\k v
k f v
x [DSum k f]
xs -> (k v
k k v -> f v -> DSum k f
forall k (tag :: k -> *) (f :: k -> *) (a :: k).
tag a -> f a -> DSum tag f
:=> f v
x)DSum k f -> [DSum k f] -> [DSum k f]
forall a. a -> [a] -> [a]
:[DSum k f]
xs) [] DMap k f
t

-- | /O(n)/. Convert to a descending list.
toDescList :: DMap k f -> [DSum k f]
toDescList :: DMap k f -> [DSum k f]
toDescList DMap k f
t  = (forall (v :: k). [DSum k f] -> k v -> f v -> [DSum k f])
-> [DSum k f] -> DMap k f -> [DSum k f]
forall k b (k :: k -> *) (f :: k -> *).
(forall (v :: k). b -> k v -> f v -> b) -> b -> DMap k f -> b
foldlWithKey (\[DSum k f]
xs k v
k f v
x -> (k v
k k v -> f v -> DSum k f
forall k (tag :: k -> *) (f :: k -> *) (a :: k).
tag a -> f a -> DSum tag f
:=> f v
x)DSum k f -> [DSum k f] -> [DSum k f]
forall a. a -> [a] -> [a]
:[DSum k f]
xs) [] DMap k f
t

{--------------------------------------------------------------------
  Building trees from ascending/descending lists can be done in linear time.

  Note that if [xs] is ascending that:
    fromAscList xs       == fromList xs
    fromAscListWith f xs == fromListWith f xs
--------------------------------------------------------------------}

-- | /O(n)/. Build a map from an ascending list in linear time.
-- /The precondition (input list is ascending) is not checked./
fromAscList :: GEq k => [DSum k f] -> DMap k f
fromAscList :: [DSum k f] -> DMap k f
fromAscList [DSum k f]
xs
  = (forall (v :: k). k v -> f v -> f v -> f v)
-> [DSum k f] -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GEq k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> [DSum k f] -> DMap k f
fromAscListWithKey (\k v
_ f v
x f v
_ -> f v
x) [DSum k f]
xs

-- | /O(n)/. Build a map from an ascending list in linear time with a
-- combining function for equal keys.
-- /The precondition (input list is ascending) is not checked./
fromAscListWithKey :: GEq k => (forall v. k v -> f v -> f v -> f v) -> [DSum k f] -> DMap k f
fromAscListWithKey :: (forall (v :: k). k v -> f v -> f v -> f v)
-> [DSum k f] -> DMap k f
fromAscListWithKey forall (v :: k). k v -> f v -> f v -> f v
f [DSum k f]
xs
  = [DSum k f] -> DMap k f
forall k (k :: k -> *) (f :: k -> *). [DSum k f] -> DMap k f
fromDistinctAscList ((k Any -> f Any -> f Any -> f Any) -> [DSum k f] -> [DSum k f]
combineEq k Any -> f Any -> f Any -> f Any
forall (v :: k). k v -> f v -> f v -> f v
f [DSum k f]
xs)
  where
  -- [combineEq f xs] combines equal elements with function [f] in an ordered list [xs]
  combineEq :: (k Any -> f Any -> f Any -> f Any) -> [DSum k f] -> [DSum k f]
combineEq k Any -> f Any -> f Any -> f Any
_ [DSum k f]
xs'
    = case [DSum k f]
xs' of
        []     -> []
        [DSum k f
x]    -> [DSum k f
x]
        (DSum k f
x:[DSum k f]
xx) -> (forall (v :: k). k v -> f v -> f v -> f v)
-> DSum k f -> [DSum k f] -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *).
GEq k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> DSum k f -> [DSum k f] -> [DSum k f]
combineEq' forall (v :: k). k v -> f v -> f v -> f v
f DSum k f
x [DSum k f]
xx

  combineEq' :: GEq k => (forall v. k v -> f v -> f v -> f v) -> DSum k f -> [DSum k f] -> [DSum k f]
  combineEq' :: (forall (v :: k). k v -> f v -> f v -> f v)
-> DSum k f -> [DSum k f] -> [DSum k f]
combineEq' forall (v :: k). k v -> f v -> f v -> f v
f DSum k f
z [] = [DSum k f
z]
  combineEq' forall (v :: k). k v -> f v -> f v -> f v
f z :: DSum k f
z@(k a
kz :=> f a
zz) (x :: DSum k f
x@(k a
kx :=> f a
xx):[DSum k f]
xs') =
    case k a -> k a -> Maybe (a :~: a)
forall k (f :: k -> *) (a :: k) (b :: k).
GEq f =>
f a -> f b -> Maybe (a :~: b)
geq k a
kx k a
kz of
        Just a :~: a
Refl   -> let yy :: f a
yy = k a -> f a -> f a -> f a
forall (v :: k). k v -> f v -> f v -> f v
f k a
kx f a
xx f a
f a
zz in (forall (v :: k). k v -> f v -> f v -> f v)
-> DSum k f -> [DSum k f] -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *).
GEq k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> DSum k f -> [DSum k f] -> [DSum k f]
combineEq' forall (v :: k). k v -> f v -> f v -> f v
f (k a
kx k a -> f a -> DSum k f
forall k (tag :: k -> *) (f :: k -> *) (a :: k).
tag a -> f a -> DSum tag f
:=> f a
yy) [DSum k f]
xs'
        Maybe (a :~: a)
Nothing     -> DSum k f
z DSum k f -> [DSum k f] -> [DSum k f]
forall a. a -> [a] -> [a]
: (forall (v :: k). k v -> f v -> f v -> f v)
-> DSum k f -> [DSum k f] -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *).
GEq k =>
(forall (v :: k). k v -> f v -> f v -> f v)
-> DSum k f -> [DSum k f] -> [DSum k f]
combineEq' forall (v :: k). k v -> f v -> f v -> f v
f DSum k f
x [DSum k f]
xs'


-- | /O(n)/. Build a map from an ascending list of distinct elements in linear time.
-- /The precondition is not checked./
fromDistinctAscList :: [DSum k f] -> DMap k f
fromDistinctAscList :: [DSum k f] -> DMap k f
fromDistinctAscList [DSum k f]
xs
  = (DMap k f -> [DSum k f] -> DMap k f)
-> Int -> [DSum k f] -> DMap k f
forall k (k :: k -> *) (f :: k -> *) b.
(DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
build DMap k f -> [DSum k f] -> DMap k f
forall a b. a -> b -> a
const ([DSum k f] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [DSum k f]
xs) [DSum k f]
xs
  where
    -- 1) use continutations so that we use heap space instead of stack space.
    -- 2) special case for n==5 to build bushier trees.

    build :: (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
    build :: (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
build DMap k f -> [DSum k f] -> b
c Int
0 [DSum k f]
xs'  = DMap k f -> [DSum k f] -> b
c DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip [DSum k f]
xs'
    build DMap k f -> [DSum k f] -> b
c Int
5 [DSum k f]
xs'  = case [DSum k f]
xs' of
                       ((k a
k1:=>f a
x1):(k a
k2:=>f a
x2):(k a
k3:=>f a
x3):(k a
k4:=>f a
x4):(k a
k5:=>f a
x5):[DSum k f]
xx)
                            -> DMap k f -> [DSum k f] -> b
c (k a -> f a -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
bin k a
k4 f a
x4 (k a -> f a -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
bin k a
k2 f a
x2 (k a -> f a -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k a
k1 f a
x1) (k a -> f a -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k a
k3 f a
x3)) (k a -> f a -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f
singleton k a
k5 f a
x5)) [DSum k f]
xx
                       [DSum k f]
_ -> [Char] -> b
forall a. HasCallStack => [Char] -> a
error [Char]
"fromDistinctAscList build"
    build DMap k f -> [DSum k f] -> b
c Int
n [DSum k f]
xs'  = Int -> b -> b
seq Int
nr (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$ (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
forall k (k :: k -> *) (f :: k -> *) b.
(DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
build (Int -> (DMap k f -> [DSum k f] -> b) -> DMap k f -> [DSum k f] -> b
forall k (k :: k -> *) (f :: k -> *) b.
Int -> (DMap k f -> [DSum k f] -> b) -> DMap k f -> [DSum k f] -> b
buildR Int
nr DMap k f -> [DSum k f] -> b
c) Int
nl [DSum k f]
xs'
                   where
                     nl :: Int
nl = Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
                     nr :: Int
nr = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
nl Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1

    buildR :: Int -> (DMap k f -> [DSum k f] -> b) -> DMap k f -> [DSum k f] -> b
    buildR :: Int -> (DMap k f -> [DSum k f] -> b) -> DMap k f -> [DSum k f] -> b
buildR Int
n DMap k f -> [DSum k f] -> b
c DMap k f
l ((k a
k:=>f a
x):[DSum k f]
ys) = (DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
forall k (k :: k -> *) (f :: k -> *) b.
(DMap k f -> [DSum k f] -> b) -> Int -> [DSum k f] -> b
build (DMap k f
-> k a
-> f a
-> (DMap k f -> [DSum k f] -> b)
-> DMap k f
-> [DSum k f]
-> b
forall k (k :: k -> *) (f :: k -> *) (v :: k) a b.
DMap k f
-> k v -> f v -> (DMap k f -> a -> b) -> DMap k f -> a -> b
buildB DMap k f
l k a
k f a
x DMap k f -> [DSum k f] -> b
c) Int
n [DSum k f]
ys
    buildR Int
_ DMap k f -> [DSum k f] -> b
_ DMap k f
_ []           = [Char] -> b
forall a. HasCallStack => [Char] -> a
error [Char]
"fromDistinctAscList buildR []"

    buildB :: DMap k f -> k v -> f v -> (DMap k f -> a -> b) -> DMap k f -> a -> b
    buildB :: DMap k f
-> k v -> f v -> (DMap k f -> a -> b) -> DMap k f -> a -> b
buildB DMap k f
l k v
k f v
x DMap k f -> a -> b
c DMap k f
r a
zs       = DMap k f -> a -> b
c (k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
bin k v
k f v
x DMap k f
l DMap k f
r) a
zs

{--------------------------------------------------------------------
  Split
--------------------------------------------------------------------}

-- | /O(log n)/. The expression (@'split' k map@) is a pair @(map1,map2)@ where
-- the keys in @map1@ are smaller than @k@ and the keys in @map2@ larger than @k@.
-- Any key equal to @k@ is found in neither @map1@ nor @map2@.
split :: forall k f v. GCompare k => k v -> DMap k f -> (DMap k f, DMap k f)
split :: k v -> DMap k f -> (DMap k f, DMap k f)
split k v
k = (DMap k f :*: DMap k f) -> (DMap k f, DMap k f)
forall a b. (a :*: b) -> (a, b)
toPair ((DMap k f :*: DMap k f) -> (DMap k f, DMap k f))
-> (DMap k f -> DMap k f :*: DMap k f)
-> DMap k f
-> (DMap k f, DMap k f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DMap k f -> DMap k f :*: DMap k f
go
  where
    go :: DMap k f -> (DMap k f :*: DMap k f)
    go :: DMap k f -> DMap k f :*: DMap k f
go DMap k f
Tip              = (DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip DMap k f -> DMap k f -> DMap k f :*: DMap k f
forall a b. a -> b -> a :*: b
:*: DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip)
    go (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r) = case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
          GOrdering v v
GLT -> let !(DMap k f
lt :*: DMap k f
gt) = DMap k f -> DMap k f :*: DMap k f
go DMap k f
l in (DMap k f
lt DMap k f -> DMap k f -> DMap k f :*: DMap k f
forall a b. a -> b -> a :*: b
:*: k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
gt DMap k f
r)
          GOrdering v v
GGT -> let !(DMap k f
lt :*: DMap k f
gt) = DMap k f -> DMap k f :*: DMap k f
go DMap k f
r in (k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
l DMap k f
lt DMap k f -> DMap k f -> DMap k f :*: DMap k f
forall a b. a -> b -> a :*: b
:*: DMap k f
gt)
          GOrdering v v
GEQ -> (DMap k f
l DMap k f -> DMap k f -> DMap k f :*: DMap k f
forall a b. a -> b -> a :*: b
:*: DMap k f
r)
{-# INLINABLE split #-}

-- | /O(log n)/. The expression (@'splitLookup' k map@) splits a map just
-- like 'split' but also returns @'lookup' k map@.
splitLookup :: forall k f v. GCompare k => k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
splitLookup :: k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)
splitLookup k v
k = Triple' (DMap k f) (Maybe (f v)) (DMap k f)
-> (DMap k f, Maybe (f v), DMap k f)
forall a b c. Triple' a b c -> (a, b, c)
toTriple (Triple' (DMap k f) (Maybe (f v)) (DMap k f)
 -> (DMap k f, Maybe (f v), DMap k f))
-> (DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f))
-> DMap k f
-> (DMap k f, Maybe (f v), DMap k f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
go
  where
    go :: DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
    go :: DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
go DMap k f
Tip              = DMap k f
-> Maybe (f v)
-> DMap k f
-> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip Maybe (f v)
forall a. Maybe a
Nothing DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r) = case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
      GOrdering v v
GLT -> let !(Triple' DMap k f
lt Maybe (f v)
z DMap k f
gt) = DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
go DMap k f
l in DMap k f
-> Maybe (f v)
-> DMap k f
-> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' DMap k f
lt Maybe (f v)
z (k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
gt DMap k f
r)
      GOrdering v v
GGT -> let !(Triple' DMap k f
lt Maybe (f v)
z DMap k f
gt) = DMap k f -> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
go DMap k f
r in DMap k f
-> Maybe (f v)
-> DMap k f
-> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' (k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
l DMap k f
lt) Maybe (f v)
z DMap k f
gt
      GOrdering v v
GEQ -> DMap k f
-> Maybe (f v)
-> DMap k f
-> Triple' (DMap k f) (Maybe (f v)) (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' DMap k f
l (f v -> Maybe (f v)
forall a. a -> Maybe a
Just f v
x) DMap k f
r

-- | /O(log n)/. The expression (@'splitMember' k map@) splits a map just
-- like 'split' but also returns @'member' k map@.
splitMember :: forall k f v. GCompare k => k v -> DMap k f -> (DMap k f, Bool, DMap k f)
splitMember :: k v -> DMap k f -> (DMap k f, Bool, DMap k f)
splitMember k v
k = Triple' (DMap k f) Bool (DMap k f) -> (DMap k f, Bool, DMap k f)
forall a b c. Triple' a b c -> (a, b, c)
toTriple (Triple' (DMap k f) Bool (DMap k f) -> (DMap k f, Bool, DMap k f))
-> (DMap k f -> Triple' (DMap k f) Bool (DMap k f))
-> DMap k f
-> (DMap k f, Bool, DMap k f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DMap k f -> Triple' (DMap k f) Bool (DMap k f)
go
  where
    go :: DMap k f -> Triple' (DMap k f) Bool (DMap k f)
    go :: DMap k f -> Triple' (DMap k f) Bool (DMap k f)
go DMap k f
Tip              = DMap k f -> Bool -> DMap k f -> Triple' (DMap k f) Bool (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip Bool
False DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r) = case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
      GOrdering v v
GLT -> let !(Triple' DMap k f
lt Bool
z DMap k f
gt) = DMap k f -> Triple' (DMap k f) Bool (DMap k f)
go DMap k f
l in DMap k f -> Bool -> DMap k f -> Triple' (DMap k f) Bool (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' DMap k f
lt Bool
z (k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
gt DMap k f
r)
      GOrdering v v
GGT -> let !(Triple' DMap k f
lt Bool
z DMap k f
gt) = DMap k f -> Triple' (DMap k f) Bool (DMap k f)
go DMap k f
r in DMap k f -> Bool -> DMap k f -> Triple' (DMap k f) Bool (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' (k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
l DMap k f
lt) Bool
z DMap k f
gt
      GOrdering v v
GEQ -> DMap k f -> Bool -> DMap k f -> Triple' (DMap k f) Bool (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' DMap k f
l Bool
True DMap k f
r

-- | /O(log n)/.
splitLookupWithKey :: forall k f v. GCompare k => k v -> DMap k f -> (DMap k f, Maybe (k v, f v), DMap k f)
splitLookupWithKey :: k v -> DMap k f -> (DMap k f, Maybe (k v, f v), DMap k f)
splitLookupWithKey k v
k = Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
-> (DMap k f, Maybe (k v, f v), DMap k f)
forall a b c. Triple' a b c -> (a, b, c)
toTriple (Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
 -> (DMap k f, Maybe (k v, f v), DMap k f))
-> (DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f))
-> DMap k f
-> (DMap k f, Maybe (k v, f v), DMap k f)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
go
  where
    go :: DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
    go :: DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
go DMap k f
Tip              = DMap k f
-> Maybe (k v, f v)
-> DMap k f
-> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip Maybe (k v, f v)
forall a. Maybe a
Nothing DMap k f
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f
Tip
    go (Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r) = case k v -> k v -> GOrdering v v
forall k (f :: k -> *) (a :: k) (b :: k).
GCompare f =>
f a -> f b -> GOrdering a b
gcompare k v
k k v
kx of
      GOrdering v v
GLT -> let !(Triple' DMap k f
lt Maybe (k v, f v)
z DMap k f
gt) = DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
go DMap k f
l in DMap k f
-> Maybe (k v, f v)
-> DMap k f
-> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' DMap k f
lt Maybe (k v, f v)
z (k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
gt DMap k f
r)
      GOrdering v v
GGT -> let !(Triple' DMap k f
lt Maybe (k v, f v)
z DMap k f
gt) = DMap k f -> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
go DMap k f
r in DMap k f
-> Maybe (k v, f v)
-> DMap k f
-> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' (k v -> f v -> DMap k f -> DMap k f -> DMap k f
forall k1 (k2 :: k1 -> *) (v :: k1) (f :: k1 -> *).
GCompare k2 =>
k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
combine k v
kx f v
x DMap k f
l DMap k f
lt) Maybe (k v, f v)
z DMap k f
gt
      GOrdering v v
GEQ -> DMap k f
-> Maybe (k v, f v)
-> DMap k f
-> Triple' (DMap k f) (Maybe (k v, f v)) (DMap k f)
forall a b c. a -> b -> c -> Triple' a b c
Triple' DMap k f
l ((k v, f v) -> Maybe (k v, f v)
forall a. a -> Maybe a
Just (k v
kx, f v
x)) DMap k f
r

{--------------------------------------------------------------------
  Eq converts the tree to a list. In a lazy setting, this
  actually seems one of the faster methods to compare two trees
  and it is certainly the simplest :-)
--------------------------------------------------------------------}
instance (GEq k, Has' Eq k f) => Eq (DMap k f) where
  DMap k f
t1 == :: DMap k f -> DMap k f -> Bool
== DMap k f
t2  = (DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
t1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
t2) Bool -> Bool -> Bool
&& (DMap k f -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
toAscList DMap k f
t1 [DSum k f] -> [DSum k f] -> Bool
forall a. Eq a => a -> a -> Bool
== DMap k f -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
toAscList DMap k f
t2)

{--------------------------------------------------------------------
  Ord
--------------------------------------------------------------------}

instance (GCompare k, Has' Eq k f, Has' Ord k f) => Ord (DMap k f) where
  compare :: DMap k f -> DMap k f -> Ordering
compare DMap k f
m1 DMap k f
m2 = [DSum k f] -> [DSum k f] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (DMap k f -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
toAscList DMap k f
m1) (DMap k f -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
toAscList DMap k f
m2)

{--------------------------------------------------------------------
  Read
--------------------------------------------------------------------}

instance (GCompare k, GRead k, Has' Read k f) => Read (DMap k f) where
  readPrec :: ReadPrec (DMap k f)
readPrec = ReadPrec (DMap k f) -> ReadPrec (DMap k f)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (DMap k f) -> ReadPrec (DMap k f))
-> ReadPrec (DMap k f) -> ReadPrec (DMap k f)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (DMap k f) -> ReadPrec (DMap k f)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (DMap k f) -> ReadPrec (DMap k f))
-> ReadPrec (DMap k f) -> ReadPrec (DMap k f)
forall a b. (a -> b) -> a -> b
$ do
    Ident [Char]
"fromList" <- ReadPrec Lexeme
lexP
    [DSum k f]
xs <- ReadPrec [DSum k f]
forall a. Read a => ReadPrec a
readPrec
    DMap k f -> ReadPrec (DMap k f)
forall (m :: * -> *) a. Monad m => a -> m a
return ([DSum k f] -> DMap k f
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
[DSum k f] -> DMap k f
fromList [DSum k f]
xs)

  readListPrec :: ReadPrec [DMap k f]
readListPrec = ReadPrec [DMap k f]
forall a. Read a => ReadPrec [a]
readListPrecDefault

{--------------------------------------------------------------------
  Show
--------------------------------------------------------------------}
instance (GShow k, Has' Show k f) => Show (DMap k f) where
    showsPrec :: Int -> DMap k f -> ShowS
showsPrec Int
p DMap k f
m = Bool -> ShowS -> ShowS
showParen (Int
pInt -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>Int
10)
        ( [Char] -> ShowS
showString [Char]
"fromList "
        ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [DSum k f] -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (DMap k f -> [DSum k f]
forall k (k :: k -> *) (f :: k -> *). DMap k f -> [DSum k f]
toList DMap k f
m)
        )

-- | /O(n)/. Show the tree that implements the map. The tree is shown
-- in a compressed, hanging format. See 'showTreeWith'.
showTree :: (GShow k, Has' Show k f) => DMap k f -> String
showTree :: DMap k f -> [Char]
showTree DMap k f
m
  = (forall (v :: k). k v -> f v -> [Char])
-> Bool -> Bool -> DMap k f -> [Char]
forall k (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> [Char])
-> Bool -> Bool -> DMap k f -> [Char]
showTreeWith forall (v :: k). k v -> f v -> [Char]
forall k' (k :: k' -> *) (f :: k' -> *) (v :: k').
(GShow k, Has' Show k f) =>
k v -> f v -> [Char]
showElem Bool
True Bool
False DMap k f
m
  where
    showElem :: (GShow k, Has' Show k f) => k v -> f v -> String
    showElem :: k v -> f v -> [Char]
showElem k v
k f v
x  = DSum k f -> [Char]
forall a. Show a => a -> [Char]
show (k v
k k v -> f v -> DSum k f
forall k (tag :: k -> *) (f :: k -> *) (a :: k).
tag a -> f a -> DSum tag f
:=> f v
x)


{- | /O(n)/. The expression (@'showTreeWith' showelem hang wide map@) shows
 the tree that implements the map. Elements are shown using the @showElem@ function. If @hang@ is
 'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If
 @wide@ is 'True', an extra wide version is shown.
-}
showTreeWith :: (forall v. k v -> f v -> String) -> Bool -> Bool -> DMap k f -> String
showTreeWith :: (forall (v :: k). k v -> f v -> [Char])
-> Bool -> Bool -> DMap k f -> [Char]
showTreeWith forall (v :: k). k v -> f v -> [Char]
showelem Bool
hang Bool
wide DMap k f
t
  | Bool
hang      = ((forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> DMap k f -> ShowS
forall k (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> DMap k f -> ShowS
showsTreeHang forall (v :: k). k v -> f v -> [Char]
showelem Bool
wide [] DMap k f
t) [Char]
""
  | Bool
otherwise = ((forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
forall k (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
showsTree forall (v :: k). k v -> f v -> [Char]
showelem Bool
wide [] [] DMap k f
t) [Char]
""

showsTree :: (forall v. k v -> f v -> String) -> Bool -> [String] -> [String] -> DMap k f -> ShowS
showsTree :: (forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
showsTree forall (v :: k). k v -> f v -> [Char]
showelem Bool
wide [[Char]]
lbars [[Char]]
rbars DMap k f
t
  = case DMap k f
t of
      DMap k f
Tip -> [[Char]] -> ShowS
showsBars [[Char]]
lbars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"|\n"
      Bin Int
_ k v
kx f v
x DMap k f
Tip DMap k f
Tip
          -> [[Char]] -> ShowS
showsBars [[Char]]
lbars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString (k v -> f v -> [Char]
forall (v :: k). k v -> f v -> [Char]
showelem k v
kx f v
x) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"\n"
      Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r
          -> (forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
forall k (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
showsTree forall (v :: k). k v -> f v -> [Char]
showelem Bool
wide ([[Char]] -> [[Char]]
withBar [[Char]]
rbars) ([[Char]] -> [[Char]]
withEmpty [[Char]]
rbars) DMap k f
r ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> ShowS
showWide Bool
wide [[Char]]
rbars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             [[Char]] -> ShowS
showsBars [[Char]]
lbars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString (k v -> f v -> [Char]
forall (v :: k). k v -> f v -> [Char]
showelem k v
kx f v
x) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"\n" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> ShowS
showWide Bool
wide [[Char]]
lbars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             (forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
forall k (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> [[Char]] -> DMap k f -> ShowS
showsTree forall (v :: k). k v -> f v -> [Char]
showelem Bool
wide ([[Char]] -> [[Char]]
withEmpty [[Char]]
lbars) ([[Char]] -> [[Char]]
withBar [[Char]]
lbars) DMap k f
l

showsTreeHang :: (forall v. k v -> f v -> String) -> Bool -> [String] -> DMap k f -> ShowS
showsTreeHang :: (forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> DMap k f -> ShowS
showsTreeHang forall (v :: k). k v -> f v -> [Char]
showelem Bool
wide [[Char]]
bars DMap k f
t
  = case DMap k f
t of
      DMap k f
Tip -> [[Char]] -> ShowS
showsBars [[Char]]
bars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"|\n"
      Bin Int
_ k v
kx f v
x DMap k f
Tip DMap k f
Tip
          -> [[Char]] -> ShowS
showsBars [[Char]]
bars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString (k v -> f v -> [Char]
forall (v :: k). k v -> f v -> [Char]
showelem k v
kx f v
x) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"\n"
      Bin Int
_ k v
kx f v
x DMap k f
l DMap k f
r
          -> [[Char]] -> ShowS
showsBars [[Char]]
bars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString (k v -> f v -> [Char]
forall (v :: k). k v -> f v -> [Char]
showelem k v
kx f v
x) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"\n" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> ShowS
showWide Bool
wide [[Char]]
bars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             (forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> DMap k f -> ShowS
forall k (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> DMap k f -> ShowS
showsTreeHang forall (v :: k). k v -> f v -> [Char]
showelem Bool
wide ([[Char]] -> [[Char]]
withBar [[Char]]
bars) DMap k f
l ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> ShowS
showWide Bool
wide [[Char]]
bars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             (forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> DMap k f -> ShowS
forall k (k :: k -> *) (f :: k -> *).
(forall (v :: k). k v -> f v -> [Char])
-> Bool -> [[Char]] -> DMap k f -> ShowS
showsTreeHang forall (v :: k). k v -> f v -> [Char]
showelem Bool
wide ([[Char]] -> [[Char]]
withEmpty [[Char]]
bars) DMap k f
r

showWide :: Bool -> [String] -> String -> String
showWide :: Bool -> [[Char]] -> ShowS
showWide Bool
wide [[Char]]
bars
  | Bool
wide      = [Char] -> ShowS
showString ([[Char]] -> [Char]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[Char]] -> [[Char]]
forall a. [a] -> [a]
reverse [[Char]]
bars)) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"|\n"
  | Bool
otherwise = ShowS
forall a. a -> a
id

showsBars :: [String] -> ShowS
showsBars :: [[Char]] -> ShowS
showsBars [[Char]]
bars
  = case [[Char]]
bars of
      [] -> ShowS
forall a. a -> a
id
      [[Char]]
_  -> [Char] -> ShowS
showString ([[Char]] -> [Char]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[Char]] -> [[Char]]
forall a. [a] -> [a]
reverse ([[Char]] -> [[Char]]
forall a. [a] -> [a]
tail [[Char]]
bars))) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
node

node :: String
node :: [Char]
node           = [Char]
"+--"

withBar, withEmpty :: [String] -> [String]
withBar :: [[Char]] -> [[Char]]
withBar [[Char]]
bars   = [Char]
"|  "[Char] -> [[Char]] -> [[Char]]
forall a. a -> [a] -> [a]
:[[Char]]
bars
withEmpty :: [[Char]] -> [[Char]]
withEmpty [[Char]]
bars = [Char]
"   "[Char] -> [[Char]] -> [[Char]]
forall a. a -> [a] -> [a]
:[[Char]]
bars

{--------------------------------------------------------------------
  Assertions
--------------------------------------------------------------------}

-- | /O(n)/. Test if the internal map structure is valid.
valid :: GCompare k => DMap k f -> Bool
valid :: DMap k f -> Bool
valid DMap k f
t
  = DMap k f -> Bool
forall k (k :: k -> *) (f :: k -> *). DMap k f -> Bool
balanced DMap k f
t Bool -> Bool -> Bool
&& DMap k f -> Bool
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
DMap k f -> Bool
ordered DMap k f
t Bool -> Bool -> Bool
&& DMap k f -> Bool
forall k (k :: k -> *) (f :: k -> *). DMap k f -> Bool
validsize DMap k f
t

ordered :: GCompare k => DMap k f -> Bool
ordered :: DMap k f -> Bool
ordered DMap k f
t
  = (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
bounded (Bool -> Some k -> Bool
forall a b. a -> b -> a
const Bool
True) (Bool -> Some k -> Bool
forall a b. a -> b -> a
const Bool
True) DMap k f
t
  where
    bounded :: GCompare k => (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
    bounded :: (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
bounded Some k -> Bool
lo Some k -> Bool
hi DMap k f
t'
      = case DMap k f
t' of
          DMap k f
Tip              -> Bool
True
          Bin Int
_ k v
kx f v
_ DMap k f
l DMap k f
r  -> Some k -> Bool
lo (k v -> Some k
forall k (tag :: k -> *) (a :: k). tag a -> Some tag
mkSome k v
kx) Bool -> Bool -> Bool
&& Some k -> Bool
hi (k v -> Some k
forall k (tag :: k -> *) (a :: k). tag a -> Some tag
mkSome k v
kx) Bool -> Bool -> Bool
&& (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
bounded Some k -> Bool
lo (Some k -> Some k -> Bool
forall a. Ord a => a -> a -> Bool
< k v -> Some k
forall k (tag :: k -> *) (a :: k). tag a -> Some tag
mkSome k v
kx) DMap k f
l Bool -> Bool -> Bool
&& (Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
forall k (k :: k -> *) (f :: k -> *).
GCompare k =>
(Some k -> Bool) -> (Some k -> Bool) -> DMap k f -> Bool
bounded (Some k -> Some k -> Bool
forall a. Ord a => a -> a -> Bool
> k v -> Some k
forall k (tag :: k -> *) (a :: k). tag a -> Some tag
mkSome k v
kx) Some k -> Bool
hi DMap k f
r

-- | Exported only for "Debug.QuickCheck"
balanced :: DMap k f -> Bool
balanced :: DMap k f -> Bool
balanced DMap k f
t
  = case DMap k f
t of
      DMap k f
Tip            -> Bool
True
      Bin Int
_ k v
_ f v
_ DMap k f
l DMap k f
r  -> (DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
1 Bool -> Bool -> Bool
|| (DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
deltaInt -> Int -> Int
forall a. Num a => a -> a -> a
*DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
r Bool -> Bool -> Bool
&& DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
deltaInt -> Int -> Int
forall a. Num a => a -> a -> a
*DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
l)) Bool -> Bool -> Bool
&&
                        DMap k f -> Bool
forall k (k :: k -> *) (f :: k -> *). DMap k f -> Bool
balanced DMap k f
l Bool -> Bool -> Bool
&& DMap k f -> Bool
forall k (k :: k -> *) (f :: k -> *). DMap k f -> Bool
balanced DMap k f
r

validsize :: DMap k f -> Bool
validsize :: DMap k f -> Bool
validsize DMap k f
t
  = (DMap k f -> Maybe Int
forall k (k :: k -> *) (f :: k -> *). DMap k f -> Maybe Int
realsize DMap k f
t Maybe Int -> Maybe Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> Maybe Int
forall a. a -> Maybe a
Just (DMap k f -> Int
forall k1 (k2 :: k1 -> *) (f :: k1 -> *). DMap k2 f -> Int
size DMap k f
t))
  where
    realsize :: DMap k f -> Maybe Int
realsize DMap k f
t'
      = case DMap k f
t' of
          DMap k f
Tip            -> Int -> Maybe Int
forall a. a -> Maybe a
Just Int
0
          Bin Int
sz k v
_ f v
_ DMap k f
l DMap k f
r -> case (DMap k f -> Maybe Int
realsize DMap k f
l,DMap k f -> Maybe Int
realsize DMap k f
r) of
                            (Just Int
n,Just Int
m)  | Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
mInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1 Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
sz  -> Int -> Maybe Int
forall a. a -> Maybe a
Just Int
sz
                            (Maybe Int, Maybe Int)
_                               -> Maybe Int
forall a. Maybe a
Nothing
{--------------------------------------------------------------------
  Utilities
--------------------------------------------------------------------}
foldlStrict :: (a -> b -> a) -> a -> [b] -> a
foldlStrict :: (a -> b -> a) -> a -> [b] -> a
foldlStrict a -> b -> a
f = a -> [b] -> a
go
  where
    go :: a -> [b] -> a
go a
z []     = a
z
    go a
z (b
x:[b]
xs) = a
z a -> a -> a
`seq` a -> [b] -> a
go (a -> b -> a
f a
z b
x) [b]
xs