{- | Representation of a structure mapping unique keys to values. The internal
structure is an AVL tree.
-}
module Mini.Data.Map (
  -- * Type
  Map,

  -- * Combination
  difference,
  intersection,
  union,

  -- * Construction
  empty,
  fromList,
  singleton,

  -- * Conversion
  toAscList,
  toDescList,

  -- * Fold
  foldlWithKey,
  foldrWithKey,

  -- * Modification
  adjust,
  delete,
  filter,
  filterWithKey,
  insert,
  update,

  -- * Query
  isSubmapOf,
  lookup,
  lookupMax,
  lookupMin,
  member,
  null,
  size,

  -- * Traversal
  traverseWithKey,

  -- * Validation
  valid,
) where

import Control.Monad (
  liftM2,
 )
import Data.Bool (
  bool,
 )
import Prelude hiding (
  filter,
  lookup,
  map,
  null,
 )

{-
 - Type
 -}

{- | A map from keys of type /k/ to values of type /a/.

The internal structure is an AVL tree; a tree that is always height-balanced
(the absolute value of the level difference between the left and right
subtrees is at most 1).
-}
data Map k a
  = -- | Empty bin
    E
  | -- | Left-heavy bin
    L (Map k a) k a (Map k a)
  | -- | Balanced bin
    B (Map k a) k a (Map k a)
  | -- | Right-heavy bin
    R (Map k a) k a (Map k a)
  deriving (Map k a -> Map k a -> Bool
(Map k a -> Map k a -> Bool)
-> (Map k a -> Map k a -> Bool) -> Eq (Map k a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k a. (Eq k, Eq a) => Map k a -> Map k a -> Bool
$c== :: forall k a. (Eq k, Eq a) => Map k a -> Map k a -> Bool
== :: Map k a -> Map k a -> Bool
$c/= :: forall k a. (Eq k, Eq a) => Map k a -> Map k a -> Bool
/= :: Map k a -> Map k a -> Bool
Eq, Eq (Map k a)
Eq (Map k a) =>
(Map k a -> Map k a -> Ordering)
-> (Map k a -> Map k a -> Bool)
-> (Map k a -> Map k a -> Bool)
-> (Map k a -> Map k a -> Bool)
-> (Map k a -> Map k a -> Bool)
-> (Map k a -> Map k a -> Map k a)
-> (Map k a -> Map k a -> Map k a)
-> Ord (Map k a)
Map k a -> Map k a -> Bool
Map k a -> Map k a -> Ordering
Map k a -> Map k a -> Map k a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall k a. (Ord k, Ord a) => Eq (Map k a)
forall k a. (Ord k, Ord a) => Map k a -> Map k a -> Bool
forall k a. (Ord k, Ord a) => Map k a -> Map k a -> Ordering
forall k a. (Ord k, Ord a) => Map k a -> Map k a -> Map k a
$ccompare :: forall k a. (Ord k, Ord a) => Map k a -> Map k a -> Ordering
compare :: Map k a -> Map k a -> Ordering
$c< :: forall k a. (Ord k, Ord a) => Map k a -> Map k a -> Bool
< :: Map k a -> Map k a -> Bool
$c<= :: forall k a. (Ord k, Ord a) => Map k a -> Map k a -> Bool
<= :: Map k a -> Map k a -> Bool
$c> :: forall k a. (Ord k, Ord a) => Map k a -> Map k a -> Bool
> :: Map k a -> Map k a -> Bool
$c>= :: forall k a. (Ord k, Ord a) => Map k a -> Map k a -> Bool
>= :: Map k a -> Map k a -> Bool
$cmax :: forall k a. (Ord k, Ord a) => Map k a -> Map k a -> Map k a
max :: Map k a -> Map k a -> Map k a
$cmin :: forall k a. (Ord k, Ord a) => Map k a -> Map k a -> Map k a
min :: Map k a -> Map k a -> Map k a
Ord)

instance (Show k, Show a) => Show (Map k a) where
  show :: Map k a -> String
show = ShowS
curl ShowS -> (Map k a -> String) -> Map k a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String
-> (Map k a -> k -> a -> Map k a -> String -> ShowS)
-> (Map k a -> k -> a -> Map k a -> String -> ShowS)
-> (Map k a -> k -> a -> Map k a -> String -> ShowS)
-> Map k a
-> String
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map [] Map k a -> k -> a -> Map k a -> String -> ShowS
forall {a} {b} {p} {p}.
(Show a, Show b) =>
p -> a -> b -> p -> String -> ShowS
go Map k a -> k -> a -> Map k a -> String -> ShowS
forall {a} {b} {p} {p}.
(Show a, Show b) =>
p -> a -> b -> p -> String -> ShowS
go Map k a -> k -> a -> Map k a -> String -> ShowS
forall {a} {b} {p} {p}.
(Show a, Show b) =>
p -> a -> b -> p -> String -> ShowS
go
   where
    go :: p -> a -> b -> p -> String -> ShowS
go p
_ a
k b
a p
_ String
recl String
recr = String
recl String -> ShowS
forall a. Semigroup a => a -> a -> a
<> (a, b) -> String
forall a. Show a => a -> String
show (a
k, b
a) String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
"," String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
recr
    curl :: ShowS
curl = String -> String -> ShowS
forall {a}. Semigroup a => a -> a -> a -> a
wrap String
"{" String
"}" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
forall {a}. [a] -> [a]
removeTrailingComma
    wrap :: a -> a -> a -> a
wrap a
open a
close a
s = a
open a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
s a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
close
    removeTrailingComma :: [a] -> [a]
removeTrailingComma [a]
s = case [a]
s of
      [] -> []
      [a
_] -> []
      (a
c : [a]
cs) -> a
c a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a]
removeTrailingComma [a]
cs

instance Functor (Map k) where
  fmap :: forall a b. (a -> b) -> Map k a -> Map k b
fmap a -> b
f =
    Map k b
-> (Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b)
-> (Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b)
-> (Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b)
-> Map k a
-> Map k b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      Map k b
forall k a. Map k a
E
      (\Map k a
_ k
k a
a Map k a
_ Map k b
recl Map k b
recr -> Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k b
recl k
k (a -> b
f a
a) Map k b
recr)
      (\Map k a
_ k
k a
a Map k a
_ Map k b
recl Map k b
recr -> Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k b
recl k
k (a -> b
f a
a) Map k b
recr)
      (\Map k a
_ k
k a
a Map k a
_ Map k b
recl Map k b
recr -> Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k b
recl k
k (a -> b
f a
a) Map k b
recr)

instance Foldable (Map k) where
  foldr :: forall a b. (a -> b -> b) -> b -> Map k a -> b
