Re: [boost] [Itl] Review

Subject: Re: [boost] [Itl] Review
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2010-03-07 15:51:04

Joachim Faulhaber wrote:
> Hi Phil,
>
> thank you again for your review.

And thank you for finally addressing this issue.  I do not have much 
time to reply, unfortunately.

> There are no data structures that are superior as such. Each has its
> pros and its cons and the user has to take her decision of choosing
> the appropriate one, dependent on the characteristics of her specific
> problem domain and use case.

Selection of appropriate data structures is vital.  What I believe you 
have done is to take one data structure and build an overly-generic 
library on top of it.  It seems to me that it would be better to either 
restrict the scope of the library to those things that it can do 
efficiently, or to extend the implementation of the library to 
efficiently support all of the advertised capabilities.

> the segmentation of the interval_map, (its
> separation into elementary intervals that the aggregation results are
> associated to), is only implicit in the [interval tree]. Moreover the
> interval_tree, in contrast to the "eager implementation" does not
> "recognize", that neighbouring intervals can be joined, because of
> equality of the aggregated values associated to the elementary
> segments.

> Most obvious is the case of an interval_set<T>. The previously
> discussed "worst case" (large intervals, that are all overlapping) is
> the best case for the eager evaluating implementation here. There will
> always be only a single interval node in the implementing std::set. So
> space and time of all operations are constant. An interval_tree would
> store all N intervals.

I think that you could quite easily update an interval tree in such a 
way that it would store an "eager" implementation.  In the case of an 
interval_set, to insert an interval into an interval tree that is 
representing an interval_set you would

1. Erase all intervals that are contained within the new interval.
2. If an interval overlaps the bottom end of the new interval, erase it 
and extend the bottom end of the new interval.
3. If an interval overlaps the top end of the new interval, erase it 
and extend the top end of the new interval.
4. Insert the modified new interval.

I guess that the other cases would be similar, and they would have the 
same time and space complexity as your current std::set implementation.

Sorry for my short reply, but we are in the last few hours of the 
review period.

Regards,  Phil.