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

Subject: Re: [boost] [Boost-users] [Review] ITL review starts today, February 18th
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-03-05 07:35:57

Hi John,

yesterday I was in a hurry, so I wasn't able to continue this
interesting discussion with you. In my last reply I didn't even notice
you are going to go on holidays so you won't be able to follow the
thread today. I don't think this is a big problem, since I am not
planning to stop being open for suggestion after the review ;-)

2010/3/4 John Reid <j.reid_at_[hidden]>:
>
>
> Joachim Faulhaber wrote:
>>
>> 2010/3/4 John Reid <j.reid_at_[hidden]>:
>>>
>>> John Reid wrote:
>>>>
>>>> Joachim Faulhaber wrote:
>>>>>>
>>>>>> So it might be better to have
>>>>>> both continuous and discrete intervals as right-open by default and to
>>>>>> allow
>>>>>> some mechanism whereby the user can choose to allow different runtime
>>>>>> bound
>>>>>> types if they need them.
>>>>>
>>>>> I agree, that right-open intervals are suitable as default. But I am
>>>>> afraid, for the continuous case, we can not guarantee that all
>>>>> operations can maintain such an invariant. BTW existing interval
>>>>> libraries e.g. boost::numeric::interval or FILIB++ work with closed
>>>>> intervals. Subtract a closed interval from an interval set with
>>>>> continuous domain_type  and you need open bounds.
>>>>
>>>> I was suggesting that your design could feature sets/maps that only had
>>>> right-open intervals. This would be the default in both continuous and
>>>> discrete domains. If the user really wanted to use all the different
>>>> interval bound types over a continuous domain then perhaps he/she could
>>>> choose to do so via a template parameter. This would probably be a rare
>>>> use
>>>> case though.
>>>>
>>> I should just say that I think all the invariants can be maintained in
>>> sets
>>> of right-open intervals. Please correct me if I'm wrong.
>>
>> I think it can be maintained for intervals of integral domain_types
>> but it can not be maintained for intervals of continuous domain_types.
>> To be more accurate: I have my doubts if it can be maintained and to
>> be even more precise: I don't know if it can be maintained in this
>> case, without loss of generality or correctness of the implementation.
>
> Given a set of right-open intervals, I can't think of any operation on that
> set with an operand of another set of half-open intervals that would
> invalidate the invariant.
>
> I wonder how often a user will want to insert/erase individual elements in a
> continuous domain. If there was an implementation for continuous domains
> that did not allow this, users could take advantage of more efficient
> interval data structures that were all right-open. I don't think that would
> preclude the provision of an interface that supported inserting/erasing
> individual elements.

Thank you for insisting =)
I wasn't open to consider the possibility of sacrificing some
functionality that I had considered being fundamental in my design.
But since you were reiterating your point, I began to see that such a
sacrifice can be relatively small and enable, on the other hand, a use
case, with a simplified interval type and simplified interval
containers that would serve an important class of use cases while
leaving out a minor one.

The loss of generality here: We won't be able to express singleton
intervals for continuous domain_types  [x,x]. Every interval [x,y)
would be empty, if y<=x, or infinite, if x<y. So we would also have to
sacrifice the possibility to perform additions, subtraction etc. of
*element*, since elements would have to be expressed via closed
intervals [x,x].

This is interesting and I am going to consider this thoroughly. Since
I am going to rework my interval concept due to the suggestions of
Jeff Flinn and Luke Simonson anyway, I think I can integrate your
suggestion as well.

> I'm interested to read the report you mentioned on your plan for an interval
> tree implementation. Unfortunately though I'm going on holiday tomorrow so
> I'll miss the end of this review and perhaps your report.

I wish you nice holidays then :)

> Thanks for taking the time to submit ITL. It is proving very useful.

Thank you again for your review and your substantial contributions on
this discussion.

Joachim.