-- incomplete patterns in 'from{Asc,Desc}List'
{-# OPTIONS_GHC -Wno-incomplete-uni-patterns #-}

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

  -- * Primitive Recursion
  set,

  -- * Construction
  empty,
  singleton,
  fromList,
  fromAscList,
  fromDescList,
  fromDistinctAscList,
  fromDistinctDescList,

  -- * 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 (
  bimap,
  first,
  second,
 )
import Data.Bool (
  bool,
 )
import Data.Function (
  on,
 )
import Prelude (
  Bool (
    False,
    True
  ),
  Eq,
  Foldable,
  Int,
  Maybe (
    Just,
    Nothing
  ),
  Monoid,
  Ord,
  Ordering (
    EQ,
    GT,
    LT
  ),
  Semigroup,
  Show,
  all,
  any,
  compare,
  div,
  error,
  flip,
  foldl,
  foldr,
  length,
  max,
  maybe,
  mempty,
  not,
  show,
  splitAt,
  uncurry,
  until,
  ($),
  (&&),
  (*),
  (+),
  (-),
  (.),
  (<),
  (<$>),
  (<*>),
  (<>),
  (==),
  (>),
 )

{-
 - 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 -> Set a -> Bool
(==) = [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
(==) ([a] -> [a] -> Bool) -> (Set a -> [a]) -> Set a -> Set a -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Set a -> [a]
forall a. Set a -> [a]
toAscList

instance (Ord a) => Ord (Set a) where
  compare :: Set a -> Set a -> Ordering
compare = [a] -> [a] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare ([a] -> [a] -> Ordering)
-> (Set a -> [a]) -> Set a -> Set a -> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Set a -> [a]
forall a. Set a -> [a]
toAscList

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 (internally structured as trees)
set
  :: b
  -- ^ Value yielded in case of empty node
  -> (Set a -> a -> Set a -> b -> b -> b)
  -- ^ Function applied in case of non-empty node:
  -- left child, element, right child, left recursion, right recursion
  -- (elements are lesser to the left, greater to the right)
  -> Set a
  -- ^ Object of the case analysis
  -> b
set :: forall b a. b -> (Set a -> a -> Set a -> b -> b -> b) -> Set a -> b
set b
e Set a -> a -> Set a -> b -> b -> b
f = b
-> (Set a -> a -> 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
f Set a -> a -> Set a -> b -> b -> b
f

-- Primitive recursion on sets
set'
  :: b
  -- ^ Value yielded in case of empty node
  -> (Set a -> a -> Set a -> b -> b -> b)
  -- ^ Function applied in case of left-heavy node:
  -- left child, element, right child, left recursion, right recursion
  -- (elements are lesser to the left, greater to the right)
  -> (Set a -> a -> Set a -> b -> b -> b)
  -- ^ Function applied in case of balanced node:
  -- left child, element, right child, left recursion, right recursion
  -- (elements are lesser to the left, greater to the right)
  -> (Set a -> a -> Set a -> b -> b -> b)
  -- ^ Function applied in case of right-heavy node:
  -- left child, element, right child, left recursion, right recursion
  -- (elements are lesser to the left, greater to the right)
  -> Set a
  -- ^ Object of the case analysis
  -> 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(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

-- | /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(n)/ Make a set from a sorted list of elements
fromAscList :: (Eq a) => [a] -> Set a
fromAscList :: forall a. Eq a => [a] -> Set a
fromAscList = [a] -> Set a
forall a. [a] -> Set a
fromDistinctAscList ([a] -> Set a) -> ([a] -> [a]) -> [a] -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. Eq a => [a] -> [a]
essence

-- | /O(n)/ Make a set from a sorted list of elements
fromDescList :: (Eq a) => [a] -> Set a
fromDescList :: forall a. Eq a => [a] -> Set a
fromDescList = [a] -> Set a
forall a. [a] -> Set a
fromDistinctDescList ([a] -> Set a) -> ([a] -> [a]) -> [a] -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> [a]
forall a. Eq a => [a] -> [a]
essence

-- | /O(n)/ Make a set from a sorted list of distinct elements
fromDistinctAscList :: [a] -> Set a
fromDistinctAscList :: forall a. [a] -> Set a
fromDistinctAscList = [a] -> Int -> Set a
forall {a}. [a] -> Int -> Set a
go ([a] -> Int -> Set a) -> ([a] -> Int) -> [a] -> Set a
forall a b. ([a] -> a -> b) -> ([a] -> a) -> [a] -> b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
power
 where
  go :: [a] -> Int -> Set a
go [] Int
_ = Set a
forall a. Set a
E
  go [a
a] Int
_ = 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
  go [a]
as Int
n =
    let len :: Int
len = [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
as
        n' :: Int
n' = Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
        c :: Set a -> a -> Set a -> Set a
c = (Set a -> a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a)
-> Bool
-> Set a
-> a
-> Set a
-> Set a
forall a. a -> a -> Bool -> a
bool 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 (Bool -> Set a -> a -> Set a -> Set a)
-> Bool -> Set a -> a -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ Int
len Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n
        ([a]
l, a
a : [a]
r) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt (Int
len Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) [a]
as
     in Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
c ([a] -> Int -> Set a
go [a]
l Int
n') a
a ([a] -> Int -> Set a
go [a]
r Int
n')

-- | /O(n)/ Make a set from a sorted list of distinct elements
fromDistinctDescList :: [a] -> Set a
fromDistinctDescList :: forall a. [a] -> Set a
fromDistinctDescList = [a] -> Int -> Set a
forall {a}. [a] -> Int -> Set a
go ([a] -> Int -> Set a) -> ([a] -> Int) -> [a] -> Set a
forall a b. ([a] -> a -> b) -> ([a] -> a) -> [a] -> b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
power
 where
  go :: [a] -> Int -> Set a
go [] Int
_ = Set a
forall a. Set a
E
  go [a
a] Int
_ = 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
  go [a]
as Int
n =
    let len :: Int
len = [a] -> Int
forall a. [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
as
        n' :: Int
n' = Int
n Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2
        c :: Set a -> a -> Set a -> Set a
c = (Set a -> a -> Set a -> Set a)
-> (Set a -> a -> Set a -> Set a)
-> Bool
-> Set a
-> a
-> Set a
-> Set a
forall a. a -> a -> Bool -> a
bool 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
R (Bool -> Set a -> a -> Set a -> Set a)
-> Bool -> Set a -> a -> Set a -> Set a
forall a b. (a -> b) -> a -> b
$ Int
len Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
n
        ([a]
l, a
a : [a]
r) = Int -> [a] -> ([a], [a])
forall a. Int -> [a] -> ([a], [a])
splitAt (Int
len Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2) [a]
as
     in Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
c ([a] -> Int -> Set a
go [a]
r Int
n') a
a ([a] -> Int -> Set a
go [a]
l Int
n')

{-
 - 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 Set a
t1 Set a
t2 = Set a
-> (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
empty Set a -> a -> Set a -> Set a -> Set a -> Set a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Set a
go Set a -> a -> Set a -> Set a -> Set a -> Set a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Set a
go Set a -> a -> Set a -> Set a -> Set a -> Set a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Set a
go Set a
t1
 where
  go :: p -> p -> p -> p -> p -> Set a
go p
_ p
_ p
_ p
_ 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 -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
delete Set a
t1 Set a
t2

-- | /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 = Set a
-> (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
empty Set a -> a -> Set a -> Set a -> Set a -> Set a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Set a
go Set a -> a -> Set a -> Set a -> Set a -> Set a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Set a
go Set a -> a -> Set a -> Set a -> Set a -> Set a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Set a
go Set a
t2
 where
  go :: p -> p -> p -> p -> p -> Set a
go p
_ p
_ p
_ p
_ p
_ =
    [a] -> Set a
forall a. [a] -> Set a
fromDistinctAscList ([a] -> Set a) -> [a] -> Set a
forall a b. (a -> b) -> a -> b
$
      (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
        (\a
a [a]
b -> [a] -> [a] -> Bool -> [a]
forall a. a -> a -> Bool -> a
bool [a]
b (a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
b) (Bool -> [a]) -> Bool -> [a]
forall a b. (a -> b) -> a -> b
$ a
a a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`member` Set a
t2)
        []
        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
t1 Set a
t2 = Set a
-> (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
t2 Set a -> a -> Set a -> Set a -> Set a -> Set a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Set a
go Set a -> a -> Set a -> Set a -> Set a -> Set a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Set a
go Set a -> a -> Set a -> Set a -> Set a -> Set a
forall {p} {p} {p} {p} {p}. p -> p -> p -> p -> p -> Set a
go Set a
t1
 where
  go :: p -> p -> p -> p -> p -> Set a
go p
_ p
_ p
_ p
_ 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 -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert Set a
t1 Set a
t2

-- | 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
a Set a
t = Set a -> Set a -> Bool -> Set a
forall a. a -> a -> Bool -> a
bool Set a
t (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
delete' a
a Set a
t) (Bool -> Set a) -> Bool -> Set a
forall a b. (a -> b) -> a -> b
$ a
a a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`member` Set a
t

-- | /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
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
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)/ Keep the elements satisfying a predicate
filter :: (a -> Bool) -> Set a -> Set a
filter :: forall a. (a -> Bool) -> Set a -> Set a
filter a -> Bool
p = [a] -> Set a
forall a. [a] -> Set a
fromDistinctAscList ([a] -> Set a) -> (Set a -> [a]) -> Set a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (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 (\a
a [a]
b -> [a] -> [a] -> Bool -> [a]
forall a. a -> a -> Bool -> a
bool [a]
b (a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
b) (Bool -> [a]) -> Bool -> [a]
forall a b. (a -> b) -> a -> b
$ a -> Bool
p a
a) []

-- | /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
a Set a
t = Set a -> Set a -> Bool -> Set a
forall a. a -> a -> Bool -> a
bool (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert' a
a Set a
t) Set a
t (Bool -> Set a) -> Bool -> Set a
forall a b. (a -> b) -> a -> b
$ a
a a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`member` Set a
t

{-
 - Partition
 -}

-- | /O(n)/ Partition a set with a predicate into @(true, false)@ subsets
partition :: (a -> Bool) -> Set a -> (Set a, Set a)
partition :: forall a. (a -> Bool) -> Set a -> (Set a, Set a)
partition a -> Bool
p =
  ([a] -> Set a) -> ([a] -> Set a) -> ([a], [a]) -> (Set a, Set a)
forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap [a] -> Set a
forall a. [a] -> Set a
fromDistinctAscList [a] -> Set a
forall a. [a] -> Set a
fromDistinctAscList
    (([a], [a]) -> (Set a, Set a))
-> (Set a -> ([a], [a])) -> Set a -> (Set a, Set a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> ([a], [a]) -> ([a], [a]))
-> ([a], [a]) -> Set a -> ([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
      (\a
a -> (([a] -> [a]) -> ([a], [a]) -> ([a], [a]))
-> (([a] -> [a]) -> ([a], [a]) -> ([a], [a]))
-> Bool
-> ([a] -> [a])
-> ([a], [a])
-> ([a], [a])
forall a. a -> a -> Bool -> a
bool ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
forall b c a. (b -> c) -> (a, b) -> (a, c)
forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second ([a] -> [a]) -> ([a], [a]) -> ([a], [a])
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 (a -> Bool
p a
a) (a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
:))
      ([], [])

-- | /O(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]
lt, Bool
a, [a]
gt) -> ([a] -> Set a
forall a. [a] -> Set a
fromDistinctAscList [a]
lt, Bool
a, [a] -> Set a
forall a. [a] -> Set a
fromDistinctAscList [a]
gt))
    (([a], Bool, [a]) -> (Set a, Bool, Set a))
-> (Set a -> ([a], Bool, [a])) -> Set a -> (Set a, Bool, Set a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> ([a], Bool, [a]) -> ([a], Bool, [a]))
-> ([a], Bool, [a]) -> Set a -> ([a], Bool, [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 ([a]
lt, Bool
a', [a]
gt) -> case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
a0 of
          Ordering
LT -> (a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
lt, Bool
a', [a]
gt)
          Ordering
EQ -> ([a]
lt, Bool
True, [a]
gt)
          Ordering
GT -> ([a]
lt, Bool
a', a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
gt)
      )
      ([], Bool
False, [])

-- | /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 -> Set a -> (a, Set a)) -> (a -> Set a) -> a -> (a, Set a)
forall a b. (a -> a -> b) -> (a -> a) -> a -> b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (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) (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 -> Set a -> (a, Set a)) -> (a -> Set a) -> a -> (a, Set a)
forall a b. (a -> a -> b) -> (a -> a) -> a -> b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (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) (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 Set a
t2 = 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 Set a
t1
 where
  go :: p -> p -> p -> p -> p -> Bool
go p
_ p
_ p
_ p
_ p
_ = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ (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) Set a
t2

-- | /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 = 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' (Set a -> Bool
forall a. Set a -> Bool
null Set a
t1) 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 Set a
t2
 where
  go :: p -> p -> p -> p -> p -> Bool
go p
_ p
_ p
_ p
_ p
_ = (a -> Bool) -> Set a -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
`member` Set a
t2) 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^2)/ 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

{-
 - Helpers
 -}

-- O(n) 'nub' for sorted lists
essence :: (Eq a) => [a] -> [a]
essence :: forall a. Eq a => [a] -> [a]
essence [] = []
essence (a
a : [a]
as) = a -> [a] -> [a]
forall {a}. Eq a => a -> [a] -> [a]
essence' a
a [a]
as
 where
  essence' :: a -> [a] -> [a]
essence' a
x1 [] = [a
x1]
  essence' a
x1 (a
x2 : [a]
xs) =
    let rest :: [a]
rest = a -> [a] -> [a]
essence' a
x2 [a]
xs
     in [a] -> [a] -> Bool -> [a]
forall a. a -> a -> Bool -> a
bool (a
x1 a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
rest) [a]
rest (Bool -> [a]) -> Bool -> [a]
forall a b. (a -> b) -> a -> b
$ a
x1 a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x2

-- The greatest power of 2 <= the length of a non-empty collection
power :: (Foldable t) => t a -> Int
power :: forall (t :: * -> *) a. Foldable t => t a -> Int
power t a
as = (Int -> Bool) -> (Int -> Int) -> Int -> Int
forall a. (a -> Bool) -> (a -> a) -> a -> a
until (Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> t a -> Int
forall a. t a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length t a
as) (Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
2) Int
2 Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2

{-
 - Let this comment serve as your warning. Return from whence you came and your
 - sanity will be spared. You have been admonished.
 -}

-- O(log n) Delete an element from a set without checking for membership
delete' :: (Ord a) => a -> Set a -> Set a
delete' :: forall a. Ord a => a -> Set a -> Set a
delete' 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'
    (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
    )
 where
  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) Insert an element into a set without checking for membership
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