I have just shipped version 0.2 of Nim R-Tree module rtree.nim to github. Integration in nimble data base should occur soon.
https://github.com/StefanSalewski/RTree
This is a fully generic module with insert(), delete(), search(), bulk-load() and nearest-neighbor search support.
I am not fully satisfied with the code, maybe we can improve it?
OK, maybe lets start with the proc vs iterator issue: We have
https://github.com/StefanSalewski/RTree/blob/master/src/rtree.nim#L894
proc findNearestBox*[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; queryObject: BoxCenter[D, RT]): L[D, RT, LT] =
var queue = initHeapQueue[RTRef[RT]]()
queue.push(t.root)
while queue.len > 0:
var el = queue.pop
if el of QE[M, D, RT, LT]:
return QE[M, D, RT, LT](el).le
elif el of Leaf[M, D, RT, LT]:
for i, o in Leaf[M, D, RT, LT](el).a:
if i == Leaf[M, D, RT, LT](el).numEntries: break
var v = QE[M, D, RT, LT](le: o, pri: dist(queryObject, o.b))
queue.push(v)
elif el of Node[M, D, RT, LT]:
for i, o in (Node[M, D, RT, LT](el).a):
if i == Node[M, D, RT, LT](el).numEntries: break
o.n.pri = dist(queryObject, (o).b)
queue.push(o.n)
else: assert false
iterator findNearestBox*[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; queryObject: BoxCenter[D, RT]): L[D, RT, LT] =
var queue = initHeapQueue[RTRef[RT]]()
queue.push(t.root)
while queue.len > 0:
var el = queue.pop
if el of QE[M, D, RT, LT]:
yield QE[M, D, RT, LT](el).le
elif el of Leaf[M, D, RT, LT]:
for i, o in Leaf[M, D, RT, LT](el).a:
if i == Leaf[M, D, RT, LT](el).numEntries: break
var v = QE[M, D, RT, LT](le: o, pri: dist(queryObject, o.b))
queue.push(v)
elif el of Node[M, D, RT, LT]:
for i, o in (Node[M, D, RT, LT](el).a):
if i == Node[M, D, RT, LT](el).numEntries: break
o.n.pri = dist(queryObject, (o).b)
queue.push(o.n)
else: assert false
So the code is nearly identical in proc and iterator, but one contains a return, the other the yield. I was just thinking about to make it more DRY and to save some lines of code. First idea is something like
proc findNearestBox*[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; queryObject: BoxCenter[D, RT]): L[D, RT, LT] =
for el in indNearestBox(t):
yield el
break
That looks good and saves a lot of code. But the iterator is not an inline one, so may above proc be slow? Or is it optimized well?
The other Idea I just had is using a template for the body with a static[bool] as parameter, which may lead to code like
template findNearestBox(prok: static[bool]) =
var queue = initHeapQueue[RTRef[RT]]()
queue.push(t.root)
while queue.len > 0:
var el = queue.pop
if el of QE[M, D, RT, LT]:
when prok:
return QE[M, D, RT, LT](el).le
else:
yield QE[M, D, RT, LT](el).le
elif el of Leaf[M, D, RT, LT]:
for i, o in Leaf[M, D, RT, LT](el).a:
if i == Leaf[M, D, RT, LT](el).numEntries: break
var v = QE[M, D, RT, LT](le: o, pri: dist(queryObject, o.b))
queue.push(v)
elif el of Node[M, D, RT, LT]:
for i, o in (Node[M, D, RT, LT](el).a):
if i == Node[M, D, RT, LT](el).numEntries: break
o.n.pri = dist(queryObject, (o).b)
queue.push(o.n)
else: assert false
proc findNearestBox*[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; queryObject: BoxCenter[D, RT]): L[D, RT, LT] =
findNearestBox(true)
iterator findNearestBox*[M, D: Dim; RT, LT](t: RTree[M, D, RT, LT]; queryObject: BoxCenter[D, RT]): L[D, RT, LT] =
findNearestBox(false)
I would assume that it will compile both. So which solution shall we use?
Well, as there are many issues maybe one more simple one now:
https://github.com/StefanSalewski/RTree/blob/master/src/rtree.nim#L278
#
when RT is float:
var m0 = system.Inf
elif RT is float32:
var m0 = 1e30 # ugly
else:
var m0 = lx.b[0].a.high
Well, there is no high() for float data type available, like var x: float; x = high(x). But system.Inf. But there seems to be no Inf for float32 available? So above code is 6 lines, is there a way to collapse it, in best case to one single line?