Re: [PATCH] Postinstall script ordering in setup - take 3

[Robert Collins <rbcollins at cygwin dot com>]

On Sat, 2003-03-15 at 09:33, Igor Pechtchanski wrote:
> Rob,
> > Your operator > and < appear to have a problem.
> >
> > foo: bar
> > gam: bar
> >
> > foo > gam    = false
> > gam < foo    = false
> > gam == foo   = false.
> >
> > I'd expect stl associative containers to choke on that.

> Not really.  I read up on that specifically.  stl containers only need a
> *partial* order.  What you're suggesting will create a total order.  Not
> an error, but overkill.  The sort function is supposed to be stable and
> keep the original order if the lessThan relation is undefined.  See
> <http://www.sgi.com/tech/stl/LessThanComparable.html>

=================

Consider the relation !(x < y) && !(y < x). If this relation is
transitive (that is, if !(x < y) && !(y < x) && !(y < z) && !(z < y)
implies !(x < z) && !(z < x)), then it satisfies the mathematical
definition of an equivalence relation. In this case, operator< is a
strict weak ordering. 

If operator< is a strict weak ordering, and if each equivalence class
has only a single element, then operator< is a total ordering.


Valid expressions
       Name
    Expression
Type requirements
   Return type
Less
x < y
 
Convertible to
bool
Greater
x > y
 
Convertible to
bool
Less or equal
x <= y
 
Convertible to
bool
Greater or equal
x >= y
 
Convertible to
bool
Expression semantics
     Name
  Expression
 Precondition
  Semantics
Postcondition
Less
x < y
x and y are in
the domain of
<
 
 
Greater
x > y
x and y are in
the domain of
<
Equivalent to
y < x [1]
 
Less or equal
x <= y
x and y are in
the domain of
<
Equivalent to
!(y < x) [1]
 
Greater or
equal
x >= y
x and y are in
the domain of
<
Equivalent to
!(x < y) [1]
 
Complexity guarantees
Invariants
Irreflexivity
x < x must be false.
Antisymmetry
x < y implies !(y < x) [2]
Transitivity
x < y and y < z implies x < z [3]
Models
      * int

Notes
[1] Only operator< is fundamental; the other inequality operators are
essentially syntactic sugar.

[2] Antisymmetry is a theorem, not an axiom: it follows from
irreflexivity and transitivity.

[3] Because of irreflexivity and transitivity, operator< always
satisfies the definition of a partial ordering. The definition of a
strict weak ordering is stricter, and the definition of a total ordering
is stricter still.
=================
foo: bar
gam: bar

gives
 
foo > bar
gam > bar
from above:
Axiom: ! (foo < gam) && (! gam < foo)
Axiom: ! (foo < gam) && (! gam < foo) && !(gam < z) && !(z < gam)

is  
!(foo < z) && (!z < foo)
ever false?
now, foo is < z when z depends on foo. !(foo < z) means z does not
depend on foo.
what do we know about z?
z does not depend on gam. !(gam < z)
gam does not depend on z  !(z < gam)
can z depend on foo and not on gam?
let z depend on foo:
so: z > foo.

now, !(gam < z) is still true. !(z < gam) is still true.
!(foo < z) is false.

Your operator  < is not a equivalence relation.

STL Containers will choke.

You fail on transitivity BTW.

Rob

-- 
Robert Collins <rbcollins at cygwin dot com>

Attachment: signature.asc
Description: This is a digitally signed message part