-- | A structure containing unique elements
module Mini.Data.Set (
  -- * Type
  Set,

  -- * Construction
  empty,
  fromList,
  singleton,

  -- * Combination
  difference,
  intersection,
  union,
  unions,

  -- * Conversion
  toAscList,
  toDescList,

  -- * Modification
  delete,
  deleteMax,
  deleteMin,
  filter,
  insert,

  -- * Partition
  partition,
  split,
  splitMax,
  splitMin,

  -- * Query
  disjoint,
  isSubsetOf,
  lookupGE,
  lookupGT,
  lookupLE,
  lookupLT,
  lookupMax,
  lookupMin,
  member,
  null,
  size,

  -- * Validation
  valid,
) where

import Control.Applicative (
  liftA2,
  (<|>),
 )
import Data.Bifunctor (
  first,
 )
import Data.Bool (
  bool,
 )
import Prelude (
  Bool (
    False,
    True
  ),
  Eq,
  Foldable,
  Int,
  Maybe (
    Just,
    Nothing
  ),
  Monoid,
  Ord,
  Ordering (
    EQ,
    GT,
    LT
  ),
  Semigroup,
  Show,
  any,
  compare,
  error,
  flip,
  foldl,
  foldr,
  max,
  maybe,
  mempty,
  not,
  show,
  uncurry,
  ($),
  (&&),
  (+),
  (-),
  (.),
  (<),
  (<$>),
  (<>),
  (==),
  (>),
 )

{-
 - Type
 -}

-- | A set containing elements of type /a/, internally structured as an AVL tree
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)

instance (Eq a) => Eq (Set a) where
  Set a
t1 == :: Set a -> Set a -> Bool
== Set a
t2 = Set a -> [a]
forall a. Set a -> [a]
toAscList Set a
t1 [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== Set a -> [a]
forall a. Set a -> [a]
toAscList Set a
t2

instance (Ord a) => Ord (Set a) where
  compare :: Set a -> Set a -> Ordering
compare Set a
t1 Set a
t2 = [a] -> [a] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Set a -> [a]
forall a. Set a -> [a]
toAscList Set a
t1) (Set a -> [a]
forall a. Set a -> [a]
toAscList Set a
t2)

instance (Show a) => Show (Set a) where
  show :: Set a -> String
show = [a] -> String
forall a. Show a => a -> String
show ([a] -> String) -> (Set a -> [a]) -> Set a -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> [a]
forall a. Set a -> [a]
toAscList

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 =>
t a -> a -> p -> p -> b -> b
go Set a -> a -> Set a -> b -> b -> b
forall {t :: * -> *} {p} {p}.
Foldable t =>
t a -> a -> p -> p -> b -> b
go Set a -> a -> Set a -> b -> b -> b
forall {t :: * -> *} {p} {p}.
Foldable t =>
t a -> a -> p -> p -> b -> b
go
   where
    go :: t a -> a -> p -> p -> b -> b
go t a
l a
a p
_ p
_ b
recr = (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
recr) t a
l

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

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

{-
 - Primitive recursion
 -}

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

{-
 - 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)/ Make a set from a list of 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)/ Make 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

{-
 - Combination
 -}

-- | /O(m log n)/ Subtract a set by another
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(m log n)/ Intersect a set with another
intersection :: (Ord a) => Set a -> Set a -> Set a
intersection :: forall a. Ord a => Set a -> Set a -> Set a
intersection Set a
t1 Set a
t2 =
  (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
t2))
    Set a
forall a. Set a
empty
    Set a
t1

-- | /O(m log n)/ Unite a set with another
union :: (Ord a) => Set a -> Set a -> Set a
union :: forall a. Ord a => Set a -> Set a -> Set a
union = (Set a -> Set a -> Set a) -> Set a -> Set a -> Set a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((Set a -> Set a -> Set a) -> Set a -> Set a -> Set a)
-> (Set a -> Set a -> Set a) -> Set a -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ (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

-- | Unite a collection of sets
unions :: (Foldable t, Ord a) => t (Set a) -> Set a
unions :: forall (t :: * -> *) a. (Foldable t, Ord a) => t (Set a) -> Set a
unions = (Set a -> Set a -> Set a) -> Set a -> t (Set a) -> Set a
forall a b. (a -> b -> b) -> b -> t a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
union Set a
forall a. Set a
empty

{-
 - Conversion
 -}

-- | /O(n)/ Turn a set into 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 a b. (a -> b -> b) -> b -> Set a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (:) []

-- | /O(n)/ Turn a set into 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 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 (:)) []

{-
 - Modification
 -}

