Boost logo

Boost :

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

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

#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

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();
      return narrow.indeterminate_value();

  template<typename T>
  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();
      return narrow.indeterminate_value();

  // etc....

  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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at