module AufgabeFFP7
where

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

type Buffer = (Int, String)

-- the empty buffer
empty :: Buffer
empty = (0, "")

-- insert character before cursor
insert :: Char -> Buffer -> Buffer
insert c (cur, buf) = (min (length buf + 1) (max (cur + 1) 1), buf1 ++ [c] ++ buf2)
  where
    (buf1, buf2) = splitAt cur buf

-- delete character before cursor
delete :: Buffer -> Buffer
delete (cur, buf)
  | buf2 == [] = (min cur (length buf1), buf1)
  | cur < 0 = (0, buf)
  | otherwise = (cur, buf1 ++ tail buf2)
  where
    (buf1, buf2) = splitAt cur buf

-- move cursor left one character
left :: Buffer -> Buffer
left (cur, buf) = (min (length buf) (max (cur - 1) 0), buf)

-- move cursor right one character
right :: Buffer -> Buffer
right (cur, buf) = (max 0 (min (cur + 1) (length buf)), buf)

-- is cursor at left end?
atLeft :: Buffer -> Bool
atLeft (cur, buf) = cur <= 0

-- is cursor at right end?
atRight :: Buffer -> Bool
atRight (cur, buf) = cur >= length buf

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

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 = all (>= 0) xs
  ==> ssfn xs == minfree xs