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
68
69
70
71
72
73
74
75
76
77
78
|
discard """
matrix: "--mm:refc; --mm:orc"
"""
# test a simple yet highly efficient set of strings
type
TRadixNodeKind = enum rnLinear, rnFull, rnLeaf
PRadixNode = ref TRadixNode
TRadixNode {.inheritable.} = object
kind: TRadixNodeKind
TRadixNodeLinear = object of TRadixNode
len: uint8
keys: array[0..31, char]
vals: array[0..31, PRadixNode]
TRadixNodeFull = object of TRadixNode
b: array[char, PRadixNode]
TRadixNodeLeaf = object of TRadixNode
s: string
PRadixNodeLinear = ref TRadixNodeLinear
PRadixNodeFull = ref TRadixNodeFull
PRadixNodeLeaf = ref TRadixNodeLeaf
proc search(r: PRadixNode, s: string): PRadixNode =
var r = r
var i = 0
while r != nil:
case r.kind
of rnLinear:
var x = PRadixNodeLinear(r)
for j in 0..int(x.len)-1:
if x.keys[j] == s[i]:
if s[i] == '\0': return r
r = x.vals[j]
inc(i)
break
break # character not found
of rnFull:
var x = PRadixNodeFull(r)
var y = x.b[s[i]]
if s[i] == '\0':
return if y != nil: r else: nil
r = y
inc(i)
of rnLeaf:
var x = PRadixNodeLeaf(r)
var j = 0
while true:
if x.s[j] != s[i]: return nil
if s[i] == '\0': return r
inc(j)
inc(i)
proc contains*(r: PRadixNode, s: string): bool =
return search(r, s) != nil
proc testOrIncl*(r: var PRadixNode, s: string): bool =
nil
proc incl*(r: var PRadixNode, s: string) = discard testOrIncl(r, s)
proc excl*(r: var PRadixNode, s: string) =
var x = search(r, s)
if x == nil: return
case x.kind
of rnLeaf: PRadixNodeLeaf(x).s = ""
of rnFull: PRadixNodeFull(x).b['\0'] = nil
of rnLinear:
var x = PRadixNodeLinear(x)
for i in 0..int(x.len)-1:
if x.keys[i] == '\0':
swap(x.keys[i], x.keys[int(x.len)-1])
dec(x.len)
break
var
root: PRadixNode
|
