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

Subject: Re: [boost] [Boost-users] [Review] ITL review starts today, February 18th
From: John Reid (j.reid_at_[hidden])
Date: 2010-03-04 12:37:09

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.

Regards,
John.