(* Code to help with the evaluation of sorting algorithms *)
(* Based on source code by Simon Moritz *)

(* The definition of the function timeIt is copied from ranTime.sml *)

(* For interactive sessions *)
load "Timer"; load "Time"; load "Random";

local
    open Timer;
    open Time;
in
    (*
       function timeIt f arg
       TYPE: ('a -> 'b) -> 'a -> real
       PRE:  (none)
       POST: the time, in seconds, for executing f(arg)
    *)
    fun timeIt f arg =
	let
	    val t = startCPUTimer()
	    val _ = f arg
	    val t' = checkCPUTimer(t)
	in
	    toReal (#usr(t'))
	end;
end;

local
    exception Error of string;
    (*
       function inputValues(x, num, s)
       TYPE: int *  real * stream -> unit
       PRE:  stream must be open for output
       POST: ()
       SE:   prints a line with x followed by num on s
    *)
    fun inputValues (x, num, s) =
	TextIO.output(s, Int.toString(x) ^ " " ^ Real.toString(num) ^"\n")

    (*
       function functionChooser(func, numOfElms, data, stream)
       TYPE: string * int * string * stream -> unit
       PRE:  stream must be open for output;
             func must be one of "listMergeSort", "listOptMergeSort",
	          and "arrayMergeSort";
	     data must be one of "sorted", "converted", and "random"
       POST: ()
       SE:   selects a sorting function (depending on the value of func)
             and a kind of input data (depending on the value of data),
             creates an array or list of length numOfElms,
	     runs that sorting function on this array or list, and
	     writes numOfElms and the time taken (in seconds) to stream
    *)
    fun functionChooser(func, numOfElms, str, stream) =
	let val a = timeIt(listMergeSort op<)
	    val b = timeIt(listOptMergeSort op<)
	    val c = timeIt(arrayMergeSort op<)
	in
	    if (func = "listMergeSort") then
		if (str = "random") then
		    inputValues (numOfElms,
				 a(Random.rangelist(0, 10000) (numOfElms, Random.newgen())), stream)
		else if (str = "sorted") then
		    inputValues(numOfElms,
				a(List.tabulate (numOfElms, fn num => num)), stream)
		else if (str = "converted") then
		    inputValues(numOfElms,
				a(List.tabulate (numOfElms, fn num => numOfElms - num)), stream)
		else raise Error ("wrong kind of structure")
	    else if (func = "listOptMergeSort") then
		if (str = "random") then
		    inputValues(numOfElms,
				b(Random.rangelist(0, 10000) (numOfElms, Random.newgen())), stream)
		else if (str = "sorted") then
		    inputValues(numOfElms,
				b(List.tabulate (numOfElms, fn num => num)), stream)
		else if (str = "converted") then
		    inputValues(numOfElms,
				b(List.tabulate (numOfElms, fn num => numOfElms - num)), stream)
		else raise Error ("wrong kind of structure")
	    else if (func = "arrayMergeSort") then
		if (str = "random") then
		    inputValues (numOfElms,
				 c(Array.fromList (Random.rangelist (0, 10000) (numOfElms, Random.newgen()))), stream)
		else if (str = "sorted") then
		    inputValues(numOfElms,
				c(Array.tabulate (numOfElms, fn num => num)), stream)
		else if (str = "converted") then
		    inputValues(numOfElms,
				c(Array.tabulate (numOfElms, fn num => numOfElms - num)), stream)
		else raise Error ("wrong kind of structure")
	    else raise Error ("wrong kind of function")
	end

    (*
       function main(func, (start, finish), n, data, f)
       TYPE: string * (int * int) * int * string * string -> unit
       PRE:  n > 1;
	     start < finish;
             func must be one of "listMergeSort", "listOptMergeSort",
	          and "arrayMergeSort";
	     data must be one of "sorted", "converted", and "random"
       POST: ()
       SE:   selects a sorting function (depending on the value of func)
             and a kind of input data (depending on the value of data),
             runs that sorting function on lists or arrays of input data
	     of n different lengths, ranging from start to finish, and
	     writes the lengths and times taken (in seconds) to
             a file named by f
    *)
    fun main(func, (start, finish), n, data, f) =
	let val () = print ("Processing "^f^"\n");
	    val step = (finish - start) div (n - 1)
	    val s = TextIO.openOut(f);
            (*
               function tableMaker(start)
               TYPE: int -> unit
               PRE:  (none)
               POST: ()
               SE:   selects a sorting function (depending on func)
                     and a kind of input data (depending on data),
                     runs that function on lists or arrays of input data
		     of lengths start, start+step, ..., finish, and
                     writes the lengths and times taken on output stream s
               VARIANT: finish - start
            *)
	    fun tableMaker( start ) =
		if (start > finish) then ()
		else (functionChooser (func, start, data, s);
		      tableMaker( start + step ))
	in
	    tableMaker( start );
	    TextIO.closeOut(s)
	end
in
     (*
        function go ()
        TYPE: unit -> unit
        PRE:  (none)
        POST: ()
        SE:   runs the three sorting functions on the three kinds of input data
              and writes the lengths and times taken to nine files:
 	       lmsS.txt  -- List merge sort with sorted input
	       lmsC.txt  -- List merge sort with reverse sorted input
	       lmsR.txt  -- List merge sort with random input
	       lmsOS.txt -- Optimised list merge sort with sorted input
	       lmsOC.txt -- Optimised list merge sort with reverse sorted input
	       lmsOR.txt -- Optimised list merge sort with random input
	       amsS.txt  -- Array merge sort with sorted input
	       amsC.txt  -- Array merge sort with reverse sorted input
	       amsR.txt  -- Array merge sort with random input
    *)
    fun go () =
	(main("listMergeSort", (1000,10000), 10, "sorted", "lmsS.txt");
	 main("listMergeSort", (1000,10000), 10, "converted", "lmsC.txt");
	 main("listMergeSort", (1000,10000), 10, "random", "lmsR.txt");

	 main("listOptMergeSort", (1000,10000), 10, "sorted", "lmsOS.txt");
	 main("listOptMergeSort", (1000,10000), 10, "converted", "lmsOC.txt");
	 main("listOptMergeSort", (1000,10000), 10, "random", "lmsOR.txt");

	 main("arrayMergeSort", (1000,10000), 10, "sorted", "amsS.txt");
	 main("arrayMergeSort", (1000,10000), 10, "converted", "amsC.txt");
	 main("arrayMergeSort", (1000,10000), 10, "random", "amsR.txt"))
end