{-# LANGUAGE LambdaCase #-}
module Mini.Data.Set (
Set,
difference,
intersection,
union,
empty,
fromList,
singleton,
toAscList,
toDescList,
delete,
filter,
insert,
isSubsetOf,
lookupMax,
lookupMin,
member,
null,
size,
valid,
) where
import Control.Monad (
liftM2,
)
import Data.Bifunctor (
first,
)
import Data.Bool (
bool,
)
import Prelude hiding (
filter,
null,
)
data Set a
=
E
|
L (Set a) a (Set a)
|
B (Set a) a (Set a)
|
R (Set a) a (Set a)
deriving (Set a -> Set a -> Bool
(Set a -> Set a -> Bool) -> (Set a -> Set a -> Bool) -> Eq (Set a)
forall a. Eq a => Set a -> Set a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Set a -> Set a -> Bool
== :: Set a -> Set a -> Bool
$c/= :: forall a. Eq a => Set a -> Set a -> Bool
/= :: Set a -> Set a -> Bool
Eq, Eq (Set a)
Eq (Set a) =>
(Set a -> Set a -> Ordering)
-> (Set a -> Set a -> Bool)
-> (Set a -> Set a -> Bool)
-> (Set a -> Set a -> Bool)
-> (Set a -> Set a -> Bool)
-> (Set a -> Set a -> Set a)
-> (Set a -> Set a -> Set a)
-> Ord (Set a)
Set a -> Set a -> Bool
Set a -> Set a -> Ordering
Set a -> Set a -> Set 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 a. Ord a => Eq (Set a)
forall a. Ord a => Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Ordering
forall a. Ord a => Set a -> Set a -> Set a
$ccompare :: forall a. Ord a => Set a -> Set a -> Ordering
compare :: Set a -> Set a -> Ordering
$c< :: forall a. Ord a => Set a -> Set a -> Bool
< :: Set a -> Set a -> Bool
$c<= :: forall a. Ord a => Set a -> Set a -> Bool
<= :: Set a -> Set a -> Bool
$c> :: forall a. Ord a => Set a -> Set a -> Bool
> :: Set a -> Set a -> Bool
$c>= :: forall a. Ord a => Set a -> Set a -> Bool
>= :: Set a -> Set a -> Bool
$cmax :: forall a. Ord a => Set a -> Set a -> Set a
max :: Set a -> Set a -> Set a
$cmin :: forall a. Ord a => Set a -> Set a -> Set a
min :: Set a -> Set a -> Set a
Ord)
instance (Show a) => Show (Set a) where
show :: Set a -> String
show = ShowS
curl ShowS -> (Set a -> String) -> Set a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String
-> (Set a -> a -> Set a -> String -> ShowS)
-> (Set a -> a -> Set a -> String -> ShowS)
-> (Set a -> a -> Set a -> String -> ShowS)
-> Set a
-> String
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set [] Set a -> a -> Set a -> String -> ShowS
forall {a} {p} {p}. Show a => p -> a -> p -> String -> ShowS
go Set a -> a -> Set a -> String -> ShowS
forall {a} {p} {p}. Show a => p -> a -> p -> String -> ShowS
go Set a -> a -> Set a -> String -> ShowS
forall {a} {p} {p}. Show a => p -> a -> p -> String -> ShowS
go
where
go :: p -> a -> p -> String -> ShowS
go p
_ a
a p
_ String
recl String
recr = String
recl String -> ShowS
forall a. Semigroup a => a -> a -> a
<> a -> String
forall a. Show a => a -> String
show a
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 = \case
[] -> []
[a
_] -> []
(a
c : [a]
cs) -> a
c a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a] -> [a]
removeTrailingComma [a]
cs
instance Foldable Set where
foldr :: forall a b. (a -> b -> b) -> b -> Set a -> b
foldr a -> b -> b
f b
b = b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set b
b Set a -> a -> Set a -> b -> b -> b
forall {t :: * -> *} {p} {p}.
Foldable t =>
p -> a -> t a -> b -> p -> b
go Set a -> a -> Set a -> b -> b -> b
forall {t :: * -> *} {p} {p}.
Foldable t =>
p -> a -> t a -> b -> p -> b
go Set a -> a -> Set a -> b -> b -> b
forall {t :: * -> *} {p} {p}.
Foldable t =>
p -> a -> t a -> b -> p -> b
go where go :: p -> a -> t a -> b -> p -> b
go p
_ a
a t a
r b
recl p
_ = (a -> b -> b) -> b -> t a -> b
forall a b. (a -> b -> b) -> b -> t a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f (a -> b -> b
f a
a b
recl) t a
r
set
:: b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set :: forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set b
e Set a -> a -> Set a -> b -> b -> b
_ Set a -> a -> Set a -> b -> b -> b
_ Set a -> a -> Set a -> b -> b -> b
_ Set a
E = b
e
set b
e Set a -> a -> Set a -> b -> b -> b
f Set a -> a -> Set a -> b -> b -> b
g Set a -> a -> Set a -> b -> b -> b
h (L Set a
l a
a Set a
r) = Set a -> a -> Set a -> b -> b -> b
f Set a
l a
a Set a
r (b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set b
e Set a -> a -> Set a -> b -> b -> b
f Set a -> a -> Set a -> b -> b -> b
g Set a -> a -> Set a -> b -> b -> b
h Set a
l) (b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set b
e Set a -> a -> Set a -> b -> b -> b
f Set a -> a -> Set a -> b -> b -> b
g Set a -> a -> Set a -> b -> b -> b
h Set a
r)
set b
e Set a -> a -> Set a -> b -> b -> b
f Set a -> a -> Set a -> b -> b -> b
g Set a -> a -> Set a -> b -> b -> b
h (B Set a
l a
a Set a
r) = Set a -> a -> Set a -> b -> b -> b
g Set a
l a
a Set a
r (b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set b
e Set a -> a -> Set a -> b -> b -> b
f Set a -> a -> Set a -> b -> b -> b
g Set a -> a -> Set a -> b -> b -> b
h Set a
l) (b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set b
e Set a -> a -> Set a -> b -> b -> b
f Set a -> a -> Set a -> b -> b -> b
g Set a -> a -> Set a -> b -> b -> b
h Set a
r)
set b
e Set a -> a -> Set a -> b -> b -> b
f Set a -> a -> Set a -> b -> b -> b
g Set a -> a -> Set a -> b -> b -> b
h (R Set a
l a
a Set a
r) = Set a -> a -> Set a -> b -> b -> b
h Set a
l a
a Set a
r (b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set b
e Set a -> a -> Set a -> b -> b -> b
f Set a -> a -> Set a -> b -> b -> b
g Set a -> a -> Set a -> b -> b -> b
h Set a
l) (b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set b
e Set a -> a -> Set a -> b -> b -> b
f Set a -> a -> Set a -> b -> b -> b
g Set a -> a -> Set a -> b -> b -> b
h Set a
r)
difference :: (Ord a) => Set a -> Set a -> Set a
difference :: forall a. Ord a => Set a -> Set a -> Set a
difference = (a -> Set a -> Set a) -> Set a -> Set a -> Set a
forall a b. (a -> b -> b) -> b -> Set a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
delete
intersection :: (Ord a) => Set a -> Set a -> Set a
intersection :: forall a. Ord a => Set a -> Set a -> Set a
intersection Set a
t = (a -> Set a -> Set a) -> Set a -> Set a -> Set a
forall a b. (a -> b -> b) -> b -> Set a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\a
a Set a
b -> Set a -> Set a -> Bool -> Set a
forall a. a -> a -> Bool -> a
bool Set a
b (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert a
a Set a
b) (a
a a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`member` Set a
t)) Set a
forall a. Set a
empty
union :: (Ord a) => Set a -> Set a -> Set a
union :: forall a. Ord a => Set a -> Set a -> Set a
union = (a -> Set a -> Set a) -> Set a -> Set a -> Set a
forall a b. (a -> b -> b) -> b -> Set a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert
empty :: Set a
empty :: forall a. Set a
empty = Set a
forall a. Set a
E
fromList :: (Ord a) => [a] -> Set a
fromList :: forall a. Ord a => [a] -> Set a
fromList = (Set a -> a -> Set a) -> Set a -> [a] -> Set a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ((a -> Set a -> Set a) -> Set a -> a -> Set a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert) Set a
forall a. Set a
empty
singleton :: a -> Set a
singleton :: forall a. a -> Set a
singleton a
a = Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
forall a. Set a
E a
a Set a
forall a. Set a
E
toAscList :: Set a -> [a]
toAscList :: forall a. Set a -> [a]
toAscList = ([a] -> a -> [a]) -> [a] -> Set a -> [a]
forall b a. (b -> a -> b) -> b -> Set a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ((a -> [a] -> [a]) -> [a] -> a -> [a]
forall a b c. (a -> b -> c) -> b -> a -> c
flip (:)) []
toDescList :: Set a -> [a]
toDescList :: forall a. Set a -> [a]
toDescList = (a -> [a] -> [a]) -> [a] -> Set a -> [a]
forall a b. (a -> b -> b) -> b -> Set a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) []
delete :: (Ord a) => a -> Set a -> Set a
delete :: forall a. Ord a => a -> Set a -> Set a
delete a
a0 Set a
t = Set a -> Set a -> Bool -> Set a
forall a. a -> a -> Bool -> a
bool Set a
t (Set a -> Set a
go Set a
t) (a
a0 a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`member` Set a
t)
where
go :: Set a -> Set a
go =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L0")
( \Set a
l a
a Set a
r Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
a of
Ordering
LT -> Set a -> a -> Set a -> Set a
deleteLl Set a
l a
a Set a
r
Ordering
EQ -> Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteL Set a
l Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
deleteLr Set a
l a
a Set a
r
)
( \Set a
l a
a Set a
r Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
a of
Ordering
LT -> Set a -> a -> Set a -> Set a
deleteBl Set a
l a
a Set a
r
Ordering
EQ -> Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteBr Set a
l Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
deleteBr Set a
l a
a Set a
r
)
( \Set a
l a
a Set a
r Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
a of
Ordering
LT -> Set a -> a -> Set a -> Set a
deleteRl Set a
l a
a Set a
r
Ordering
EQ -> Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteR Set a
l Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
deleteRr Set a
l a
a Set a
r
)
deleteRl :: Set a -> a -> Set a -> Set a
deleteRl Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L1")
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
la of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftR (Set a -> a -> Set a -> Set a
deleteLl Set a
ll a
la Set a
lr) a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftR (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteL Set a
ll Set a
lr) a
a Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftR (Set a -> a -> Set a -> Set a
deleteLr Set a
ll a
la Set a
lr) a
a Set a
r
)
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
la of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R (Set a -> a -> Set a -> Set a
deleteBl Set a
ll a
la Set a
lr) a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftR' (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteBr Set a
ll Set a
lr) a
a Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R (Set a -> a -> Set a -> Set a
deleteBr Set a
ll a
la Set a
lr) a
a Set a
r
)
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
la of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftR (Set a -> a -> Set a -> Set a
deleteRl Set a
ll a
la Set a
lr) a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftR (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteR Set a
ll Set a
lr) a
a Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftR (Set a -> a -> Set a -> Set a
deleteRr Set a
ll a
la Set a
lr) a
a Set a
r
)
Set a
l
deleteRr :: Set a -> a -> Set a -> Set a
deleteRr Set a
l a
a =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L2")
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
ra of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightR Set a
l a
a (Set a -> a -> Set a -> Set a
deleteLl Set a
rl a
ra Set a
rr)
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightR Set a
l a
a (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteL Set a
rl Set a
rr)
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightR Set a
l a
a (Set a -> a -> Set a -> Set a
deleteLr Set a
rl a
ra Set a
rr)
)
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
ra of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
deleteBl Set a
rl a
ra Set a
rr)
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightR' Set a
l a
a (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteBl Set a
rl Set a
rr)
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
deleteBr Set a
rl a
ra Set a
rr)
)
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
ra of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightR Set a
l a
a (Set a -> a -> Set a -> Set a
deleteRl Set a
rl a
ra Set a
rr)
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightR Set a
l a
a (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteR Set a
rl Set a
rr)
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightR Set a
l a
a (Set a -> a -> Set a -> Set a
deleteRr Set a
rl a
ra Set a
rr)
)
deleteBl :: Set a -> a -> Set a -> Set a
deleteBl Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L3")
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
la of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftB (Set a -> a -> Set a -> Set a
deleteLl Set a
ll a
la Set a
lr) a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftB (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteL Set a
ll Set a
lr) a
a Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftB (Set a -> a -> Set a -> Set a
deleteLr Set a
ll a
la Set a
lr) a
a Set a
r
)
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
la of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
deleteBl Set a
ll a
la Set a
lr) a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftB' (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteBr Set a
ll Set a
lr) a
a Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
deleteBr Set a
ll a
la Set a
lr) a
a Set a
r
)
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
la of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftB (Set a -> a -> Set a -> Set a
deleteRl Set a
ll a
la Set a
lr) a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftB (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteR Set a
ll Set a
lr) a
a Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftB (Set a -> a -> Set a -> Set a
deleteRr Set a
ll a
la Set a
lr) a
a Set a
r
)
Set a
l
deleteBr :: Set a -> a -> Set a -> Set a
deleteBr Set a
l a
a =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L4")
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
ra of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightB Set a
l a
a (Set a -> a -> Set a -> Set a
deleteLl Set a
rl a
ra Set a
rr)
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightB Set a
l a
a (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteL Set a
rl Set a
rr)
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightB Set a
l a
a (Set a -> a -> Set a -> Set a
deleteLr Set a
rl a
ra Set a
rr)
)
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
ra of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a (Set a -> a -> Set a -> Set a
deleteBl Set a
rl a
ra Set a
rr)
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightB' Set a
l a
a (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteBl Set a
rl Set a
rr)
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a (Set a -> a -> Set a -> Set a
deleteBr Set a
rl a
ra Set a
rr)
)
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
ra of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightB Set a
l a
a (Set a -> a -> Set a -> Set a
deleteRl Set a
rl a
ra Set a
rr)
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightB Set a
l a
a (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteR Set a
rl Set a
rr)
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightB Set a
l a
a (Set a -> a -> Set a -> Set a
deleteRr Set a
rl a
ra Set a
rr)
)
deleteLl :: Set a -> a -> Set a -> Set a
deleteLl Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L5")
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
la of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftL (Set a -> a -> Set a -> Set a
deleteLl Set a
ll a
la Set a
lr) a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftL (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteL Set a
ll Set a
lr) a
a Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftL (Set a -> a -> Set a -> Set a
deleteLr Set a
ll a
la Set a
lr) a
a Set a
r
)
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
la of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
deleteBl Set a
ll a
la Set a
lr) a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftL' (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteBr Set a
ll Set a
lr) a
a Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
deleteBr Set a
ll a
la Set a
lr) a
a Set a
r
)
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
la of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftL (Set a -> a -> Set a -> Set a
deleteRl Set a
ll a
la Set a
lr) a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftL (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteR Set a
ll Set a
lr) a
a Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftL (Set a -> a -> Set a -> Set a
deleteRr Set a
ll a
la Set a
lr) a
a Set a
r
)
Set a
l
deleteLr :: Set a -> a -> Set a -> Set a
deleteLr Set a
l a
a =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L6")
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
ra of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightL Set a
l a
a (Set a -> a -> Set a -> Set a
deleteLl Set a
rl a
ra Set a
rr)
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightL Set a
l a
a (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteL Set a
rl Set a
rr)
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightL Set a
l a
a (Set a -> a -> Set a -> Set a
deleteLr Set a
rl a
ra Set a
rr)
)
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
ra of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a (Set a -> a -> Set a -> Set a
deleteBl Set a
rl a
ra Set a
rr)
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightL' Set a
l a
a (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteBl Set a
rl Set a
rr)
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a (Set a -> a -> Set a -> Set a
deleteBr Set a
rl a
ra Set a
rr)
)
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
ra of
Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightL Set a
l a
a (Set a -> a -> Set a -> Set a
deleteRl Set a
rl a
ra Set a
rr)
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightL Set a
l a
a (Set a -> Set a -> Set a
forall {a}. Set a -> Set a -> Set a
substituteR Set a
rl Set a
rr)
Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightL Set a
l a
a (Set a -> a -> Set a -> Set a
deleteRr Set a
rl a
ra Set a
rr)
)
rebalanceR :: Set a -> a -> Set a -> Set a
rebalanceR Set a
l a
a =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L7")
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L8")
(\Set a
rll a
rla Set a
rlr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
rll) a
rla (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
rlr a
ra Set a
rr))
(\Set a
rll a
rla Set a
rlr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
rll) a
rla (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
rlr a
ra Set a
rr))
(\Set a
rll a
rla Set a
rlr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
rll) a
rla (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
rlr a
ra Set a
rr))
Set a
rl
)
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
rl) a
ra Set a
rr)
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
rl) a
ra Set a
rr)
rebalanceL :: Set a -> a -> Set a -> Set a
rebalanceL Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L9")
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll a
la (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
lr a
a Set a
r))
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
ll a
la (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
lr a
a Set a
r))
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L10")
(\Set a
lrl a
lra Set a
lrr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll a
la Set a
lrl) a
lra (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
lrr a
a Set a
r))
(\Set a
lrl a
lra Set a
lrr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll a
la Set a
lrl) a
lra (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
lrr a
a Set a
r))
(\Set a
lrl a
lra Set a
lrr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
ll a
la Set a
lrl) a
lra (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
lrr a
a Set a
r))
Set a
lr
)
Set a
l
checkLeftR :: Set a -> a -> Set a -> Set a
checkLeftR Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L11")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
rebalanceR Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
Set a
l
checkLeftB :: Set a -> a -> Set a -> Set a
checkLeftB Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L12")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
Set a
l
checkLeftL :: Set a -> a -> Set a -> Set a
checkLeftL Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L13")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
Set a
l
checkRightR :: Set a -> a -> Set a -> Set a
checkRightR Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L14")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
Set a
r
checkRightB :: Set a -> a -> Set a -> Set a
checkRightB Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L15")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
Set a
r
checkRightL :: Set a -> a -> Set a -> Set a
checkRightL Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L16")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
rebalanceL Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
Set a
r
substituteR :: Set a -> Set a -> Set a
substituteR Set a
l =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L17")
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> (a -> Set a -> Set a) -> (a, Set a) -> Set a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightR Set a
l) ((a, Set a) -> Set a) -> (a, Set a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (a, Set a)
forall {t}. Set t -> t -> Set t -> (t, Set t)
popLeftL Set a
rl a
ra Set a
rr)
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> (a -> Set a -> Set a) -> (a, Set a) -> Set a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightR' Set a
l) ((a, Set a) -> Set a) -> (a, Set a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (a, Set a)
forall {t}. Set t -> t -> Set t -> (t, Set t)
popLeftB Set a
rl a
ra Set a
rr)
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> (a -> Set a -> Set a) -> (a, Set a) -> Set a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightR Set a
l) ((a, Set a) -> Set a) -> (a, Set a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (a, Set a)
forall {t}. Set t -> t -> Set t -> (t, Set t)
popLeftR Set a
rl a
ra Set a
rr)
substituteBr :: Set a -> Set a -> Set a
substituteBr Set a
l =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
Set a
forall a. Set a
E
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> (a -> Set a -> Set a) -> (a, Set a) -> Set a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightB Set a
l) ((a, Set a) -> Set a) -> (a, Set a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (a, Set a)
forall {t}. Set t -> t -> Set t -> (t, Set t)
popLeftL Set a
rl a
ra Set a
rr)
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> (a -> Set a -> Set a) -> (a, Set a) -> Set a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightB' Set a
l) ((a, Set a) -> Set a) -> (a, Set a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (a, Set a)
forall {t}. Set t -> t -> Set t -> (t, Set t)
popLeftB Set a
rl a
ra Set a
rr)
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> (a -> Set a -> Set a) -> (a, Set a) -> Set a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkRightB Set a
l) ((a, Set a) -> Set a) -> (a, Set a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (a, Set a)
forall {t}. Set t -> t -> Set t -> (t, Set t)
popLeftR Set a
rl a
ra Set a
rr)
substituteBl :: Set a -> Set a -> Set a
substituteBl Set a
l Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
Set a
forall a. Set a
E
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> (\(Set a
l', a
a) -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftB Set a
l' a
a Set a
r) ((Set a, a) -> Set a) -> (Set a, a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (Set a, a)
forall {t}. Set t -> t -> Set t -> (Set t, t)
popRightL Set a
ll a
la Set a
lr)
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> (\(Set a
l', a
a) -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftB' Set a
l' a
a Set a
r) ((Set a, a) -> Set a) -> (Set a, a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (Set a, a)
forall {t}. Set t -> t -> Set t -> (Set t, t)
popRightB Set a
ll a
la Set a
lr)
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> (\(Set a
l', a
a) -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftB Set a
l' a
a Set a
r) ((Set a, a) -> Set a) -> (Set a, a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (Set a, a)
forall {t}. Set t -> t -> Set t -> (Set t, t)
popRightR Set a
ll a
la Set a
lr)
Set a
l
substituteL :: Set a -> Set a -> Set a
substituteL Set a
l Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.delete: L18")
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> (\(Set a
l', a
a) -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftL Set a
l' a
a Set a
r) ((Set a, a) -> Set a) -> (Set a, a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (Set a, a)
forall {t}. Set t -> t -> Set t -> (Set t, t)
popRightL Set a
ll a
la Set a
lr)
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> (\(Set a
l', a
a) -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftL' Set a
l' a
a Set a
r) ((Set a, a) -> Set a) -> (Set a, a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (Set a, a)
forall {t}. Set t -> t -> Set t -> (Set t, t)
popRightB Set a
ll a
la Set a
lr)
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> (\(Set a
l', a
a) -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
checkLeftL Set a
l' a
a Set a
r) ((Set a, a) -> Set a) -> (Set a, a) -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> a -> Set a -> (Set a, a)
forall {t}. Set t -> t -> Set t -> (Set t, t)
popRightR Set a
ll a
la Set a
lr)
Set a
l
checkLeftR' :: Set a -> a -> Set a -> Set a
checkLeftR' Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
rebalanceR Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
Set a
l
checkLeftB' :: Set a -> a -> Set a -> Set a
checkLeftB' Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
Set a
l
checkLeftL' :: Set a -> a -> Set a -> Set a
checkLeftL' Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
Set a
l
checkRightR' :: Set a -> a -> Set a -> Set a
checkRightR' Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
Set a
r
checkRightB' :: Set a -> a -> Set a -> Set a
checkRightB' Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
Set a
r
checkRightL' :: Set a -> a -> Set a -> Set a
checkRightL' Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
rebalanceL Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
Set a
r
popLeftR :: Set t -> t -> Set t -> (t, Set t)
popLeftR Set t
l t
a Set t
r =
(t, Set t)
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> Set t
-> (t, Set t)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(t
a, Set t
r)
( \Set t
ll t
la Set t
lr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l') -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkLeftR Set t
l' t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> (t, Set t)
popLeftL Set t
ll t
la Set t
lr
)
(\Set t
ll t
la Set t
lr (t, Set t)
_ (t, Set t)
_ -> Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftRB Set t
ll t
la Set t
lr t
a Set t
r)
( \Set t
ll t
la Set t
lr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l') -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkLeftR Set t
l' t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> (t, Set t)
popLeftR Set t
ll t
la Set t
lr
)
Set t
l
popLeftB :: Set a -> a -> Set a -> (a, Set a)
popLeftB Set a
l a
a Set a
r =
(a, Set a)
-> (Set a -> a -> Set a -> (a, Set a) -> (a, Set a) -> (a, Set a))
-> (Set a -> a -> Set a -> (a, Set a) -> (a, Set a) -> (a, Set a))
-> (Set a -> a -> Set a -> (a, Set a) -> (a, Set a) -> (a, Set a))
-> Set a
-> (a, Set a)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(a
a, Set a
forall a. Set a
E)
(\Set a
ll a
la Set a
lr (a, Set a)
_ (a, Set a)
_ -> Set a -> a -> Set a -> a -> Set a -> (a, Set a)
forall {t}. Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBL Set a
ll a
la Set a
lr a
a Set a
r)
(\Set a
ll a
la Set a
lr (a, Set a)
_ (a, Set a)
_ -> Set a -> a -> Set a -> a -> Set a -> (a, Set a)
forall {t}. Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBB Set a
ll a
la Set a
lr a
a Set a
r)
(\Set a
ll a
la Set a
lr (a, Set a)
_ (a, Set a)
_ -> Set a -> a -> Set a -> a -> Set a -> (a, Set a)
forall {t}. Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBR Set a
ll a
la Set a
lr a
a Set a
r)
Set a
l
popLeftL :: Set t -> t -> Set t -> (t, Set t)
popLeftL Set t
l t
a Set t
r =
(t, Set t)
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> Set t
-> (t, Set t)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> (t, Set t)
forall a. HasCallStack => String -> a
error String
"Set.delete: L19")
( \Set t
ll t
la Set t
lr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l') -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkLeftL Set t
l' t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> (t, Set t)
popLeftL Set t
ll t
la Set t
lr
)
(\Set t
ll t
la Set t
lr (t, Set t)
_ (t, Set t)
_ -> Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftLB Set t
ll t
la Set t
lr t
a Set t
r)
( \Set t
ll t
la Set t
lr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l') -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkLeftL Set t
l' t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> (t, Set t)
popLeftR Set t
ll t
la Set t
lr
)
Set t
l
popLeftRB :: Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftRB Set t
ll t
la Set t
lr t
a Set t
r =
(t, Set t)
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> Set t
-> (t, Set t)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(t
la, Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
rebalanceR Set t
forall a. Set a
E t
a Set t
r)
( \Set t
lll t
lla Set t
llr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
R Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBL Set t
lll t
lla Set t
llr t
la Set t
lr
)
( \Set t
lll t
lla Set t
llr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
R Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBB Set t
lll t
lla Set t
llr t
la Set t
lr
)
( \Set t
lll t
lla Set t
llr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
R Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBR Set t
lll t
lla Set t
llr t
la Set t
lr
)
Set t
ll
popLeftBB :: Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBB Set t
ll t
la Set t
lr t
a Set t
r =
(t, Set t)
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> Set t
-> (t, Set t)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(t
la, Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
R Set t
forall a. Set a
E t
a Set t
r)
( \Set t
lll t
lla Set t
llr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
B Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBL Set t
lll t
lla Set t
llr t
la Set t
lr
)
( \Set t
lll t
lla Set t
llr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
B Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBB Set t
lll t
lla Set t
llr t
la Set t
lr
)
( \Set t
lll t
lla Set t
llr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
B Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBR Set t
lll t
lla Set t
llr t
la Set t
lr
)
Set t
ll
popLeftLB :: Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftLB Set t
ll t
la Set t
lr t
a Set t
r =
(t, Set t)
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> (Set t -> t -> Set t -> (t, Set t) -> (t, Set t) -> (t, Set t))
-> Set t
-> (t, Set t)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(t
la, Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
B Set t
forall a. Set a
E t
a Set t
forall a. Set a
E)
( \Set t
lll t
lla Set t
llr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
L Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBL Set t
lll t
lla Set t
llr t
la Set t
lr
)
( \Set t
lll t
lla Set t
llr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
L Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBB Set t
lll t
lla Set t
llr t
la Set t
lr
)
( \Set t
lll t
lla Set t
llr (t, Set t)
_ (t, Set t)
_ ->
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
L Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBR Set t
lll t
lla Set t
llr t
la Set t
lr
)
Set t
ll
popLeftBR :: Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBR Set t
ll t
la Set t
lr t
a Set t
r =
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkLeftB Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> (t, Set t)
popLeftR Set t
ll t
la Set t
lr
popLeftBL :: Set t -> t -> Set t -> t -> Set t -> (t, Set t)
popLeftBL Set t
ll t
la Set t
lr t
a Set t
r =
(\(t
a', Set t
l) -> (t
a', Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkLeftB Set t
l t
a Set t
r)) ((t, Set t) -> (t, Set t)) -> (t, Set t) -> (t, Set t)
forall a b. (a -> b) -> a -> b
$
Set t -> t -> Set t -> (t, Set t)
popLeftL Set t
ll t
la Set t
lr
popRightR :: Set t -> t -> Set t -> (Set t, t)
popRightR Set t
l t
a =
(Set t, t)
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> Set t
-> (Set t, t)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> (Set t, t)
forall a. HasCallStack => String -> a
error String
"Set.delete: L20")
(\Set t
rl t
ra Set t
rr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkRightR Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> (Set t, t)
popRightL Set t
rl t
ra Set t
rr)
(\Set t
rl t
ra Set t
rr (Set t, t)
_ (Set t, t)
_ -> Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightRB Set t
l t
a Set t
rl t
ra Set t
rr)
(\Set t
rl t
ra Set t
rr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkRightR Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> (Set t, t)
popRightR Set t
rl t
ra Set t
rr)
popRightB :: Set b -> b -> Set b -> (Set b, b)
popRightB Set b
l b
a =
(Set b, b)
-> (Set b -> b -> Set b -> (Set b, b) -> (Set b, b) -> (Set b, b))
-> (Set b -> b -> Set b -> (Set b, b) -> (Set b, b) -> (Set b, b))
-> (Set b -> b -> Set b -> (Set b, b) -> (Set b, b) -> (Set b, b))
-> Set b
-> (Set b, b)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set b
forall a. Set a
E, b
a)
(\Set b
rl b
ra Set b
rr (Set b, b)
_ (Set b, b)
_ -> Set b -> b -> Set b -> b -> Set b -> (Set b, b)
forall {t}. Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBL Set b
l b
a Set b
rl b
ra Set b
rr)
(\Set b
rl b
ra Set b
rr (Set b, b)
_ (Set b, b)
_ -> Set b -> b -> Set b -> b -> Set b -> (Set b, b)
forall {t}. Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBB Set b
l b
a Set b
rl b
ra Set b
rr)
(\Set b
rl b
ra Set b
rr (Set b, b)
_ (Set b, b)
_ -> Set b -> b -> Set b -> b -> Set b -> (Set b, b)
forall {t}. Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBR Set b
l b
a Set b
rl b
ra Set b
rr)
popRightL :: Set t -> t -> Set t -> (Set t, t)
popRightL Set t
l t
a =
(Set t, t)
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> Set t
-> (Set t, t)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set t
l, t
a)
(\Set t
rl t
ra Set t
rr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkRightL Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> (Set t, t)
popRightL Set t
rl t
ra Set t
rr)
(\Set t
rl t
ra Set t
rr (Set t, t)
_ (Set t, t)
_ -> Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightLB Set t
l t
a Set t
rl t
ra Set t
rr)
(\Set t
rl t
ra Set t
rr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkRightL Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> (Set t, t)
popRightR Set t
rl t
ra Set t
rr)
popRightRB :: Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightRB Set t
l t
a Set t
rl t
ra =
(Set t, t)
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> Set t
-> (Set t, t)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
B Set t
forall a. Set a
E t
a Set t
forall a. Set a
E, t
ra)
(\Set t
rrl t
rra Set t
rrr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
R Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBL Set t
rl t
ra Set t
rrl t
rra Set t
rrr)
(\Set t
rrl t
rra Set t
rrr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
R Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBB Set t
rl t
ra Set t
rrl t
rra Set t
rrr)
(\Set t
rrl t
rra Set t
rrr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
R Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBR Set t
rl t
ra Set t
rrl t
rra Set t
rrr)
popRightBB :: Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBB Set t
l t
a Set t
rl t
ra =
(Set t, t)
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> Set t
-> (Set t, t)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
L Set t
l t
a Set t
forall a. Set a
E, t
ra)
(\Set t
rrl t
rra Set t
rrr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
B Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBL Set t
rl t
ra Set t
rrl t
rra Set t
rrr)
(\Set t
rrl t
rra Set t
rrr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
B Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBB Set t
rl t
ra Set t
rrl t
rra Set t
rrr)
(\Set t
rrl t
rra Set t
rrr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
B Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBR Set t
rl t
ra Set t
rrl t
rra Set t
rrr)
popRightLB :: Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightLB Set t
l t
a Set t
rl t
ra =
(Set t, t)
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> (Set t -> t -> Set t -> (Set t, t) -> (Set t, t) -> (Set t, t))
-> Set t
-> (Set t, t)
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
rebalanceL Set t
l t
a Set t
forall a. Set a
E, t
ra)
(\Set t
rrl t
rra Set t
rrr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
L Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBL Set t
rl t
ra Set t
rrl t
rra Set t
rrr)
(\Set t
rrl t
rra Set t
rrr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
L Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBB Set t
rl t
ra Set t
rrl t
rra Set t
rrr)
(\Set t
rrl t
rra Set t
rrr (Set t, t)
_ (Set t, t)
_ -> (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
L Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBR Set t
rl t
ra Set t
rrl t
rra Set t
rrr)
popRightBR :: Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBR Set t
l t
a Set t
rl t
ra Set t
rr = (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkRightB Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> (Set t, t)
popRightR Set t
rl t
ra Set t
rr
popRightBL :: Set t -> t -> Set t -> t -> Set t -> (Set t, t)
popRightBL Set t
l t
a Set t
rl t
ra Set t
rr = (Set t -> Set t) -> (Set t, t) -> (Set t, t)
forall a b c. (a -> b) -> (a, c) -> (b, c)
forall (p :: * -> * -> *) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first (Set t -> t -> Set t -> Set t
forall a. Set a -> a -> Set a -> Set a
checkRightB Set t
l t
a) ((Set t, t) -> (Set t, t)) -> (Set t, t) -> (Set t, t)
forall a b. (a -> b) -> a -> b
$ Set t -> t -> Set t -> (Set t, t)
popRightL Set t
rl t
ra Set t
rr
filter :: (Ord a) => (a -> Bool) -> Set a -> Set a
filter :: forall a. Ord a => (a -> Bool) -> Set a -> Set a
filter a -> Bool
p = (a -> Set a -> Set a) -> Set a -> Set a -> Set a
forall a b. (a -> b -> b) -> b -> Set a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\a
a Set a
b -> Set a -> Set a -> Bool -> Set a
forall a. a -> a -> Bool -> a
bool Set a
b (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert a
a Set a
b) (a -> Bool
p a
a)) Set a
forall a. Set a
empty
insert :: (Ord a) => a -> Set a -> Set a
insert :: forall a. Ord a => a -> Set a -> Set a
insert a
a0 =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
forall a. Set a
E a
a0 Set a
forall a. Set a
E)
(\Set a
l a
a Set a
r Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
insertL Set a
l a
a Set a
r)
(\Set a
l a
a Set a
r Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
insertB Set a
l a
a Set a
r)
(\Set a
l a
a Set a
r Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
insertR Set a
l a
a Set a
r)
where
insertR :: Set a -> a -> Set a -> Set a
insertR Set a
l a
a Set a
r =
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
a of
Ordering
LT -> Set a -> a -> Set a -> Set a
insertRl Set a
l a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a0 Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
insertRr Set a
l a
a Set a
r
insertB :: Set a -> a -> Set a -> Set a
insertB Set a
l a
a Set a
r =
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
a of
Ordering
LT -> Set a -> a -> Set a -> Set a
insertBl Set a
l a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a0 Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
insertBr Set a
l a
a Set a
r
insertL :: Set a -> a -> Set a -> Set a
insertL Set a
l a
a Set a
r =
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
a of
Ordering
LT -> Set a -> a -> Set a -> Set a
insertLl Set a
l a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a0 Set a
r
Ordering
GT -> Set a -> a -> Set a -> Set a
insertLr Set a
l a
a Set a
r
insertRl :: Set a -> a -> Set a -> Set a
insertRl Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
forall a. Set a
E a
a0 Set a
forall a. Set a
E) a
a Set a
r)
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R (Set a -> a -> Set a -> Set a
insertL Set a
ll a
la Set a
lr) a
a Set a
r)
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
let l' :: Set a
l' = Set a -> a -> Set a -> Set a
insertB Set a
ll a
la Set a
lr
in Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.insert: L0")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l' a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l' a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l' a
a Set a
r)
Set a
l'
)
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R (Set a -> a -> Set a -> Set a
insertR Set a
ll a
la Set a
lr) a
a Set a
r)
Set a
l
insertBl :: Set a -> a -> Set a -> Set a
insertBl Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
forall a. Set a
E a
a0 Set a
forall a. Set a
E) a
a Set a
r)
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
insertL Set a
ll a
la Set a
lr) a
a Set a
r)
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
let l' :: Set a
l' = Set a -> a -> Set a -> Set a
insertB Set a
ll a
la Set a
lr
in Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.insert: L1")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l' a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l' a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l' a
a Set a
r)
Set a
l'
)
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
insertR Set a
ll a
la Set a
lr) a
a Set a
r)
Set a
l
insertBr :: Set a -> a -> Set a -> Set a
insertBr Set a
l a
a =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
forall a. Set a
E a
a0 Set a
forall a. Set a
E))
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a (Set a -> a -> Set a -> Set a
insertL Set a
rl a
ra Set a
rr))
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
let r :: Set a
r = Set a -> a -> Set a -> Set a
insertB Set a
rl a
ra Set a
rr
in Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.insert: L2")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a Set a
r)
Set a
r
)
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a (Set a -> a -> Set a -> Set a
insertR Set a
rl a
ra Set a
rr))
insertLr :: Set a -> a -> Set a -> Set a
insertLr Set a
l a
a =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
forall a. Set a
E a
a0 Set a
forall a. Set a
E))
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a (Set a -> a -> Set a -> Set a
insertL Set a
rl a
ra Set a
rr))
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
let r :: Set a
r = Set a -> a -> Set a -> Set a
insertB Set a
rl a
ra Set a
rr
in Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.insert: L3")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
r)
Set a
r
)
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a (Set a -> a -> Set a -> Set a
insertR Set a
rl a
ra Set a
rr))
insertRr :: Set a -> a -> Set a -> Set a
insertRr Set a
l a
a =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.insert: L4")
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
insertL Set a
rl a
ra Set a
rr))
( \Set a
rl a
ra Set a
rr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
ra of
Ordering
LT -> Set a -> a -> Set a -> a -> Set a -> Set a
insertRrl Set a
l a
a Set a
rl a
ra Set a
rr
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
rl a
a0 Set a
rr)
Ordering
GT -> Set a -> a -> Set a -> a -> Set a -> Set a
insertRrr Set a
l a
a Set a
rl a
ra Set a
rr
)
(\Set a
rl a
ra Set a
rr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
insertR Set a
rl a
ra Set a
rr))
insertLl :: Set a -> a -> Set a -> Set a
insertLl Set a
l a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.insert: L5")
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
insertL Set a
ll a
la Set a
lr) a
a Set a
r)
( \Set a
ll a
la Set a
lr Set a
_ Set a
_ ->
case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a0 a
la of
Ordering
LT -> Set a -> a -> Set a -> a -> Set a -> Set a
insertLll Set a
ll a
la Set a
lr a
a Set a
r
Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll a
a0 Set a
lr) a
a Set a
r
Ordering
GT -> Set a -> a -> Set a -> a -> Set a -> Set a
insertLlr Set a
ll a
la Set a
lr a
a Set a
r
)
(\Set a
ll a
la Set a
lr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
insertR Set a
ll a
la Set a
lr) a
a Set a
r)
Set a
l
insertRrr :: Set a -> a -> Set a -> a -> Set a -> Set a
insertRrr Set a
l a
a Set a
rl a
ra =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
rl) a
ra (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
forall a. Set a
E a
a0 Set a
forall a. Set a
E))
(\Set a
rrl a
rra Set a
rrr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
rl a
ra (Set a -> a -> Set a -> Set a
insertL Set a
rrl a
rra Set a
rrr)))
( \Set a
rrl a
rra Set a
rrr Set a
_ Set a
_ ->
let rr :: Set a
rr = Set a -> a -> Set a -> Set a
insertB Set a
rrl a
rra Set a
rrr
in Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.insert: L6")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
rl) a
ra Set a
rr)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
rl a
ra Set a
rr))
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
rl) a
ra Set a
rr)
Set a
rr
)
(\Set a
rrl a
rra Set a
rrr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
rl a
ra (Set a -> a -> Set a -> Set a
insertR Set a
rrl a
rra Set a
rrr)))
insertLll :: Set a -> a -> Set a -> a -> Set a -> Set a
insertLll Set a
ll a
la Set a
lr a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
forall a. Set a
E a
a0 Set a
forall a. Set a
E) a
la (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
lr a
a Set a
r))
(\Set a
lll a
lla Set a
llr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
insertL Set a
lll a
lla Set a
llr) a
la Set a
lr) a
a Set a
r)
( \Set a
lll a
lla Set a
llr Set a
_ Set a
_ ->
let ll' :: Set a
ll' = Set a -> a -> Set a -> Set a
insertB Set a
lll a
lla Set a
llr
in Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.insert: L7")
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll' a
la (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
lr a
a Set a
r))
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll' a
la Set a
lr) a
a Set a
r)
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll' a
la (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
lr a
a Set a
r))
Set a
ll'
)
(\Set a
lll a
lla Set a
llr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
insertR Set a
lll a
lla Set a
llr) a
la Set a
lr) a
a Set a
r)
Set a
ll
insertRrl :: Set a -> a -> Set a -> a -> Set a -> Set a
insertRrl Set a
l a
a Set a
rl a
ra Set a
rr =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
forall a. Set a
E) a
a0 (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
forall a. Set a
E a
ra Set a
rr))
(\Set a
rll a
rla Set a
rlr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
insertL Set a
rll a
rla Set a
rlr) a
ra Set a
rr))
( \Set a
rll a
rla Set a
rlr Set a
_ Set a
_ ->
let rl' :: Set a
rl' = Set a -> a -> Set a -> Set a
insertB Set a
rll a
rla Set a
rlr
in Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.insert: L8")
(\Set a
rll' a
rla' Set a
rlr' Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
l a
a Set a
rll') a
rla' (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
rlr' a
ra Set a
rr))
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
rl' a
ra Set a
rr))
(\Set a
rll' a
rla' Set a
rlr' Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
l a
a Set a
rll') a
rla' (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
rlr' a
ra Set a
rr))
Set a
rl'
)
(\Set a
rll a
rla Set a
rlr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
l a
a (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
insertR Set a
rll a
rla Set a
rlr) a
ra Set a
rr))
Set a
rl
insertLlr :: Set a -> a -> Set a -> a -> Set a -> Set a
insertLlr Set a
ll a
la Set a
lr a
a Set a
r =
Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll a
la Set a
forall a. Set a
E) a
a0 (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
forall a. Set a
E a
a Set a
r))
(\Set a
lrl a
lra Set a
lrr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll a
la (Set a -> a -> Set a -> Set a
insertL Set a
lrl a
lra Set a
lrr)) a
a Set a
r)
( \Set a
lrl a
lra Set a
lrr Set a
_ Set a
_ ->
let lr' :: Set a
lr' = Set a -> a -> Set a -> Set a
insertB Set a
lrl a
lra Set a
lrr
in Set a
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a -> Set a -> Set a)
-> Set a
-> Set a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
(String -> Set a
forall a. HasCallStack => String -> a
error String
"Set.insert: L9")
(\Set a
lrl' a
lra' Set a
lrr' Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll a
la Set a
lrl') a
lra' (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
R Set a
lrr' a
a Set a
r))
(\Set a
_ a
_ Set a
_ Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll a
la Set a
lr') a
a Set a
r)
(\Set a
lrl' a
lra' Set a
lrr' Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L Set a
ll a
la Set a
lrl') a
lra' (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
lrr' a
a Set a
r))
Set a
lr'
)
(\Set a
lrl a
lra Set a
lrr Set a
_ Set a
_ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
L (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
B Set a
ll a
la (Set a -> a -> Set a -> Set a
insertR Set a
lrl a
lra Set a
lrr)) a
a Set a
r)
Set a
lr
isSubsetOf :: (Ord a) => Set a -> Set a -> Bool
isSubsetOf :: forall a. Ord a => Set a -> Set a -> Bool
isSubsetOf Set a
p Set a
q = (a -> Bool -> Bool) -> Bool -> Set a -> Bool
forall a b. (a -> b -> b) -> b -> Set a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\a
a Bool
b -> a
a a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`member` Set a
q Bool -> Bool -> Bool
&& Bool
b) Bool
True Set a
p
lookupMax :: Set a -> Maybe a
lookupMax :: forall a. Set a -> Maybe a
lookupMax = Maybe a
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> Set a
-> Maybe a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set Maybe a
forall a. Maybe a
Nothing Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {a} {a} {p}. p -> a -> Set a -> p -> Maybe a -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {a} {a} {p}. p -> a -> Set a -> p -> Maybe a -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {a} {a} {p}. p -> a -> Set a -> p -> Maybe a -> Maybe a
go
where
go :: p -> a -> Set a -> p -> Maybe a -> Maybe a
go p
_ a
a Set a
r p
_ Maybe a
recr = Maybe a
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> Set a
-> Maybe a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set (a -> Maybe a
forall a. a -> Maybe a
Just a
a) Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Maybe a
go' Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Maybe a
go' Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Maybe a
go' Set a
r where go' :: p -> p -> p -> p -> p -> Maybe a
go' p
_ p
_ p
_ p
_ p
_ = Maybe a
recr
lookupMin :: Set a -> Maybe a
lookupMin :: forall a. Set a -> Maybe a
lookupMin = Maybe a
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> Set a
-> Maybe a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set Maybe a
forall a. Maybe a
Nothing Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {a} {a} {p} {p}. Set a -> a -> p -> Maybe a -> p -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {a} {a} {p} {p}. Set a -> a -> p -> Maybe a -> p -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {a} {a} {p} {p}. Set a -> a -> p -> Maybe a -> p -> Maybe a
go
where
go :: Set a -> a -> p -> Maybe a -> p -> Maybe a
go Set a
l a
a p
_ Maybe a
recl p
_ = Maybe a
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> (Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a)
-> Set a
-> Maybe a
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set (a -> Maybe a
forall a. a -> Maybe a
Just a
a) Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Maybe a
go' Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Maybe a
go' Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Maybe a
go' Set a
l where go' :: p -> p -> p -> p -> p -> Maybe a
go' p
_ p
_ p
_ p
_ p
_ = Maybe a
recl
member :: (Ord a) => a -> Set a -> Bool
member :: forall a. Ord a => a -> Set a -> Bool
member a
a = Bool
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> Set a
-> Bool
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set Bool
False Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {p} {p}. p -> a -> p -> Bool -> Bool -> Bool
go Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {p} {p}. p -> a -> p -> Bool -> Bool -> Bool
go Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {p} {p}. p -> a -> p -> Bool -> Bool -> Bool
go
where
go :: p -> a -> p -> Bool -> Bool -> Bool
go p
_ a
a' p
_ Bool
recl Bool
recr = case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
a' of
Ordering
LT -> Bool
recl
Ordering
EQ -> Bool
True
Ordering
GT -> Bool
recr
null :: Set a -> Bool
null :: forall a. Set a -> Bool
null = Bool
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> Set a
-> Bool
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set Bool
True Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Bool
go Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Bool
go Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Bool
go where go :: p -> p -> p -> p -> p -> Bool
go p
_ p
_ p
_ p
_ p
_ = Bool
False
size :: Set a -> Int
size :: forall a. Set a -> Int
size =
Int
-> (Set a -> a -> Set a -> Int -> Int -> Int)
-> (Set a -> a -> Set a -> Int -> Int -> Int)
-> (Set a -> a -> Set a -> Int -> Int -> Int)
-> Set a
-> Int
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
Int
0
(\Set a
_ a
_ Set a
_ Int
recl Int
recr -> Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recl Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recr)
(\Set a
_ a
_ Set a
_ Int
recl Int
recr -> Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recl Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recr)
(\Set a
_ a
_ Set a
_ Int
recl Int
recr -> Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recl Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
recr)
valid :: (Ord a) => Set a -> Bool
valid :: forall a. Ord a => Set a -> Bool
valid = (Bool -> Bool -> Bool)
-> (Set a -> Bool) -> (Set a -> Bool) -> Set a -> Bool
forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 Bool -> Bool -> Bool
(&&) Set a -> Bool
forall a. Set a -> Bool
balanced Set a -> Bool
ordered
where
balanced :: Set a -> Bool
balanced =
Bool
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> Set a
-> Bool
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
Bool
True
(\Set a
l a
_ Set a
r Bool
recl Bool
recr -> Set a -> Int
forall a. Set a -> Int
levels Set a
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Set a -> Int
forall a. Set a -> Int
levels Set a
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
(\Set a
l a
_ Set a
r Bool
recl Bool
recr -> Set a -> Int
forall a. Set a -> Int
levels Set a
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- Set a -> Int
forall a. Set a -> Int
levels Set a
r Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0 Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
(\Set a
l a
_ Set a
r Bool
recl Bool
recr -> Set a -> Int
forall a. Set a -> Int
levels Set a
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Set a -> Int
forall a. Set a -> Int
levels Set 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 :: Set a -> Int
levels = Int
-> (Set a -> a -> Set a -> Int -> Int -> Int)
-> (Set a -> a -> Set a -> Int -> Int -> Int)
-> (Set a -> a -> Set a -> Int -> Int -> Int)
-> Set a
-> Int
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set Int
0 Set a -> a -> Set a -> Int -> Int -> Int
forall {p} {p} {p}. p -> p -> p -> Int -> Int -> Int
go Set a -> a -> Set a -> Int -> Int -> Int
forall {p} {p} {p}. p -> p -> p -> Int -> Int -> Int
go Set a -> a -> Set a -> Int -> Int -> Int
forall {p} {p} {p}. p -> p -> p -> Int -> Int -> Int
go where go :: p -> p -> p -> Int -> Int -> Int
go 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 :: Set a -> Bool
ordered = Bool
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> Set a
-> Bool
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set Bool
True Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {a}. Ord a => Set a -> a -> Set a -> Bool -> Bool -> Bool
go Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {a}. Ord a => Set a -> a -> Set a -> Bool -> Bool -> Bool
go Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {a}. Ord a => Set a -> a -> Set a -> Bool -> Bool -> Bool
go
where
go :: Set a -> a -> Set a -> Bool -> Bool -> Bool
go Set a
l a
a Set a
r Bool
recl Bool
recr =
Bool
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> Set a
-> Bool
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
Bool
True
(\Set a
_ a
la Set a
_ Bool
_ Bool
_ -> a
la a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
a Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
(\Set a
_ a
la Set a
_ Bool
_ Bool
_ -> a
la a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
a Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
(\Set a
_ a
la Set a
_ Bool
_ Bool
_ -> a
la a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
a Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
Set a
l
Bool -> Bool -> Bool
&& Bool
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> (Set a -> a -> Set a -> Bool -> Bool -> Bool)
-> Set a
-> Bool
forall b a.
b
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> (Set a -> a -> Set a -> b -> b -> b)
-> Set a
-> b
set
Bool
True
(\Set a
_ a
ra Set a
_ Bool
_ Bool
_ -> a
ra a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
a Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
(\Set a
_ a
ra Set a
_ Bool
_ Bool
_ -> a
ra a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
a Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
(\Set a
_ a
ra Set a
_ Bool
_ Bool
_ -> a
ra a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
a Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr)
Set a
r