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-22 18:29:40

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_at_[hidden]>:
> 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