-- ============================================================
-- Break the Loop. Part 3.
-- All examples in one file.
-- Uncomment the desired main call and run.
-- ============================================================


-- ============================================================
-- Optional type (introduced in Part 2)
-- ============================================================

data Optional a = Empty | Result a deriving (Show)


-- ============================================================
-- Task 8. Finding the maximum using tail recursion
-- ============================================================

-- Safe and fast maximum search
myMaxTail :: [Int] -> Optional Int
myMaxTail []     = Empty           -- base case: empty list — nothing to search
myMaxTail (x:xs) = walk xs x       -- take the head as the starting candidate and go
  where
    walk []     currentMax = Result currentMax  -- list exhausted — winner found
    walk (y:ys) currentMax =
        let newMax = if y > currentMax then y else currentMax  -- keep the stronger candidate
        in walk ys newMax           -- last action is a call to walk — tail recursion


-- ============================================================
-- Task 9. Sorting a list
-- ============================================================

-- Removes the FIRST occurrence of an element from the list (not the first element!)
removeFirstMatch :: (Eq a) => a -> [a] -> [a]
removeFirstMatch _ []     = []               -- base case: empty list — nothing to remove
removeFirstMatch x (y:ys)
    | x == y    = ys                         -- match found — return the tail, head is gone
    | otherwise = y : removeFirstMatch x ys  -- no match — keep the head, search in the tail

-- Selection sort: find the maximum, remove it, repeat
naiveSort :: [Int] -> [Int]
naiveSort [] = []       -- base case: empty list is already sorted
naiveSort xs =
    case myMaxTail xs of
        Empty    -> []  -- we won't get here (xs is non-empty), but the type demands it
        Result m ->
            let rest = removeFirstMatch m xs  -- list without the found maximum
            in naiveSort rest ++ [m]          -- sort the rest, append maximum at the end

-- Quicksort: describe what a sorted list IS, not how to build it
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []           -- base case: empty list is sorted by definition
quicksort (x:xs) =          -- x is the pivot, xs is the rest
    let smallerSorted = quicksort [a | a <- xs, a <= x]  -- everyone not taller than pivot — left
        biggerSorted  = quicksort [a | a <- xs, a > x]   -- everyone taller — right
    in  smallerSorted ++ [x] ++ biggerSorted  -- assemble: smaller, pivot, larger


-- ============================================================
-- Task 10. Building a set from a list elements
-- ============================================================

-- Tree type definition
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

-- Insert an element into a binary search tree (smaller — left, larger — right)
treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = Node x EmptyTree EmptyTree  -- found the spot — place the node
treeInsert x (Node val left right)
    | x == val = Node val left right                  -- element already exists — duplicate ignored
    | x < val  = Node val (treeInsert x left) right   -- smaller — go into the left subtree
    | x > val  = Node val left (treeInsert x right)   -- larger — go into the right subtree

-- Convert a list into a binary search tree — duplicates vanish on their own
listToTree :: (Ord a) => [a] -> Tree a
listToTree []     = EmptyTree                      -- base case: empty list — empty tree
listToTree (x:xs) = treeInsert x (listToTree xs)  -- build the tree from the tail first, then insert the head


-- ============================================================
-- Run examples
-- Uncomment the desired main call
-- ============================================================

main :: IO ()
main = runNaiveSort
-- main = runQuicksort
-- main = runTree

runNaiveSort :: IO ()
runNaiveSort = do
    putStrLn "=== Task 8: maximum with tail recursion ==="
    print (myMaxTail [3, 1, 4, 1, 5, 9, 2, 6])
    putStrLn "=== Task 9: naive sort ==="
    print (naiveSort [3, 1, 4, 1, 5, 9, 2, 6])

runQuicksort :: IO ()
runQuicksort = do
    putStrLn "=== Task 9: quicksort ==="
    print (quicksort [3, 1, 4, 1, 5, 9, 2, 6])

runTree :: IO ()
runTree = do
    putStrLn "=== Task 10: list to tree ==="
    print (listToTree [3, 5, 3, 1, 4, 1, 2, 2])