(***********************************************************************)
(*                                                                     *)
(*                           Objective Caml                            *)
(*                                                                     *)
(*               Pierre Weis, projet Cristal, INRIA Rocquencourt       *)
(*                                                                     *)
(*  Copyright 2001 Institut National de Recherche en Informatique et   *)
(*  en Automatique.  All rights reserved.  This file is distributed    *)
(*  only by permission.                                                *)
(*                                                                     *)
(***********************************************************************)
type état =
  { mutable dtransitions : transition array;
    dterminal : bool }
and transition =
  | Vers of état
  | Rejet;;

exception Échec;;

let reconnaît automate chaîne =
  let état_courant = ref automate in 
  try
    for i = 0 to String.length chaîne - 1 do
    match !état_courant.dtransitions.(int_of_char chaîne.[i]) with
    | Rejet  -> raise Échec
    | Vers e -> état_courant := e
    done;
    !état_courant.dterminal
  with Échec -> false;;

open Auto;;

type ensemble_d'états =
  { contenu  : Ensent.t;
    éléments : Auto.état list };;

let vide = { contenu = Ensent.vide; éléments = [] };;

let est_vide ens =
  match ens.éléments with [] -> true | _ -> false;;

let appartient état ens =
  Ensent.appartient état.numéro ens.contenu;;

let ajoute état ens =
  { contenu  = Ensent.ajoute état.numéro ens.contenu;
    éléments = état :: ens.éléments };;

let rec ajoute_fermeture état ferm =
  if appartient état ferm then ferm else
    List.fold_right ajoute_fermeture
      état.epsilon_transitions (ajoute état ferm);;

let fermeture état = ajoute_fermeture état vide;;

let fermeture_ens ens = List.fold_right ajoute_fermeture ens.éléments vide;;

let déplacements liste_états =
  let t = Array.make 256 vide in
  List.iter
    (function état ->
      List.iter
        (function (car, dest) ->
          let i = int_of_char car in t.(i) <- ajoute dest t.(i))
      état.transitions)
    liste_états;
  t;;

let déterminise état_initial =
  let états_connus = Hashtbl.create 51
  and à_remplir = Stack.create () in
  let traduire ens =
    try Hashtbl.find états_connus ens.contenu
    with Not_found ->
      let nouvel_état =
        { dterminal = List.exists (function n -> n.terminal) ens.éléments;
          dtransitions = Array.make 256 Rejet } in
      Hashtbl.add états_connus ens.contenu nouvel_état;
      Stack.push (ens.éléments, nouvel_état) à_remplir;
      nouvel_état in
  let nouvel_état_initial =
    traduire (fermeture état_initial) in
  begin try
    while true do
      let (liste, nouvel_état) = Stack.pop à_remplir in
      let dépl = déplacements liste in
      for i = 0 to 255 do
        if not (est_vide dépl.(i)) then
          nouvel_état.dtransitions.(i) <-
            Vers(traduire (fermeture_ens dépl.(i)))
      done
    done
  with Stack.Empty -> ()
  end;
  nouvel_état_initial;;