(* * * * * * * * * * *
 * Resource Aware ML *
 * * * * * * * * * * *
 *
 * * *  Use Cases  * *
 *
 * File:
 *   examples/quicksort.raml
 *
 * Author:
 *   Jan Hoffmann, Shu-Chun Weng (2014)
 *
 * Description:
 *   Tony Hoare's quicksort for lists.
 *
 *)


let rec append l1 l2 =
  match l1 with
    | [] -> l2
    | x::xs -> x::(append xs l2)


let rec partition f l =
  match l with
    | [] -> ([],[])
    | x::xs ->
      let (cs,bs) = partition f xs in
      Raml.tick 1.0;
      if f x then
	(cs,x::bs)
      else
	(x::cs,bs)


let rec quicksort gt = function
  | [] -> []
  | x::xs ->
      let ys, zs = partition (gt x) xs in
      append (quicksort gt ys) (x :: (quicksort gt zs))


let _ =
  quicksort (fun a b -> a <= b)  [9;8;7;6;5;4;3;2;1]


let compare (a:int*int) (b:int*int) =
  let (a1,a2) = a in
  let (b1,b2) = b in
  if not (a1=b1) then
    a1 < b1
  else
    a2 <= b2

let quicksort_pairs = quicksort compare


let _ =
  quicksort_pairs [(1,2);(3,4);(3,5);(1,1)]