module AufgabeFFP7
where

import Data.Char
import Data.List hiding ((\\))
import Test.QuickCheck

type Buffer = (Int, String)

-- the empty buffer
--TODO empty :: Buffer

-- insert character before cursor
--TODO insert :: Char -> Buffer -> Buffer

-- delete character before cursor
--TODO delete :: Buffer -> Buffer

-- move cursor left one character
--TODO left :: Buffer -> Buffer

-- move cursor right one character
--TODO right :: Buffer -> Buffer

-- is cursor at left end?
--TODO atLeft :: Buffer -> Bool

-- is cursor at right end?
--TODO atRight :: Buffer -> Bool

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

type BufferI = (String, String)

-- the empty buffer
--TODO emptyI :: BufferI

-- insert character before cursor
--TODO insertI :: Char -> BufferI -> BufferI

-- delete character before cursor
--TODO deleteI :: BufferI -> BufferI

-- move cursor left one character
--TODO leftI :: BufferI -> BufferI

-- move cursor right one character
--TODO rightI :: BufferI -> BufferI

-- is cursor at left end?
--TODO atLeftI :: BufferI -> Bool

-- is cursor at right end?
--TODO atRightI :: BufferI -> Bool

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

--TODO retrieve :: BufferI -> Buffer

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

--TODO: quicheck stuff

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

-- from slide 154
divideAndConquer :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s
divideAndConquer indiv solve divide combine initPb = dAC initPb
  where
    dAC pb
      | indiv pb = solve pb
      | otherwise = combine pb (map dAC (divide pb))

-- from slide 156
quickSort :: Ord a => [a] -> [a]
quickSort lst = divideAndConquer indiv solve divide combine lst
  where
    indiv ls = length ls <= 1
    solve = id
    divide (l:ls) = [[ x | x <- ls, x <= l], [ x | x <- ls, x > l] ]
    combine (l:_) [l1,l2] = l1 ++ [l] ++ l2

removeDuplicates :: [Int] -> [Int]
removeDuplicates xs = nub xs

-- from slide 245
ssfn :: [Int] -> Int
ssfn xs = sap 0 (removeDuplicates (quickSort xs))

sap :: Int -> [Int] -> Int
sap n [] = n
sap n (x:xs)
  | n /= x = n
  | otherwise = sap (n + 1) xs

-- from slide 247
(\\) :: Eq a => [a] -> [a] -> [a]
xs \\ ys = filter (\x -> x `notElem` ys) xs

minfree :: [Int] -> Int
minfree xs = head ([0..] \\ xs)

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

type Nat = [Int]

prop_ssfn_eq_minfree_a :: Nat -> Bool
prop_ssfn_eq_minfree_a xs = minfree pos == ssfn pos
  where
    pos = filter (>= 0) xs

prop_ssfn_eq_minfree_b :: Nat -> Property
prop_ssfn_eq_minfree_b xs = filter (< 0) xs == []
  ==> ssfn xs == minfree xs