{- Sorting Functions
   CSci 450/503, Fall 2016
   2016-11-26: H. Conrad Cunningham
-}

import Html exposing (..)

-- Function isort takes an unsorted list of comparable values and
-- returns the resulting sorted list. It uses an insertion sort
-- algorithm. Type variable comparable is restricted to values that
-- can be compared.

isort : List comparable -> List comparable
-- isort : List Int -> Intisort : List Int -> List Int
isort xs =
   case xs of
       []        ->  []
       x :: xs ->  insert x (isort xs)  

insert : comparable -> List comparable -> List comparable
-- insert : Int -> List Int -> List Int
insert x xs =
   case xs of
      []       -> [x]
      y :: ys  ->
         if x <= y then
            x :: y :: ys
         else
            y :: insert x ys

-- Function msort takes a less-than comparison function and an
-- unsorted list of values and returns the resulting sorted list. It
-- uses the higher order argument and applies the merge sort
-- algorithm.

msort less xs =
   case xs of
      []  -> []
      [x] -> [x]
      _   -> 
         let 
            n  = (List.length xs) // 2
            ls = List.take n xs
            rs = List.drop n xs
            -- using type inference for this local function
            merge ss ts =
               case (ss,ts) of
                  ([], _ )         -> ts
                  (_,  [])         -> ss
                  (s::sst, t::tst) ->
                     if less s t then
                        s :: merge sst ts
                     else
                        t :: merge ss  tst          
         in
            merge (msort less ls) (msort less rs)

-- Simple Display Functions

newline = br [] []

displayLines : List String -> List (Html msg)
displayLines ss = 
   case ss of
      []      -> []
      x :: xs -> text x :: newline :: displayLines xs

display : List String -> Html msg
display ls = p [] (displayLines ls)

-- Some testing

list0 = []
list1 = [1]
list2 = [2,1]
list3 = [1,2,3]
list4 = [0,9,8,7,6,5,4,3,2,1]

sort0 = isort list0
sort1 = isort list1
sort2 = isort list2
sort3 = isort list3
sort4 = isort list4

msort0 = msort (<) list0
msort1 = msort (<) list1
msort2 = msort (<) list2
msort3 = msort (<) list3
msort4 = msort (<) list4

main =
  display 
     [ "Start!"
     , "isort tests:" 
     , toString sort0
     , toString sort1
     , toString sort2
     , toString sort3
     , toString sort4
     , "msort tests:"
     , toString msort0
     , toString msort1
     , toString msort2
     , toString msort3
     , toString msort4     
     , "End!"
     ]