{-# LANGUAGE LambdaCase #-}

{- | Representation of a structure containing unique elements. The internal
structure is an AVL tree.
-}
module Mini.Data.Set (
  -- * Type
  Set,

  -- * Combination
  difference,
  intersection,
  union,

  -- * Construction
  empty,
  fromList,
  singleton,

  -- * Conversion
  toAscList,
  toDescList,

  -- * Modification
  delete,
  filter,
  insert,

  -- * Query
  isSubsetOf,
  lookupMax,
  lookupMin,
  member,
  null,
  size,

  -- * Validation
  valid,
) where

import Control.Monad (
  liftM2,
 )
import Data.Bifunctor (
  first,
 )
import Data.Bool (
  bool,
 )
import Prelude hiding (
  filter,
  null,
 )

{-
 - Type
 -}

{- | A set containing elements of type /a/.

The internal structure is an AVL tree; a tree that is always height-balanced
(the absolute value of the level difference between the left and right
subtrees is at most 1).
-}
data Set a
  = -- | Empty node
    E
  | -- | Left-heavy node
    L (Set a) a (Set a)
  | -- | Balanced node
    B (Set a) a (Set a)
  | -- | Right-heavy node
    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

{-
 - Primitive recursion
 -}

-- | Primitive recursion on sets
set
  :: b
  -- ^ Empty node
  -> (Set a -> a -> Set a -> b -> b -> b)
  -- ^ Left-heavy node: left child, element, right child, left recursion, right
  -- recursion
  -> (Set a -> a -> Set a -> b -> b -> b)
  -- ^ Balanced node: left child, element, right child, left recursion, right
  -- recursion
  -> (Set a -> a -> Set a -> b -> b -> b)
  -- ^ Right-heavy node: left child, element, right child, left recursion, right
  -- recursion
  -> Set a
  -- ^ Set
  -> 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)

{-
 - Combination
 -}

-- | \(O(n \log n)\) Set difference
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

-- | \(O(n \log n)\) Set intersection
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

-- | \(O(n \log n)\) Set union
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

{-
 - Construction
 -}

-- | \(O(1)\) The empty set
empty :: Set a
empty :: forall a. Set a
empty = Set a
forall a. Set a
E

{- | \(O(n \log n)\) From a tail-biased list of elements to a set containing the
elements
-}
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

-- | \(O(1)\) From an element to a set with a single element
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

{-
 - Conversion
 -}

-- | \(O(n)\) From a set to a list of elements in ascending order
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 (:)) []

-- | \(O(n)\) From a set to a list of elements in descending order
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 (:) []

{-
 - Modification
 -}

-- | \(O(\log n)\) From an element and a set to the set without the element
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

{- | \(O(n)\) From a predicate and a set to the set with elements satisfying the
predicate
-}
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

-- | \(O(\log n)\) From an element and a set to the set including the element
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

{-
 - Query
 -}

{- | \(O(n \log n)\) From a set and another set to whether the former is a
subset of the latter
-}
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

-- | \(O(\log n)\) From a set to the maximum element of the set
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

-- | \(O(\log n)\) From a set to the minimum element of the set
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

{- | \(O(\log n)\) From an element and a set to whether the element is in the
set
-}
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

-- | \(O(1)\) From a set to whether the set is empty
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

-- | \(O(n)\) From a set to the size of the set
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)

{-
 - Validation
 -}

{- | \(O(n)\) From a set to whether its internal structure is valid, i.e.
height-balanced and ordered
-}
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