{-# language DeriveGeneric #-}
module Blueprint where

import Prelude hiding ( reverse, sum )
import Test.LeanCheck
import Test.LeanCheck.Generic
import GHC.Generics

data Bintree a = Leaf | Branch (Bintree a) a (Bintree a)  
     deriving (Eq, Show, Generic)

instance (Listable a) =>  Listable (Bintree a) where tiers = genericTiers

t :: Bintree Int
t = Branch (Branch Leaf 5 Leaf)
     	    3
     	    (Branch Leaf 2 (Branch Leaf 4 Leaf) )

size :: Bintree Int -> Int
size t = case t of
  Leaf         -> 0
  Branch l k r -> (size l) + 1 + (size r)

leaves :: Bintree a -> Int
leaves t = case t of
  Leaf         -> 1
  Branch l k r -> (leaves l) + (leaves r)

bt_sum :: Bintree Int -> Int
bt_sum t = case t of
  Leaf         -> 0
  Branch l k r -> (bt_sum l) + k + (bt_sum r)

wurzel :: Bintree a -> Maybe a
wurzel t = case t of
    Leaf  -> Nothing
    Branch _ k _-> Just k 

inorder :: Bintree a -> [a]
inorder t = case t of
    Leaf         -> []
    Branch l k r -> (inorder l)  ++ [k] ++ (inorder r)

test_inorder :: Bool
test_inorder = and
         [ inorder (t) == [5,3,2,4]
         , holds 1000 $ \ t -> size t == length (inorder t)
         ]

full :: Int -> Bintree Int
full h = if h > 0 
    then Branch (full (h-1)) h (full (h-1))  
    else Leaf

test_full :: Bool
test_full = and
         [ size (full 3) == 7
         , holds 30 $ \ k -> size (full k) == if k > 0 then 2^k - 1 else 0
         ]