(* * * * * * * * * * *
 * 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 rec compare_list (l1:int list) l2 =
  match l1 with
    | [] -> true
    | x::xs ->
      match l2 with
	| [] -> false
	| y::ys ->
	  if x = y then
	    compare_list xs ys
	  else
	    x <= y

let quicksort_list = quicksort compare_list


let ll =
[ [4;1;1]
; [4;1]
; [4]
; [2;1]
; [1;3;3;3]
; [1;2;3;4]
; [1;2]
]

let ll' =
[ [1;1;1;1;1]
; [1;1;1;1]
; [1;1;1]
; [1;1]
; [1]
]

let _ =
  quicksort_list  ll'