module Exercise_8 where
import Control.Monad
import Data.Ratio
import Test.QuickCheck

{- Library -- nicht veraendern -}

data PosShape = At Shape (Integer, Integer)

data Shape =
  Circle Integer |
  Rectangle Integer Integer -- Breite, Höhe
  deriving (Show, Eq)

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

insert :: Ord a => a -> Tree a -> Tree a
insert x Empty = Node x Empty Empty
insert x (Node a l r)
  | x < a = Node a (insert x l) r
  | x > a = Node a l (insert x r)
  | otherwise = Node a l r

delete :: Ord a => a -> Tree a -> Tree a
delete x Empty = Empty
delete x (Node a l r)
  | x == a     =  combine l r
  | x < a      =  Node a (delete x l) r
  | otherwise  =  Node a l (delete x r)

combine :: Tree a -> Tree a -> Tree a
combine Empty r  =  r
combine l Empty  =  l
combine l r      =  Node m l r'  where (m,r') = delL r

delL :: Tree a -> (a, Tree a)
delL (Node a Empty r)  = (a, r)
delL (Node a l     r)  = (m, Node a l' r)  where (m,l') = delL l

-- 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))]

data RegEx =
  Any |
  One Char |
  OneIn [(Char, Char)] |
  Concat RegEx RegEx |
  Alt RegEx RegEx |
  Repeat RegEx

{- End Library -}



-- WICHTIG
-- Dieses Template ist nur fuer die Hausaufgaben gedacht!

{- H1 -}

isHeap :: Ord a => Tree a -> Bool
isHeap t = undefined


{- H2 -}

data Direction = L | R
  deriving (Show, Eq)

replace :: [Direction] -> Tree a -> Tree a -> Maybe (Tree a)
replace ds t' t = undefined


{- H3 -}

find' :: Ord a => a -> Tree a -> Bool
find' x t = undefined

{- H4 -}

maybeMap :: (a -> Maybe b) -> [a] -> Maybe [b]
maybeMap = undefined

inverses :: [Integer] -> Maybe [Rational]
inverses = undefined

{- H5 -}

{-WETT-}
match :: RegEx -> String -> Bool
match regex str = undefined
{-TTEW-}