module Mini.Data.Map (
Map,
empty,
fromList,
singleton,
difference,
intersection,
union,
toAscList,
toDescList,
foldlWithKey,
foldrWithKey,
adjust,
delete,
filter,
filterWithKey,
insert,
update,
isSubmapOf,
lookup,
lookupMax,
lookupMin,
member,
null,
size,
traverseWithKey,
valid,
) where
import Control.Monad (
liftM2,
)
import Data.Bool (
bool,
)
import Prelude (
Applicative,
Bool (
False,
True
),
Eq,
Foldable,
Functor,
Int,
Maybe (
Just,
Nothing
),
Monoid,
Ord,
Ordering (
EQ,
GT,
LT
),
Semigroup,
Show,
Traversable,
compare,
const,
error,
flip,
fmap,
foldl,
foldr,
max,
maybe,
mempty,
not,
pure,
show,
traverse,
uncurry,
($),
(&&),
(+),
(-),
(.),
(<),
(<$>),
(<*>),
(<>),
(==),
(>),
)
data Map k a
=
E
|
L (Map k a) k a (Map k a)
|
B (Map k a) k a (Map k a)
|
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 b -> 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
forall {t} {t} {t} {p} {p}.
(t -> t -> b -> t) -> p -> t -> a -> p -> t -> t
go 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)
-> Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b
forall {t} {t} {t} {p} {p}.
(t -> t -> b -> t) -> p -> t -> a -> p -> t -> t
go 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)
-> Map k a -> k -> a -> Map k a -> Map k b -> Map k b -> Map k b
forall {t} {t} {t} {p} {p}.
(t -> t -> b -> t) -> p -> t -> a -> p -> t -> t
go 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)
where
go :: (t -> t -> b -> t) -> p -> t -> a -> p -> t -> t
go t -> t -> b -> t
c p
_ t
k a
a p
_ t
recl = t -> t -> b -> t
c t
recl t
k (a -> b
f a
a)
instance Foldable (Map k) where
foldr :: forall a b. (a -> b -> b) -> b -> Map k a -> b
foldr = (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) -> b -> Map k a -> b)
-> ((a -> b -> b) -> k -> a -> b -> b)
-> (a -> b -> b)
-> b
-> Map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> k -> a -> b -> b
forall a b. a -> b -> a
const
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
map
:: 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 :: 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)
empty :: Map k a
empty :: forall k a. Map k a
empty = Map k a
forall k a. Map k a
E
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
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
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)
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
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
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) []
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) []
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
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
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 -> 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
forall {t} {t} {t}.
(t -> k -> a -> t -> t) -> t -> k -> a -> t -> t -> t -> t
go 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)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {t} {t} {t}.
(t -> k -> a -> t -> t) -> t -> k -> a -> t -> t -> t -> t
go 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)
-> Map k a -> k -> a -> Map k a -> Map k a -> Map k a -> Map k a
forall {t} {t} {t}.
(t -> k -> a -> t -> t) -> t -> k -> a -> t -> t -> t -> t
go 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)
where
go :: (t -> k -> a -> t -> t) -> t -> k -> a -> t -> t -> t -> t
go t -> k -> a -> t -> t
c t
l k
k a
a t
r t
recl t
recr = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
k0 k
k of
Ordering
LT -> t -> k -> a -> t -> t
c t
recl k
k a
a t
r
Ordering
EQ -> t -> k -> a -> t -> t
c t
l k
k (a -> a
f a
a) t
r
Ordering
GT -> t -> k -> a -> t -> t
c t
l k
k a
a t
recr
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
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
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
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
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
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
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
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
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
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
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
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 -> Int -> Int
forall {a} {p} {p} {p} {p}.
Num a =>
p -> p -> p -> p -> a -> a -> a
go Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {a} {p} {p} {p} {p}.
Num a =>
p -> p -> p -> p -> a -> a -> a
go Map k a -> k -> a -> Map k a -> Int -> Int -> Int
forall {a} {p} {p} {p} {p}.
Num a =>
p -> p -> p -> p -> a -> a -> a
go
where
go :: p -> p -> p -> p -> a -> a -> a
go p
_ p
_ p
_ p
_ a
recl a
recr = a
1 a -> a -> a
forall a. Num a => a -> a -> a
+ a
recl a -> a -> a
forall a. Num a => a -> a -> a
+ a
recr
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 b -> k -> b -> Map k b -> Map k b)
-> Map k a
-> k
-> a
-> Map k a
-> f (Map k b)
-> f (Map k b)
-> f (Map k b)
forall {a} {a} {b} {p} {p}.
(a -> k -> b -> a -> b) -> p -> k -> a -> p -> f a -> f a -> f b
go 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)
-> Map k a
-> k
-> a
-> Map k a
-> f (Map k b)
-> f (Map k b)
-> f (Map k b)
forall {a} {a} {b} {p} {p}.
(a -> k -> b -> a -> b) -> p -> k -> a -> p -> f a -> f a -> f b
go 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)
-> Map k a
-> k
-> a
-> Map k a
-> f (Map k b)
-> f (Map k b)
-> f (Map k b)
forall {a} {a} {b} {p} {p}.
(a -> k -> b -> a -> b) -> p -> k -> a -> p -> f a -> f a -> f b
go 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)
where
go :: (a -> k -> b -> a -> b) -> p -> k -> a -> p -> f a -> f a -> f b
go a -> k -> b -> a -> b
c p
_ k
k a
a p
_ f a
recl f a
recr = a -> k -> b -> a -> b
c (a -> k -> b -> a -> b) -> f a -> f (k -> b -> a -> b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f a
recl f (k -> b -> a -> b) -> f k -> f (b -> a -> 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 -> a -> b) -> f b -> f (a -> 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 (a -> b) -> f a -> f 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 a
recr
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 {k} {a} {p} {a}.
Ord k =>
Map k a -> k -> p -> Map k a -> Bool -> Bool -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {k} {a} {p} {a}.
Ord k =>
Map k a -> k -> p -> Map k a -> Bool -> Bool -> Bool
go Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {k} {a} {p} {a}.
Ord k =>
Map k a -> k -> p -> Map k a -> Bool -> Bool -> Bool
go
where
go :: Map k a -> k -> p -> Map k a -> Bool -> Bool -> Bool
go Map k a
l k
k p
_ Map k a
r Bool
recl Bool
recr =
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 -> k -> p -> p -> p -> p -> Bool
lt Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> k -> p -> p -> p -> p -> Bool
lt Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> k -> p -> p -> p -> p -> Bool
lt Map k a
l
Bool -> 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 -> 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 -> k -> p -> p -> p -> p -> Bool
gt Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> k -> p -> p -> p -> p -> Bool
gt Map k a -> k -> a -> Map k a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> k -> p -> p -> p -> p -> Bool
gt Map k a
r
where
lt :: p -> k -> p -> p -> p -> p -> Bool
lt p
_ k
lk p
_ p
_ p
_ p
_ = k
lk k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr
gt :: p -> k -> p -> p -> p -> p -> Bool
gt p
_ k
rk p
_ p
_ p
_ p
_ = k
rk k -> k -> Bool
forall a. Ord a => a -> a -> Bool
> k
k Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr