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

Subject: Re: [boost] [Boost-users] [Review] ITL review starts today, February 18th
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2010-03-04 08:41:42

Hi John,

2010/3/4 John Reid <j.reid_at_[hidden]>:
> Joachim Faulhaber wrote:
>>
>> There has been a discussion on this point already.
>> http://permalink.gmane.org/gmane.comp.lib.boost.devel/199905
>>
>> For continuous data types it seems like interval bounds are needed as
>> data member. For intervals of integral types the bound_type can be a
>> static property. I will adapt the design in this point.
>>
>
> I assume most uses of the library will either be over discrete domains or
> continuous domains where the presence/absence of individual elements is
> irrelevant. In both cases right-open intervals are a natural way of
> implementing a solution. I haven't thought of an application over a
> continuous domain where it is necessary to cater for the inclusion/exclusion
> of individual elements. Do you know of one?

Personally, I haven't seen one. But the design of the ITL is based on
the premise that interval sets/maps are sets/maps of elements. I have
called this the fundamental view. Within this design it must always be
possible to add or subtract individual elements or element value pairs
to and from interval_sets/maps for all possible domain types.

Given this premise, I need to provide a correct implementation for
e.g. a subtraction of an element for continuous domain_types. Using
open interval bounds this implementation can be given. I'm not aware
of a good alternative.

> So it might be better to have
> both continuous and discrete intervals as right-open by default and to allow
> some mechanism whereby the user can choose to allow different runtime bound
> types if they need them.

I agree, that right-open intervals are suitable as default. But I am
afraid, for the continuous case, we can not guarantee that all
operations can maintain such an invariant. BTW existing interval
libraries e.g. boost::numeric::interval or FILIB++ work with closed
intervals. Subtract a closed interval from an interval set with
continuous domain_type  and you need open bounds.

> I have some further unrelated design questions/points:
>
> Is there a function to return the distance between two intervals?

hull(x,y).left_subtract(x).right_subtract(y).length();

I admit this is not extremely elegant...
I deliberately left functions and calculations out, that rely on
distance measures, because, in the general case ITL intervals and
interval containers only require an ordered domain type. So you can
use strings, sequences or other data types that do not implement a
distance measure.

> The default interval type is closed. Isn't right-open a more natural choice
> for most applications?

Good question ... I tried to change this in the past but encountered
problems with unsigned integral domain types that flipped to max_int
by singular applications of decrement operator -- in the current
implementation. May be I should check this point more thoroughly
again. I could get rid of the unloved unon<T>() meta function. ...

> It makes interval subtraction slightly simpler for
> example. I've always found right-open intervals an easier concept to think
> about and they make coding easier although this library removes any concerns
> about the latter.
>
> What is the meaning of the cardinality of a continuous interval? It seems to
> be defined to be 0? Why not make it only available for discrete domains?

Try this:

interval<double> x(0.0, 1.0);
if(x.cardinality() == numeric_limits<interval<double>::size_type>::infinity())
  cout << "cardinality is infinite\n";

for doubles a, b with a < b:
[a,b).cardinality() == infinity  but
{[a,a],[b,b]}.cardinality() == 2

Function cardinality() has been introduced to make clear: This
function yields the number of *elements*, and not the number of
iteratable entities in the interval container. For continuous
domain_types the cardinality of an interval container can be infinite
but it can be finite as well.

> I would like to see interoperability with other boost libraries such as
> boost.hash and boost.serialization. Both would be very useful for my current
> application.

I haven't checked this yet. There should be some kind of basic
interoperability through (segment) iterators and element_iterators.

> Why were the interval combining styles implemented as subclasses? Wouldn't
> the design have been more flexible if they were implemented as a policy
> template parameter? That's just my feeling about it, I don't feel qualified
> to offer a strong opinion.

Part of these things have an "historical" background. The lib started
with an OO design in a commercial company and has seen a lot of
refactorings, that tried to keep a kind of back compatibility.

>>>> - What is your evaluation of the documentation?
>>>
>>> Good. A tutorial would be a welcome addition. Some functions were
>>> undocumented, I'm assuming they're documented in the review version.
>>
>> The "handcrafted" documentation relates to the major interface of
>> overloaded functions and function templates. In order to keep that
>> short, more specific functions are only documented in the part of the
>> documentation that is generated from doxygen comments:
>>
>> http://www.joachim-faulhaber.de/boost_itl/doc/libs/itl/doc/html/interval_template_library_reference.html
>>
>> And yes, there may be few that have been forgotten. Please tell me,
>> which ones you missed specifically.
>
> I'll try to find them again.

Thanks and best regards,
Joachim