diff options
author | Araq <rumpf_a@web.de> | 2018-09-14 15:47:37 +0200 |
---|---|---|
committer | Araq <rumpf_a@web.de> | 2018-09-14 15:47:37 +0200 |
commit | 5ee904643af3c5bf126121cd9534ddcb11cd4630 (patch) | |
tree | 6e29b631d5b25380a5488d74cdca851502164787 /tests/generics | |
parent | 4ab99537875a763e0540fbbe48d69cad454ca792 (diff) | |
download | Nim-5ee904643af3c5bf126121cd9534ddcb11cd4630.tar.gz |
fixes #8883
Diffstat (limited to 'tests/generics')
-rw-r--r-- | tests/generics/trtree.nim | 657 |
1 files changed, 657 insertions, 0 deletions
diff --git a/tests/generics/trtree.nim b/tests/generics/trtree.nim new file mode 100644 index 000000000..875b628ae --- /dev/null +++ b/tests/generics/trtree.nim @@ -0,0 +1,657 @@ +discard """ + output: '''1 [2, 3, 4, 7] +[0, 0]''' +""" + +# Nim RTree and R*Tree implementation +# S. Salewski, 06-JAN-2018 + +# http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf +# http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf + +# RT: range type like float, int +# D: Dimension +# M: Max entries in one node +# LT: leaf type + +type + Dim* = static[int] + Ext[RT] = tuple[a, b: RT] # extend (range) + Box*[D: Dim; RT] = array[D, Ext[RT]] # Rectangle for 2D + BoxCenter*[D: Dim; RT] = array[D, RT] + L*[D: Dim; RT, LT] = tuple[b: Box[D, RT]; l: LT] # called Index Entry or index record in the Guttman paper + H[M, D: Dim; RT, LT] = ref object of RootRef + parent: H[M, D, RT, LT] + numEntries: int + level: int + N[M, D: Dim; RT, LT] = tuple[b: Box[D, RT]; n: H[M, D, RT, LT]] + LA[M, D: Dim; RT, LT] = array[M, L[D, RT, LT]] + NA[M, D: Dim; RT, LT] = array[M, N[M, D, RT, LT]] + Leaf[M, D: Dim; RT, LT] = ref object of H[M, D, RT, LT] + a: LA[M, D, RT, LT] + Node[M, D: Dim; RT, LT] = ref object of H[M, D, RT, LT] + a: NA[M, D, RT, LT] + + RTree*[M, D: Dim; RT, LT] = ref object of RootRef + root: H[M, D, RT, LT] + bigM: int + m: int + + RStarTree*[M, D: Dim; RT, LT] = ref object of RTree[M, D, RT, LT] + firstOverflow: array[32, bool] + p: int + +proc newLeaf[M, D: Dim; RT, LT](): Leaf[M, D, RT, LT] = + new result + +proc newNode[M, D: Dim; RT, LT](): Node[M, D, RT, LT] = + new result + +proc newRTree*[M, D: Dim; RT, LT](minFill: range[30 .. 50] = 40): RTree[M, D, RT, LT] = + assert(M > 1 and M < 101) + new result + result.bigM = M + result.m = M * minFill div 100 + result.root = newLeaf[M, D, RT, LT]() + +proc newRStarTree*[M, D: Dim; RT, LT](minFill: range[30 .. 50] = 40): RStarTree[M, D, RT, LT] = + assert(M > 1 and M < 101) + new result + result.bigM = M + result.m = M * minFill div 100 + result.p = M * 30 div 100 + result.root = newLeaf[M, D, RT, LT]() + +proc center(r: Box): auto =#BoxCenter[r.len, type(r[0].a)] = + var result: BoxCenter[r.len, type(r[0].a)] + for i in 0 .. r.high: + when r[0].a is SomeInteger: + result[i] = (r[i].a + r[i].b) div 2 + elif r[0].a is SomeReal: + result[i] = (r[i].a + r[i].b) / 2 + else: assert false + return result + +proc distance(c1, c2: BoxCenter): auto = + var result: type(c1[0]) + for i in 0 .. c1.high: + result += (c1[i] - c2[i]) * (c1[i] - c2[i]) + return result + +proc overlap(r1, r2: Box): auto = + result = type(r1[0].a)(1) + for i in 0 .. r1.high: + result *= (min(r1[i]. b, r2[i]. b) - max(r1[i]. a, r2[i]. a)) + if result <= 0: return 0 + +proc union(r1, r2: Box): Box = + for i in 0 .. r1.high: + result[i]. a = min(r1[i]. a, r2[i]. a) + result[i]. b = max(r1[i]. b, r2[i]. b) + +proc intersect(r1, r2: Box): bool = + for i in 0 .. r1.high: + if r1[i].b < r2[i].a or r1[i].a > r2[i].b: + return false + return true + +proc area(r: Box): auto = #type(r[0].a) = + result = type(r[0].a)(1) + for i in 0 .. r.high: + result *= r[i]. b - r[i]. a + +proc margin(r: Box): auto = #type(r[0].a) = + result = type(r[0].a)(0) + for i in 0 .. r.high: + result += r[i]. b - r[i]. a + +# how much enlargement does r1 need to include r2 +proc enlargement(r1, r2: Box): auto = + area(union(r1, r2)) - area(r1) + +proc search*[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; b: Box[D, RT]): seq[LT] = + proc s[M, D: Dim; RT, LT](n: H[M, D, RT, LT]; b: Box[D, RT]; res: var seq[LT]) = + if n of Node[M, D, RT, LT]: + let h = Node[M, D, RT, LT](n) + for i in 0 ..< n.numEntries: + if intersect(h.a[i].b, b): + s(h.a[i].n, b, res) + elif n of Leaf[M, D, RT, LT]: + let h = Leaf[M, D, RT, LT](n) + for i in 0 ..< n.numEntries: + if intersect(h.a[i].b, b): + res.add(h.a[i].l) + else: assert false + result = newSeq[LT]() + s(t.root, b, result) + +# Insertion +# a R*TREE proc +proc chooseSubtree[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; b: Box[D, RT]; level: int): H[M, D, RT, LT] = + assert level >= 0 + var n = t.root + while n.level > level: + let nn = Node[M, D, RT, LT](n) + var i0 = 0 # selected index + var minLoss = type(b[0].a).high + if n.level == 1: # childreen are leaves -- determine the minimum overlap costs + for i in 0 ..< n.numEntries: + let nx = union(nn.a[i].b, b) + var loss = 0 + for j in 0 ..< n.numEntries: + if i == j: continue + loss += (overlap(nx, nn.a[j].b) - overlap(nn.a[i].b, nn.a[j].b)) # overlap (i, j) == (j, i), so maybe cache that? + var rep = loss < minLoss + if loss == minLoss: + let l2 = enlargement(nn.a[i].b, b) - enlargement(nn.a[i0].b, b) + rep = l2 < 0 + if l2 == 0: + let l3 = area(nn.a[i].b) - area(nn.a[i0].b) + rep = l3 < 0 + if l3 == 0: + rep = nn.a[i].n.numEntries < nn.a[i0].n.numEntries + if rep: + i0 = i + minLoss = loss + else: + for i in 0 ..< n.numEntries: + let loss = enlargement(nn.a[i].b, b) + var rep = loss < minLoss + if loss == minLoss: + let l3 = area(nn.a[i].b) - area(nn.a[i0].b) + rep = l3 < 0 + if l3 == 0: + rep = nn.a[i].n.numEntries < nn.a[i0].n.numEntries + if rep: + i0 = i + minLoss = loss + n = nn.a[i0].n + return n + +proc chooseLeaf[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; b: Box[D, RT]; level: int): H[M, D, RT, LT] = + assert level >= 0 + var n = t.root + while n.level > level: + var j = -1 # selected index + var x: type(b[0].a) + let nn = Node[M, D, RT, LT](n) + for i in 0 ..< n.numEntries: + let h = enlargement(nn.a[i].b, b) + if j < 0 or h < x or (x == h and area(nn.a[i].b) < area(nn.a[j].b)): + x = h + j = i + n = nn.a[j].n + return n + +proc pickSeeds[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; n: Node[M, D, RT, LT] | Leaf[M, D, RT, LT]; bx: Box[D, RT]): (int, int) = + var i0, j0: int + var bi, bj: type(bx) + var largestWaste = type(bx[0].a).low + for i in -1 .. n.a.high: + for j in 0 .. n.a.high: + if unlikely(i == j): continue + if unlikely(i < 0): + bi = bx + else: + bi = n.a[i].b + bj = n.a[j].b + let b = union(bi, bj) + let h = area(b) - area(bi) - area(bj) + if h > largestWaste: + largestWaste = h + i0 = i + j0 = j + return (i0, j0) + +proc pickNext[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; n0, n1, n2: Node[M, D, RT, LT] | Leaf[M, D, RT, LT]; b1, b2: Box[D, RT]): int = + let a1 = area(b1) + let a2 = area(b2) + var d = type(a1).low + for i in 0 ..< n0.numEntries: + let d1 = area(union(b1, n0.a[i].b)) - a1 + let d2 = area(union(b2, n0.a[i].b)) - a2 + if (d1 - d2) * (d1 - d2) > d: + result = i + d = (d1 - d2) * (d1 - d2) + +from algorithm import SortOrder, sort +proc sortPlus[T](a: var openArray[T], ax: var T, cmp: proc (x, y: T): int {.closure.}, order = algorithm.SortOrder.Ascending) = + var j = 0 + let sign = if order == algorithm.SortOrder.Ascending: 1 else: -1 + for i in 1 .. a.high: + if cmp(a[i], a[j]) * sign < 0: + j = i + if cmp(a[j], ax) * sign < 0: + swap(ax, a[j]) + a.sort(cmp, order) + +# R*TREE procs +proc rstarSplit[M, D: Dim; RT, LT](t: RStarTree[M, D, RT, LT]; n: var Node[M, D, RT, LT] | var Leaf[M, D, RT, LT]; lx: L[D, RT, LT] | N[M, D, RT, LT]): type(n) = + type NL = type(lx) + var nBest: type(n) + new nBest + var lx = lx + when n is Node[M, D, RT, LT]: + lx.n.parent = n + var lxbest: type(lx) + var m0 = lx.b[0].a.high + for d2 in 0 ..< 2 * D: + let d = d2 div 2 + if d2 mod 2 == 0: + sortPlus(n.a, lx, proc (x, y: NL): int = cmp(x.b[d].a, y.b[d].a)) + else: + sortPlus(n.a, lx, proc (x, y: NL): int = cmp(x.b[d].b, y.b[d].b)) + for i in t.m - 1 .. n.a.high - t.m + 1: + var b = lx.b + for j in 0 ..< i: # we can precalculate union() for range 0 .. t.m - 1, but that seems to give no real benefit. Maybe for very large M? + #echo "x",j + b = union(n.a[j].b, b) + var m = margin(b) + b = n.a[^1].b + for j in i ..< n.a.high: # again, precalculation of tail would be possible + #echo "y",j + b = union(n.a[j].b, b) + m += margin(b) + if m < m0: + nbest[] = n[] + lxbest = lx + m0 = m + var i0 = -1 + var o0 = lx.b[0].a.high + for i in t.m - 1 .. n.a.high - t.m + 1: + var b1 = lxbest.b + for j in 0 ..< i: + b1 = union(nbest.a[j].b, b1) + var b2 = nbest.a[^1].b + for j in i ..< n.a.high: + b2 = union(nbest.a[j].b, b2) + let o = overlap(b1, b2) + if o < o0: + i0 = i + o0 = o + n.a[0] = lxbest + for i in 0 ..< i0: + n.a[i + 1] = nbest.a[i] + new result + result.level = n.level + result.parent = n.parent + for i in i0 .. n.a.high: + result.a[i - i0] = nbest.a[i] + n.numEntries = i0 + 1 + result.numEntries = M - i0 + when n is Node[M, D, RT, LT]: + for i in 0 ..< result.numEntries: + result.a[i].n.parent = result + +proc quadraticSplit[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; n: var Node[M, D, RT, LT] | var Leaf[M, D, RT, LT]; lx: L[D, RT, LT] | N[M, D, RT, LT]): type(n) = + var n1, n2: type(n) + var s1, s2: int + new n1 + new n2 + n1.parent = n.parent + n2.parent = n.parent + n1.level = n.level + n2.level = n.level + var lx = lx + when n is Node[M, D, RT, LT]: + lx.n.parent = n + (s1, s2) = pickSeeds(t, n, lx.b) + assert s1 >= -1 and s2 >= 0 + if unlikely(s1 < 0): + n1.a[0] = lx + else: + n1.a[0] = n.a[s1] + dec(n.numEntries) + if s2 == n.numEntries: # important fix + s2 = s1 + n.a[s1] = n.a[n.numEntries] + inc(n1.numEntries) + var b1 = n1.a[0].b + n2.a[0] = n.a[s2] + dec(n.numEntries) + n.a[s2] = n.a[n.numEntries] + inc(n2.numEntries) + var b2 = n2.a[0].b + if s1 >= 0: + n.a[n.numEntries] = lx + inc(n.numEntries) + while n.numEntries > 0 and n1.numEntries < (t.bigM + 1 - t.m) and n2.numEntries < (t.bigM + 1 - t.m): + let next = pickNext(t, n, n1, n2, b1, b2) + let d1 = area(union(b1, n.a[next].b)) - area(b1) + let d2 = area(union(b2, n.a[next].b)) - area(b2) + if (d1 < d2) or (d1 == d2 and ((area(b1) < area(b2)) or (area(b1) == area(b2) and n1.numEntries < n2.numEntries))): + n1.a[n1.numEntries] = n.a[next] + b1 = union(b1, n.a[next].b) + inc(n1.numEntries) + else: + n2.a[n2.numEntries] = n.a[next] + b2 = union(b2, n.a[next].b) + inc(n2.numEntries) + dec(n.numEntries) + n.a[next] = n.a[n.numEntries] + if n.numEntries == 0: + discard + elif n1.numEntries == (t.bigM + 1 - t.m): + while n.numEntries > 0: + dec(n.numEntries) + n2.a[n2.numEntries] = n.a[n.numEntries] + inc(n2.numEntries) + elif n2.numEntries == (t.bigM + 1 - t.m): + while n.numEntries > 0: + dec(n.numEntries) + n1.a[n1.numEntries] = n.a[n.numEntries] + inc(n1.numEntries) + when n is Node[M, D, RT, LT]: + for i in 0 ..< n2.numEntries: + n2.a[i].n.parent = n2 + n[] = n1[] + return n2 + +proc overflowTreatment[M, D: Dim; RT, LT](t: RStarTree[M, D, RT, LT]; n: var Node[M, D, RT, LT] | var Leaf[M, D, RT, LT]; lx: L[D, RT, LT] | N[M, D, RT, LT]): type(n) + +proc adjustTree[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; l, ll: H[M, D, RT, LT]; hb: Box[D, RT]) = + var n = l + var nn = ll + assert n != nil + while true: + if n == t.root: + if nn == nil: + break + t.root = newNode[M, D, RT, LT]() + t.root.level = n.level + 1 + Node[M, D, RT, LT](t.root).a[0].n = n + n.parent = t.root + nn.parent = t.root + t.root.numEntries = 1 + let p = Node[M, D, RT, LT](n.parent) + var i = 0 + while p.a[i].n != n: + inc(i) + var b: type(p.a[0].b) + if n of Leaf[M, D, RT, LT]: + when false:#if likely(nn.isNil): # no performance gain + b = union(p.a[i].b, Leaf[M, D, RT, LT](n).a[n.numEntries - 1].b) + else: + b = Leaf[M, D, RT, LT](n).a[0].b + for j in 1 ..< n.numEntries: + b = trtree.union(b, Leaf[M, D, RT, LT](n).a[j].b) + elif n of Node[M, D, RT, LT]: + b = Node[M, D, RT, LT](n).a[0].b + for j in 1 ..< n.numEntries: + b = union(b, Node[M, D, RT, LT](n).a[j].b) + else: + assert false + #if nn.isNil and p.a[i].b == b: break # no performance gain + p.a[i].b = b + n = H[M, D, RT, LT](p) + if unlikely(nn != nil): + if nn of Leaf[M, D, RT, LT]: + b = Leaf[M, D, RT, LT](nn).a[0].b + for j in 1 ..< nn.numEntries: + b = union(b, Leaf[M, D, RT, LT](nn).a[j].b) + elif nn of Node[M, D, RT, LT]: + b = Node[M, D, RT, LT](nn).a[0].b + for j in 1 ..< nn.numEntries: + b = union(b, Node[M, D, RT, LT](nn).a[j].b) + else: + assert false + if p.numEntries < p.a.len: + p.a[p.numEntries].b = b + p.a[p.numEntries].n = nn + inc(p.numEntries) + assert n != nil + nn = nil + else: + let h: N[M, D, RT, LT] = (b, nn) + if t of RStarTree[M, D, RT, LT]: + nn = overflowTreatment(RStarTree[M, D, RT, LT](t), p, h) + elif t of RTree[M, D, RT, LT]: + nn = quadraticSplit(RTree[M, D, RT, LT](t), p, h) + else: + assert false + assert n == H[M, D, RT, LT](p) + assert n != nil + assert t.root != nil + +proc insert*[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; leaf: N[M, D, RT, LT] | L[D, RT, LT]; level: int = 0) = + when leaf is N[M, D, RT, LT]: + assert level > 0 + type NodeLeaf = Node[M, D, RT, LT] + else: + assert level == 0 + type NodeLeaf = Leaf[M, D, RT, LT] + for d in leaf.b: + assert d.a <= d.b + let l = NodeLeaf(chooseSubtree(t, leaf.b, level)) + if l.numEntries < l.a.len: + l.a[l.numEntries] = leaf + inc(l.numEntries) + when leaf is N[M, D, RT, LT]: + leaf.n.parent = l + adjustTree(t, l, nil, leaf.b) + else: + let l2 = quadraticSplit(t, l, leaf) + assert l2.level == l.level + adjustTree(t, l, l2, leaf.b) + +# R*Tree insert procs +proc rsinsert[M, D: Dim; RT, LT](t: RStarTree[M, D, RT, LT]; leaf: N[M, D, RT, LT] | L[D, RT, LT]; level: int) + +proc reInsert[M, D: Dim; RT, LT](t: RStarTree[M, D, RT, LT]; n: var Node[M, D, RT, LT] | var Leaf[M, D, RT, LT]; lx: L[D, RT, LT] | N[M, D, RT, LT]) = + type NL = type(lx) + var lx = lx + var buf: type(n.a) + let p = Node[M, D, RT, LT](n.parent) + var i = 0 + while p.a[i].n != n: + inc(i) + let c = center(p.a[i].b) + sortPlus(n.a, lx, proc (x, y: NL): int = cmp(distance(center(x.b), c), distance(center(y.b), c))) + n.numEntries = M - t.p + swap(n.a[n.numEntries], lx) + inc n.numEntries + var b = n.a[0].b + for i in 1 ..< n.numEntries: + b = union(b, n.a[i].b) + p.a[i].b = b + for i in M - t.p + 1 .. n.a.high: + buf[i] = n.a[i] + rsinsert(t, lx, n.level) + for i in M - t.p + 1 .. n.a.high: + rsinsert(t, buf[i], n.level) + +proc overflowTreatment[M, D: Dim; RT, LT](t: RStarTree[M, D, RT, LT]; n: var Node[M, D, RT, LT] | var Leaf[M, D, RT, LT]; lx: L[D, RT, LT] | N[M, D, RT, LT]): type(n) = + if n.level != t.root.level and t.firstOverflow[n.level]: + t.firstOverflow[n.level] = false + reInsert(t, n, lx) + return nil + else: + let l2 = rstarSplit(t, n, lx) + assert l2.level == n.level + return l2 + +proc rsinsert[M, D: Dim; RT, LT](t: RStarTree[M, D, RT, LT]; leaf: N[M, D, RT, LT] | L[D, RT, LT]; level: int) = + when leaf is N[M, D, RT, LT]: + assert level > 0 + type NodeLeaf = Node[M, D, RT, LT] + else: + assert level == 0 + type NodeLeaf = Leaf[M, D, RT, LT] + let l = NodeLeaf(chooseSubtree(t, leaf.b, level)) + if l.numEntries < l.a.len: + l.a[l.numEntries] = leaf + inc(l.numEntries) + when leaf is N[M, D, RT, LT]: + leaf.n.parent = l + adjustTree(t, l, nil, leaf.b) + else: + when leaf is N[M, D, RT, LT]: # TODO do we need this? + leaf.n.parent = l + let l2 = overflowTreatment(t, l, leaf) + if l2 != nil: + assert l2.level == l.level + adjustTree(t, l, l2, leaf.b) + +proc insert*[M, D: Dim; RT, LT](t: RStarTree[M, D, RT, LT]; leaf: L[D, RT, LT]) = + for d in leaf.b: + assert d.a <= d.b + for i in mitems(t.firstOverflow): + i = true + rsinsert(t, leaf, 0) + +# delete +proc findLeaf[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; leaf: L[D, RT, LT]): Leaf[M, D, RT, LT] = + proc fl[M, D: Dim; RT, LT](h: H[M, D, RT, LT]; leaf: L[D, RT, LT]): Leaf[M, D, RT, LT] = + var n = h + if n of Node[M, D, RT, LT]: + for i in 0 ..< n.numEntries: + if intersect(Node[M, D, RT, LT](n).a[i].b, leaf.b): + let l = fl(Node[M, D, RT, LT](n).a[i].n, leaf) + if l != nil: + return l + elif n of Leaf[M, D, RT, LT]: + for i in 0 ..< n.numEntries: + if Leaf[M, D, RT, LT](n).a[i] == leaf: + return Leaf[M, D, RT, LT](n) + else: + assert false + return nil + fl(t.root, leaf) + +proc condenseTree[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; leaf: Leaf[M, D, RT, LT]) = + var n: H[M, D, RT, LT] = leaf + var q = newSeq[H[M, D, RT, LT]]() + var b: type(leaf.a[0].b) + while n != t.root: + let p = Node[M, D, RT, LT](n.parent) + var i = 0 + while p.a[i].n != n: + inc(i) + if n.numEntries < t.m: + dec(p.numEntries) + p.a[i] = p.a[p.numEntries] + q.add(n) + else: + if n of Leaf[M, D, RT, LT]: + b = Leaf[M, D, RT, LT](n).a[0].b + for j in 1 ..< n.numEntries: + b = union(b, Leaf[M, D, RT, LT](n).a[j].b) + elif n of Node[M, D, RT, LT]: + b = Node[M, D, RT, LT](n).a[0].b + for j in 1 ..< n.numEntries: + b = union(b, Node[M, D, RT, LT](n).a[j].b) + else: + assert false + p.a[i].b = b + n = n.parent + if t of RStarTree[M, D, RT, LT]: + for n in q: + if n of Leaf[M, D, RT, LT]: + for i in 0 ..< n.numEntries: + for i in mitems(RStarTree[M, D, RT, LT](t).firstOverflow): + i = true + rsinsert(RStarTree[M, D, RT, LT](t), Leaf[M, D, RT, LT](n).a[i], 0) + elif n of Node[M, D, RT, LT]: + for i in 0 ..< n.numEntries: + for i in mitems(RStarTree[M, D, RT, LT](t).firstOverflow): + i = true + rsinsert(RStarTree[M, D, RT, LT](t), Node[M, D, RT, LT](n).a[i], n.level) + else: + assert false + elif t of RTree[M, D, RT, LT]: + for n in q: + if n of Leaf[M, D, RT, LT]: + for i in 0 ..< n.numEntries: + insert(RTree[M, D, RT, LT](t), Leaf[M, D, RT, LT](n).a[i]) + elif n of Node[M, D, RT, LT]: + for i in 0 ..< n.numEntries: + insert(RTree[M, D, RT, LT](t), Node[M, D, RT, LT](n).a[i], n.level) + else: + assert false + else: + assert false + +proc delete*[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; leaf: L[D, RT, LT]): bool {.discardable.} = + let l = findLeaf(t, leaf) + if l.isNil: + return false + else: + var i = 0 + while l.a[i] != leaf: + inc(i) + dec(l.numEntries) + l.a[i] = l.a[l.numEntries] + condenseTree(t, l) + if t.root.numEntries == 1: + if t.root of Node[M, D, RT, LT]: + t.root = Node[M, D, RT, LT](t.root).a[0].n + t.root.parent = nil + return true + +when isMainModule: + + var t = [4, 1, 3, 2] + var xt = 7 + sortPlus(t, xt, system.cmp, SortOrder.Ascending) + echo xt, " ", t + + type + RSE = L[2, int, int] + RSeq = seq[RSE] + + proc rseq_search(rs: RSeq; rse: RSE): seq[int] = + result = newSeq[int]() + for i in rs: + if intersect(i.b, rse.b): + result.add(i.l) + + proc rseq_delete(rs: var RSeq; rse: RSE): bool = + for i in 0 .. rs.high: + if rs[i] == rse: + #rs.delete(i) + rs[i] = rs[rs.high] + rs.setLen(rs.len - 1) + return true + + import random, algorithm + + proc test(n: int) = + var b: Box[2, int] + echo center(b) + var x1, x2, y1, y2: int + var t = newRStarTree[8, 2, int, int]() + #var t = newRTree[8, 2, int, int]() + var rs = newSeq[RSE]() + for i in 0 .. 5: + for i in 0 .. n - 1: + x1 = rand(1000) + y1 = rand(1000) + x2 = x1 + rand(25) + y2 = y1 + rand(25) + b = [(x1, x2), (y1, y2)] + let el: L[2, int, int] = (b, i + 7) + t.insert(el) + rs.add(el) + + for i in 0 .. (n div 4): + let j = rand(rs.high) + var el = rs[j] + assert t.delete(el) + assert rs.rseq_delete(el) + + for i in 0 .. n - 1: + x1 = rand(1000) + y1 = rand(1000) + x2 = x1 + rand(100) + y2 = y1 + rand(100) + b = [(x1, x2), (y1, y2)] + let el: L[2, int, int] = (b, i) + let r = search(t, b) + let r2 = rseq_search(rs, el) + assert r.len == r2.len + assert r.sorted(system.cmp) == r2.sorted(system.cmp) + + test(5500) + + # 651 lines + |