(* Carsten Schuermann *)
(* Modules *)

signature DICT = 
  sig
    type 'a dict
      
    val empty : 'a dict
    val insert : 'a dict * (string * 'a) -> 'a dict 
  end


structure Dict : DICT =
  struct
    datatype 'a dict 
      = Empty
      | Node of 'a dict * (string * 'a) * 'a dict
      
    val empty = Empty
    fun insert (Empty, (k, x)) = Node (Empty, (k, x), Empty)
      | insert (Node (left, (k', y), right), (k, x)) = 
        if k' = k then Node (left, (k, x), right)
	else if k' < k then Node (insert (left, (k, x)), (k', y), right)
	     else Node (left, (k', y), insert (right, (k, x)))
  end


signature DICT = 
   sig
    type key
    type 'a dict
      
    val empty : 'a dict
    val insert : 'a dict * (key * 'a) -> 'a dict 
    val lookup : 'a dict * key -> 'a option
  end

datatype Order = LT | EQ | GT

functor Dict (type key
	      val compare : key * key -> Order) : DICT =
  struct
    type key =key 
    datatype 'a dict 
      = Empty
      | Node of 'a dict * (key * 'a) * 'a dict
      
    val empty = Empty
    fun insert (Empty, (k, x)) = Node (Empty, (k, x), Empty)
      | insert (Node (left, (k', y), right), (k, x)) = 
        (case (compare (k, k')) 
	   of EQ =>  Node (left, (k, x), right)
	    | LT => Node (insert (left, (k, x)), (k', y), right)
	    | GT => Node (left, (k', y), insert (right, (k, x))))

    fun lookup ( Empty, k) = NONE
      | lookup (Node (l, (k, x), r), k') = 
        (case (compare (k, k')) of
	   EQ => SOME x
	 | LT => lookup (l, k')
	 | GT => lookup (r, k'))
   
  end

structure StringDict = Dict (type key = string
			     val compare = fn (k1, k2) => if k1 = k2 then EQ 
							  else if String.<(k1, k2) then LT 
							       else GT)


structure IntDict = Dict (type key = int
			  val compare = fn (k1, k2) => if k1 = k2 then EQ 
						       else if Int.<(k1, k2) then LT 
							    else GT)