----- Original Message ----
From: Joachim Faulhaber <afojgo@googlemail.com> To: boost@lists.boost.org Sent: Fri, December 17, 2010 12:32:48 AM Subject: Re: [boost] Interval Trees & ICL
2010/12/16 Phil Endecott <spam_from_boost_dev@chezphil.org>:
My idea is to consider an interval (low,high) as a point in a 2D plain. Then, a query to find all of the intervals overlapping (a,b) is the same as the query to find all the points in the quarter-plane where low<b and high>a.
Any 2D data structure could be used to store these (e.g. quadtrees etc), but the aim here is to adapt a 1D data structure. I have used the Z-curve method [3] to do this efficiently for some years now and it works well. The idea is that you bitwise-interleave the two values and use this as the key. You can then iterate over all points in a rectangle by iterating over all points in the 1D range between the interleaved bottom left and top right corner values.
Hi Phil,
I find your idea quite nifty and fascinating. The transformation from intervals to 2D plane to z-curve ordering is quite powerful and opens up new frames of thinking on the problem. I guess I need a little more thinking time and intend to post another answer tomorrow.
Best regards, Joachim
-- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de
That is an interesting idea. However, I see the method (or at least some implementations of it) are covered by a patent. Presumably that could affect its adoption into boost? I'm broadly against software patents but things get hairy if you give the lawyers a hook to fish with. Actually digging a bit further it could be that the patent is to prevent evil lawyers doing this as the claim is by an academic rather than say Oracle (unless he works for Oracle!) Looks like enough of it is prior art that something could be used. I note that the current interval containers could also be considered / are implemented as adapters fitting over sets or maps so this would be a good fit. It might thus be quicker to integrate. Regards, Bruce.