Re: [boost] Interval Library and comparison operators

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-09-05 19:30:55

On Thursday 05 September 2002 02:41 pm, David Bergman wrote:
> So, back to the ordering. Which one is the most natural choice? Hmm,
> there are obviously three orderings that popup:
>
> 1. The lexicographic (yes, that is a properly chosen name) ordering,
> where
>      ' [a1, a2] < [b1, b2] ' iff ' a1 < b1 || a1 == b1 && a2 < b2 '
>
> 2. The (strict; some people are strict about strictness ;-) subset
> ordering, where
>      ' A < B ' iff A is a subset of B; when all end points reside in the
> same chain, this is reduced to ' b1 <= a1 && a2 <= b2 && !(A == B) '
>
> 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.

Playing a bit of Devil's Pragmatist here:

Will someone vouch for applications of the interval library that require these 
orderings?

I can vouch for the need for the definition:
  [a,b] RelOp [c,d] := x RelOp y for all (x, y) where a <= x <= c, b <= y <= d

In the area of static analysis, this is the definition I would need. I also 
need those obscure tribools when either x RelOp y is indeterminate or when 
x1 RelOp y1 .and. (.not. x2 RelOp y2).

There may be a billion different orderings to choose from, but unless these 
orderings are _useful_ in some application, we really shouldn't consider them 
for a library.

For instance, I'm not convinced I see any reason for the subset ordering. If 
you want to perform subset comparisons then you probably don't want 
intervals: you want sets that happen to have a contiguous representation 
within numerical bounds.

        Doug