foldr a -> b -> b
f b
b = b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map b
b Map k a -> k -> a -> Map k a -> b -> b -> b
forall {t :: * -> *} {p} {p} {p}.
Foldable t =>
p -> p -> a -> t a -> b -> p -> b
go Map k a -> k -> a -> Map k a -> b -> b -> b
forall {t :: * -> *} {p} {p} {p}.
Foldable t =>
p -> p -> a -> t a -> b -> p -> b
go Map k a -> k -> a -> Map k a -> b -> b -> b
forall {t :: * -> *} {p} {p} {p}.
Foldable t =>
p -> p -> a -> t a -> b -> p -> b
go where go :: p -> p -> a -> t a -> b -> p -> b
go p
_ p
_ a
a t a
r b
recl p
_ = (a -> b -> b) -> b -> t a -> b
forall a b. (a -> b -> b) -> b -> t a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f (a -> b -> b
f a
a b
recl) t a
r

instance Traversable (Map k) where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map k a -> f (Map k b)
traverse = (k -> a -> f b) -> Map k a -> f (Map k b)
forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> Map k a -> f (Map k b)
traverseWithKey ((k -> a -> f b) -> Map k a -> f (Map k b))
-> ((a -> f b) -> k -> a -> f b)
-> (a -> f b)
-> Map k a
-> f (Map k b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> k -> a -> f b
forall a b. a -> b -> a
const

instance (Ord k) => Semigroup (Map k a) where
  <> :: Map k a -> Map k a -> Map k a
(<>) = Map k a -> Map k a -> Map k a
forall k a. Ord k => Map k a -> Map k a -> Map k a
union

instance (Ord k) => Monoid (Map k a) where
  mempty :: Map k a
mempty = Map k a
forall k a. Map k a
empty

{-
 - Primitive recursion
 -}

-- | Primitive recursion on maps
map
  :: b
  -- ^ Empty bin
  -> (Map k a -> k -> a -> Map k a -> b -> b -> b)
  -- ^ Left-heavy bin: left child, key, value, right child, left recursion,
  -- right recursion
  -> (Map k a -> k -> a -> Map k a -> b -> b -> b)
  -- ^ Balanced bin: left child, key, value, right child, left recursion, right
  -- recursion
  -> (Map k a -> k -> a -> Map k a -> b -> b -> b)
  -- ^ Right-heavy bin: left child, key, value, right child, left recursion,
  -- right recursion
  -> Map k a
  -- ^ Map
  -> b
map :: forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
_ Map k a -> k -> a -> Map k a -> b -> b -> b
_ Map k a -> k -> a -> Map k a -> b -> b -> b
_ Map k a
E = b
e
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h (L Map k a
l k
k a
a Map k a
r) = Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a
l k
k a
a Map k a
r (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
l) (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
r)
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h (B Map k a
l k
k a
a Map k a
r) = Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a
l k
k a
a Map k a
r (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
l) (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
r)
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h (R Map k a
l k
k a
a Map k a
r) = Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
l k
k a
a Map k a
r (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
l) (b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map b
e Map k a -> k -> a -> Map k a -> b -> b -> b
f Map k a -> k -> a -> Map k a -> b -> b -> b
g Map k a -> k -> a -> Map k a -> b -> b -> b
h Map k a
r)

{-
 - Combination
 -}

-- | \(O(n \log n)\) Map difference (matching only on keys)
difference :: (Ord k) => Map k a -> Map k b -> Map k a
difference :: forall k a b. Ord k => Map k a -> Map k b -> Map k a
difference = (k -> b -> Map k a -> Map k a) -> Map k a -> Map k b -> Map k a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k b
_ Map k a
b -> k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete k
k Map k a
b)

-- | \(O(n \log n)\) Left-biased map intersection (matching only on keys)
intersection :: (Ord k) => Map k a -> Map k b -> Map k a
intersection :: forall k a b. Ord k => Map k a -> Map k b -> Map k a
intersection Map k a
t1 Map k b
t2 =
  (k -> a -> Map k a -> Map k a) -> Map k a -> Map k a -> Map k a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey
    (\k
k a
a Map k a
b -> Map k a -> Map k a -> Bool -> Map k a
forall a. a -> a -> Bool -> a
bool Map k a
b (k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
insert k
k a
a Map k a
b) (Bool -> Map k a) -> Bool -> Map k a
forall a b. (a -> b) -> a -> b
$ k
k k -> Map k b -> Bool
forall k a. Ord k => k -> Map k a -> Bool
`member` Map k b
t2)
    Map k a
forall k a. Map k a
empty
    Map k a
t1

-- | \(O(n \log n)\) Left-biased map union (matching only on keys)
union :: (Ord k) => Map k a -> Map k a -> Map k a
union :: forall k a. Ord k => Map k a -> Map k a -> Map k a
union Map k a
t = (k -> a -> Map k a -> Map k a) -> Map k a -> Map k a -> Map k a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k a
a Map k a
b -> Map k a -> Map k a -> Bool -> Map k a
forall a. a -> a -> Bool -> a
bool Map k a
b (k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
insert k
k a
a Map k a
b) (Bool -> Map k a) -> (Bool -> Bool) -> Bool -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bool -> Bool
not (Bool -> Map k a) -> Bool -> Map k a
forall a b. (a -> b) -> a -> b
$ k
k k -> Map k a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
`member` Map k a
t) Map k a
t

{-
 - Construction
 -}

-- | \(O(1)\) The empty map
empty :: Map k a
empty :: forall k a. Map k a
empty = Map k a
forall k a. Map k a
E

{- | \(O(n \log n)\) From a tail-biased list of @(key, value)@ pairs to a map
with bins containing the keys and values
-}
fromList :: (Ord k) => [(k, a)] -> Map k a
fromList :: forall k a. Ord k => [(k, a)] -> Map k a
fromList = (Map k a -> (k, a) -> Map k a) -> Map k a -> [(k, a)] -> Map k a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (((k, a) -> Map k a -> Map k a) -> Map k a -> (k, a) -> Map k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((k, a) -> Map k a -> Map k a) -> Map k a -> (k, a) -> Map k a)
-> ((k, a) -> Map k a -> Map k a) -> Map k a -> (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ (k -> a -> Map k a -> Map k a) -> (k, a) -> Map k a -> Map k a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
insert) Map k a
forall k a. Map k a
empty

-- | \(O(1)\) From a key and a value to a map with a single bin
singleton :: k -> a -> Map k a
singleton :: forall k a. k -> a -> Map k a
singleton k
k a
a = Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k a
a Map k a
forall k a. Map k a
E

{-
 - Conversion
 -}

{- | \(O(n)\) From a map to a list of @(key, value)@ pairs in key-ascending
order
-}
toAscList :: Map k a -> [(k, a)]
toAscList :: forall k a. Map k a -> [(k, a)]
toAscList = ([(k, a)] -> k -> a -> [(k, a)]) -> [(k, a)] -> Map k a -> [(k, a)]
forall b k a. (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey (\[(k, a)]
b k
k a
a -> (k
k, a
a) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
b) []

{- | \(O(n)\) From a map to a list of @(key, value)@ pairs in key-descending
order
-}
toDescList :: Map k a -> [(k, a)]
toDescList :: forall k a. Map k a -> [(k, a)]
toDescList = (k -> a -> [(k, a)] -> [(k, a)]) -> [(k, a)] -> Map k a -> [(k, a)]
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k a
a [(k, a)]
b -> (k
k, a
a) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
b) []

{-
 - Fold
 -}

