[PATCH] Postinstall script ordering in setup - take 3
Robert Collins
rbcollins@cygwin.com
Sat Mar 15 21:48:00 GMT 2003
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@cygwin.com>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
URL: <http://cygwin.com/pipermail/cygwin-apps/attachments/20030315/d4e66a2d/attachment.sig>
More information about the Cygwin-apps
mailing list