I tried to create a generic RTree. Beginning was easy, tests of union() and
intersect() was working fine. But I did not got search() working -- it gets a
rtree parameter and a box, which both are generic. I tried with proc p() which
compiles when one of the parameters is used, but not when both are present.
I have to admit that such a generic RTree is really hard for the compiler.
Maybe I should use a non generic search box (with fixed high enough dimension)
for search proc.
# http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf
# RT: range type like float, int
# D: Dimension
# M: Max entries in one node
# LT: leaf type
type
Dim = static[Natural]
Ext[RT] = tuple[a, b: RT] # extend (range)
Box[D: Dim; RT] = array[D, Ext[RT]]
L[D: Dim; RT, LT] = tuple[b: Box[D, RT]; l: LT]
N[D: Dim; RT] = tuple[b: Box[D, RT]; n: N]
LA[M, D: Dim; RT, LT] = ref array[M, L[D, RT, LT]]
NA[M, D: Dim; RT] = ref array[M, N[D, RT]]
H[M, D: Dim; RT, LT] = ref object of RootObj
parent: H[M, D, RT, LT]
Leaf[M, D: Dim; RT, LT] = ref object of H
a: LA[M, D, RT, LT]
Node[M, D: Dim; RT, LT] = ref object of H
a: NA[M, D, RT]
RTree[M, D: Dim; RT, LT] = ref object
root: H[M, D, RT, LT]
proc newRTree[M, D: Dim; RT, LT](): RTree[M, D, RT, LT] =
new result
var rt = newRTree[50, 2, float, int]()
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 search[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; b: Box[D, RT]) =
#return newSeq[int]()
discard
proc p(t: RTree; s: Box) =
discard
var m, n: Box[2, int]
m[0].a = 1
m[0].b = 2
m[1].a = 5
m[1].b = 7
n = [(a: 2, b: 3), (a: 3, b: 6)]
echo union(m, n)
echo intersect(n, m)
#search(rt, m)
p(rt, m)
$ nim c rtree.nim
rtree.nim(60, 2) Error: type mismatch: got (RTree[50, 2, system.float,
system.int], Box[2, system.int])
but expected one of:
proc p(t: RTree; s: Box)
