1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
module Cmap = Map.Make(Char)
type 'a t = {
data : 'a option ;
next : 'a t Cmap.t ;
}
let rec dump fmt n =
begin
Format.fprintf fmt "@[<hov 2>{" ;
if n.data <> None then Format.fprintf fmt "* " ;
Cmap.iter
(fun c n ->
Format.fprintf fmt "@ %c: %a" c dump n
) n.next ;
Format.fprintf fmt " }@]" ;
end
let empty = { data = None ; next = Cmap.empty }
let rec insert k a v node =
try
let c = a.[k] in
let n0 = try Cmap.find c node.next with Not_found -> empty in
let n1 = insert (succ k) a v n0 in
{ node with next = Cmap.add c n1 node.next }
with Invalid_argument _ ->
{ node with data = Some v }
let add a v n = insert 0 a v n
let rec lookup best text k node =
try
let best = match node.data with None -> best | data -> data in
lookup best text (succ k) (Cmap.find text.[k] node.next)
with Not_found | Invalid_argument _ ->
match node.data with
| Some _ as data -> data
| None -> best
let find text k n = lookup None text k n
let starts_with ~prefix text k =
try
let n = String.length prefix in
for i = 0 to n - 1 do
if text.[k + i] <> prefix.[i] then raise Not_found
done ; true
with Not_found | Invalid_argument _ -> false
let ends_with ~suffix text k =
try
let n = String.length suffix in
for i = 0 to n - 1 do
if text.[k - n + i] <> suffix.[i] then raise Not_found
done ; true
with Not_found | Invalid_argument _ -> false