{- | \(O(n)\) From a left-associative operation on keys and values, a starting
accumulator and a map to a thing
-}
foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey :: forall b k a. (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey b -> k -> a -> b
f b
b = b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map b
b Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. Map k a -> k -> a -> p -> p -> b -> b
go Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. Map k a -> k -> a -> p -> p -> b -> b
go Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. Map k a -> k -> a -> p -> p -> b -> b
go
 where
  go :: Map k a -> k -> a -> p -> p -> b -> b
go Map k a
l k
k a
a p
_ p
_ b
recr = (b -> k -> a -> b) -> b -> Map k a -> b
forall b k a. (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey b -> k -> a -> b
f (b -> k -> a -> b
f b
recr k
k a
a) Map k a
l

{- | \(O(n)\) From a right-associative operation on keys and values, a starting
accumulator and a map to a thing
-}
foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey :: forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey k -> a -> b -> b
f b
b = b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map b
b Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. p -> k -> a -> Map k a -> b -> p -> b
go Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. p -> k -> a -> Map k a -> b -> p -> b
go Map k a -> k -> a -> Map k a -> b -> b -> b
forall {p} {p}. p -> k -> a -> Map k a -> b -> p -> b
go
 where
  go :: p -> k -> a -> Map k a -> b -> p -> b
go p
_ k
k a
a Map k a
r b
recl p
_ = (k -> a -> b -> b) -> b -> Map k a -> b
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey k -> a -> b -> b
f (k -> a -> b -> b
f k
k a
a b
recl) Map k a
r

{-
 - Modification
 -}

{- | \(O(\log n)\) From an operation, a key and a map to the map adjusted by
applying the operation to the value associated with the key
-}
adjust :: (Ord k) => (a -> a) -> k -> Map k a -> Map k a
adjust :: forall k a. Ord k => (a -> a) -> k -> Map k a -> Map k a
adjust a -> a
f k
k0 =
  Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
    Map k a
forall k a. Map k a
E
    ( \Map k a
l k
k a
a Map k a
r Map k a
recl Map k a
recr ->
        case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
          Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
recl k
k a
a Map k a
r
          Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k (a -> a
f a
a) Map k a
r
          Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
recr
    )
    ( \Map k a
l k
k a
a Map k a
r Map k a
recl Map k a
recr ->
        case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
          Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
recl k
k a
a Map k a
r
          Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k (a -> a
f a
a) Map k a
r
          Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
recr
    )
    ( \Map k a
l k
k a
a Map k a
r Map k a
recl Map k a
recr ->
        case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
          Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
recl k
k a
a Map k a
r
          Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k (a -> a
f a
a) Map k a
r
          Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
recr
    )

-- | \(O(\log n)\) From a key and a map to the map without the key
delete :: (Ord k) => k -> Map k a -> Map k a
delete :: forall k a. Ord k => k -> Map k a -> Map k a
delete k
k0 Map k a
t = Map k a -> Map k a -> Bool -> Map k a
forall a. a -> a -> Bool -> a
bool Map k a
t (Map k a -> Map k a
forall {t}. Map k t -> Map k t
go Map k a
t) (k
k0 k -> Map k a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
`member` Map k a
t)
 where
  go :: Map k t -> Map k t
go =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L0")
      ( \Map k t
l k
k t
a Map k t
r Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
l k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
l Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
l k
k t
a Map k t
r
      )
      ( \Map k t
l k
k t
a Map k t
r Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
l k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBr Map k t
l Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
l k
k t
a Map k t
r
      )
      ( \Map k t
l k
k t
a Map k t
r Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
l k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
l Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall {t}. Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
l k
k t
a Map k t
r
      )
  deleteRl :: Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
l k
k t
a Map k t
r =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L1")
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR' (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBr Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      Map k t
l
  deleteRr :: Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
l k
k t
a =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L2")
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR' Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBl Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
rl k
rk t
ra Map k t
rr)
      )
  deleteBl :: Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
l k
k t
a Map k t
r =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L3")
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB' (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBr Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      Map k t
l
  deleteBr :: Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
l k
k t
a =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L4")
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB' Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBl Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
rl k
rk t
ra Map k t
rr)
      )
  deleteLl :: Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
l k
k t
a Map k t
r =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L5")
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL' (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBr Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      ( \Map k t
ll k
lk t
la Map k t
lr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
ll Map k t
lr) k
k t
a Map k t
r
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
ll k
lk t
la Map k t
lr) k
k t
a Map k t
r
      )
      Map k t
l
  deleteLr :: Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
l k
k t
a =
    Map k t
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> (Map k t -> k -> t -> Map k t -> Map k t -> Map k t -> Map k t)
-> Map k t
-> Map k t
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k t
forall a. HasCallStack => String -> a
error String
"Map.delete: L6")
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteL Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteLr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL' Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteBl Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteBr Map k t
rl k
rk t
ra Map k t
rr)
      )
      ( \Map k t
rl k
rk t
ra Map k t
rr Map k t
_ Map k t
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRl Map k t
rl k
rk t
ra Map k t
rr)
            Ordering
EQ -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> Map k t -> Map k t
forall {k} {a}. Map k a -> Map k a -> Map k a
substituteR Map k t
rl Map k t
rr)
            Ordering
GT -> Map k t -> k -> t -> Map k t -> Map k t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k t
l k
k t
a (Map k t -> k -> t -> Map k t -> Map k t
deleteRr Map k t
rl k
rk t
ra Map k t
rr)
      )
  rebalanceR :: Map k a -> k -> a -> Map k a -> Map k a
rebalanceR Map k a
l k
k a
a =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L7")
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
            (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L8")
            (\Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rll) k
rlk a
rla (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
rlr k
rk a
ra Map k a
rr))
            (\Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rll) k
rlk a
rla (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rlr k
rk a
ra Map k a
rr))
            (\Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
rll) k
rlk a
rla (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rlr k
rk a
ra Map k a
rr))
            Map k a
rl
      )
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
rl) k
rk a
ra Map k a
rr)
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rl) k
rk a
ra Map k a
rr)
  rebalanceL :: Map k a -> k -> a -> Map k a -> Map k a
rebalanceL Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L9")
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lr k
k a
a Map k a
r))
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
ll k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
lr k
k a
a Map k a
r))
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
            (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L10")
            (\Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la Map k a
lrl) k
lrk a
lra (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
lrr k
k a
a Map k a
r))
            (\Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la Map k a
lrl) k
lrk a
lra (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lrr k
k a
a Map k a
r))
            (\Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
ll k
lk a
la Map k a
lrl) k
lrk a
lra (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lrr k
k a
a Map k a
r))
            Map k a
lr
      )
      Map k a
l
  checkLeftR :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftR Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L11")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceR Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkLeftB :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftB Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L12")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkLeftL :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftL Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L13")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkRightR :: Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L14")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      Map k a
r
  checkRightB :: Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L15")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      Map k a
r
  checkRightL :: Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L16")
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceL Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      Map k a
r
  substituteR :: Map k a -> Map k a -> Map k a
