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

Subject: Re: [boost] [Review] ITL review starts today, February 18th
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-02-22 22:00:18

Hi Luke,

thank you for commenting on my library.

2010/2/23 Simonson, Lucanus J <lucanus.j.simonson_at_[hidden]>:
> 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;
>> }

ooops: simpler of course
bool is(bound_type bt){ return bt==left_open; }

>>
>> 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.

Not *all* of them. Non-member generic functions are:
==, !=, <, >, <=, >=,
hull, left_subract, right_subtract,
&, intersects, is_disjoint

> That means I have to duplicate them to implement my
> own interval class that satisfies the interval interface.

Yes. I see now the importance to keep the class
interface minimal here, which currently is not the case.
But I think, this can be achieved quickly by a number
of straight forward refactorings.

> 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.

I think this works for integer coordinates only.

> The OO style of the library design with large numbers of
> member functions for interval and container classes is somewhat
> off-putting.

Most of the core functions including all set theoretic operations
for the interval containers are provided as non-member generic
functions.

> 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.

I agree. This is not done yet. Smart as you are you spotted this
immediately ;-)

> 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

nice wording ;-) I think the admissible combinations are
chosen carefully and each of them has use cases. I could
add examples to the docs.

> 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.
oh thanks!

> 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.

... but much less advanced in the boostifying process and suffering
from many more problems

> The whole community could benefit from better test utilities.
> Not everyone uses interval sets,

... not yet ;-)

> but everyone writes tests.

Thank you for your straight and valuable comments.

Best regards,
Joachim