(* functor for binary search trees *)

(* based on examples from Ullman's book, chapter 8 *)

(* define a signature for the functor's parameter, i.e. satisfied only
by structures that are suitable as functor inputs *)

signature TOTALORDER = sig
	  type element;
	  val lt : element * element -> bool
end;

(* define a functor that takes a structure and produces a structure as
a result *)

functor MakeBST(Lt: TOTALORDER):
   sig
	type 'label btree;
	exception EmptyTree;
	val create : Lt.element btree;
	val lookup : Lt.element * Lt.element btree -> bool;
	val insert : Lt.element * Lt.element btree -> Lt.element btree;
	val deletemin : Lt.element btree -> Lt.element *Lt.element btree;
	val delete : Lt.element *Lt.element btree -> Lt.element btree
   end
=
struct
open Lt;
   
datatype 'label btree =
	 Empty |
	 Node of 'label * 'label btree * 'label btree;

val create = Empty;

fun lookup(x, Empty) = false
|   lookup(x, Node(y, left, right)) =
    if lt(x,y) then lookup(x, left)
    else if lt(y,x) then lookup(x, right)
    else (* x=y *) true;

fun insert(x, Empty) = Node(x, Empty, Empty)
|   insert(x, T as Node(y,left,right)) =
	if lt(x, y) then Node(y, insert(x, left), right)
	else if lt(y, x) then Node(y, left, insert(x, right))
	else (* x=y *) T;  (* do nothing; x was already there *)

exception EmptyTree;

fun deletemin(Empty) = raise EmptyTree
|   deletemin(Node(y, Empty, right)) = (y,right)
    (* The critical case.  if the left subtree is empty, then the
    element at the current node is min. *)
|   deletemin(Node(w, left, right)) =
        let val (y, L) = deletemin(left)
	in (y, Node(w, L, right))
	end;

fun delete(x, Empty) = Empty
|   delete(x, Node(y, left, right)) =
    if lt(x, y) then Node(y, delete(x,left), right)
    else if lt(y, x) then Node(y, left, delete(x, right))
    else (* x=y *)
	 case (left, right) of
	      (Empty, r) => r |
	      (l, Empty) => l |
	      (l, r) => let val(z, r1) = deletemin(r)
			in Node(z, l, r1)
			end;
end;

(* from Figure 8.8 *)

(* define a "functor input" structure with a signature that matches *)

structure String: TOTALORDER = struct
    type element = string;
    fun lt(x, y) =
	let 
	    fun lower(nil) = nil
	    |   lower(c::cs) = (Char.toLower c)::lower(cs);
	in implode(lower(explode(x))) < implode(lower(explode(y)))
    end;
end;

(* apply the functor to that structure to produce the desired
structure *)

structure StringBST = MakeBST(String);

(* test it out a little *)

open StringBST;
val t1 = create;
val t2 = insert("foo", t1);
val t3 = insert("bar", t2);
lookup("bar", t3);
val t4 = delete("baz", t3);



</code>