(* 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:  s 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 "arrayInsertionSort";
	     data must be one of "sorted", "inverted", 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(arrayInsertionSort 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 = "inverted") 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 = "inverted") then
		    inputValues(numOfElms,
				b(List.tabulate (numOfElms, fn num => numOfElms - num)), stream)
		else raise Error ("wrong kind of structure")
	    else if (func = "arrayInsertionSort") 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 = "inverted") 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 "arrayInsertionSort";
	     data must be one of "sorted", "inverted", 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
	       lmsI.txt  -- List merge sort with inverse sorted input
	       lmsR.txt  -- List merge sort with random input
	       lmsOS.txt -- Optimised list merge sort with sorted input
	       lmsOI.txt -- Optimised list merge sort with inverse sorted input
	       lmsOR.txt -- Optimised list merge sort with random input
	       aisS.txt  -- Array insertion sort with sorted input
	       aisI.txt  -- Array insertion sort with inverse sorted input
	       aisR.txt  -- Array insertion sort with random input
    *)
    fun go () =
	(main("listMergeSort", (1000,10000), 10, "sorted", "lmsS.txt");
	 main("listMergeSort", (1000,10000), 10, "inverted", "lmsI.txt");
	 main("listMergeSort", (1000,10000), 10, "random", "lmsR.txt");

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

	 main("arrayInsertionSort", (1000,10000), 10, "sorted", "aisS.txt");
	 main("arrayInsertionSort", (1000,10000), 10, "inverted", "aisI.txt");
	 main("arrayInsertionSort", (1000,10000), 10, "random", "aisR.txt"))
end