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@mail.cryst.bbk.ac.uk>:
Joachim Faulhaber wrote:
2010/3/4 John Reid <j.reid@mail.cryst.bbk.ac.uk>:
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.