discard """
output: '''
312
1000000
1000000
500000
0
'''
"""
import strutils
type
PNode[T,D] = ref TNode[T,D]
TItem {.acyclic, pure, final, shallow.} [T,D] = object
key: T
value: D
node: PNode[T,D]
when not (D is string):
val_set: bool
TItems[T,D] = seq[ref TItem[T,D]]
TNode {.acyclic, pure, final, shallow.} [T,D] = object
slots: TItems[T,D]
left: PNode[T,D]
count: int32
RPath[T,D] = tuple[
Xi: int,
Nd: PNode[T,D] ]
const
cLen1 = 2
cLen2 = 16
cLen3 = 32
cLenCenter = 80
clen4 = 96
cLenMax = 128
cCenter = cLenMax div 2
proc len[T,D] (n:PNode[T,D]): int {.inline.} =
return n.count
proc clean[T: SomeOrdinal|SomeNumber](o: var T) {.inline.} = discard
proc clean[T: string|seq](o: var T) {.inline.} =
o = nil
proc clean[T,D] (o: ref TItem[T,D]) {.inline.} =
when (D is string) :
o.value = nil
else :
o.val_set = false
proc isClean[T,D] (it: ref TItem[T,D]): bool {.inline.} =
when (D is string) :
return it.value == nil
else :
return not it.val_set
proc isClean[T,D](n: PNode[T,D], x: int): bool {.inline.} =
when (D is string):
return n.slots[x].value == nil
else:
return not n.slots[x].val_set
proc setItem[T,D](Akey: T, Avalue: D, ANode: PNode[T,D]): ref TItem[T,D] {.inline.} =
new(result)
result.key = Akey
result.value = Avalue
result.node = ANode
when not (D is string) :
result.val_set = true
proc cmp[T:int8|int16|int32|int64|int] (a,b: T): T {.inline.} =
return a-b
template binSearchImpl *(docmp: untyped) =
var bFound = false
result = 0
var H = haystack.len - 1
while result <= H :
var I {.inject.} = (result + H) shr 1
var SW = docmp
if SW < 0: result = I + 1
else:
H = I - 1
if SW == 0 : bFound = true
if bFound: inc(result)
else: result = - result
proc bSearch[T,D] (haystack: PNode[T,D], needle:T): int {.inline.} =
binSearchImpl(haystack.slots[I].key.cmp(needle))
proc DeleteItem[T,D] (n: PNode[T,D], x: int): PNode[T,D] {.inline.} =
var w = n.slots[x]
if w.node != nil :
clean(w)
return n
dec(n.count)
if n.count > 0 :
for i in countup(x, n.count - 1) : n.slots[i] = n.slots[i + 1]
n.slots[n.count] = nil
case n.count
of cLen1 : setLen(n.slots, cLen1)
of cLen2 : setLen(n.slots, cLen2)
of cLen3 : setLen(n.slots, cLen3)
of cLenCenter : setLen(n.slots, cLenCenter)
of cLen4 : setLen(n.slots, cLen4)
else: discard
result = n
else :
result = n.left
n.slots = @[]
n.left = nil
proc internalDelete[T,D] (ANode: PNode[T,D], key: T, Avalue: var D): PNode[T,D] =
var Path: array[0..20, RPath[T,D]]
var n = ANode
result = n
clean(Avalue)
var h = 0
while n != nil:
var x = bSearch(n, key)
if x <= 0 :
Path[h].Nd = n
Path[h].Xi = - x
inc(h)
if x == 0 :
n = n.left
else :
x = (-x) - 1
if x < n.count :
n = n.slots[x].node
else :
n = nil
else :
dec(x)
if isClean(n, x) : return
Avalue = n.slots[x].value
var n2 = DeleteItem(n, x)
dec(h)
while (n2 != n) and (h >= 0) :
n = n2
var w = addr Path[h]
x = w.Xi - 1
if x >= 0 :
if (n == nil) and isClean(w.Nd, x) :
n = w.Nd
n.slots[x].node = nil
n2 = DeleteItem(n, x)
else :
w.Nd.slots[x].node = n
return
else :
w.Nd.left = n
return
dec(h)
if h < 0:
result = n2
return
proc internalFind[T,D] (n: PNode[T,D], key: T): ref TItem[T,D] {.inline.} =
var wn = n
while wn != nil :
var x = bSearch(wn, key)
if x <= 0 :
if x == 0 :
wn = wn.left
else :
x = (-x) - 1
if x < wn.count :
wn = wn.slots[x].node
else :
return nil
else :
return wn.slots[x - 1]
return nil
proc traceTree[T,D](root: PNode[T,D]) =
proc traceX(x: int) =
write stdout, "("
write stdout, x
write stdout, ") "
proc traceEl(el: ref TItem[T,D]) =
write stdout, " key: "
write stdout, el.key
write stdout, " value: "
write stdout, el.value
proc traceln(space: string) =
writeLine stdout, ""
write stdout, space
proc doTrace(n: PNode[T,D], level: int) =
var space = spaces(2 * level)
traceln(space)
write stdout, "node: "
if n == nil:
writeLine stdout, "is empty"
return
write stdout, n.count
write stdout, " elements: "
if n.left != nil:
traceln(space)
write stdout, "left: "
doTrace(n.left, level+1)
for i, el in n.slots:
if el != nil and not isClean(el):
traceln(space)
traceX(i)
if i >= n.count:
write stdout, "error "
else:
traceEl(el)
if el.node != nil: doTrace(el.node, level+1)
else : write stdout, " empty "
elif i < n.count :
traceln(space)
traceX(i)
write stdout, "clean: "
when T is string :
if el.key != nil: write stdout, el.key
else : write stdout, el.key
if el.node != nil: doTrace(el.node, level+1)
else : write stdout, " empty "
writeLine stdout,""
doTrace(root, 0)
proc InsertItem[T,D](APath: RPath[T,D], ANode:PNode[T,D], Akey: T, Avalue: D) =
var x = - APath.Xi
inc(APath.Nd.count)
case APath.Nd.count
of cLen1: setLen(APath.Nd.slots, cLen2)
of cLen2: setLen(APath.Nd.slots, cLen3)
of cLen3: setLen(APath.Nd.slots, cLenCenter)
of cLenCenter: setLen(APath.Nd.slots, cLen4)
of cLen4: setLen(APath.Nd.slots, cLenMax)
else: discard
for i in countdown(APath.Nd.count.int - 1, x + 1): shallowCopy(APath.Nd.slots[i], APath.Nd.slots[i - 1])
APath.Nd.slots[x] = setItem(Akey, Avalue, ANode)
proc SplitPage[T,D](n, left: PNode[T,D], xi: int, Akey:var T, Avalue:var D): PNode[T,D] =
var x = -xi
var it1: TItems[T,D]
it1.newSeq(cLenCenter)
new(result)
result.slots.newSeq(cLenCenter)
result.count = cCenter
if x == cCenter:
for i in 0..cCenter-1: shallowCopy(it1[i], left.slots[i])
for i in 0..cCenter-1: shallowCopy(result.slots[i], left.slots[cCenter + i])
result.left = n
else :
if x < cCenter :
for i in 0..x-1: shallowCopy(it1[i], left.slots[i])
it1[x] = setItem(Akey, Avalue, n)
for i in x+1 .. cCenter-1: shallowCopy(it1[i], left.slots[i-1])
var w = left.slots[cCenter-1]
Akey = w.key
Avalue = w.value
result.left = w.node
for i in 0..cCenter-1: shallowCopy(result.slots[i], left.slots[cCenter + i])
else :
for i in 0..cCenter-1: shallowCopy(it1[i], left.slots[i])
x = x - (cCenter + 1)
for i in 0..x-1: shallowCopy(result.slots[i], left.slots[cCenter + i + 1])
result.slots[x] = setItem(Akey, Avalue, n)
for i in x+1 .. cCenter-1: shallowCopy(result.slots[i], left.slots[cCenter + i])
var w = left.slots[cCenter]
Akey = w.key
Avalue = w.value
result.left = w.node
left.count = cCenter
shallowCopy(left.slots, it1)
proc internalPut[T,D](ANode: ref TNode[T,D], Akey: T, Avalue: D, Oldvalue: var D): ref TNode[T,D] =
var h: int
var Path: array[0..30, RPath[T,D]]
var left: PNode[T,D]
var n = ANode
result = ANode
h = 0
while n != nil:
var x = bSearch[T,D](n, Akey)
if x <= 0 :
Path[h].Nd = n
Path[h].Xi = x
inc(h)
if x == 0 :
n = n.left
else :
x = (-x)-1
if x < n.count :
n = n.slots[x].node
else :
n = nil
else :
var w = n.slots[x - 1]
Oldvalue = w.value
w.value = Avalue
return
dec(h)
left = nil
var lkey = Akey
var lvalue = Avalue
while h >= 0 :
if Path[h].Nd.count < cLenMax :
InsertItem(Path[h], n, lkey, lvalue)
return
else :
left = Path[h].Nd
n = SplitPage(n, left, Path[h].Xi, lkey, lvalue)
dec(h)
new(result)
result.slots.newSeq(cLen1)
result.count = 1
result.left = left
result.slots[0] = setItem(lkey, lvalue, n)
proc CleanTree[T,D](n: PNode[T,D]): PNode[T,D] =
if n.left != nil :
n.left = CleanTree(n.left)
for i in 0 .. n.count - 1 :
var w = n.slots[i]
if w.node != nil :
w.node = CleanTree(w.node)
clean(w.value)
clean(w.key)
n.slots = nil
return nil
proc VisitAllNodes[T,D](n: PNode[T,D], visit: proc(n: PNode[T,D]): PNode[T,D] {.closure.} ): PNode[T,D] =
if n != nil :
if n.left != nil :
n.left = VisitAllNodes(n.left, visit)
for i in 0 .. n.count - 1 :
var w = n.slots[i]
if w.node != nil :
w.node = VisitAllNodes(w.node, visit)
return visit(n)
return nil
proc VisitAllNodes[T,D](n: PNode[T,D], visit: proc(n: PNode[T,D]) {.closure.} ) =
if n != nil:
if n.left != nil :
VisitAllNodes(n.left, visit)
for i in 0 .. n.count - 1 :
var w = n.slots[i]
if w.node != nil :
VisitAllNodes(w.node, visit)
visit(n)
proc VisitAll[T,D](n: PNode[T,D], visit: proc(Akey: T, Avalue: D) {.closure.} ) =
if n != nil:
if n.left != nil :
VisitAll(n.left, visit)
for i in 0 .. n.count - 1 :
var w = n.slots[i]
if not w.isClean :
visit(w.key, w.value)
if w.node != nil :
VisitAll(w.node, visit)
proc VisitAll[T,D](n: PNode[T,D], visit: proc(Akey: T, Avalue: var D):bool {.closure.} ): PNode[T,D] =
if n != nil:
var n1 = n.left
if n1 != nil :
var n2 = VisitAll(n1, visit)
if n1 != n2 :
n.left = n2
var i = 0
while i < n.count :
var w = n.slots[i]
if not w.isClean :
if visit(w.key, w.value) :
result = DeleteItem(n, i)
if result == nil : return
dec(i)
n1 = w.node
if n1 != nil :
var n2 = VisitAll(n1, visit)
if n1 != n2 :
w.node = n2
inc(i)
return n
iterator keys* [T,D] (n: PNode[T,D]): T =
if n != nil :
var Path: array[0..20, RPath[T,D]]
var level = 0
var nd = n
var i = -1
while true :
if i < nd.count :
Path[level].Nd = nd
Path[level].Xi = i
if i < 0 :
if nd.left != nil :
nd = nd.left
inc(level)
else : inc(i)
else :
var w = nd.slots[i]
if not w.isClean() :
yield w.key
if w.node != nil :
nd = w.node
i = -1
inc(level)
else : inc(i)
else :
dec(level)
if level < 0 : break
nd = Path[level].Nd
i = Path[level].Xi
inc(i)
proc test() =
var oldvalue: int
var root = internalPut[int, int](nil, 312, 312, oldvalue)
var someOtherRoot = internalPut[string, int](nil, "312", 312, oldvalue)
var it1 = internalFind(root, 312)
echo it1.value
for i in 1..1_000_000:
root = internalPut(root, i, i, oldvalue)
var cnt = 0
oldvalue = -1
when true : # code compiles, when this or the other when is switched to false
for k in root.keys :
if k <= oldvalue :
echo k
oldvalue = k
inc(cnt)
echo cnt
when true :
cnt = 0
VisitAll(root, proc(key, val: int) = inc(cnt))
echo cnt
when true :
root = VisitAll(root, proc(key: int, value: var int): bool =
return key mod 2 == 0 )
cnt = 0
oldvalue = -1
VisitAll(root, proc(key: int, value: int) {.closure.} =
if key <= oldvalue :
echo key
oldvalue = key
inc(cnt) )
echo cnt
root = VisitAll(root, proc(key: int, value: var int): bool =
return key mod 2 != 0 )
cnt = 0
oldvalue = -1
VisitAll(root, proc(key: int, value: int) {.closure.} =
if key <= oldvalue :
echo "error ", key
oldvalue = key
inc(cnt) )
echo cnt
#traceTree(root)
test()