substituteR Map k a
l =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L17")
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map k a
rl k
rk a
ra Map k a
rr
      )
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR' Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftB Map k a
rl k
rk a
ra Map k a
rr
      )
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map k a
rl k
rk a
ra Map k a
rr
      )
  substituteBr :: Map k a -> Map k a -> Map k a
substituteBr Map k a
l =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      Map k a
forall k a. Map k a
E
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map k a
rl k
rk a
ra Map k a
rr
      )
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB' Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftB Map k a
rl k
rk a
ra Map k a
rr
      )
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          (\(k
k, a
a, Map k a
r) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map k a
l k
k a
a Map k a
r) ((k, a, Map k a) -> Map k a) -> (k, a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map k a
rl k
rk a
ra Map k a
rr
      )
  substituteBl :: Map k a -> Map k a -> Map k a
substituteBl Map k a
l Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      Map k a
forall k a. Map k a
E
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map k a
ll k
lk a
la Map k a
lr
      )
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB' Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightB Map k a
ll k
lk a
la Map k a
lr
      )
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map k a
ll k
lk a
la Map k a
lr
      )
      Map k a
l
  substituteL :: Map k a -> Map k a -> Map k a
substituteL Map k a
l Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.delete: L18")
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map k a
ll k
lk a
la Map k a
lr
      )
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL' Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightB Map k a
ll k
lk a
la Map k a
lr
      )
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          (\(Map k a
l', k
k, a
a) -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL Map k a
l' k
k a
a Map k a
r) ((Map k a, k, a) -> Map k a) -> (Map k a, k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$
            Map k a -> k -> a -> Map k a -> (Map k a, k, a)
forall {t} {t}. Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map k a
ll k
lk a
la Map k a
lr
      )
      Map k a
l
  checkLeftR' :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftR' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceR Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkLeftB' :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftB' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkLeftL' :: Map k a -> k -> a -> Map k a -> Map k a
checkLeftL' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      Map k a
l
  checkRightR' :: Map k a -> k -> a -> Map k a -> Map k a
checkRightR' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
      Map k a
r
  checkRightB' :: Map k a -> k -> a -> Map k a -> Map k a
checkRightB' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
      Map k a
r
  checkRightL' :: Map k a -> k -> a -> Map k a -> Map k a
checkRightL' Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceL Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
      Map k a
r
  popLeftR :: Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map t t