-- | /O(log n)/ Delete an element from a set
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(log n)/ Delete the maximum element from a set
deleteMax :: (Ord a) => Set a -> Set a
deleteMax :: forall a. Ord a => Set a -> Set a
deleteMax Set a
t = Set a -> (a -> Set a) -> Maybe a -> Set a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Set a
t ((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
delete Set a
t) (Maybe a -> Set a) -> Maybe a -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> Maybe a
forall a. Set a -> Maybe a
lookupMax Set a
t

-- | /O(log n)/ Delete the minimum element from a set
deleteMin :: (Ord a) => Set a -> Set a
deleteMin :: forall a. Ord a => Set a -> Set a
deleteMin Set a
t = Set a -> (a -> Set a) -> Maybe a -> Set a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Set a
t ((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
delete Set a
t) (Maybe a -> Set a) -> Maybe a -> Set a
forall a b. (a -> b) -> a -> b
$ Set a -> Maybe a
forall a. Set a -> Maybe a
lookupMin Set a
t

-- | /O(n log n)/ Keep the elements satisfying a 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) (Bool -> Set a) -> Bool -> Set a
forall a b. (a -> b) -> a -> b
$ a -> Bool
p a
a) Set a
forall a. Set a
empty

-- | /O(log n)/ Insert an element into a set
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

{-
 - Partition
 -}

-- | /O(n log n)/ Partition a set with a predicate into @(true, false)@ subsets
partition :: (Ord a) => (a -> Bool) -> Set a -> (Set a, Set a)
partition :: forall a. Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
partition a -> Bool
p =
  (a -> (Set a, Set a) -> (Set a, Set 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
t1, Set a
t2) -> (Set a, Set a) -> (Set a, Set a) -> Bool -> (Set a, Set a)
forall a. a -> a -> Bool -> a
bool (Set a
t1, a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert a
a Set a
t2) (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert a
a Set a
t1, Set a
t2) (Bool -> (Set a, Set a)) -> Bool -> (Set a, Set a)
forall a b. (a -> b) -> a -> b
$ a -> Bool
p a
a)
    (Set a
forall a. Set a
empty, Set a
forall a. Set a
empty)

-- | /O(n log n)/ Split a set by an element into @(lt, eq, gt)@ subsets
split :: (Ord a) => a -> Set a -> (Set a, Bool, Set a)
split :: forall a. Ord a => a -> Set a -> (Set a, Bool, Set a)
split a
a0 =
  (a -> (Set a, Bool, Set a) -> (Set a, Bool, Set a))
-> (Set a, Bool, Set a) -> Set a -> (Set a, Bool, 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
t1, Bool
a', Set a
t2) -> case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
a0 of
        Ordering
LT -> (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert a
a Set a
t1, Bool
a', Set a
t2)
        Ordering
EQ -> (Set a
t1, Bool
True, Set a
t2)
        Ordering
GT -> (Set a
t1, Bool
a', a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert a
a Set a
t2)
    )
    (Set a
forall a. Set a
empty, Bool
False, Set a
forall a. Set a
empty)

-- | /O(log n)/ Split a set by its maximum element
splitMax :: (Ord a) => Set a -> Maybe (a, Set a)
splitMax :: forall a. Ord a => Set a -> Maybe (a, Set a)
splitMax Set a
t = (\a
a -> (a
a, Set a -> Set a
forall a. Ord a => Set a -> Set a
deleteMax Set a
t)) (a -> (a, Set a)) -> Maybe a -> Maybe (a, Set a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set a -> Maybe a
forall a. Set a -> Maybe a
lookupMax Set a
t

-- | /O(log n)/ Split a set by its minimum element
splitMin :: (Ord a) => Set a -> Maybe (a, Set a)
splitMin :: forall a. Ord a => Set a -> Maybe (a, Set a)
splitMin Set a
t = (\a
a -> (a
a, Set a -> Set a
forall a. Ord a => Set a -> Set a
deleteMin Set a
t)) (a -> (a, Set a)) -> Maybe a -> Maybe (a, Set a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set a -> Maybe a
forall a. Set a -> Maybe a
lookupMin Set a
t

{-
 - Query
 -}

-- | /O(m log n)/ Check whether two sets have no elements in common
disjoint :: (Ord a) => Set a -> Set a -> Bool
disjoint :: forall a. Ord a => Set a -> Set a -> Bool
disjoint Set a
t1 = Bool -> Bool
not (Bool -> Bool) -> (Set a -> Bool) -> Set a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> Set a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`member` Set a
t1)

-- | /O(n log m)/ Check whether the elements of a set exist in the other
isSubsetOf :: (Ord a) => Set a -> Set a -> Bool
isSubsetOf :: forall a. Ord a => Set a -> Set a -> Bool
isSubsetOf Set a
t1 Set a
t2 = (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
t2 Bool -> Bool -> Bool
&& Bool
b) Bool
True Set a
t1

-- | /O(log n)/ Fetch the least element greater than or equal to the given one
lookupGE :: (Ord a) => a -> Set a -> Maybe a
lookupGE :: forall a. Ord a => a -> Set a -> Maybe a
lookupGE a
a0 = 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} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go
 where
  go :: p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go p
_ a
a p
_ Maybe a
recl Maybe a
recr = case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
a0 of
    Ordering
