(* * * * * * * * * * *
 * Resource Aware ML *
 * * * * * * * * * * *
 *
 * * *  Use Case  * *
 *
 * File:
 *   examples/aws/sort_average.raml
 *
 * Author:
 *   Jan Hoffmann, Ronghui Gu (2015)
 * 
 * Description:
 *   Using Amazon's DynamoDB to sort students according to their avarage grades. 
 *)

exception Not_found of int * int

type 'a option = None | Some of 'a

let db_query student_id course_id =
  Raml.tick(1.0);  Some 1.0

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

let rec partition gt acc l =
  match l with
    | [] -> acc
    | x::xs ->
      let (cs,bs,acc) = acc in
      let (is_greater,acc') = gt x acc in
      if is_greater then
  	partition gt (cs,x::bs,acc') xs
      else
  	partition gt (x::cs,bs,acc') xs

let rec quicksort gt acc l = match l with
  | [] -> ([],acc)
  | x::xs ->
    let ys, zs, acc' = partition (gt x) ([],[],acc) xs in
    let (l1,acc'') = quicksort gt acc' ys in
    let (l2,acc''') = quicksort gt acc'' zs in
    (append  (x :: l1) l2, acc''')


let rec foldl f acc l =
  match l with
    | [] -> acc
    | x::xs -> foldl f (f acc x) xs

let average_grade student_id course_ids =
  let f acc cid =
    let (length,sum) = acc in
    let grade = match db_query student_id cid with
      | Some q -> q
      | None -> raise (Not_found (student_id,cid))
    in
    (length +. 1.0, sum +. grade)
  in
  let (length,sum) = foldl f (0.0,0.0) course_ids in
  sum /. length

let greater_eq sid1 sid2 course_ids =
  (average_grade sid1 course_ids >= average_grade sid2 course_ids, course_ids)

let sort_students student_ids course_ids =
  let (sorted_sids, acc) = quicksort greater_eq course_ids student_ids in
  sorted_sids


let rec map f l =
  match l with
    | [] -> []
    | x::xs -> (f x) :: (map f xs)

let make_table student_ids course_ids =

  let rec mk_table sids cids =
    match sids with
      | [] -> []
      | x::xs ->
	let cid_map =
	  let f cid =
	    let grade =
	      match db_query x cid with
	  	| Some q -> q
	  	| None -> raise (Not_found (x,cid))
	    in
	    (cid,grade)
	  in
	  map f cids
	in
	(x,cid_map)::(mk_table xs cids)
  in
  mk_table student_ids course_ids


let rec find f l =
  match l with
    | [] -> raise (Not_found (-1,-1))
    | x::xs ->
      let (key,value) = x in
      if f key then
	value
      else
	find f xs

let lookup sid cid table =
  let cid_map = find (fun (id:int) -> id = sid) table in
  find (fun (id:int) -> id = cid) cid_map


let average_grade' student_id course_ids table =
  let f acc cid =
    let (length,sum,table) = acc in
    let grade = lookup student_id cid table in
    (length +. 1.0, sum +. grade, table)
  in
  let (length,sum,table') = foldl f (0.0,0.0,table) course_ids in
  (sum /. length,table')


let greater_eq' course_ids sid1 sid2 table =
  let (grade1, table1) = average_grade' sid1 course_ids table in
  let (grade2, table2) = average_grade' sid2 course_ids table1 in
  (grade1 >= grade2, table2)


let sort_students_efficient student_ids course_ids =
  let (sorted_sids, acc) = quicksort (greater_eq' course_ids)  (make_table student_ids course_ids) student_ids in
  sorted_sids

let students = [1;2;3;4;5;6]
let courses = [12;13;14;15;16;17;18]

let _ = sort_students students courses

(* let _ = sort_students_efficient students courses *)