diff options
Diffstat (limited to 'tests/generics/tgeneric3.nim')
| -rw-r--r-- | tests/generics/tgeneric3.nim | 487 |
1 files changed, 487 insertions, 0 deletions
diff --git a/tests/generics/tgeneric3.nim b/tests/generics/tgeneric3.nim new file mode 100644 index 000000000..29a73afc6 --- /dev/null +++ b/tests/generics/tgeneric3.nim @@ -0,0 +1,487 @@ +discard """ +output: ''' +312 +1000 +1000 +500 +0 +''' +""" + +import strutils + +type + PNode[T,D] = ref TNode[T,D] + TItem[T,D] {.acyclic, pure, final, shallow.} = 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[T,D] {.acyclic, pure, final, shallow.} = 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): APath.Nd.slots[i] = move 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: + it1[i] = move left.slots[i] + for i in 0..cCenter-1: + result.slots[i] = move left.slots[cCenter + i] + result.left = n + else : + if x < cCenter : + for i in 0..x-1: + it1[i] = move left.slots[i] + it1[x] = setItem(Akey, Avalue, n) + for i in x+1 .. cCenter-1: + it1[i] = move 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: + result.slots[i] = move left.slots[cCenter + i] + else : + for i in 0..cCenter-1: + it1[i] = move left.slots[i] + x = x - (cCenter + 1) + for i in 0..x-1: + result.slots[i] = move left.slots[cCenter + i + 1] + result.slots[x] = setItem(Akey, Avalue, n) + for i in x+1 .. cCenter-1: + result.slots[i] = move left.slots[cCenter + i] + var w = left.slots[cCenter] + Akey = w.key + Avalue = w.value + result.left = w.node + left.count = cCenter + left.slots = move 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: + 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() |