R-tree to be available in mdds

Hey there,

I'm currently working toward getting the next version of mdds [1] released.  One highlight of the 
next release is the inclusion of R-tree.  For those of you unfamiliar with R-tree, it is a data 
structure known to be optimal for indexing multi-dimensional spatial data, and is heavily used in 
e.g. storing 2D/2D map data and shape data with bounding boxes.  The one being implemented in mdds 
is a variant of R-tree known as R*-tree [2].

I can think of many areas where R-tree could be used inside the libreoffice code base, but one area 
I am particularly interested in is formula dependency tracking, especially those that involve cell 
ranges.  I suspect that, if implemented correctly, the use of R-tree could improve the query speed 
and also potentially minimize the complexity of the range-based listener-broadcaster handling on 
the libreoffice side (by moving the complexity of managing the data structure into mdds).  Also, by 
using R-tree to manage formula dependency data, we could in theory merge all of cell-to-cell, 
cell-to-range, range-to-cell and range-to-range dependency tracking into a single data structure, 
which to me is a very attractive proposition.

Now, this all sounds good, but I'm fully aware that I'm being overly optimistic not to mention 
biased, and it's entirely possible that I'm wrong, and using R-tree in range-based dependency 
tracking would end up in more pain and less gain.  So, my current plan is to experiment this idea 
of mine in the ixion library [3] first, then if it works well there, we can re-visit it here 
perhaps with more confidence.  I just wanted to throw this idea on this list early, and see what 
you guys think.

Thoughts?

Kohei

[1] https://gitlab.com/mdds/mdds
[2] https://en.wikipedia.org/wiki/R*_tree
[3] https://gitlab.com/ixion/ixion

--
Kohei Yoshida, LibreOffice Calc volunteer hacker