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