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
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk