
Boost : 
Subject: Re: [boost] [Review] ITL review starts today, February 18th
From: Jeff Flinn (TriumphSprint2000_at_[hidden])
Date: 20100223 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 runtime 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
>> inhouse 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 boundness. I'm always suspect of
enum's that encode type information anyway.
Jeff
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk