(***********************************************************************)
(*                                                                     *)
(*                                 GALAX                               *)
(*                            XML Query Engine                         *)
(*                                                                     *)
(*  Copyright 2001, Lucent Technologies.                               *)
(*  Distributed only by permission.                                    *)
(*                                                                     *)
(***********************************************************************)

(* TypeName_DFA has four modules:  StateSet, Alphabet, StateToTransitionMap, TransitionMap *)
(* StateSet and Alphabet are ocaml Sets *)
(* StateToTransitionMap and TransitionMap are ocaml Map *)
(* The type dfa is a 5-tuple *)
(*      type dfa =
	  {
	  mutable dfa_states : StateSet.t;
	  mutable dfa_alphabet : Alphabet.t;
	  mutable dfa_start_state : StateSet.elt option;
	  mutable dfa_final_states : StateSet.t;
	  mutable dfa_transitions :
            Fsa.State.t TransitionMap.t StateToTransitionMap.t;
	} 
*)

module TypeName_DFA :
    sig
      module StateSet : (Set.S with type elt = Fsa.State.t
                                and type t = Set.Make(Fsa.State).t)
      module Alphabet : (Set.S with type elt = Fsa.OrderedTypeNames.t
                                and type t = Set.Make(Fsa.OrderedTypeNames).t)
      module StateToTransitionMap : (Map.S with type key = Fsa.State.t)
      module TransitionMap : (Map.S with type key = Fsa.OrderedTypeNames.t)

      type dfa =
	  {
	  mutable dfa_states : StateSet.t;
	  mutable dfa_alphabet : Alphabet.t;
	  mutable dfa_start_state : StateSet.elt option;
	  mutable dfa_final_states : StateSet.t;
	  mutable dfa_transitions :
            Fsa.State.t TransitionMap.t StateToTransitionMap.t;
	} 

      val dfa_empty : dfa
      val fresh_dfa_empty : unit -> dfa

      val get_dfa_alphabet : dfa -> Alphabet.t
      val add_letter : dfa -> Alphabet.elt -> unit
      val add_all_letters : dfa -> Alphabet.t -> unit

      val get_dfa_states : dfa -> StateSet.t
      val get_dfa_start_state : dfa -> StateSet.elt option
      val get_dfa_final_states : dfa -> StateSet.t

      val add_state : dfa -> StateSet.elt -> unit
      val set_start_state : dfa -> StateSet.elt -> unit
      val set_final_states : dfa -> StateSet.t -> unit

      val get_dfa_transitions :
	  dfa -> Fsa.State.t TransitionMap.t StateToTransitionMap.t
      val get_TransitionMap :
	  dfa -> StateToTransitionMap.key -> Fsa.State.t TransitionMap.t
      val get_destStateSet :
	  StateSet.elt TransitionMap.t -> TransitionMap.key -> StateSet.t
      val get_destStateSet_s :
	  dfa -> StateToTransitionMap.key -> TransitionMap.key -> StateSet.t

      val add_transitions_aux :
	  dfa -> StateToTransitionMap.key -> Alphabet.elt * StateSet.elt -> unit
      val add_transitions :
	  dfa -> StateSet.elt -> (Alphabet.elt * StateSet.elt) list -> unit
      val negates : dfa -> dfa

      val print_automata :
	  dfa -> (Alphabet.elt -> 'a) -> (StateSet.elt -> 'b) -> unit
    end

(* same as TypeName_DFA EXCEPT the StateSet module has elt Fsa.StatePair*)    
module TypeName_DFA_Pair :
    sig
      module StateSet : (Set.S with type elt = Fsa.StatePair.t
                                and type t = Set.Make(Fsa.StatePair).t)
      module Alphabet : (Set.S with type elt = Fsa.OrderedTypeNames.t
                                and type t = Set.Make(Fsa.OrderedTypeNames).t)
      module StateToTransitionMap : (Map.S with type key = Fsa.StatePair.t)
      module TransitionMap : (Map.S with type key = Fsa.OrderedTypeNames.t)

      type dfa =
	  { mutable dfa_states : StateSet.t;
	    mutable dfa_alphabet : Alphabet.t;
	    mutable dfa_start_state : StateSet.elt option;
	    mutable dfa_final_states : StateSet.t;
	    mutable dfa_transitions :
	      Fsa.StatePair.t TransitionMap.t StateToTransitionMap.t } 

      val dfa_empty : dfa
      val fresh_dfa_empty : unit -> dfa

      val get_dfa_alphabet : dfa -> Alphabet.t
      val add_letter : dfa -> Alphabet.elt -> unit
      val add_all_letters : dfa -> Alphabet.t -> unit

      val get_dfa_states : dfa -> StateSet.t
      val get_dfa_start_state : dfa -> StateSet.elt option
      val get_dfa_final_states : dfa -> StateSet.t

      val add_state : dfa -> StateSet.elt -> unit
      val set_start_state : dfa -> StateSet.elt -> unit
      val set_final_states : dfa -> StateSet.t -> unit

      val get_dfa_transitions :
	  dfa -> Fsa.StatePair.t TransitionMap.t StateToTransitionMap.t
      val get_TransitionMap :
	  dfa -> StateToTransitionMap.key -> Fsa.StatePair.t TransitionMap.t
      val get_destStateSet :
	  StateSet.elt TransitionMap.t -> TransitionMap.key -> StateSet.t

      val get_destStateSet_s :
	      dfa -> StateToTransitionMap.key -> TransitionMap.key -> StateSet.t
      val add_transitions_aux :
	  dfa -> StateToTransitionMap.key -> Alphabet.elt * StateSet.elt -> unit
      val add_transitions :
	  dfa -> StateSet.elt -> (Alphabet.elt * StateSet.elt) list -> unit
      val negates : dfa -> dfa

      val print_automata :
	  dfa -> (Alphabet.elt -> 'a) -> (StateSet.elt -> 'b) -> unit
    end
    
val negates_in_alphabet_space : TypeName_DFA.dfa -> TypeName_DFA.Alphabet.t -> TypeName_DFA.dfa

