Re: [Boost-users] Review of Interval Template Library (ITL) for inclusion

Subject: Re: [Boost-users] Review of Interval Template Library (ITL) for inclusion
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-03-15 06:41:35

Hi Jerry,

sorry for my late reply. I was looking for reviews mainly on the boost
developers list so I overlooked your report. Then I took a few days
off from work and boost ;) So thank you for using the ITL and for
taking the time to share your experiences.

2010/3/5 Jerry Jeremiah <Jerry.Jeremiah_at_[hidden]>:
[...]
>
> Firstly, I want to say that I have never participated in a review before so
> hopefully I can meet expectations for a good quality review.  And let me
> also say, I am really glad that the review period was extended - I just
> don’t have time to get onto something specific within a week.
>
>
> This review wasn’t really an academic exercise for me.  This library has a
> practical use for me so this review is a by-product of my attempt to see how
> using the library would compare with what I would have to hand write to get
> the same result.

I am pleased to see that the library found another use case in real
world applications :)

> I work for a telecom and we have call detail records for
> millions of calls per day.  What I want to know is how many simultaneous
> phone calls are there at any point in time.  Traditionally, one would make
> an integer array of 7 days x 86400 seconds to hold the number of calls for
> each second in the week and then increment all the seconds between the start
> and end time of each call.  With this library one simply inserts into an
> interval map the start and end times of the calls and then iterates through
> the map printing out the results.
>
> I read all the documentation twice.  The first time didn’t really make it
> clear how all the possible options related to each other and in what
> circumstances I would use each of them.  But the second reading really
> helped.  The examples in the documentation (like Table 1.3) were useful to
> my understanding.  I thought the documentation was quite comprehensive and I
> really appreciated that – an example of that is Table 1.12 which I mention
> later on.
>
> The thing that differentiates a library from something I would write is that
> a library must cater for every single possible use.  I thought the author
> went to a lot of effort to do this and the number of combinations of sets
> and maps that the library supports far exceeds the number of different use
> cases I have.
>
> The code samples helped clarify the differences between the different
> options.  I didn’t see an example where split_interval_map gave a result
> that was more useful than that of the interval_map.  When would not joining
> touching intervals with the same value be the desired outcome?  I guess the
> “time grid” could be such an example but it didn’t use interval maps.

Good examples are supposed to be short. If we put a lot of features in
them, people tend to not read them because they get to long. So it's
always a compromise. You are right. The use case you mention has no
explicit example, but it could be added to the "time grid" example.
You can intersect a split_interval_map with an interval_set in order
to place certain interval borders, e.g. months, into that
split_interval_map, despite of the fact, that an equal value is
associated.

In an interval_map the intersected intervals would be immediatedly
joined again due to equal associated values. In a split_interval_map
the interval borders will be preseved. This is useful for computations
and reports in the field of accountancy for instance.

> I am not a meta-programming guru so looking at the source for Proto, MPL or
> Fusion just confuses me and I try to avoid that at all costs.  I was a bit
> scared to look at the source for this library, but I put on a brave face and
> had a peek.  It wasn’t all that scary after all – it was quite readable.
> The source reminds me a lot like the STL headers which I guess isn’t that
> surprising since it is implementing similar style containers (map and set).
>
> In the Party example a boost::itl::set<string> is used to store the names of
> the guests because it supports += as set union.  In that example you can
> just as easily use:  struct GuestSetT : public std::set<string> {
> std::set<string> & operator += (const std::set<string> & right) {
> insert(right.begin(), right.end()); return *this; }}; My question is, does
> this example really benefit from using itl::set?   I do see value in
> itl::set and itl::map on their own but except this one use there aren’t any
> examples that show why they would suit a particular application.

In the ITL not only operator += but also -= and &= are "pervasive" and
they are expected as defaults for interval maps in order to perform
"aggregate on onverlap", where the operator is passed to combine
associated values in case of overlap of intervals. One of the reasons
to introduce itl::set and itl::map was to support these operators, so
that interval maps of sets or even interval maps of maps of ... work
"out of the box" without the need for the user to write adapter code
(like the one proposed above).

Other reviewers have criticised these "element containers" of the ITL
as well. I am going to consinder their arguments in a redesign of the
ITL's interface. One possibility that I will most likely provide is
adaptercode for std::containers directly that implements the operators
that are expected for "aggregate on overlap".

> I played with all the examples without any problem and I made a couple of my
> own.  The library handled my example use cases elegantly although I
> certainly never did anything complicated enough to test the limits of the
> library.  I used MSVC 2005 on Windows XP.  There just wasn’t time to try a
> full test with millions of phone calls spread over several days so I don’t
> really have any idea how the performance compares to anything - I am
> depending on the table in the documentation (Table 1.12) for those answers.
>
> I was a bit concerned about the questions raised by
> http://comments.gmane.org/gmane.comp.lib.boost.devel/199902 - I did notice
> the disclaimer in the documentation saying that an interval_map of sets is a
> bad idea but maybe that should be explained more explicitly under the
> complexity topic.

Yes, that's a good idea.

> From my point of view, the library has practical uses.  I found the library
> easy to use because the documentation was comprehensive and the examples
> covered my use cases.  I don’t really understand how
>
> I think it would make a good addition to boost and so my vote is yes.

Thank you again for your review

Best regards,
Joachim