module AufgabeFFP3
where

import Prelude hiding (filter)

type Weight = Int
type Value = Int
type Item = (Weight, Value)
type Items = [Item]

type Load = [Item]

type Loads = [Load]
type LoadWghtVal = (Load, Weight, Value)
type MaxWeight = Weight

safeGet :: [Integer] -> Int -> Integer -- get element of list, default to 0
safeGet l i
	| i < length l = l !! i
	| otherwise = 0

toBin :: Integer -> [Integer] -- get binary representation of integer
toBin 0 = []
toBin i = [rem] ++ toBin quot
	where ( quot, rem ) = quotRem i 2

hasBit :: Integer -> Int -> Bool -- check if the binary representation of a number has the ith bit set
hasBit num ith = (safeGet (toBin num) ith) == 1

getChoice :: Items -> Int -> Items -- choose a subset determined by binary representation of l
getChoice l i = concat ( map (choose l) [0..(length l)-1]  )
	where
	choose l pos 
		| hasBit (fromIntegral i) pos = [ l !! pos ]
		| otherwise = []

generator:: Items -> Loads -- get all possible choices (2^n)
generator l = map ( getChoice l ) [1..num]
	where num = (2^(length l)) - 1

transformer :: Loads -> [LoadWghtVal] -- calc sum of weight and value for all lists of items
transformer l = map trans l

trans :: Load -> LoadWghtVal -- worker of transformer
trans load = (load, weight, value)
	where 
	weight = sum $ map fst load
	value = sum $ map snd load

getWeight :: LoadWghtVal -> Weight
getWeight (_, w, _) = w

getVal :: LoadWghtVal -> Value
getVal (_, _, v) = v

filter :: MaxWeight -> [LoadWghtVal] -> [LoadWghtVal] -- drop those with too much weight
filter max l = [ x | x <- l, getWeight x <= max ]

selector :: [LoadWghtVal] -> [LoadWghtVal] -- get those with max val
selector l = [ x | x <- l, getVal x == max ]
	where max = maximum $ map getVal l

selector1 :: [LoadWghtVal] -> [LoadWghtVal] -- all with max val
selector1 = selector

selector2 :: [LoadWghtVal] -> [LoadWghtVal] -- get ones with min weight
selector2 l = [ x | x <- best, getWeight x == min ]
	where
	min = minimum $ map getWeight best
	best = selector l