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

(* $Id: fsa.mli,v 1.2 2001/12/14 19:06:03 simeon Exp $ *)

open Printf
open Error

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

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

module OrderedTypeNames :
    sig
      type t = Sym.rgroup_symbol
      val compare : t -> t -> int
    end

(* TypeName_NFA has four modules:  StateSet, Alphabet, StateToTransitionMap, TransitionMap *)
(* StateSet and Alphabet are ocaml Sets *)
(* StateToTransitionMap and TransitionMap are ocaml Map *)
(* The type nfa is a 5-tuple *)
(*     type nfa = {
	mutable nfa_states : StateSet.t;
	mutable nfa_alphabet : Alphabet.t;
	mutable nfa_start_state : StateSet.elt option;
	mutable nfa_final_states : StateSet.t;
	mutable nfa_transitions :
          StateSet.t TransitionMap.t StateToTransitionMap.t;
      } 
*)
module TypeName_NFA :
  sig
    module StateSet : (Set.S with type elt = State.t
                              and type t = Set.Make(State).t)
    module Alphabet : (Set.S with type elt = OrderedTypeNames.t
                              and type t = Set.Make(OrderedTypeNames).t)
    module StateToTransitionMap : (Map.S with type key = State.t)
    module TransitionMap : (Map.S with type key = OrderedTypeNames.t)

    type nfa = {
	mutable nfa_states : StateSet.t;
	mutable nfa_alphabet : Alphabet.t;
	mutable nfa_start_state : StateSet.elt option;
	mutable nfa_final_states : StateSet.t;
	mutable nfa_transitions :
          StateSet.t TransitionMap.t StateToTransitionMap.t;
      }

    val nfa_empty : nfa

    val fresh_nfa_empty : unit -> nfa

    (* accessor, construction function of alphabet for an automata *)

    val get_nfa_alphabet : nfa -> Alphabet.t
    val add_letter : nfa -> Alphabet.elt -> unit
    val add_all_letters : nfa -> Alphabet.t -> unit

    (* accessor, construction function of state for an automata *)

    val get_nfa_states : nfa -> StateSet.t
    val get_nfa_start_state : nfa -> StateSet.elt option
    val get_nfa_final_states : nfa -> StateSet.t

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

    (* accessor, construction function of transition for an automata*)

    val get_nfa_transitions : nfa -> StateSet.t TransitionMap.t StateToTransitionMap.t
 
    val get_TransitionMap :
	nfa -> StateToTransitionMap.key -> StateSet.t TransitionMap.t
    val get_destStateSet : 'a TransitionMap.t -> TransitionMap.key -> 'a
    val get_destStateSet_s :
	nfa -> StateToTransitionMap.key -> TransitionMap.key -> StateSet.t

    (* construction of transitions for an automata. *)
    (* this uses some of the accessor functions *)

    val add_transitions_aux :
	nfa -> StateSet.elt -> TransitionMap.key * StateSet.elt -> unit
    val add_transitions :
	nfa -> StateSet.elt -> (TransitionMap.key * StateSet.elt) list -> unit

    val print_automata : nfa -> (Alphabet.elt -> unit) -> (StateSet.elt -> unit) -> unit
  end

(* same as TypeName_NFA EXCEPT the StateSet module has elt Fsa.StatePair*)    

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

      type nfa = {
	  mutable nfa_states : StateSet.t;
	  mutable nfa_alphabet : Alphabet.t;
	  mutable nfa_start_state : StateSet.elt option;
	  mutable nfa_final_states : StateSet.t;
	  mutable nfa_transitions :
            StateSet.t TransitionMap.t StateToTransitionMap.t;
	} 

      val nfa_empty : nfa
	  
      val fresh_nfa_empty : unit -> nfa
	  
    (* accessor, construction function of alphabet for an automata*)

      val get_nfa_alphabet : nfa -> Alphabet.t
      val add_letter : nfa -> Alphabet.elt -> unit
      val add_all_letters : nfa -> Alphabet.t -> unit
	  
    (* accessor, construction function of state for an automata*)

      val get_nfa_states : nfa -> StateSet.t
      val get_nfa_start_state : nfa -> StateSet.elt option
      val get_nfa_final_states : nfa -> StateSet.t
	  
      val add_state : nfa -> StateSet.elt -> unit
      val set_start_state : nfa -> StateSet.elt -> unit
      val set_final_states : nfa -> StateSet.t -> unit
	  
    (* accessor, construction function of transition for an automata*)

      val get_nfa_transitions : nfa -> StateSet.t TransitionMap.t StateToTransitionMap.t
	  
      val get_TransitionMap :
	  nfa -> StateToTransitionMap.key -> StateSet.t TransitionMap.t
      val get_destStateSet : 'a TransitionMap.t -> TransitionMap.key -> 'a
      val get_destStateSet_s :
	  nfa -> StateToTransitionMap.key -> TransitionMap.key -> StateSet.t
	      
    (* construction of transitions for an automata. *)
    (* this uses some of the accessor functions *)

      val add_transitions_aux :
	  nfa -> StateSet.elt -> TransitionMap.key * StateSet.elt -> unit
      val add_transitions :
	  nfa -> StateSet.elt -> (TransitionMap.key * StateSet.elt) list -> unit
	      
      val print_automata : nfa -> (Alphabet.elt -> unit) -> (StateSet.elt -> unit) -> unit
    end

