Hi Jeff! Congratulations =) Your are the first one to comment on my project in this review period. You are raising some good points about aspects of the design I stopped thinking about ... 2010/2/22 Jeff Flinn <TriumphSprint2000@hotmail.com>:
Hartmut Kaiser wrote:
Hi all,
The formal review of the Interval Template Library (ITL) starts today, February 18th, 2010 and will end February 27th, 2010. ITL is being developed by Joachim Faulhaber.
------------------------------------------------
About the library:
The Interval Template Library (ITL) is a library of interval containers that facilitates computations on collections of intervals and associated values. ... Hmm, not much discussion yet. While this is not my review I'll make a few comments.
I was able to port at least my necessary portions of split interval map to CodeWarrior 9.4 and was successful in using it to generate a column coverage graph of what is effectively the columns of possibly large sparse matrices.
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.
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. 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. 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.
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.
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. Thank you for your comments and for raising these interesting points. I will adapt the documentation and check, if an integral_rightopen_interval<T> class template can be used seamlessly. Best, Joachim