l t
k t
a Map t t
r =
    (t, t, Map t t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> Map t t
-> (t, t, Map t t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (t
k, t
a, Map t t
r)
      ( \Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l') -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR Map t t
l' t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map t t
ll t
lk t
la Map t t
lr
      )
      (\Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ -> Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftRB Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r)
      ( \Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l') -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftR Map t t
l' t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map t t
ll t
lk t
la Map t t
lr
      )
      Map t t
l
  popLeftB :: Map k a -> k -> a -> Map k a -> (k, a, Map k a)
popLeftB Map k a
l k
k a
a Map k a
r =
    (k, a, Map k a)
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> (k, a, Map k a)
    -> (k, a, Map k a)
    -> (k, a, Map k a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> (k, a, Map k a)
    -> (k, a, Map k a)
    -> (k, a, Map k a))
-> (Map k a
    -> k
    -> a
    -> Map k a
    -> (k, a, Map k a)
    -> (k, a, Map k a)
    -> (k, a, Map k a))
-> Map k a
-> (k, a, Map k a)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (k
k, a
a, Map k a
forall k a. Map k a
E)
      (\Map k a
ll k
lk a
la Map k a
lr (k, a, Map k a)
_ (k, a, Map k a)
_ -> Map k a
-> k -> a -> Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBL Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r)
      (\Map k a
ll k
lk a
la Map k a
lr (k, a, Map k a)
_ (k, a, Map k a)
_ -> Map k a
-> k -> a -> Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBB Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r)
      (\Map k a
ll k
lk a
la Map k a
lr (k, a, Map k a)
_ (k, a, Map k a)
_ -> Map k a
-> k -> a -> Map k a -> k -> a -> Map k a -> (k, a, Map k a)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBR Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r)
      Map k a
l
  popLeftL :: Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map t t
l t
k t
a Map t t
r =
    (t, t, Map t t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> Map t t
-> (t, t, Map t t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> (t, t, Map t t)
forall a. HasCallStack => String -> a
error String
"Map.delete: L19")
      ( \Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l') -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL Map t t
l' t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map t t
ll t
lk t
la Map t t
lr
      )
      (\Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ -> Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftLB Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r)
      ( \Map t t
ll t
lk t
la Map t t
lr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l') -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftL Map t t
l' t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map t t
ll t
lk t
la Map t t
lr
      )
      Map t t
l
  popLeftRB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftRB Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r =
    (t, t, Map t t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> Map t t
-> (t, t, Map t t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (t
lk, t
la, Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceR Map t t
forall k a. Map k a
E t
k t
a Map t t
r)
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBL Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBB Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBR Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      Map t t
ll
  popLeftBB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBB Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r =
    (t, t, Map t t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> Map t t
-> (t, t, Map t t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (t
lk, t
la, Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
forall k a. Map k a
E t
k t
a Map t t
r)
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBL Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBB Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBR Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      Map t t
ll
  popLeftLB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftLB Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r =
    (t, t, Map t t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (t, t, Map t t)
    -> (t, t, Map t t)
    -> (t, t, Map t t))
-> Map t t
-> (t, t, Map t t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (t
lk, t
la, Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
forall k a. Map k a
E t
k t
a Map t t
forall k a. Map k a
E)
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBL Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBB Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      ( \Map t t
lll t
llk t
lla Map t t
llr (t, t, Map t t)
_ (t, t, Map t t)
_ ->
          (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBR Map t t
lll t
llk t
lla Map t t
llr t
lk t
la Map t t
lr
      )
      Map t t
ll
  popLeftBR :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBR Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r =
    (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
      Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftR Map t t
ll t
lk t
la Map t t
lr
  popLeftBL :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftBL Map t t
ll t
lk t
la Map t t
lr t
k t
a Map t t
r =
    (\(t
k', t
a', Map t t
l) -> (t
k', t
a', Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkLeftB Map t t
l t
k t
a Map t t
r)) ((t, t, Map t t) -> (t, t, Map t t))
-> (t, t, Map t t) -> (t, t, Map t t)
forall a b. (a -> b) -> a -> b
$
      Map t t -> t -> t -> Map t t -> (t, t, Map t t)
popLeftL Map t t
ll t
lk t
la Map t t
lr
  popRightR :: Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map t t
l t
k t
a =
    (Map t t, t, t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> Map t t
-> (Map t t, t, t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> (Map t t, t, t)
forall a. HasCallStack => String -> a
error String
"Map.delete: L20")
      ( \Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map t t
rl t
rk t
ra Map t t
rr
      )
      (\Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ -> Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightRB Map t t
l t
k t
a Map t t
rl t
rk t
ra Map t t
rr)
      ( \Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightR Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map t t
rl t
rk t
ra Map t t
rr
      )
  popRightB :: Map b c -> b -> c -> Map b c -> (Map b c, b, c)
popRightB Map b c
l b
k c
a =
    (Map b c, b, c)
-> (Map b c
    -> b
    -> c
    -> Map b c
    -> (Map b c, b, c)
    -> (Map b c, b, c)
    -> (Map b c, b, c))
-> (Map b c
    -> b
    -> c
    -> Map b c
    -> (Map b c, b, c)
    -> (Map b c, b, c)
    -> (Map b c, b, c))
-> (Map b c
    -> b
    -> c
    -> Map b c
    -> (Map b c, b, c)
    -> (Map b c, b, c)
    -> (Map b c, b, c))
-> Map b c
-> (Map b c, b, c)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map b c
forall k a. Map k a
E, b
k, c
a)
      (\Map b c
rl b
rk c
ra Map b c
rr (Map b c, b, c)
_ (Map b c, b, c)
_ -> Map b c
-> b -> c -> Map b c -> b -> c -> Map b c -> (Map b c, b, c)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBL Map b c
l b
k c
a Map b c
rl b
rk c
ra Map b c
rr)
      (\Map b c
rl b
rk c
ra Map b c
rr (Map b c, b, c)
_ (Map b c, b, c)
_ -> Map b c
-> b -> c -> Map b c -> b -> c -> Map b c -> (Map b c, b, c)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBB Map b c
l b
k c
a Map b c
rl b
rk c
ra Map b c
rr)
      (\Map b c
rl b
rk c
ra Map b c
rr (Map b c, b, c)
_ (Map b c, b, c)
_ -> Map b c
-> b -> c -> Map b c -> b -> c -> Map b c -> (Map b c, b, c)
forall {t} {t}.
Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBR Map b c
l b
k c
a Map b c
rl b
rk c
ra Map b c
rr)
  popRightL :: Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map t t
l t
k t
a =
    (Map t t, t, t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> Map t t
-> (Map t t, t, t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map t t
l, t
k, t
a)
      ( \Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map t t
rl t
rk t
ra Map t t
rr
      )
      (\Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ -> Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightLB Map t t
l t
k t
a Map t t
rl t
rk t
ra Map t t
rr)
      ( \Map t t
rl t
rk t
ra Map t t
rr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightL Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map t t
rl t
rk t
ra Map t t
rr
      )
  popRightRB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightRB Map t t
l t
k t
a Map t t
rl t
rk t
ra =
    (Map t t, t, t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> Map t t
-> (Map t t, t, t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
forall k a. Map k a
E t
k t
a Map t t
forall k a. Map k a
E, t
rk, t
ra)
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBL Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBB Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBR Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
  popRightBB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBB Map t t
l t
k t
a Map t t
rl t
rk t
ra =
    (Map t t, t, t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> Map t t
-> (Map t t, t, t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
forall k a. Map k a
E, t
rk, t
ra)
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBL Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBB Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBR Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
  popRightLB :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightLB Map t t
l t
k t
a Map t t
rl t
rk t
ra =
    (Map t t, t, t)
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> (Map t t
    -> t
    -> t
    -> Map t t
    -> (Map t t, t, t)
    -> (Map t t, t, t)
    -> (Map t t, t, t))
-> Map t t
-> (Map t t, t, t)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
rebalanceL Map t t
l t
k t
a Map t t
forall k a. Map k a
E, t
rk, t
ra)
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBL Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBB Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
      ( \Map t t
rrl t
rrk t
rra Map t t
rrr (Map t t, t, t)
_ (Map t t, t, t)
_ ->
          (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
            Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBR Map t t
rl t
rk t
ra Map t t
rrl t
rrk t
rra Map t t
rrr
      )
  popRightBR :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBR Map t t
l t
k t
a Map t t
rl t
rk t
ra Map t t
rr =
    (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
      Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightR Map t t
rl t
rk t
ra Map t t
rr
  popRightBL :: Map t t
-> t -> t -> Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightBL Map t t
l t
k t
a Map t t
rl t
rk t
ra Map t t
rr =
    (\(Map t t
r, t
k', t
a') -> (Map t t -> t -> t -> Map t t -> Map t t
forall k a. Map k a -> k -> a -> Map k a -> Map k a
checkRightB Map t t
l t
k t
a Map t t
r, t
k', t
a')) ((Map t t, t, t) -> (Map t t, t, t))
-> (Map t t, t, t) -> (Map t t, t, t)
forall a b. (a -> b) -> a -> b
$
      Map t t -> t -> t -> Map t t -> (Map t t, t, t)
popRightL Map t t
rl t
rk t
ra Map t t
rr

{- | \(O(n)\) From a predicate and a map to the map with values satisfying the
predicate
-}
filter :: (Ord k) => (a -> Bool) -> Map k a -> Map k a
filter :: forall k a. Ord k => (a -> Bool) -> Map k a -> Map k a
filter a -> Bool
p = (k -> a -> Map k a -> Map k a) -> Map k a -> Map k a -> Map k a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k a
a Map k a
b -> Map k a -> Map k a -> Bool -> Map k a
forall a. a -> a -> Bool -> a
bool Map k a
b (k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
insert k
k a
a Map k a
b) (Bool -> Map k a) -> Bool -> Map k a
forall a b. (a -> b) -> a -> b
$ a -> Bool
p a
a) Map k a
forall k a. Map k a
empty

{- | \(O(n)\) From a predicate and a map to the map with keys and values
satisfying the predicate
-}
filterWithKey :: (Ord k) => (k -> a -> Bool) -> Map k a -> Map k a
filterWithKey :: forall k a. Ord k => (k -> a -> Bool) -> Map k a -> Map k a
filterWithKey k -> a -> Bool
p = (k -> a -> Map k a -> Map k a) -> Map k a -> Map k a -> Map k a
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k a
a Map k a
b -> Map k a -> Map k a -> Bool -> Map k a
forall a. a -> a -> Bool -> a
bool Map k a
b (k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
insert k
k a
a Map k a
b) (Bool -> Map k a) -> Bool -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> a -> Bool
p k
k a
a) Map k a
forall k a. Map k a
empty

{- | \(O(\log n)\) From a key, a value and a map to the map including a bin
containing the key and the value
-}
insert :: (Ord k) => k -> a -> Map k a -> Map k a
insert :: forall k a. Ord k => k -> a -> Map k a -> Map k a
insert k
k0 a
a0 =
  Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
    (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E)
    (\Map k a
l k
k a
a Map k a
r Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
l k
k a
a Map k a
r)
    (\Map k a
l k
k a
a Map k a
r Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
l k
k a
a Map k a
r)
    (\Map k a
l k
k a
a Map k a
r Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
l k
k a
a Map k a
r)
 where
  insertR :: Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
l k
k a
a Map k a
r =
    case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
      Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
insertRl Map k a
l k
k a
a Map k a
r
      Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k0 a
a0 Map k a
r
      Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
insertRr Map k a
l k
k a
a Map k a
r
  insertB :: Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
l k
k a
a Map k a
r =
    case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
      Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
insertBl Map k a
l k
k a
a Map k a
r
      Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k0 a
a0 Map k a
r
      Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
insertBr Map k a
l k
k a
a Map k a
r
  insertL :: Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
l k
k a
a Map k a
r =
    case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
      Ordering
LT -> Map k a -> k -> a -> Map k a -> Map k a
insertLl Map k a
l k
k a
a Map k a
r
      Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k0 a
a0 Map k a
r
      Ordering
GT -> Map k a -> k -> a -> Map k a -> Map k a
insertLr Map k a
l k
k a
a Map k a
r
  insertRl :: Map k a -> k -> a -> Map k a -> Map k a
insertRl Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E) k
k a
a Map k a
r)
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          let l' :: Map k a
l' = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
ll k
lk a
la Map k a
lr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L0")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l' k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l' k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l' k
k a
a Map k a
r)
                Map k a
l'
      )
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      Map k a
l
  insertBl :: Map k a -> k -> a -> Map k a -> Map k a
insertBl Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E) k
k a
a Map k a
r)
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          let l' :: Map k a
l' = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
ll k
lk a
la Map k a
lr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L1")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l' k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l' k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l' k
k a
a Map k a
r)
                Map k a
l'
      )
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      Map k a
l
  insertBr :: Map k a -> k -> a -> Map k a -> Map k a
insertBr Map k a
l k
k a
a =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E))
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
rl k
rk a
ra Map k a
rr))
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          let r :: Map k a
r = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
rl k
rk a
ra Map k a
rr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L2")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a Map k a
r)
                Map k a
r
      )
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
rl k
rk a
ra Map k a
rr))
  insertLr :: Map k a -> k -> a -> Map k a -> Map k a
