(* Cat Huston - s0346906 *)
(* Functional Programming and Specification - Practical 1, Exercise 2 *)




datatype element = Word of string | Index of int (* the bstw message is a list of elements, which can either be a Word (string) or an Index (int) *)




fun toWords msg = (* splits a string into a list of words *)
	let fun join w ws = if w = [] then ws else w::ws (* creates a join function to append words to the list *)
		fun toWords' [] acc = join acc [] (* base case for an empty message *)
			| toWords' (x::st) acc =
				if Char.isSpace x then join acc (toWords' st [] ) (* space indicates the end of a word *)
				(* deals with punctuation 
				else if Char.isPunct x then join acc (join [x] (toWords' st [])) (* punctuation indicates the end of a word *) *)
				else toWords' st (acc @ [x]) (* the end of the word hasn't been reached, continue until a space or punctuation is found *)
	in map implode (toWords' (explode msg) [])
end;




fun findIndex x ys = (* checks to see if the current word is in the compression table *) 
	let fun findIndex' x [] _ = NONE (* the end of the table is reached and word isn't there *)
	| findIndex' x (y::ys) i = 
	if x = y then SOME i (* the word is there - return the index *)
		else findIndex' x ys (i+1) (* try the next entry in the table *)
	in findIndex' x ys 0
end




fun compress [] table = [] (* compresses the list and replaces repeated words with their indexes *)
	| compress(word::words) table = 
		case findIndex word table of (* calls findIndex to see if the word has already been used *)
		NONE => Word word :: compress words (word :: table)
		| SOME i => let val head = if i = 0 then [] else List.take (table, (i-1)) val table' = word :: (head) @ (List.drop (table, i))
		in
			Index i :: compress words table'
		end;




fun uncompress table [] = [] (* replaces any index with the word *)
	| uncompress table (word::words) = 
		case word of 
		Word w => w :: uncompress (w :: table) words (* if it's a word, put it to the top of the table *)
		| Index i => let val head = if i = 0 then [] else List.take (table, (i-1)) (* can't do List.take on -1 *)
				val w = List.nth (table, i) (* gets the element at i *)
				val table' = w :: (head) @ (List.drop (table, i)) (* rearranges the table *)
			in
				w :: uncompress table' words
			end;




fun unWords [] = "" (* base case - empty string *)
	| unWords (m::ms) =
		(* deals with punctuation
		if Char.isPunct (List.hd (explode m)) then m ^ (unWords ms) (* doesn't leave a space before punctuation *)
				else *) " " ^ m ^ (unWords ms)




fun bstw msg = 
	compress (toWords msg) []




fun unbstw msg =
	if uncompress [] msg = [] then "" (* case for empty input *)
	else
		implode (List.tl (explode(unWords (uncompress [] msg))));
	(* unWords will always start with a space, the implode/List.tl/explode gets rid of it *)