module AufgabeFFP8
where

import Data.Char
import Data.Array
import Data.List hiding ((\\), insert, delete, sort)
import Test.QuickCheck

type Nat = [Int]

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

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

-- checklist
minfree_chl :: [Int] -> Int
minfree_chl = search . checklist

search :: Array Int Bool -> Int
search = length . takeWhile id . elems

checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0, n) 
	(zip (filter (<=n) xs) (repeat True))
	where n = length xs

-- countlist
minfree_col :: [Int] -> Int
minfree_col = search_countlist . countlist

countlist :: [Int] -> Array Int Int
countlist xs = accumArray (+) 0 (0, n) (zip xs (repeat 1))
	where n = safe_maximum xs

safe_maximum :: [Int] -> Int
safe_maximum [] = 0
safe_maximum xs = maximum xs

-- unused
sort :: [Int] -> [Int]
sort xs = concat [replicate k x | (x, k) <- assocs ( countlist xs ) ]

search_countlist :: Array Int Int -> Int
search_countlist = length . takeWhile (/= 0) . elems

-- basic divide-and-conquer
minfree_b :: [Int] -> Int
minfree_b xs = 	if (null ([0..b-1] \\ us))
								then (head ([b..] \\ vs))
								else (head ([0..] \\ us))
								where
								(us, vs) = partition (<b) xs
								b = 1 + (length xs) `div` 2

-- refined divide-and-conquer
minfree_r :: [Int] -> Int
minfree_r xs = minfrom 0 xs

minfrom :: Int -> [Int] -> Int
minfrom a xs
	| null xs = a
	| length us == b-a = minfrom b vs
	| otherwise = minfrom a us
	where
	(us, vs) = partition (<b) xs
	b = a + 1 + (length xs) `div` 2

-- optimised divide-and-conquer
minfree_o :: [Int] -> Int
minfree_o xs = minfrom_o 0 (length xs, xs)

minfrom_o :: Int -> (Int, [Int]) -> Int
minfrom_o a (n, xs)
	| n == 0 = a
	| m == b-a = minfrom_o b (n-m, vs)
	| otherwise = minfrom_o a (m, us)
	where 
	(us, vs) = partition (<b) xs
	b = a + 1 + n `div` 2
	m = length us


-- basic divide-and-conquer mittels higher order function
--minfree_bhof :: [Int] -> Int

-- refined divide-and-conquer mittels higher order function
--minfree_rhof :: [Int] -> Int

-- optimised divide-and-conquer mittels higher order function
--minfree_ohof :: [Int] -> Int



-- QuickCheck part