1structure UTF8Set :> UTF8Set =
2struct
3
4datatype t = N of bool * (int,t)Binarymap.dict
5
6open UTF8
7
8val empty = N(false, Binarymap.mkDict Int.compare)
9
10fun add(N (b,m), s) =
11    case getChar s of
12      NONE => N(true, m)
13    | SOME ((c,i), rest) => let
14      in
15        case Binarymap.peek (m, i) of
16          NONE => N(b, Binarymap.insert(m, i, add(empty, rest)))
17        | SOME t => N(b, Binarymap.insert(m, i, add(t, rest)))
18      end
19
20fun addList (t, slist) = List.foldl (fn (s,t) => add(t,s)) t slist
21
22fun isEmpty (N(b,m)) = not b andalso Binarymap.numItems m = 0
23
24fun listItems set = let
25  fun listItems' pfx acc (N(b,m)) = let
26    fun foldthis (i,set,acc) =
27        listItems' (pfx ^ chr i) acc set
28    val acc' = if b then pfx :: acc else acc
29  in
30    Binarymap.foldl foldthis acc' m
31  end
32in
33  listItems' "" [] set
34end
35
36fun member(N(b,m),s) =
37    case getChar s of
38      NONE => b
39    | SOME((_,i), rest) => let
40      in
41        case Binarymap.peek(m,i) of
42          NONE => false
43        | SOME s' => member (s', rest)
44      end
45
46fun longest_pfx_member(set, s) = let
47  fun recurse best curpfx s (N(b,m)) = let
48    val best = if b then SOME {pfx=curpfx,rest=s} else best
49  in
50    case getChar s of
51      NONE => best
52    | SOME ((_, i), rest) => let
53      in
54        case Binarymap.peek (m,i) of
55          NONE => best
56        | SOME set => recurse best (curpfx ^ chr i) rest set
57      end
58  end
59in
60  recurse NONE "" s set
61end
62
63
64
65end (* struct *)
66