module Exercise_9 where
import Test.QuickCheck
import Control.Monad

{- Library -- nicht veraendern -}

data Tree a = Empty | Node a (Tree a) (Tree a)
  deriving (Eq, Show)

data Tree23 a = Leaf a
              | Branch2 (Tree23 a) a (Tree23 a)
              | Branch3 (Tree23 a) a (Tree23 a) a (Tree23 a)
  deriving Show

mirror :: Tree a -> Tree a
mirror Empty = Empty
mirror (Node x l r) = Node x (mirror r) (mirror l)

flat :: Tree a -> [a]
flat Empty = []
flat (Node x l r) = flat l ++ [x] ++ flat r

-- allow QuickCheck to generate arbitrary values of type Tree
instance Arbitrary a => Arbitrary (Tree a) where
  arbitrary = sized tree
    where
    tree 0 = return Empty
    tree n | n > 0 = oneof [return Empty,
      liftM3 Node arbitrary (tree (n `div` 2)) (tree (n `div` 2))]
  shrink Empty = []
  shrink (Node x l r) = l : r : map (\l' -> Node x l' r) (shrink l)
        ++ map (\r' -> Node x l r') (shrink r)

-- examples for G9.2
balancedTrees =
    [ Empty
    , Node 0 Empty Empty
    , Node 0 (Node 1 Empty Empty) Empty
    , Node 4 (Node 2 Empty (Node 5 Empty Empty)) (Node 0 Empty Empty)
    , Node 1 (Node 0 Empty (Node 3 Empty Empty))
             (Node 0 Empty (Node 3 Empty Empty))
    ]

unbalancedTrees =
    [ Node 3 (Node 2 Empty (Node 1 Empty Empty)) Empty
    , Node 4 (Node 3 (Node 2 (Node 1 Empty Empty) Empty) Empty)
             (Node 3 Empty (Node 2 Empty (Node 1 Empty Empty)))
    , Node 9 (Node 8 (Node 7 Empty Empty ) Empty)
             (Node 1 (Node 0 Empty (Node 3 Empty Empty))
                     (Node 0 Empty (Node 3 Empty Empty)))
    ]

{- H9.1 -}

{- H9.2 -}

inorder :: Tree a -> [a]
inorder = undefined

preorder :: Tree a -> [a]
preorder = undefined

postorder :: Tree a -> [a]
postorder = undefined

{- H9.3 -}

-- makeBalanced :: Int -> SkeleTree
-- makeBalanced = undefined
--
-- makeAllBalanced :: Int -> SkeleTree
-- makeAllBalanced = undefined

{- H9.4 -}

find23 :: Ord a => a -> Tree23 a -> Bool
find23 = undefined