mirror of
https://github.com/nim-lang/Nim.git
synced 2025-12-29 01:14:41 +00:00
919a889ba8
* system refactor, move out 600 lines * compilation, slice, backwardsindex, misc_num moved out of system * some procs/types moved into arithmetics, basic_types * system no longer depends on syncio * some procs moved around to fit with their surroundings * make exceptions an import, old ops to misc_num * move instantiationInfo back * move back nim version, fix windows echo * include compilation * better docs for imported modules, fix unsigned ops also remove ze, ze64, toU8, toU16, toU32 with nimPreviewSlimSystem * fix terminal * workaround IC test & weird csize bug, changelog * move NimMajor etc back to compilation, rebase for CI * try ic fix * form single `indices`, slim out TaintedString, try fix IC * fix CI, update changelog, addQuitProc * fix CI * try fix CI * actually fix CI finally hopefully * Update lib/system/compilation.nim Co-authored-by: ringabout <43030857+ringabout@users.noreply.github.com> * update kochdocs * hopefully fix csize uses for slimsystem * fix tquit Co-authored-by: ringabout <43030857+ringabout@users.noreply.github.com>
75 lines
1.8 KiB
Nim
75 lines
1.8 KiB
Nim
# 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
|
|
|