This is the mail archive of the
`cygwin-apps@cygwin.com`
mailing list for the Cygwin project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

Other format: | [Raw text] |

*From*: Robert Collins <rbcollins at cygwin dot com>*To*: cygwin-apps at cygwin dot com*Date*: 16 Mar 2003 08:48:44 +1100*Subject*: Re: [PATCH] Postinstall script ordering in setup - take 3*Organization*:*References*: <Pine.GSO.4.44.0303141729320.13439-100000@slinky.cs.nyu.edu>

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**

**Follow-Ups**:**Re: [PATCH] Postinstall script ordering in setup - take 3***From:*Robert Collins

**Partial vs. strict weak ordering (was Re: [PATCH] Postinstall script ordering in setup - take 3)***From:*Igor Pechtchanski

**References**:**Re: [PATCH] Postinstall script ordering in setup - take 3***From:*Igor Pechtchanski

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |