On 02/16/2012 12:21 AM, Goswin von Brederlow wrote:
Francois Berenger<beren...@riken.jp> writes:
Hello,
I did a naive implementation of interval trees for float intervals.
It is available here:
https://github.com/HappyCrow/interval-tree
I wonder if it is possible to construct the trees in a tail recursive
fashion. Maybe I knew how to do this when I was still at university.
Regards,
Francois.
| Node of
(* x_mid left_list right_list left_tree right_tree *)
float * interval list * interval list * interval_tree * interval_tree
Why interval list? You only need a single interval in leafes and none in
other nodes (although it can help to store min and max in each node).
Not in my case, there is a payload associated with each interval in my
application so I need to keep track of the individual intervals.
You are also missing insert and remove operations,
I don't miss anything: I don't need these operations in my application.
> which is the actually
hard part in this. Inserting an interval might require merging the
rightmost interval left of the root and the leftmost interval right of
the root. So you would have 2 removals and one insertion of a combined
interval, which complicates balancing the whole thing efficiently.
I hope you have a good book on this.
By the way, the one I refer to in my code is quite nice.
At first I thought it was too theoretical for me, but in fact
they give algorithms in recursive form so the book can become pretty handy.
That is the part I'm struggling with.
You might be intersted into having a look at
the Computational Geometry Algorithms Library: http://www.cgal.org/
It's open source and it's also an INRIA product,
which makes two good points. ;)
You might want to bind your code to this library (they introduced
some framework recently, SWIG if I remember well, so that it should be
easy to do wrappers for any language).
It's heavily templated C++ code, good luck if you read their code.
They have a lot of crazily useful data structures (interval skip lists,
k-d trees, segment trees, range trees, AABB trees), and their
code is impossible to crash when using some specific math kernels.
Regards,
F.
--
Caml-list mailing list. Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
