-- Exercitiul 1

data Arbore a
    = Nod (Arbore a) a (Arbore a)
    | Vid

-- For testing purposes.
instance Eq a => Eq (Arbore a) where
    Vid == Vid = True
    _ == Vid = False
    Vid == _ = False
    (Nod stA a drA) == (Nod stB b drB) = a == b && stA == stB && drA == drB

instance Show a => Show (Arbore a) where  
    show Vid = "VID"
    show (Nod st a dr) = show st ++ " " ++ show a ++ " " ++ show dr

-- rootBigger x y -> checks if root of x is bigger than all the elements in y
rootBigger :: Ord a => Arbore a -> Arbore a -> Bool
rootBigger Vid _ = True
rootBigger _ Vid = True
rootBigger (Nod x a y) (Nod st other dr) = a > other && rootBigger (Nod x a y) st && rootBigger (Nod x a y) dr

-- rootSmaller x y -> checks if root of x is smaller than all the elements in y
rootSmaller :: Ord a => Arbore a -> Arbore a -> Bool
rootSmaller Vid _ = True
rootSmaller _ Vid = True
rootSmaller (Nod x a y) (Nod st other dr) = a < other && rootSmaller (Nod x a y) st && rootSmaller (Nod x a y) dr

-- a)
verif :: Ord a => Arbore a -> Bool
verif Vid = True
verif (Nod st a dr) = rootBigger (Nod st a dr) st && rootSmaller (Nod st a dr) dr && verif st && verif dr

arb1 :: Arbore Integer
arb1 = Nod Vid 5 Vid
arb2 :: Arbore Integer
arb2 = Nod (Nod Vid 3 Vid) 5 (Nod Vid 7 Vid)

test1 :: Bool
test1 = verif arb1

test2 :: Bool
test2 = verif arb2

test3 :: Bool
test3 = not (verif (Nod (Nod Vid 6 Vid) 5 (Nod Vid 7 Vid)))

test4 :: Bool
test4 = not (verif (Nod (Nod Vid 3 Vid) 5 (Nod Vid 7 (Nod Vid 4 Vid))))

test5 :: Bool
test5 = not (verif (Nod (Nod Vid 3 Vid) 5 (Nod Vid 7 (Nod Vid 7 Vid))))

-- b)
insert :: Ord t => Arbore t -> t -> Arbore t
insert Vid x = Nod Vid x Vid
insert (Nod st a dr) x
    | x < a = Nod (insert st x) a dr
    | x > a = Nod st a (insert dr x)
    | otherwise = Nod st a dr

test6 :: Bool
test6 = insert Vid 5 == Nod Vid 5 Vid

test7 :: Bool
test7 = insert arb1 5 == arb1

test8 :: Bool
test8 = insert arb2 6 == Nod (Nod Vid 3 Vid) 5 (Nod (Nod Vid 6 Vid) 7 Vid)

-- c)
instance Functor Arbore where
    fmap _ Vid = Vid
    fmap f (Nod st a dr) = Nod (fmap f st) (f a) (fmap f dr)

test9 :: Bool
test9 = fmap (+1) arb2 == Nod (Nod Vid 4 Vid) 6 (Nod Vid 8 Vid)