-- ?

-- Abstraction function
{-
    alpha (S x) = undefined

    To show: (10 things)
-}

-- Interface
newtype Set a = S (...)

invar :: Integral a => Set a -> Bool
invar (S s) = undefined

empty :: Set a
empty = undefined

insert :: Integral a => a -> Set a -> Set a
insert n (S s) = undefined

isin :: Integral a => a -> Set a -> Bool
isin n (S s) = undefined

size :: Integral a => Set a -> Integer
size (S s) = undefined

union :: Integral a => Set a -> Set a -> Set a
union (S s1) (S s2) = undefined

delete :: Integral a => a -> Set a -> Set a
delete n (S s) = undefined

-- Implementation
type PairList a = [(a, a)]

invarPL :: Integral a => PairList a -> Bool
invarPL [] = True
invarPL [(m,n)] = m <= n
invarPL ((m1,n1):(m2,n2):ms) =
    m1 <= n1 && n1 + 1 < m2 && invarPL ((m2,n2):ms)

emptyPL :: PairList a
emptyPL = []

insertPL :: Integral a => a -> PairList a -> PairList a
insertPL n [] = [(n,n)]
insertPL n ((k1,l1) : (k2,l2) : ks)
    | l1 + 1 == n && n + 1 == k2 = (k1,l2) : ks
insertPL n ((k,l) : ks)
    | n + 1 == k = (n,l) : ks
    | n < k = (n,n) : (k,l) : ks
    | k <= n && n <= l = (k,l) : ks
    | l + 1 == n = (k,n) : ks
    | otherwise = (k,l) : insertPL n ks

isinPL :: Ord a => a -> PairList a -> Bool
isinPL n = any (\(k,l) -> k <= n && n <= l)

sizePL :: Integral a => PairList a -> Integer
sizePL [] = 0
sizePL ((k,l) : s) = toInteger (l - k + 1) + sizePL s

unionPL :: Integral a => PairList a -> PairList a -> PairList a
unionPL [] ls = ls
unionPL ks [] = ks
unionPL ((k1,l1):ks) ((k2,l2):ls) =
    if k1 <= k2
    then if l1 + 1 < k2 then (k1,l1) : unionPL ks ((k2, l2):ls)
         else if l1 <= l2 then unionPL ks ((k1,l2):ls)
         else {- l1 > l2 -} unionPL ((k1,l1):ks) ls
    else if k1 <= l2 + 1
    then if l1 <= l2 then unionPL ks ((k2,l2):ls)
         else {- l1 > l2 -} unionPL ((k2,l1):ks) ls
    else (k2,l2) : unionPL ((k1,l1):ks) ls

deletePL :: Integral a => a -> PairList a -> PairList a
deletePL n [] = []
deletePL n ((k,l) : ks)
    | n < k = (k,l) : ks
    | n == k = if k < l then (k+1,l) : ks else ks
    | k < n && n < l = (k,n-1) : (n+1,l) : ks
    | n == l = if k < l then (k,l-1) : ks else ks
    | otherwise = (k,l) : deletePL n ks