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 = nil 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) when isMainModule: 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()