Hi Phil, in my first reply to your review I was pretty frustrated and angry. Meanwhile I regret to have answered in that mood, because, at least in my case, those negative feelings disturb clear thinking :( and I typed out some false and some half-baked stuff. 2010/2/23 Phil Endecott <spam_from_boost_dev@chezphil.org>
My review of the proposed Interval Template Library follows. This is based only on studying the documentation, and previous discussion of the library on the Boost mailing list (e.g. http://lists.boost.org/Archives/boost/2009/03/149396.php ).
Joachim has clearly put a lot of work into what is a substantial and well-documented library. Unfortunately, it seems to me that it is built on a weak foundation.
[...]
I was hoping to find that this library was an implementation of an interval tree. But it is not: it is built on top of normal standard-library containers. The implementation used can find the intervals that overlap a point in O(M + log N) time, but to do so it needs worst-case O(N^2) space and I think it needs O(N^2 log N) time to build that structure.
[...]
My feeling is that since the interval tree data structure is so well known and its performance is so much better, we should not accept this library.
If I look at your arguments in a relaxed way, I have to acknowledge that they are substantial. I knew that this point (particularly space efficiency) for the interval_maps of collections, was a weak point. And I had *hoped* all the positive aspects of my work would compensate. I also remember my tendency to deny that issue, when you first addressed it last year. And denial never works ;-/ So, yes, your review as an answer to this was justified. Sticking to that point shows your standing for quality of boost libraries. This is of value, independent of the fact, that this kind of standing can be pretty unpleasant for contributors. Another thing that I wasn't able to see in my frustrated mood were the positive remarks about my work in your posting.
Ideally it would be possible for Joachim to replace ITL's current standard containers with an interval tree implementation. Could an interval tree be implemented with an interval sufficiently similar to a std::set/map to make that possible, without losing the complexity benefits?
Once again, I believe that apart from this weak foundation this looks like an excellent submission that is comprehensive and well-documented.
Even if your overall judgement is "reject", I have the impression that you find the library in it's substance valuable and that you also expressed, that it is a good candidate for boost, if the efficiency issue will be addressed. So I'd like to thank you for the positive feedback as well. Hoping that you stay supportive both for boost quality and also for my project ... Best regards, Joachim