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. ... I would have expected the containers to be templated on an interval type, negating the need for run-time determination of boundtype. With the current design, a rather heavy interval is required with it's boundtype data member.
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.
My domain type is a simple int, an index into a row of a sparse matrix. Our in-house Interval class is always right_open, so there is only the need for a begin and end value leading to minimal memory usage. The current library design requires me to convert between ITL intervals and my own application's intervals. I'd have like to be able to provide a model of an interval concept that the ITL container would use.
The breakthroughs of yesterday can be the obstacles of today. 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.
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 ? true : false; }
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?
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.
Along the same lines I've found little need for the mutators. An interval really only needs default and copy constructors, and one taking the upper and lower values. All mutations merely construct a new interval using calculated values and begin/end values from source intervals.
For a nice and simple integral_rightopen_interval<T> the mutating operations are pretty simple and you can work with a fairly minimal class. If you work with arbitrary interval bounds these computations can be quite nasty, so I prefer defining functions that hide the distinction of cases that one always gets wrong.
Perhaps bound_type should be refactored from an enum into a class that provides the facilities dealing with bound-ness. I'm always suspect of enum's that encode type information anyway. Jeff