RE: [boost] Interval Library and comparison operators

From: David Bergman (davidb_at_[hidden])
Date: 2002-09-05 19:41:46

Doug,

I think the game was partly to come up with something not too unnatural
(since there are no really natural total ordering; and such attempts
would be too restricted to a specific problem area), as to have it as
the underlying order to use these intervals in STL (and similar
libraries, I know one specific library...) structures and algorithms.

The "real" relations (ordering and other) have to supplied by the
application developer.

Your "forall"-scheme is a reasonable one, but is not valid when it comes
to equivalence, since you would lose reflexivity... I actually could
argue that it is not a good one when it comes to other congruence
relations on the same grounds.

You are right, there should not be enforced ordering, such as subset
ordering, since application areas vary considerably. I would like to
have total ordering just to be able to put intervals in STL collections,
though... You see, there are other Devil's Pragmatists here ;-)

/David

-----Original Message-----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Douglas Gregor
Sent: Thursday, September 05, 2002 8:31 PM
To: boost_at_[hidden]
Subject: Re: [boost] Interval Library and comparison operators

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
_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost