diff options
Diffstat (limited to 'tests/stdlib/tstrset.nim')
-rw-r--r-- | tests/stdlib/tstrset.nim | 74 |
1 files changed, 74 insertions, 0 deletions
diff --git a/tests/stdlib/tstrset.nim b/tests/stdlib/tstrset.nim new file mode 100644 index 000000000..9cdb5ed35 --- /dev/null +++ b/tests/stdlib/tstrset.nim @@ -0,0 +1,74 @@ +# test a simple yet highly efficient set of strings + +type + TRadixNodeKind = enum rnLinear, rnFull, rnLeaf + PRadixNode = ref TRadixNode + TRadixNode = object {.inheritable.} + kind: TRadixNodeKind + TRadixNodeLinear = object of TRadixNode + len: int8 + 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..ze(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..ze(x.len)-1: + if x.keys[i] == '\0': + swap(x.keys[i], x.keys[ze(x.len)-1]) + dec(x.len) + break + +var + root: PRadixNode + |