(**************************************************************************)
(*                                                                        *)
(*  Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre,       *)
(*  Kim Nguyen, Laurent Sartre                                            *)
(*                                                                        *)
(*  Informatique - MP2I/MPI - CPGE 1re et 2e années.                      *)
(*  Cours et exercices corrigés. Éditions Ellipses, 2022.                 *)
(*                                                                        *)
(*  https://www.informatique-mpi.fr/                                      *)
(*                                                                        *)
(**************************************************************************)

(* Arbres préfixes (trie)

   réalisant ici des tableaux associatifs mutables dont les clés sont
   des chaînes.

   Cf lzw.ml pour une application. *)

type 'a trie = {
  mutable value: 'a option;
       branches: (char, 'a trie) Hashtbl.t;
}

val create: unit -> 'a trie

val is_empty: 'a trie -> bool

val contains: 'a trie -> string -> bool

val get: 'a trie -> string -> 'a

val put: 'a trie -> string -> 'a -> unit

val remove: 'a trie -> string -> unit

val prefix: 'a trie -> string -> int * 'a
(** `prefix t s` est la longueur du plus grand préfixe de `s` qui est une clé
    dans `t`, et la valeur associée ;
    lève `Not_found` si aucun préfixe de `s` n'est dans `t` *)

val prefix_sub: 'a trie -> string -> int -> int * 'a
(** `prefix t s i` est la longueur du plus grand préfixe de `s[i..[`
    qui est une clé dans `t`, et la valeur associée ;
    lève `Not_found` si aucun préfixe de `s[i..[` n'est dans `t` *)

val pattern: 'a trie -> ?wildcard:char -> string -> (string * 'a) list
(** Toutes les entrées correspond à un motif donné, où le caractère
    `wildcard` est le motif universel (par défaut '_').
    Ainsi, `pattern t "a___a"` renvoie toutes les entrées de 5 lettres
    commençant et se terminant par 'a'. *)

val below: (string -> 'a -> unit) -> 'a trie -> string -> unit
(**  `below f t s` parcourt toutes les entrées pour un préfixe `s` donné *)

val iter: (string -> 'a -> unit) -> 'a trie -> unit
(** parcourt toutes les entrées *)