module Make = functor (K : Set.OrderedType) ->
struct
type key = K.t
module M = Map.Make(K)
type 'a t =
{ value : 'a option;
sons : ('a t) M.t
}
let empty = { value = None; sons = M.empty }
let rec add key_lst value trie =
match key_lst with
| [] -> { trie with value = Some value }
| key::key_lst ->
let sub_trie =
if M.mem key trie.sons then M.find key trie.sons
else empty
in
{ trie with sons = M.add key (add key_lst value sub_trie) trie.sons }
let rec mem key_lst trie =
match key_lst with
| [] -> trie.value <> None
| key::key_lst -> M.mem key trie.sons && (mem key_lst (M.find key trie.sons))
let rec find key_lst trie =
match key_lst, trie.value with
| [], Some value -> value
| [], None -> failwith "Not found"
| key::key_lst, _ ->
if M.mem key trie.sons then find key_lst (M.find key trie.sons)
else failwith "Not found"
let rec longest stream trie =
if Stream_lzw.is_empty stream then
if trie.value = None then None else Some ([],stream)
else
let (key,str) = Stream_lzw.read stream in
let longest_tail =
if M.mem key trie.sons then longest str (M.find key trie.sons)
else None
in
match longest_tail, trie.value with
| Some (l1,stream), _ -> Some (key::l1,stream)
| None, None -> None
| None, Some _ -> Some ([],stream)
let rec fold f trie init =
let updated_value =
match trie.value with
| Some value -> f [] value init
| None -> init
in
M.fold
(fun key trie value -> fold (fun kl b v -> f (key::kl) b v) trie value)
trie.sons
updated_value
end
