module type ordered type =
    sig
      
      type t
	     
      val compare : t -> t -> int
				
    end

module type S =
  sig
    
    type elt
	   
    val empty : t
		  
    val is_empty : bool
		     
    val add : elt -> t -> t
			    
    val mem : elt -> t -> bool
			    
    val remove : elt -> t -> t
			       
    val fold : (elt -> 'a -> 'a) -> t -> elt -> 'a
						  
    val union : t -> t -> t
			    
    val inter : t -> t -> t
			    
  end

module type Word =
  sig

    module Letter : OrderedType

    type word

    val empty : word

    val is_empty : word -> bool

    val add_end : word -> Letter.t -> word

    val pop : word -> Letter.t * word

  end
    
module type Chose =
  functor (X:Word) ->
  sig
    
    module EltMap = Map.Make(X.letter)
			    
    type t = T of (bool * t EltMap)
		    
    let empty = T (false, EltMap.empty)
		  
    let is_empty T(b,m) = (not b) && EltMap.empty m
						  
    exception Already_in

    let rec addaux w (T(b,m)) = if X.is_empty w then if b then raise Already_in
				else let c,w' = X.pop in
				     let t'   = try EltMap.find c m
					      with not_found -> empty in
				     let t''  = add w' t' in
				     let m'   = EltMap.add c t'' m in
				     T(b,m')

    let add w t = try add_aux w t with Already_in -> t

    let rec mem_aux w (T(b,m)) = if X.is_empty w then b
				 else let x,w' = X.pop w in
				      let t'   = EltMap.find c m in
				      mem_aux t'

    let mem w t = try mem_aux w t with not_foun -> false

    exception Empty

    let remove_aux w (T(b,m)) = if X.is_empty w then if b
				then if EltMap.is_empty m
				then raise Empty
			        else raise Not-found  
						     else let c,w' =  X.pop w in
							  let m = 
						 
    let remove w t = try remove_aux w t with not_found -> t
					   | Empty     -> empty


						       

  end