(*
*************
2/6/2007
csci5161
*)

(* Problem 3 Step 1 *)
signature BTREE =
sig
 type item
 datatype btree = E of unit | N of item * btree * btree

 val initTree : unit -> btree
 val insert : btree * item -> btree
 val find : btree * item -> bool
 val print : btree -> unit
end

(* Problem 3 Step 2 *)
signature ITEM =
sig
 type item
 val leq : item * item -> bool
 val eq : item * item -> bool
 val toString : item -> string
end

(* Problem 3 Step 3 *)
functor BTree(
 structure Item: ITEM): BTREE =
 struct
  type item = Item.item
  datatype btree = E of unit | N of item * btree * btree

  fun initTree() = E()

  fun insert (E(),value) = N(value, E(), E())
    | insert (N(v,l,r), value) =
	if Item.leq(value,v) = true then N(v,insert(l,value),r)
	else N(v,l,insert(r, value))

  fun find (E(), value) = false
    | find (N(v,l,r), value) =
	if Item.eq(value, v) = true then true
	else if Item.leq(value, v) = true then find(l, value)
	     else find(r, value)

  fun print (E()) = ()
    | print (N(v,l,r)) = (print(l); TextIO.print(Item.toString(v)^" "); print(r))

 end

(* Problem 3 Step 4 *)
structure IntItem: ITEM =
 struct
  type item = int 

  fun leq(v1,v2) = v1 <= v2
  fun eq(v1,v2) = v1 = v2
  fun toString(v) = Int.toString(v)

 end

structure StringItem: ITEM =
 struct
  type item = string 

  fun leq(v1,v2) = 
	if String.compare(v1,v2) = GREATER then false
	else true

  fun eq(v1,v2) = 
	if String.compare(v1,v2) = EQUAL then true
	else false

  fun toString(v) = v

 end

(* Problem 3 Step 5 *)

structure IntBTree = BTree(structure Item = IntItem)
structure StringBTree = BTree(structure Item = StringItem)

(* some test code *)
val tree1 = IntBTree.insert (IntBTree.insert (IntBTree.insert (IntBTree.insert (IntBTree.initTree(), 53), 2), 8), 31);
val test1 = IntBTree.find(tree1,2);
IntBTree.print(tree1);

val tree2 = StringBTree.insert (StringBTree.insert (StringBTree.insert (StringBTree.insert (StringBTree.initTree(), "hi"), "testing"), "ajs"), "5161!!");
val test2 = StringBTree.find(tree2, "ajs");
StringBTree.print(tree2);