Re: [boost] [Review] ITL review starts today, February 18th

Subject: Re: [boost] [Review] ITL review starts today, February 18th
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-02-22 19:53:54

Joachim Faulhaber wrote:
> So the first moment I thought you caught me on a serious design
> flaw. But after browsing the code I am fairly sure, that I can provide
> what you desire.
> 
> (1) There is a template template parameter Interval already that
> requires the domain_type and an ordering on the domain_type.
> 
> (2) For a simpler interval class template like  e.g.
> integral_rightopen_interval<T> the implementation will then be
> probably simpler or even trivial. e.g:
> 
> bool is(bound_type bt){
>    return bt==left_open ? true : false;
> }
> 
> and since the bound type is always the same, is does not
> have to be a class member anymore.

I had a similar concern to Jeff.  I didn't seen any template parameter for Interval before, but there it is.

  template<class, ITL_COMPARE>class Interval = itl::interval,

However, I'm not entirely satisfied with it because all of the utility functions for intervals are implemented as members of the interval class.  That means I have to duplicate them to implement my own interval class that satisfies the interval interface.  If they were non-member generic functions I could call them on my interval type and the bound checking would compile away with constant propagation to produce efficient code.  The interval set operations are simple enough to implement (particularly with compile time policies for open/closed) that I doubt people would try to satisfy the interface of the Interval parameter required by your interval set class and would choose to implement the algorithm themselves.

The way I always implemented open/closed semantics (with integer coordinates) was to left shift by one and bloat the interval by one on the ends that are closed.  This gives max performance and minimal storage since it uses bits that were going to waste anyway and does the work of doing bounds comparison in the same instruction that does coordinate comparison.

The OO style of the library design with large numbers of member functions for interval and container classes is somewhat off-putting.  I would rather see a separation between data structures and algorithms.  The algorithms are what are important.  Right now the library provides most of the generic programming magic required to make the operators work with any type that is a set or map of intervals, but requires the object type to provide member functions for operations that could have been implemented as free functions.  There are two algorithms for interval set operations (one is O(n log m) and the other is O(n + m)).  I would like to use the container and algorithm appropriate for what I expect n and m to be.  Also, if I call A = B & C I would like the O(n + m) algorithm to be used and not the O(n log m) algorithm in addition to an O(n + m) copy.  If I want to invoke the O(n + m) set operation algorithm why can't I use any container type for the input and output interval sets since I don't need any O(log n) insertion or removal?

I think the quality of the library is quite good, and I hope to find time for a full review before the end of the review period.  I found the number of styles of set operation, element vs. interval and sets vs. maps to be a somewhat bewildering combination of features and I'm still getting oriented in the documentation and code.  I see a lot of improvement over the course of the two years or so since it was first discussed on the mailing list.  I think the law proving test library used in the tests is a much more generally useful and stronger candidate for becoming a boost library.  The whole community could benefit from better test utilities.  Not everyone uses interval sets, but everyone writes tests.

Best wishes,
Luke