{-






-}




leaf x = Node x Null Null
t = Node 17 (Node 12 (Node 5 Null (leaf 8)) (leaf 15)) (Node 1005 (Node 32 (leaf 30) (Node 46 Null (leaf 57))) (Node 1 Null (Node 2 Null (Node 3 Null Null))))



data Tree a = Null | Node a (Tree a) (Tree a) deriving (Show,Eq)
data Box a = One a | Many [a] deriving (Show, Eq)
data KeyPress = Delete | Backspace | Type Char deriving (Show, Eq)

ifMany (Many _) = True
isMany _ = False
isType (Type _) = True
isType _ = False


treeHeight (Node val l r) = (max (treeHeight l) (treeHeight r)) + 1
treeHeight Null = 0

inorder (Node v left right) = ((inorder left) ++ [v] ++ (inorder right))
inorder Null = []


-- utilities

splitNum n = ((n `div` 2), (n `div` 2) + (n `mod` 2))

iter 0 f val = val
iter n f val = iter (n-1) f (f val)

betterZip :: [[a]] -> [[a]]
betterZip l = if any null l then [] else (map head l) : betterZip (map tail l)

pad c padval lst
  | length lst == c = lst
  | length lst < c  = pad c padval (lst ++ [padval])
  | otherwise  = error("list bigger than padding")



(spaces, arrows, vert) = (create ' ', create '|', create '-') where create char s = pad s char "" -- replicate benutzen

replaceEvery every elem lst = [if index `mod` every == 0 then elem else charNow |
  (index, charNow) <- zip [0..length(lst)-1] lst]

--mapShowOnPostorder = filter ((head.filter) isMany) rotatedTree



boxedTreeRepr :: (Show t) => Tree t -> [[Box Char]]
boxedTreeRepr tree = (unrotateTree . (rotatedTree' 0)) tree
  where
    rotatedTree' :: (Show t) => Int -> Tree t -> [[Box Char]]
    rotatedTree' c (Node val left right) =
      (rotatedTree' (c+cIncr)  left) ++
      [(map One (if c == 0 then "" else ((spaces (c-cIncr)) ++ "+" ++ (arrows (cIncr-1))))) ++ [Many (show val)] ]
      ++ rotatedTree' (c+cIncr)  right

    rotatedTree' c Null =  []

    --maxShowLength = foldr max 0 (inorder tree)
    cIncr = 3

    putSpaces (a:b:xs) = a : (replicate 5 []) ++ putSpaces (b:xs)
    putSpaces  [x] = [x]
    putSpaces [] = []

    unrotateTree myFlipped = (betterZip) (map myPad (putSpaces myFlipped))
      where myPad = pad ((treeHeight t)*cIncr)  (One ' ')



expandBoxesIntoString = (typing2string.boxes2typing)
  where

    boxes2typing :: [Box Char] -> [KeyPress]
    boxes2typing (One a : rest) = Type a : boxes2typing rest
    boxes2typing (Many as : rest) =  (replicate a Backspace) ++ (map Type as) ++ (replicate a Delete) ++ boxes2typing rest
      where (a, b) = splitNum $ length as

    boxes2typing [] = []

    applyOne (Delete : Type _ : rest) = rest
    applyOne (Type _ : Backspace : rest) = rest

    applyOne (Delete : Delete : rest) = Delete : (applyOne $ Delete:rest)
    applyOne (a : b : rest) = a : (applyOne $ b:rest)
    applyOne x = error $ "no matching for: " ++ show x


    applyAllBackspaces typing = iter backspaces applyOne typing
      where backspaces = length $ filter (not.isType) typing

    typing2string typing = map (\(Type x)->x) (applyAllBackspaces typing)



myShow tree = unlines $ map (dontPutMinus.expandBoxesIntoString) (boxedTreeRepr t) -- naja soll nur bei jeden drittten element angewendet werden, aber die funktion putMinus und dontPutMinus ist falsch und ich hab kein bock mehr


putMinus ('+':xs) = '+':dontPutMinus xs
putMinus (' ':xs)   = '-':putMinus xs
putMinus (x:xs)     =  x:putMinus xs
putMinus [] = []

dontPutMinus ('+':xs) = '+':putMinus xs
dontPutMinus (' ':xs)   = ' ':dontPutMinus xs
dontPutMinus (x:xs)     =  x:dontPutMinus xs
dontPutMinus [] = []

{-
Beachte wie das ergebnis falsch ist, aber der ansatz ist ok

*Main> putStr $ myShow t
            +----------17----------------------------+
            |                                         |
            |                                         |
+----------12----+                 +---------------1005---+
|                 |                 |                       |
|                 |                 |                       |
5     +----------15----------+    32    +-----------------1-----+
      |                       |           |                       |
      |                       |           |                       |
      8                      30         46    +-----------------2-----+
                                                |                       |
                                                |                       |
                                               57                      3





-}