Re: [boost] [Review] ITL review starts today, February 18th

Subject: Re: [boost] [Review] ITL review starts today, February 18th
From: Jeff Flinn (TriumphSprint2000_at_[hidden])
Date: 2010-02-23 10:16:18

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