--
--
-- Order
--
--

ordering :=
  algebraicDataMatcher
    | less
    | equal
    | greater

compare m n :=
  if isCollection m
    then compareC m n
    else if m < n then Less else if m = n then Equal else Greater

compareC c1 c2 :=
  match (c1, c2) as (list something, list something) with
    | ([], []) -> Equal
    | ([], _) -> Less
    | (_, []) -> Greater
    | ($x :: $xs, #x :: $ys) -> compareC xs ys
    | ($x :: _, $y :: _) -> compare x y

min $x $y := if x < y then x else y

max $x $y := if x > y then x else y

min/fn f $xs := foldl1 2#(if f %1 %2 = Less then %1 else %2) xs

max/fn f $xs := foldl1 2#(if f %1 %2 = Greater then %1 else %2) xs

minimum $xs := foldl1 min xs

maximum $xs := foldl1 max xs

splitByOrdering := 2#(splitByOrdering/fn compare %1 %2)

splitByOrdering/fn f p xs :=
  match xs as list something with
    | [] -> ([], [], [])
    | $x :: $rs ->
      let (ys1, ys2, ys3) := splitByOrdering/fn f p rs
       in match f x p as ordering with
            | less -> (x :: ys1, ys2, ys3)
            | equal -> (ys1, x :: ys2, ys3)
            | greater -> (ys1, ys2, x :: ys3)

sort := 1#(sort/fn compare %1)

sort/fn f xs :=
  match xs as list something with
    | [] -> []
    | $x :: [] -> [x]
    | _ ->
      let n := length xs
          p := nth (quotient n 2) xs
          (ys1, ys2, ys3) := splitByOrdering/fn f p xs
       in sort/fn f ys1 ++ ys2 ++ sort/fn f ys3

sortStrings xs :=
  sort/fn 2#(compareC (map ctoi (unpack %1)) (map ctoi (unpack %2))) xs

merge xs ys :=
  match (xs, ys) as (list something, list something) with
    | ([], _) -> ys
    | (_, []) -> xs
    | ($x :: $txs, ?(>= x) :: _) -> x :: merge txs ys
    | (_, $y :: $tys) -> y :: merge xs tys

merge/fn f xs ys :=
  match (xs, ys) as (list something, list something) with
    | ([], _) -> ys
    | (_, []) -> xs
    | ($x :: $txs, ?1#(f %1 x = Greater) :: _) -> x :: merge txs ys
    | (_, $y :: $tys) -> y :: merge xs tys

minimize f xs :=
  foldl1 2#(if compare (f %1) (f %2) = Less then %1 else %2) xs

maximize f xs :=
  foldl1 2#(if compare (f %1) (f %2) = Greater then %1 else %2) xs