[std-interval] Interval comparison operators

[Fernando Cacciola]

Ron Avitzur wrote:

> Hello,
>
> If a programmer constructs an STL container of intervals which uses 
> operator< by default, it would be safer if that failed to compile (if 
> it has the wrong signature and there is no automatic conversion to 
> bool, for example), rather than if it compiled but sometimes failed at 
> run-time because either operator< or the automatic conversion to bool 
> threw an exception, which is not allowed to happen for comparisons 
> used in standard containers.
>
> Being able to write certainly(X < Y) makes for readable code. Allowing 
> if(X < Y) to compile with some default meaning introduces potential 
> for confusion and subtle run-time errors.
>
OK, you make a good point. I'm inclined to agree, but it must be noticed 
that removing the throwing conversion to bool altogether requires a new 
level of complexity in the library. Consider:

template< class T > sign_t det2(T a, T b, T c, T d) {
          T u = a * d, v = b * c;
          if (u < v ) return negative;
          if ( u > v ) return positive;
          return zero;
        }

sign_t good_det2(double a, double b, double c, double d) {
          try { return det2< interval<double> >(a, b, c, d); }
          catch(...) { return det2< exact >(a, b, c, d); }
        }

And let's imagine that there are no throwing conversions to bool (not 
even explicit for the sake of the argument).
Since there are no exceptions one should be able to, after changing 
det2() accordingly, get rid of the try block right?
But how does the "filtering" function knows that the det2() wasn't 
computed robustly without exceptions?
det2() just can't return sign_t anymore.

A solution, which is the one that CGAL uses, could be:

template< class T >
interval<sign_t> det2(T a, T b, T c, T d)
{
  T u = a * d, v = b * c;
   if (certainly(u < v) ) return negative;
   if (certainly(u > v) ) return positive;
   if (certainly(u == v) ) return zero ;
   return interval<sign_t>::empty();
}

sign_t good_det2(double a, double b, double c, double d)
{
  sign_t r = det2< interval<double> >(a, b, c, d);
  if ( is_empty(r)  )
    r = det2< exact >(a, b, c, d);
  return r ;
}

But as you can see this is more complicated: first, there has to be a 
discrete interval<E> and not just interval<bool>; second, the programmer 
must be much more explicitly aware of the trivalued logic.
For instance, if det2() is written as this it won't work correctly:

template< class T >
interval<sign_t> det2(T a, T b, T c, T d)
{
  T u = a * d, v = b * c;
   if (certainly(u < v) ) return negative;
   if (certainly(u > v) ) return positive;
   return zero ; // WRONG. It will return zero when in reality the 
intervals overlapped
}

OTOH, the presence of the throwing conversion to bool _and_ inertial<E> 
can also lead to bugs.
That is, say I love to be utterly explicit so I try to stay away from 
conversion to bool, but I write:

template< class T >
interval<sign_t> det2(T a, T b, T c, T d)
{
  T u = a * d, v = b * c;
   if (certainly(u < v) ) return negative;
   if (certainly(u > v) ) return positive;
   if (u == v ) return zero ; // HERE
   return interval<sign_t>::empty();
}

The intention is to avoid having to put det2() in a try block (that's 
the purpose of the wrapped result type), but I made a mistake: the 
conversion to bool in (u==v) will throw instead of fall thru the final 
return as was the intention.

So, without a throwing conversion to bool, the proposal must incorporate 
interval<E> for all discrete types besides bool in order to let the user 
actually get away without exceptions.

FWIW, in CGAL interval<E> is spelled uncertain<E> to make it more clear 
and it has it's own set of functions (that is, there are no arithmetic 
or comparison operators for uncertain<E>, is_empty() is spelled 
is_indeterminate(), etc...)

But this goes out of the scope of the proposal (unless you bring it into 
scope :)

Best

Fernando Cacciola