module Lib where

import qualified Data.Map as Map

insertionSort :: [Int] -> [Int]
insertionSort list = doInsertionSort list []

doInsertionSort :: [Int] -> [Int] -> [Int]
doInsertionSort list res = case list of
    []     -> res
    (x:xs) -> doInsertionSort xs (res ++ [(findMin xs x [])])

findMin :: [Int] -> Int -> [Int] -> [Int]
findMin list cur res = case list of
    []                  -> cur
    (x:xs) | (x < cur)  -> findMin xs x
    _                   -> findMin xs cur


cntSort :: [Int] -> [Int]
cntSort list = genSorted [] $ countElements list Map.empty

countElements :: [Int] -> Map.Map Int Int -> [(Int,Int)]
countElements list res = case list of
    []     -> Map.toAscList res
    (x:xs) -> case Map.lookup res x of
        Just v  -> countElements xs Map.insert x (v + 1)
        Nothing -> countElements xs Map.insert x 1

genSorted :: [Int] -> [(Int,Int)] -> [Int]
genSorted res freq = case freq of
    []          -> res
    ((value, cnt):xs) -> genSorted (res ++ (repeatElement value cnt [])) xs

repeatElement :: Int -> Int -> [Int]
repeatElement v cnt res = case cnt  of
    _ | (cnt == 0) -> res
    _              -> repeatElement v (cnt - 1) (res ++ [v])


{-
practice1 :: () -> IO()
practice1 = do
    let d = 2
    let x = case d of
        0 -> insertionSort list
        1 -> cntSort list
-}