module Charmap =
  Map.Make
    (struct
      type t = char
      let compare : char -> char -> int = compare
    end);;

type 'a t = 'a node Charmap.t
and 'a node = {
    info : 'a option;
    suffixes : 'a t; 
  } 


let empty = Charmap.empty

let find_largest_prefix key dict =
  let len1 = String.length key -1 in
  let rec search offset dict res =
    if offset > len1 then res
    else
      try
        let node = Charmap.find key.[offset] dict in
        let res = match node.info with Some _ as res -> res | _ -> res in
        search (offset + 1) node.suffixes res
      with
        Not_found -> res in
  match search 0 dict None with
    Some r -> r 
  | None -> raise Not_found
  ;;

(* Return a new dictionary that extend the old one with a new binding.
   Does not modify the old dictionnary. *)

let none = { info = None; suffixes = empty; }

let add key v dict =
  let len1 = String.length key -1 in
  let rec add offset dict =
    if offset > len1 then dict (* we are adding the empty word to dict *)
    else
      let node =
        try Charmap.find key.[offset] dict with Not_found -> none in
      Charmap.add key.[offset]
        { info = if offset < len1 then node.info else Some v;
          suffixes = add (offset + 1) node.suffixes; }
        dict
  in
  add 0 dict;;

let remove (key : string) (dict : 'a t) : 'a t = assert false;;

let rec iter f dict =
  let do_node key node =
    begin match node.info with Some d -> f d | None -> () end;
    iter node.suffixes in
  Charmap.iter do_node;;
    
          
let fold f d a = assert false;;