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-04 12:40:58

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.
>
> 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.
>
> Thanks for taking the time to submit ITL. It is proving very useful.
>
Thanks, that good to hear :)

Sorry I am already late ;-/

More on the tomorrow.

Cheers,
Joachim