Re: [boost] Interval Library and comparison operators

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-09-05 11:06:21

On Thursday 05 September 2002 04:31 am, Guillaume Melquiond wrote:
> Another solution would be to add a third function to the comparison policy
> in order for the library to correctly handle <= and >=.
>
> Please give (or remind) your opinion on these problems. The comparison
> operators are probably the most awkard point of this library; and I hope
> this thread will allow a consensus to emerge, and that no reviewer will
> afterwards raise the comparison operators issue as a reason to reject the
> library.

I'm backing away from my proposal to remove all comparison policies. If the 
difference between the policies were merely the way in which the 
indeterminate case is handled, as it first appeared, then I would still think 
that tribool without comparison policies would be the right approach. 
However, it's hard to get around the fact that i <= j can mean either a 
subset check, <= holds for all pairs, <= holds for any pair, etc. depending 
on the domain in which the interval library is used. As soon as we select one 
of these semantics to implement in the library, we've excluded domains that 
need the other sets of semantics. Even explicit comparison functions don't 
help all that much: posle vs. cerle tells us the resolution of the 
indeterminate case, but not the underlying semantics of the operation.

It seems there are really only two options here:
  1) Don't support any comparison operators, or
  2) Use comparison policies

If we were to choose the former, users will write their own versions of 
operators <, <=, >, >=, ==, !=. Inevitably, we will come across a project 
that has two different meanings of operator< for intervals (but the function 
signature will be the same), leading to ODR violations and confused 
programmers.

Comparison policies do have some benefit over letting users define the 
operators directly. The type signatures will be distinct for different 
semantics (because the name of the semantics is embedded in the interval 
instantiation as a comparison policy argument), so that interval types with 
different comparison semantics can coexist. Inevitably, some users will get 
bitten because they assume a particular comparison semantics that is not the 
actual comparison semantics used, but this is the price we pay when we expose 
policies directly to the user. 

I see two issues that comparison policies are trying to solve:
  1) What to do with indeterminate comparison results
  2) What to do with different comparison semantics

#1 is already addressed in the library with compare_certainly, 
compare_possibly, and compare_full. Sylvain gave a convincing argument for 
compare_full, and I think we have a convincing argument for a 3-state result. 
Is there a convincing argument for allowing both compare_certainly and 
compare_possibly? 

#2 is partially addressed in the library. Comparison policies allow the 
semantics to differ for < and ==, but do not allow for semantics where !< and 
>= may be different. I think this axis of the comparison policies should be 
extended so that comparison policies supply functions for _all_ relational 
operators.

So why not organize the policies along these two axes? Have comparison 
semantics policies and boolean narrowing policies separately, and compose 
them for use in comparing intervals?

Boolean narrowing policies would define the return type of comparisons and 
handle the narrowing from 3-state boolean values to 2-state boolean values 
(if needed) or translate from the interval library's 3 states into the 3 
states for a 3-state boolean type. Some models of this concept might be:

template<typename Function>
struct narrow_user_defined
{
  typedef bool result_type;
  inline bool false_value() { return false; }
  inline bool true_value() { return true; }
  inline bool indeterminate_value() { Function f; return f(); }
};

struct narrow_tribool
{
  typedef tribool result_type;
  inline tribool false_value() { return tribool(false); }
  inline tribool true_value() { return tribool(true); }
  inline tribool indeterminate_value() { return tribool(indeterminate); }
};

Then the comparison semantics policies would be parameterized by the narrowing 
policy, e.g.,

template<typename Narrow>
struct all_pairs_semantics
{
  typedef typename Narrow::result_type result_type;

  template<typename T>
  result_type less_than(const T& xl, const T& xu, const T& yl, const T& yu)
  { 
    if (xu < yl)
      return narrow.true_value();
    else if (yu < xl)
      return narrow.false_value();
    else
      return narrow.indeterminate_value();
  }

  template<typename T>
  result_type 
  less_or_equal(const T& xl, const T& xu, const T& yl, const T& yu)
  {
    if (xu <= yl)
      return narrow.true_value();
    else if (yu < xl)
      return narrow.false_value();
    else
      return narrow.indeterminate_value();
  }

  // etc.... 

private:
  Narrow narrow;
};

The above definition will also work when comparison of Ts returns a 3-state 
boolean type that evalutes "certainly" in a boolean context.

        Doug