[boost] Re: Proposal: Interval arithmetic library

From: Martin Schürch (mschuerch_at_[hidden])
Date: 2000-03-07 09:27:42

Thanks for feedback.

When I read the other mails about the intervall library, I think it would be
hard to combine the actual main
idea of intervall with the folloeing ones. But anyway here they are

Jens Maurer wrote:

> Martin Schürch wrote:
> > What I found in both areas often very useful are comparison operators
> > only with a real. e.g. [a,b] < 3.14.
>
> This is implemented.  Real numbers automatically convert to intervals,
> so [3,4] < 5 says "true" and [3,4] < 3.5 says "false".  Just to show
> the usefulness of <boost/operators.hpp> and save a few clock cycles, I
> also implemented these comparisons directly, so no conversion is
> necessary.

But are they exactly the same?
e.g. [1,2] <2.0 is false with the direct implementation:
    template<class RealType, class Traits>
    inline bool operator<(const interval<RealType, Traits>& x, double y)
    {
      return x.upper() < y;
    }

but is true when written like [1,2] < interval(2), because the constructor
introduces some tolerance.

I think when intervall should be used in other areas this lost of exact control
is one of the main problems.

>
>
> > Concept
> >     1: [1,100] < [20,60] <-> comparison is "set" - like
>
> Use the provided "interval::contains" member function for that.

ok

>
>
> >     2: [0,1] <[3,7] <-> Like your interval "<"
>
> I intended my interval class to be a drop-in replacement for "double"
> and give sensible results most of the time. That means, my interval "<"
> is defined so that all numbers of the first interval must be lower than
> the second.
>
> Please speak up what else you need.  I'm most interested in people
> actually trying to *use* this.

1) scale relative to a given value
 intervall scale( const  intervall& rng, double mirrorPt, double factor )
{
  return intervall(factor*(rng.lower()-mirrorPt), factor*(rng.upper()-mirrorPt)
);
 }

2) special case for scale-point == median()
intervall symmetric_scale( const intervall& rng, double factor )
  { return scale(rng, centre(rng), factor); }

3) bool do_overlap( I1, I2);
4)  intervall combine(const intervall& r1, const intervall& r2);
    precondition : do_overlap(r1,r2)

5)  intervall intersect(const intervall& r1, const intervall& r2);
precondition : do_overlap(r1,r2)

6) Not directly related:
What I found a very big help in my work, is to have a concept of a uniform
intervall intersection.
I have attached (not boost compatible) the code.
e.g.
intervall I(0, 1.0);
UnifIntervallSplit uis = UnifIntervallSplit::create_co(I, 150);
//represents a sequence (N=150) of uniform distance values, where uis[0] =0
(because of the _c) and
// uis[size()] would be1 (not index size()-1 because of the "o" .for(int i=0;
i<uis.size(); ++i) {
    //do something
    cout << uis[i];
}

_co means closed open. There are also _cc, _oc, _oo

The main idea is to handle the problem if the last (or first) point is on the
intervall border or not
once for ever.

The concept could also be expanded to support input_iterators

>
> > more specific functionality. Especially comparison is one of the often
> > disturbing points. (e.g. in your code : !(I1 < I2) && !(I2
> > < I1) does not imply (I1== I2)  can lead to problems)
>
> At least it's documented :-)  Anyway, is there a useful definition
> for interval "<" that does not have the above deficiency?  The
> "set_less_eq" also has the problem, for example with [1,3] <? [2,4].

Yes it also has the same problems, but propably the user does not expect as
much
from a function called "set_less_eq" as from "<"

>
> Of course we could define a "<" which compares the widths of the
> intervals, but this would probably only come in handy for map<>
> and set<>.  And for these, we can specialized std::less.

I think different things are needed in different situations. You are of course
right, that other behavior
can implemented with addidional functions. But the greatest advantage of the
operators are there easy
notation and that's also a great trap.

So why not seperate the different concepts by different namespaces.

e.g.

{
using namespace boost::interval_error_arithmetic;
    ...
    //you behaviour : your <, *=, ...
}
{
    using namespace boost::interval_centre_based;

    intervall I(0.1,0.5);
    I *= 2.0;    // [0.1, 0.5] -> [-0.1, 0.7]
    I += 7;    // shift of the range without introducing any tolerance

}

Martin