Boost logo

Boost :

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at