-- Code from Section 1.2

module Maxiphobic where

data Ord a => Tree a = Null | Fork Int a (Tree a) (Tree a)

isEmpty :: Ord a => Tree a -> Bool
isEmpty Null = True
isEmpty (Fork n x a b) = False

minElem :: Ord a => Tree a -> a
minElem (Fork n x a b) = x

deleteMin :: Ord a => Tree a -> Tree a
deleteMin (Fork n x a b) = merge a b

insert :: Ord a => a -> Tree a -> Tree a
insert x a = merge (Fork 1 x Null Null) a

merge :: Ord a => Tree a -> Tree a -> Tree a
merge a Null = a
merge Null b = b
merge a b
   | minElem a <= minElem b = join a b
   | otherwise = join b a

join (Fork n x a b) c = Fork (n + size c) x aa (merge bb cc)
        where (aa,bb,cc) = orderBySize a b c

orderBySize a b c
   | size a == biggest = (a,b,c)
   | size b == biggest = (b,a,c)
   | size c == biggest = (c,a,b)
  where
     biggest = size a `max` size b `max` size c

size Null = 0
size (Fork n x a b) = n