
Boost : 
Subject: Re: [boost] [Review] ITL review starts today, February 18th
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 20100222 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. Nonmember 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 nonmember 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
> offputting.
Most of the core functions including all set theoretic operations
for the interval containers are provided as nonmember 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk