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

Subject: Re: [boost] [Review] ITL review starts today, February 18th
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-02-23 15:56:30

2010/2/23 Jeff Flinn <TriumphSprint2000_at_[hidden]>:
> 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