2010/2/23 Jeff Flinn <TriumphSprint2000@hotmail.com>:
Joachim Faulhaber wrote:
Hi Jeff!
...
The Interval Template Library (ITL) is a library of interval containers that facilitates computations on collections of intervals and associated values.
...
To represent the four boundtypes only 2 bits are required, which are currently coded into one byte. But yes, due to memory alignment the boundtype finally covers 4 bytes which is, using an interval<int>, 50% more than what you would like to have.
Yes, I can foresee needing maps with over 10M intervals in the not too distant future. [...]
Basic to the design of itl::interval was the desire to make the library as generic as possible. The "key_type", which I have named "domain_type" of intervals and interval containers are supposed to be not limited to integral types or even numeric types. I wanted to be able to have e.g. interval_set<int> but also interval_set<double> interval_set<rationale<int>> and even interval_set<string>. And one of the breakthroughs of the design was the realisation that this could be done using interval bounds.
Yes, I agree bound_type is an important concept. The question is whether an interval's bound_type should be a runtime data member or part of the interval's type. My inclination is the latter. I would think that the problem domain would be dealing with only intervals of a particular bound_type, hence a container would be templated on the bound_type in addition to the domain and co domain types. If there is a need for mixed bound_types within a single problem domain, there could be a run time bound_type. But I shouldn't have to pay those run time costs if my problem domain doesn't need to.
Here is an example demonstrating that different bound_types may occur at run time. // Pseudo code: interval_set<double> x = {[0.0, 2.0)}; x -= 1.0; // or equivalently x -= [1.0, 1.0]; // x now contains: // x == {[0.0, 1.0),(1.0, 2.0)}
Since we were using ITL in a context where the memory demand of the bound_type member never was a problem, I never asked myself the question if there could be the desire for a simpler interval template.
As a generic container I think scalability is very important.
So the first moment I thought you caught me on a serious design flaw. But after browsing the code I am fairly sure, that I can provide what you desire.
(1) There is a template template parameter Interval already that requires the domain_type and an ordering on the domain_type.
(2) For a simpler interval class template like e.g. integral_rightopen_interval<T> the implementation will then be probably simpler or even trivial. e.g:
bool is(bound_type bt){ return bt==left_open; }
and since the bound type is always the same, is does not have to be a class member anymore.
If the bound_type is always the same, why would the container or the algorithms ever ask for bound_type discrimination?
as the example above shows, for continuous domain_types bound_types of intervals in interval containers can be different at run time. All 4 types [..], [..), (..], (..) can be generated by application of operations. So you need a function that selects or tests them if you want to print an interval container, for instance. The current implementation of itl::interval is a "one size fits all" type of class template that has been so handy, that I never considered to really use a different one. Meanwhile, I have implemented an integral_interval<T> that does what you need and it works correctly within interval containers. So, yes, you can use ITL with different and also smaller interval types. Still, it turns out, that the interface, that has to be implemented is not as minimal as would be desired. Currently I think, that there are two important kinds of intervals. Intervals of integral types and intervals of continuous types. The latter need IMO dynamic border_type info. The former don't and are much simpler to implement. So I think I will provide two interval templates as defaults for the Interval template parameter, that are set at compile time dependent on the type traits of the domain_type of the interval container. Both implement the same common interface that is used in algorithms. But intervals of integral types need less effort, if the user wants to customize her own.
I wasn't able to find any description of the class invariants for interval.
Can be added.
For example in our own Interval class the upper/end value must be greater than/equal to the lower/begin value which is a precondition to the constructor taking a pair of domain values. We do provide a static makeNormalized method to produce a proper interval when the order of the domain arguments is unknown, which is not very often in our usage so you don't pay that cost. In my case I hadn't the need for 'reversed' intervals, but I could see that being required for some use cases. Does ITL handle that?
Nope.
Perhaps directionality should be another concept of intervals.
To be honest, I'm not very fond of this idea.
Thank you again, Jeff. Best regards, Joachim