insertLr Map k a
l k
k a
a =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E))
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
rl k
rk a
ra Map k a
rr))
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          let r :: Map k a
r = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
rl k
rk a
ra Map k a
rr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L3")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
r)
                Map k a
r
      )
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
rl k
rk a
ra Map k a
rr))
  insertRr :: Map k a -> k -> a -> Map k a -> Map k a
insertRr Map k a
l k
k a
a =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L4")
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
rl k
rk a
ra Map k a
rr))
      ( \Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
rk of
            Ordering
LT -> Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertRrl Map k a
l k
k a
a Map k a
rl k
rk a
ra Map k a
rr
            Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rl k
k0 a
a0 Map k a
rr)
            Ordering
GT -> Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertRrr Map k a
l k
k a
a Map k a
rl k
rk a
ra Map k a
rr
      )
      (\Map k a
rl k
rk a
ra Map k a
rr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
rl k
rk a
ra Map k a
rr))
  insertLl :: Map k a -> k -> a -> Map k a -> Map k a
insertLl Map k a
l k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L5")
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      ( \Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ ->
          case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
lk of
            Ordering
LT -> Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertLll Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r
            Ordering
EQ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
k0 a
a0 Map k a
lr) k
k a
a Map k a
r
            Ordering
GT -> Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertLlr Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r
      )
      (\Map k a
ll k
lk a
la Map k a
lr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
ll k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      Map k a
l
  insertRrr :: Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertRrr Map k a
l k
k a
a Map k a
rl k
rk a
ra =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rl) k
rk a
ra (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E))
      (\Map k a
rrl k
rrk a
rra Map k a
rrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rl k
rk a
ra (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
rrl k
rrk a
rra Map k a
rrr)))
      ( \Map k a
rrl k
rrk a
rra Map k a
rrr Map k a
_ Map k a
_ ->
          let rr :: Map k a
rr = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
rrl k
rrk a
rra Map k a
rrr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L6")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rl) k
rk a
ra Map k a
rr)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rl k
rk a
ra Map k a
rr))
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rl) k
rk a
ra Map k a
rr)
                Map k a
rr
      )
      (\Map k a
rrl k
rrk a
rra Map k a
rrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rl k
rk a
ra (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
rrl k
rrk a
rra Map k a
rrr)))
  insertLll :: Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertLll Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k0 a
a0 Map k a
forall k a. Map k a
E) k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lr k
k a
a Map k a
r))
      (\Map k a
lll k
llk a
lla Map k a
llr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
lll k
llk a
lla Map k a
llr) k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      ( \Map k a
lll k
llk a
lla Map k a
llr Map k a
_ Map k a
_ ->
          let ll' :: Map k a
ll' = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
lll k
llk a
lla Map k a
llr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L7")
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll' k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lr k
k a
a Map k a
r))
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll' k
lk a
la Map k a
lr) k
k a
a Map k a
r)
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll' k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lr k
k a
a Map k a
r))
                Map k a
ll'
      )
      (\Map k a
lll k
llk a
lla Map k a
llr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
lll k
llk a
lla Map k a
llr) k
lk a
la Map k a
lr) k
k a
a Map k a
r)
      Map k a
ll
  insertRrl :: Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertRrl Map k a
l k
k a
a Map k a
rl k
rk a
ra Map k a
rr =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
forall k a. Map k a
E) k
k0 a
a0 (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
rk a
ra Map k a
rr))
      (\Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
rll k
rlk a
rla Map k a
rlr) k
rk a
ra Map k a
rr))
      ( \Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ ->
          let rl' :: Map k a
rl' = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
rll k
rlk a
rla Map k a
rlr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L8")
                ( \Map k a
rll' k
rlk' a
rla' Map k a
rlr' Map k a
_ Map k a
_ ->
                    Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
l k
k a
a Map k a
rll')
                      k
rlk'
                      a
rla'
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
rlr' k
rk a
ra Map k a
rr)
                )
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rl' k
rk a
ra Map k a
rr))
                ( \Map k a
rll' k
rlk' a
rla' Map k a
rlr' Map k a
_ Map k a
_ ->
                    Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
l k
k a
a Map k a
rll')
                      k
rlk'
                      a
rla'
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
rlr' k
rk a
ra Map k a
rr)
                )
                Map k a
rl'
      )
      (\Map k a
rll k
rlk a
rla Map k a
rlr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
l k
k a
a (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
rll k
rlk a
rla Map k a
rlr) k
rk a
ra Map k a
rr))
      Map k a
rl
  insertLlr :: Map k a -> k -> a -> Map k a -> k -> a -> Map k a -> Map k a
insertLlr Map k a
ll k
lk a
la Map k a
lr k
k a
a Map k a
r =
    Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la Map k a
forall k a. Map k a
E) k
k0 a
a0 (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
forall k a. Map k a
E k
k a
a Map k a
r))
      (\Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
insertL Map k a
lrl k
lrk a
lra Map k a
lrr)) k
k a
a Map k a
r)
      ( \Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ ->
          let lr' :: Map k a
lr' = Map k a -> k -> a -> Map k a -> Map k a
insertB Map k a
lrl k
lrk a
lra Map k a
lrr
           in Map k a
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> (Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a)
-> Map k a
-> Map k a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
                (String -> Map k a
forall a. HasCallStack => String -> a
error String
"Map.insert: L9")
                ( \Map k a
lrl' k
lrk' a
lra' Map k a
lrr' Map k a
_ Map k a
_ ->
                    Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la Map k a
lrl')
                      k
lrk'
                      a
lra'
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R Map k a
lrr' k
k a
a Map k a
r)
                )
                (\Map k a
_ k
_ a
_ Map k a
_ Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la Map k a
lr') k
k a
a Map k a
r)
                ( \Map k a
lrl' k
lrk' a
lra' Map k a
lrr' Map k a
_ Map k a
_ ->
                    Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L Map k a
ll k
lk a
la Map k a
lrl')
                      k
lrk'
                      a
lra'
                      (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
lrr' k
k a
a Map k a
r)
                )
                Map k a