LT -> Maybe a
recr
    Ordering
EQ -> a -> Maybe a
forall a. a -> Maybe a
Just a
a
    Ordering
GT -> Maybe a
recl Maybe a -> Maybe a -> Maybe a
forall a. Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> a -> Maybe a
forall a. a -> Maybe a
Just a
a

-- | /O(log n)/ Fetch the least element strictly greater than the given one
lookupGT :: (Ord a) => a -> Set a -> Maybe a
lookupGT :: forall a. Ord a => a -> Set a -> Maybe a
lookupGT a
a0 = 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} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go
 where
  go :: p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go p
_ a
a p
_ Maybe a
recl Maybe a
recr = case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
a0 of
    Ordering
LT -> Maybe a
recr
    Ordering
EQ -> Maybe a
recr
    Ordering
GT -> Maybe a
recl Maybe a -> Maybe a -> Maybe a
forall a. Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> a -> Maybe a
forall a. a -> Maybe a
Just a
a

-- | /O(log n)/ Fetch the greatest element less than or equal to the given one
lookupLE :: (Ord a) => a -> Set a -> Maybe a
lookupLE :: forall a. Ord a => a -> Set a -> Maybe a
lookupLE a
a0 = 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} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go
 where
  go :: p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go p
_ a
a p
_ Maybe a
recl Maybe a
recr = case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
a0 of
    Ordering
LT -> Maybe a
recr Maybe a -> Maybe a -> Maybe a
forall a. Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> a -> Maybe a
forall a. a -> Maybe a
Just a
a
    Ordering
EQ -> a -> Maybe a
forall a. a -> Maybe a
Just a
a
    Ordering
GT -> Maybe a
recl

-- | /O(log n)/ Fetch the greatest element strictly less than the given one
lookupLT :: (Ord a) => a -> Set a -> Maybe a
lookupLT :: forall a. Ord a => a -> Set a -> Maybe a
lookupLT a
a0 = 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} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go Set a -> a -> Set a -> Maybe a -> Maybe a -> Maybe a
forall {p} {p}. p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go
 where
  go :: p -> a -> p -> Maybe a -> Maybe a -> Maybe a
go p
_ a
a p
_ Maybe a
recl Maybe a
recr = case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
a0 of
    Ordering
LT -> Maybe a
recr Maybe a -> Maybe a -> Maybe a
forall a. Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> a -> Maybe a
forall a. a -> Maybe a
Just a
a
    Ordering
EQ -> Maybe a
recl
    Ordering
GT -> Maybe a
recl

-- | /O(log n)/ Fetch the maximum element, or 'Nothing' if the set is empty
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)/ Fetch the minimum element, or 'Nothing' if the set is empty
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)/ Check whether an element is in a set
member :: (Ord a) => a -> Set a -> Bool
member :: forall a. Ord a => a -> Set a -> Bool
member a
a0 = 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
a0 a
a of
    Ordering
LT -> Bool
recl
    Ordering
EQ -> Bool
True
    Ordering
GT -> Bool
recr

-- | /O(1)/ Check whether a 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)/ Get the size of a 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 -> Int -> Int
forall {a} {p} {p} {p}. Num a => p -> p -> p -> a -> a -> a
go Set a -> a -> Set a -> Int -> Int -> Int
forall {a} {p} {p} {p}. Num a => p -> p -> p -> a -> a -> a
go Set a -> a -> Set a -> Int -> Int -> Int
forall {a} {p} {p} {p}. Num a => p -> p -> p -> a -> a -> a
go where go :: p -> p -> p -> a -> a -> a
go p
_ p
_ p
_ a
recl a
recr = a
1 a -> a -> a
forall a. Num a => a -> a -> a
+ a
recl a -> a -> a
forall a. Num a => a -> a -> a
+ a
recr

{-
 - Validation
 -}

-- | /O(n)/ Check whether a set is internally 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 a b c.
(a -> b -> c) -> (Set a -> a) -> (Set a -> b) -> Set a -> c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 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 -> Set a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p}. p -> a -> p -> p -> p -> Bool
lt Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p}. p -> a -> p -> p -> p -> Bool
lt Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p}. p -> a -> p -> p -> p -> Bool
lt 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 -> Set a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p}. p -> a -> p -> p -> p -> Bool
gt Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p}. p -> a -> p -> p -> p -> Bool
gt Set a -> a -> Set a -> Bool -> Bool -> Bool
forall {p} {p} {p} {p}. p -> a -> p -> p -> p -> Bool
gt Set a
r
     where
      lt :: p -> a -> p -> p -> p -> Bool
lt p
_ a
la p
_ p
_ p
_ = a
la a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
a Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr
      gt :: p -> a -> p -> p -> p -> Bool
gt p
_ a
ra p
_ p
_ p
_ = a
ra a -> a -> Bool
forall a. Ord a => a -> a -> Bool
> a
a Bool -> Bool -> Bool
&& Bool
recl Bool -> Bool -> Bool
&& Bool
recr