RE: [boost] Interval Library and comparison operators

From: Guillaume Melquiond (gmelquio_at_[hidden])
Date: 2002-09-06 04:53:53

On Thu, 5 Sep 2002, David Bergman wrote:

> So, back to the ordering. Which one is the most natural choice? Hmm,
> there are obviously three orderings that popup:
[...]
> 3. The "complete position" ordering (have no proper name for it...),
> where
>      ' [a1, a2] < [b1, b2] ' iff ' a2 < b1 && a1 < b1 '
>    the extra conjunct ' a1 < b1 ' is needed to ensure that all end
> points are in the same chain, since we else can get A < B && B < A, if
> the points lie in a circle.

Two years ago, when an interval library was already discussed on this
mailing-list, some people suggested the library should handle intervals
with inverted bounds. However, during this review, it seems everybody has
agreed that the two bounds of an interval are ordered.

So I don't understand your point. We have 'a1 <= a2'; and the order, even
if it is a partial order, has the transitivity property. So we are sure
that 'a2 < b1' iff 'a2 < b1 && a1 < b1'.

> Partial orderings always have, and should have, these "undefined
> regions". What is the problem with that? Forcing those regions to be
> defined by either (1) introducing inconsistencies, such as defining '<='
> to be '!>', or (2) using obscure tribools will not help.

Concerning your first point, you are mistaken if you think defining '<='
to be '!>' was meant to force these regions to be defined. In fact, these
still exists some undefined region, since you can easily find two
intervals x and y such as we don't have 'x < y' nor 'x = y' nor 'x > y'
(and that's got nothing to do with the definition of '<=').

Using "obscure tribools" is really a great help when solving inequation
systems (it's my current business) or doing static analysis. For example,
you are trying to solve 'f(x) > 0' where x and 'f(x)' are intervals. There
are three possibilities. First, the comparison result may be
tribool::true; in that case, you know that each element of x is a solution
to the inequation. The result may also be tribool::false; in that case,
you are sure no element of x is a solution. Finally, the result may be
tribool::maybe and you need to do additional computations.

> We all have to realize that at least two of the orderings above are
> partial, there is not much we can do about it.
> 
> No matter what ordering chosen, '<=' should be regarded as syntactic
> sugar for '< || ==' in the case there exists an equivalence, such as
> here...

Yes, '<=' should probably be seen as '< || =='. But such a relation is
completely useless in my opinion. So I'm more and more driven to forsake
'<=' and '>='.

> I must be extremely stupid/ignorant not to see the problem by these
> fairly straight-forward definitions, so I hope someone will enlighten
> me, so I also can join the "tribool and complex ordering" choire ;-)
> 
> David

Regards,

Guillaume