lr'
      )
      (\Map k a
lrl k
lrk a
lra Map k a
lrr Map k a
_ Map k a
_ -> Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k a -> k -> a -> Map k a -> Map k a
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B Map k a
ll k
lk a
la (Map k a -> k -> a -> Map k a -> Map k a
insertR Map k a
lrl k
lrk a
lra Map k a
lrr)) k
k a
a Map k a
r)
      Map k a
lr

{- | \(O(\log n)\) From an operation, a key and a map to the map updated by
applying the operation to the value associated with the key (setting if
'Just', deleting if 'Nothing')
-}
update :: (Ord k) => (a -> Maybe a) -> k -> Map k a -> Map k a
update :: forall k a. Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
update a -> Maybe a
f k
k Map k a
t =
  Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
    Map k a
t
    ( Map k a -> (a -> Map k a) -> Maybe a -> Map k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe
        (k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
delete k
k Map k a
t)
        (\a
a -> k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
insert k
k a
a Map k a
t)
        (Maybe a -> Map k a) -> (a -> Maybe a) -> a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Maybe a
f
    )
    (Maybe a -> Map k a) -> Maybe a -> Map k a
forall a b. (a -> b) -> a -> b
$ k -> Map k a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
lookup k
k Map k a
t

{-
 - Query
 -}

{- | \(O(n \log n)\) From a map and another map to whether the former is a
submap of the latter (matching on keys and values)
-}
isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
isSubmapOf :: forall k a. (Ord k, Eq a) => Map k a -> Map k a -> Bool
isSubmapOf Map k a
p Map k a
q =
  (k -> a -> Bool -> Bool) -> Bool -> Map k a -> Bool
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey
    (\k
k a
a Bool
b -> Bool -> (a -> Bool) -> Maybe a -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False ((Bool -> Bool -> Bool
&& Bool
b) (Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
a)) (Maybe a -> Bool) -> Maybe a -> Bool
forall a b. (a -> b) -> a -> b
$ k -> Map k a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
lookup k
k Map k a
q)
    Bool
True
    Map k a
p

{- | \(O(\log n)\) From a key and a map to the value associated with the key in
the map
-}
lookup :: (Ord k) => k -> Map k a -> Maybe a
lookup :: forall k a. Ord k => k -> Map k a -> Maybe a
lookup k
k = Maybe a
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> Map k a
-> Maybe a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map Maybe a
forall a. Maybe a
Nothing Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {a} {p}.
p -> k -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {a} {p}.
p -> k -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {a} {p}.
p -> k -> a -> p -> Maybe a -> Maybe a -> Maybe a
go
 where
  go :: p -> k -> a -> p -> Maybe a -> Maybe a -> Maybe a
go p
_ k
k' a
a p
_ Maybe a
recl Maybe a
recr = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k' of
    Ordering
LT -> Maybe a
recl
    Ordering
EQ -> a -> Maybe a
forall a. a -> Maybe a
Just a
a
    Ordering
GT -> Maybe a
recr

{- | \(O(\log n)\) From a map to the value associated with the maximum key in
the map
-}
lookupMax :: Map k a -> Maybe a
lookupMax :: forall k a. Map k a -> Maybe a
lookupMax = Maybe a
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> Map k a
-> Maybe a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map Maybe a
forall a. Maybe a
Nothing Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {a} {k} {a} {p}.
p -> p -> a -> Map k a -> p -> Maybe a -> Maybe a
go Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {a} {k} {a} {p}.
p -> p -> a -> Map k a -> p -> Maybe a -> Maybe a
go Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {a} {k} {a} {p}.
p -> p -> a -> Map k a -> p -> Maybe a -> Maybe a
go
 where
  go :: p -> p -> a -> Map k a -> p -> Maybe a -> Maybe a
go p
_ p
_ a
a Map k a
r p
_ Maybe a
recr = Maybe a
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> Map k a
-> Maybe a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map (a -> Maybe a
forall a. a -> Maybe a
Just a
a) Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe a
go' Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe a
go' Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe a
go' Map k a
r where go' :: p -> p -> p -> p -> p -> p -> Maybe a
go' p
_ p
_ p
_ p
_ p
_ p
_ = Maybe a
recr

{- | \(O(\log n)\) From a map to the value associated with the minimum key in
the map
-}
lookupMin :: Map k a -> Maybe a
lookupMin :: forall k a. Map k a -> Maybe a
lookupMin = Maybe a
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> Map k a
-> Maybe a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map Maybe a
forall a. Maybe a
Nothing Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {k} {a} {p} {a} {p} {p}.
Map k a -> p -> a -> p -> Maybe a -> p -> Maybe a
go Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {k} {a} {p} {a} {p} {p}.
Map k a -> p -> a -> p -> Maybe a -> p -> Maybe a
go Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {k} {a} {p} {a} {p} {p}.
Map k a -> p -> a -> p -> Maybe a -> p -> Maybe a
go
 where
  go :: Map k a -> p -> a -> p -> Maybe a -> p -> Maybe a
go Map k a
l p
_ a
a p
_ Maybe a
recl p
_ = Maybe a
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> (Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a)
-> Map k a
-> Maybe a
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map (a -> Maybe a
forall a. a -> Maybe a
Just a
a) Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe a
go' Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe a
go' Map k a -> k -> a -> Map k a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p} {p}.
p -> p -> p -> p -> p -> p -> Maybe a
go' Map k a
l where go' :: p -> p -> p -> p -> p -> p -> Maybe a
go' p
_ p
_ p
_ p
_ p
_ p
_ = Maybe a
recl

-- | \(O(\log n)\) From a key and a map to whether the key is in the map
member :: (Ord k) => k -> Map k a -> Bool
member :: forall k a. Ord k => k -> Map k a -> Bool
member k
k = Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map Bool
False Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p}. p -> k -> p -> p -> Bool -> Bool -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p}. p -> k -> p -> p -> Bool -> Bool -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p}. p -> k -> p -> p -> Bool -> Bool -> Bool
go
 where
  go :: p -> k -> p -> p -> Bool -> Bool -> Bool
go p
_ k
k' p
_ p
_ Bool
recl Bool
recr = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k k
k' of
    Ordering
LT -> Bool
recl
    Ordering
EQ -> Bool
True
    Ordering
GT -> Bool
recr

-- | \(O(1)\) From a map to whether the map is empty
null :: Map k a -> Bool
null :: forall k a. Map k a -> Bool
null = Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map Bool
True Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> p -> Bool
go where go :: p -> p -> p -> p -> p -> p -> Bool
go p
_ p
_ p
_ p
_ p
_ p
_ = Bool
False

-- | \(O(n)\) From a map to the size of the map
size :: Map k a -> Int
size :: forall k a. Map k a -> Int
size =
  Int
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> Map k a
-> Int
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
    Int
