Re: [boost] [Itl] Review

Subject: Re: [boost] [Itl] Review
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-02-26 11:02:52

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_at_[hidden]>

> 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