(***********************************************************************)
(*                                                                     *)
(*                           Corrector                                 *)
(*                                                                     *)
(*       Damien Doligez and Francois Rouaix, INRIA Rocquencourt        *)
(*                                                                     *)
(*  Copyright 1997 Institut National de Recherche en Informatique et   *)
(*  Automatique.  Distributed only by permission.                      *)
(*                                                                     *)
(***********************************************************************)

(* The notion of word *)
module type Words = sig
  type t
  type letter				(* must support = *)
  val length : t -> int			(* length of word in letters *)
  val get : t -> int -> letter		(* nth letter of word starting at 0 *)
  val implode : letter list -> t	(* build word from letters *)

end

(* The dictionary as an automata *)
module type DictAutom = sig
  type t				(* a dictionary instance *)
  type state
  type label
  val initial : t -> state		(* initial state of automata *)
  val is_final : t -> state -> bool	(* check if state is final *)
  val transition : t -> state -> label -> state
    (* apply transition, raises Not_found if unavailable *)
  val transitions : t -> state -> label list
    (* list of available transitions in a given state *)
end  

module Make(W : Words)(D : DictAutom with type label = W.letter) : sig
   (* Cost parameters *)
   type costs = {
       tr : int;				(* transposition cost *)
       del : int;				(* delete cost *)
       ins : int;				(* insert cost *)
       subst : W.letter -> W.letter -> int;     (* param. substitution cost *)
       max : W.t -> int			        (* max authorized cost *)
       } 
   val default_costs : costs
   val suggest : D.t -> costs -> W.t -> (int * (W.t * int) list)
   val f : D.t -> costs -> W.t -> (int * (W.t * int) list)
 end