0
    (\Map k a
_ k
_ a
_ Map k a
_ Int
recl Int
recr -> Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recl Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recr)
    (\Map k a
_ k
_ a
_ Map k a
_ Int
recl Int
recr -> Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recl Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recr)
    (\Map k a
_ k
_ a
_ Map k a
_ Int
recl Int
recr -> Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recl Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recr)

{-
 - Traversal
 -}

{- | \(O(n)\) From a lifting operation on keys and values and a map to a lifted
map
-}
traverseWithKey :: (Applicative f) => (k -> a -> f b) -> Map k a -> f (Map k b)
traverseWithKey :: forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> Map k a -> f (Map k b)
traverseWithKey k -> a -> f b
f =
  f (Map k b)
-> (Map k a
    -> k -> a -> Map k a -> f (Map k b) -> f (Map k b) -> f (Map k b))
-> (Map k a
    -> k -> a -> Map k a -> f (Map k b) -> f (Map k b) -> f (Map k b))
-> (Map k a
    -> k -> a -> Map k a -> f (Map k b) -> f (Map k b) -> f (Map k b))
-> Map k a
-> f (Map k b)
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
    (Map k b -> f (Map k b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Map k b
forall k a. Map k a
E)
    (\Map k a
_ k
k a
a Map k a
_ f (Map k b)
recl f (Map k b)
recr -> Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
L (Map k b -> k -> b -> Map k b -> Map k b)
-> f (Map k b) -> f (k -> b -> Map k b -> Map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Map k b)
recl f (k -> b -> Map k b -> Map k b)
-> f k -> f (b -> Map k b -> Map k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> k -> f k
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure k
k f (b -> Map k b -> Map k b) -> f b -> f (Map k b -> Map k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> k -> a -> f b
f k
k a
a f (Map k b -> Map k b) -> f (Map k b) -> f (Map k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> f (Map k b)
recr)
    (\Map k a
_ k
k a
a Map k a
_ f (Map k b)
recl f (Map k b)
recr -> Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
B (Map k b -> k -> b -> Map k b -> Map k b)
-> f (Map k b) -> f (k -> b -> Map k b -> Map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Map k b)
recl f (k -> b -> Map k b -> Map k b)
-> f k -> f (b -> Map k b -> Map k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> k -> f k
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure k
k f (b -> Map k b -> Map k b) -> f b -> f (Map k b -> Map k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> k -> a -> f b
f k
k a
a f (Map k b -> Map k b) -> f (Map k b) -> f (Map k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> f (Map k b)
recr)
    (\Map k a
_ k
k a
a Map k a
_ f (Map k b)
recl f (Map k b)
recr -> Map k b -> k -> b -> Map k b -> Map k b
forall k a. Map k a -> k -> a -> Map k a -> Map k a
R (Map k b -> k -> b -> Map k b -> Map k b)
-> f (Map k b) -> f (k -> b -> Map k b -> Map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Map k b)
recl f (k -> b -> Map k b -> Map k b)
-> f k -> f (b -> Map k b -> Map k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> k -> f k
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure k
k f (b -> Map k b -> Map k b) -> f b -> f (Map k b -> Map k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> k -> a -> f b
f k
k a
a f (Map k b -> Map k b) -> f (Map k b) -> f (Map k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> f (Map k b)
recr)

{-
 - Validation
 -}

{- | \(O(n)\) From a map to whether its internal structure is valid, i.e.
height-balanced and ordered
-}
valid :: (Ord k) => Map k a -> Bool
valid :: forall k a. Ord k => Map k a -> Bool
valid = (Bool -> Bool -> Bool)
-> (Map k a -> Bool) -> (Map k a -> Bool) -> Map k a -> Bool
forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 Bool -> Bool -> Bool
(&&) Map k a -> Bool
forall k a. Map k a -> Bool
balanced Map k a -> Bool
forall {a}. Map k a -> Bool
ordered
 where
  balanced :: Map k a -> Bool
balanced =
    Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
      Bool
True
      (\Map k a
l k
_ a
_ Map k a
r Bool
recl Bool
recr -> Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
      (\Map k a
l k
_ a
_ Map k a
r Bool
recl Bool
recr -> Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
      (\Map k a
l k
_ a
_ Map k a
r Bool
recl Bool
recr -> Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Map k a -> Int
forall k a. Map k a -> Int
levels Map k a
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
  levels :: Map k a -> Int
levels = Int
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> (Map k a -> k -> a -> Map k a -> Int -> Int -> Int)
-> Map k a
-> Int
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map Int
0 Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {p} {p} {p} {p}. p -> p -> p -> p -> Int -> Int -> Int
go Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {p} {p} {p} {p}. p -> p -> p -> p -> Int -> Int -> Int
go Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {p} {p} {p} {p}. p -> p -> p -> p -> Int -> Int -> Int
go where go :: p -> p -> p -> p -> Int -> Int -> Int
go p
_ p
_ p
_ p
_ Int
recl Int
recr = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
recl Int
recr :: Int
  ordered :: Map k a -> Bool
ordered = Bool
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> (Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool)
-> Map k a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map Bool
True Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {a} {a} {p} {a}.
Ord a =>
Map a a -> a -> p -> Map a a -> Bool -> Bool -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {a} {a} {p} {a}.
Ord a =>
Map a a -> a -> p -> Map a a -> Bool -> Bool -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {a} {a} {p} {a}.
Ord a =>
Map a a -> a -> p -> Map a a -> Bool -> Bool -> Bool
go
   where
    go :: Map a a -> a -> p -> Map a a -> Bool -> Bool -> Bool
go Map a a
l a
k p
_ Map a a
r Bool
recl Bool
recr =
      Bool
-> (Map a a -> a -> a -> Map a a -> Bool -> Bool -> Bool)
-> (Map a a -> a -> a -> Map a a -> Bool -> Bool -> Bool)
-> (Map a a -> a -> a -> Map a a -> Bool -> Bool -> Bool)
-> Map a a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
        Bool
True
        (\Map a a
_ a
lk a
_ Map a a
_ Bool
_ Bool
_ -> a
lk a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
k Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
        (\Map a a
_ a
lk a
_ Map a a
_ Bool
_ Bool
_ -> a
lk a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
k Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
        (\Map a a
_ a
lk a
_ Map a a
_ Bool
_ Bool
_ -> a
lk a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
k Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
        Map a a
l
        Bool -> Bool -> Bool
&& Bool
-> (Map a a -> a -> a -> Map a a -> Bool -> Bool -> Bool)
-> (Map a a -> a -> a -> Map a a -> Bool -> Bool -> Bool)
-> (Map a a -> a -> a -> Map a a -> Bool -> Bool -> Bool)
-> Map a a
-> Bool
forall b k a.
b
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> (Map k a -> k -> a -> Map k a -> b -> b -> b)
-> Map k a
-> b
map
          Bool
True
          (\Map a a
_ a
rk a
_ Map a a
_ Bool
_ Bool
_ -> a
rk a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
          (\Map a a
_ a
rk a
_ Map a a
_ Bool
_ Bool
_ -> a
rk a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
          (\Map a a
_ a
rk a
_ Map a a
_ Bool
_ Bool
_ -> a
rk a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
k Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
          Map a a
r