(* COMP 302 Homework 3
   Instructors: Francisco Ferreira, Andrew Cave
   Due: Monday Feb 18th, 2:35pm (BEGINNING OF CLASS)
*)

(* Question 1: Continuations and Tries *)

datatype 'a trie = Node of 'a * ('a trie) list | Empty;

type dict = (char trie) list

val empty = []

exception notImplemented 
(* -------------------------------------------------------------*)
(* QUESTION 1.1 : Insert a string into a trie  [20 points]      *)
(* -------------------------------------------------------------*)

(* Insert a word in a dictionary *)
(* Duplicate inserts are allowed *)

(* ins: char list * (char trie) list -> (char trie) list *)
fun ins ([], []) = [Empty]
  | ins ([], (t::ts)) = t::(ins ([], ts))
  | ins (c::cs, []) = [Node (c, ins (cs, []))]
  | ins (c::cs, Empty::t) = Empty::(ins (c::cs, t))
  | ins (c::cs, (Node (c',ts))::t) = if c = c' then (Node (c',ins (cs, ts)))::t
                                     else (Node (c',ts))::(ins (c::cs, t))
 
(* insert : string * (char trie) list -> (char trie) list *)
fun insert(s, t) = 
  let
    val l = String.explode s  (* turns a string into a char list *)
  in
    ins(l,t) 
    handle notImplemented => (print "Note: Insertion into a trie is not (yet) implemented.\n";empty)
  end 

(* -------------------------------------------------------------*)
(* QUESTION 1.2 : Find all words in the trie                    *) 
(* -------------------------------------------------------------*)
(* Find all words in the trie using continuations               *)

fun words_in_trie Empty cont = cont [[]]
  | words_in_trie (Node (c, ts)) cont = all_words ts (fn r => cont (map (fn w => c::w) r))
and all_words [] cont = cont []
  | all_words (t::ts) cont = words_in_trie t (fn r1 => all_words ts (fn r2 => cont (r1 @ r2)))

fun all_entries t = 
  all_words t (fn l => map (fn w => String.implode w) l)
  handle notImplemented => 
    (print "Note: Retrieving all words in a trie is not (yet) implemented.\n"; [])


(* See hw3q2.sml for the Question 2 template *)

(* -------------------------------------------------------------*)
(* QUESTION 3: References                                       *)
(* -------------------------------------------------------------*)

(* count how often we access a given reference 
   returns 3 things: 
     
      accepts some inital value
     1 counter for accessing the cell
     2 a function for reading
     3 a function for writing
*)

fun monRef i =
  let val x = ref i
      val cnt = ref 0
      fun read () = (cnt := !cnt + 1; !x)
      fun write y = (cnt := !cnt + 1; x := y)
  in
    (cnt,read,write)
  end

fun imperative_fact (n:int) =
    let
        val result = ref 1
        val i = ref 0
    in
       while (not (!i = n)) do
	 ( i := !i +1;
	   result := !result * !i);
	   !result
    end

(* monitored factorial version *)

fun mon_fact (n:int) =
    let val (result_cnt, result_read, result_write) = monRef 1
        val (i_cnt, i_read, i_write) = monRef 0
    in
       while (not (i_read () = n)) do
          ( i_write ((i_read ()) + 1);
            result_write ((result_read ()) * (i_read ())));
       (result_read (), !result_cnt + !i_cnt)
    end