import Picture

{- 

-- Einige Standard-Listenfunktionen ------------------------------------

head             :: [a] -> a            -- erstes Listenelement selektieren
head (x:_)        = x

last             :: [a] -> a            -- letztes Listenelement selektieren
last [x]          = x
last (_:xs)       = last xs

tail             :: [a] -> [a]          -- Restliste (ohne erstes Element) bilden
tail (_:xs)       = xs

init             :: [a] -> [a]          -- Anfangsliste (ohne letztes Element) bilden
init [x]          = []
init (x:xs)       = x : init xs

null             :: [a] -> Bool         -- Test auf leere Liste
null []           = True
null (_:_)        = False

(++)             :: [a] -> [a] -> [a]   -- Listenkonkatenation
[]     ++ ys      = ys
(x:xs) ++ ys      = x : (xs ++ ys)

length           :: [a] -> Int          -- Laengenfunktion
length []         = 0
length (_:xs)     = 1 + length xs

reverse          :: [a] -> [a]          -- Listenspiegelung
reverse []        = []
reverse (x:xs)    = (reverse xs) ++ [x]

(!!)             :: [b] -> Int -> b     -- Elementselektion
(x:_)  !! 0       = x
(_:xs) !! n | n>0 = xs !! (n-1)
(_:_)  !! _       = error "Prelude.!!: negative index"
[]     !! _       = error "Prelude.!!: index too large"

take                :: Int -> [a] -> [a] -- Praefixliste vorgegebener Laenge bilden
take 0 _             = []
take _ []            = []
take n (x:xs) | n>0  = x : take (n-1) xs
take _ _             = error "Prelude.take: negative argument"

drop                :: Int -> [a] -> [a] -- Suffixliste durch Weglassen bilden
drop 0 xs            = xs
drop _ []            = []
drop n (_:xs) | n>0  = drop (n-1) xs
drop _ _             = error "Prelude.drop: negative argument"

-}



-------------------------------------------------------------------
-- Sortieren durch Einfuegen
-------------------------------------------------------------------

isort        :: [Int] -> [Int] 
isort []     =  []
isort (x:xs) =  insert x (isort xs)

-- Einfuegen eines Elements in eine sortierte Liste
insert          :: Int -> [Int] -> [Int]
insert x []     =  [x]
insert x l@(y:ys) 
    | x < y     =  x:l
    | otherwise =  y : insert x ys

-------------------------------------------------------------------

-------------------------------------------------------------------
-- Quicksort
-------------------------------------------------------------------


qsort        :: [Int] -> [Int]
qsort []     =  []
qsort (x:xs) =  qsort smalls ++ x: qsort bigs
    where (smalls,bigs) = split x xs


-- Aufteilen einer Liste bzgl. eines Pivotelements
split           :: Int -> [Int] -> ([Int],[Int])
split x []      =  ([],[])
split x (y:ys)
    | x < y     =  (left, y:right)
    | otherwise =  (y:left, right)
    where (left,right) = split x ys


-------------------------------------------------------------------
-- Listenabstraktionen
-------------------------------------------------------------------

-- alternative Definition von split

split' x ys = ([a | a<-ys, a<x], [a | a<-ys, a>=x])

--------------------------------------------------------------
-- alternative Definition der Funktionen aus dem Modul Picture
--------------------------------------------------------------

flipV', flipH', invertColour' :: Picture -> Picture
flipV' pic = [reverse row | row <- pic]
flipH' pic = reverse pic

invertColour' pic = [ [changeColour c | c <- row] | row <- pic]
  where  changeColour :: Char -> Char
         changeColour '#' = '.'
         changeColour _   = '#'


above', aside' :: Picture -> Picture -> Picture
above' p1 p2  = p1 ++ p2
aside' p1 p2  = [ r1 ++ r2 | r1 <- p1, r2 <- p2 ]
                -- Was läuft hier falsch?

-- Korrektur: 
aside'' p1 p2  = [ p1!!(i-1) ++ p2!!(i-1) | i <- [1..length p1]]


-- einige einfache Textverarbeitungsfunktionen

digits    :: String -> String
digits st =  [ch | ch <- st, isDigit ch]

upper     :: String -> String
upper st  =  [toUpper ch | ch <- st, isAlpha ch]