module BspLists where
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)

concat           :: [[a]] -> [a]        -- Flachklopfen von Listen
concat []         = []
concat (xs:xss)   = xs ++ concat xss 

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 _ _             = []

drop                :: Int -> [a] -> [a] -- Suffixliste durch Weglassen bilden
drop 0 xs            = xs
drop _ []            = []
drop n (_:xs) | n>0  = drop (n-1) xs
drop _ _             = []

replicate           :: Int -> a -> [a]
replicate 0 x        = []
replicate (n+1) x    = x : replicate n x
replicate _     _    = []

zip                 :: [a] -> [b] -> [(a,b)]
zip  xs []           = []
zip  [] ys           = []
zip  (x:xs) (y:ys)   = (x,y) : zip xs ys
-}



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

-- Filterfunktionen

filter_even :: [Integer] -> [Integer]
filter_even ys = [y | y <- ys, even y]

filter_odd :: [Integer] -> [Integer]
filter_odd ys = [y | y <- ys, odd y]


-- doppelte Generatoren

opairs :: Int -> [(Int,Int)]
opairs n = [(x,y) | x <- [1..n], y <- [x..n]]

my_concat :: [[a]] -> [a]
my_concat xss = [x | xs <- xss, x <- xs]
 

--------------------------------------------------------------
-- alternative Definition der Funktionen aus dem Modul Picture
--------------------------------------------------------------
-- type Picture = [String]


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?

-- Korrekturen: 
aside'' p1 p2  = [ p1!!(i-1) ++ p2!!(i-1) | i <- [1..length p1]]
aside''' p1 p2 = [ r1 ++ r2 | (r1,r2) <- zip p1 p2] 


project :: Eq a => [(a,b)] -> a -> [b]
project l a = [ b | (x,b) <- l, x == a ]

project' :: [(a,b)] -> a -> [b]
project' l a = [ b | (a,b) <- l ]







-- einige einfache Textverarbeitungsfunktionen

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

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

isDigit c = c<='9' && c>='0'
isAlpha c = (c<='z' && c>='a') || (c>='A' && c<='Z') || c == ' ' 
toUpper c | (c>='A' && c<='Z') || c == ' ' = c
          | (c<='z' && c>='a') = toEnum (fromEnum c + fromEnum 'A' - fromEnum 'a')