From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=0.4 required=5.0 tests=BAYES_00,FORGED_MUA_MOZILLA autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,f6c360ce344b2364 X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Received: by 10.68.219.170 with SMTP id pp10mr2891982pbc.1.1340910335215; Thu, 28 Jun 2012 12:05:35 -0700 (PDT) Path: l9ni30531pbj.0!nntp.google.com!news1.google.com!news4.google.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Niklas Holsti Newsgroups: comp.lang.ada Subject: Re: My Invention of "Bug Sort". Date: Thu, 28 Jun 2012 22:05:20 +0300 Organization: Tidorum Ltd Message-ID: References: <3852c348-a728-44ed-b065-c8a596c1e235@googlegroups.com><698085ff-6ca3-4a0e-b963-11bdcf11e6b5@googlegroups.com> <1u9ig9nnen59q$.ajozwlsekr7l.dlg@40tude.net> Mime-Version: 1.0 X-Trace: individual.net gXbQwcxR08ma2iQ0DXY9QgxQNMVpULGJk9aylDTSm4B4OGe9aQ574SJ1tiOygpbnlu Cancel-Lock: sha1:pa8ZOm7zfyPcvodaZshWn2hc5Ws= User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6; rv:12.0) Gecko/20120428 Thunderbird/12.0.1 In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Date: 2012-06-28T22:05:20+03:00 List-Id: On 12-06-27 01:29 , Randy Brukardt wrote: > "Simon Wright" wrote in message > news:m2sjdnyrlh.fsf@pushface.org... > ... >> I notice http://www.ada-auth.org/standards/12rm/html/RM-A-18.html#p5 - >> the last part of this is very terse. Wikipedia suggests that "(or both)" >> should be added. But I'm still baffled; and this paragraph appears to be >> for users, not implementers! > > This is the definition of "strict weak ordering", it is described as > precisely as possible. There's nothing really here for users; A user (programmer) using Ada.Containers and providing an actual Boolean function for "<" must make sure that this actual function obeys this rule; otherwise the container may not work as intended (as Randy said). So *in principle* users need to understand this. The first three rules (with names, even more terse) are simple to understand, because they are familiar properties from the usual complete ordering of numbers and strings: - irreflexive: x < x must be False for all values x. - asymmetric: if x < y is True, then y < x must be False. - transitive: if x < y is True, and y < z is True, then x < z must be True also. It is the fourth rule that is tricky, because it is important only when there are incomparable (but different) values x and y for which neither x < y nor y < x is True. If we use the symbol x # y for this "incomparability" relation between x and y, the fourth rule can be stated as: the relation # is an equivalence relation (a reflexive and transitive relation). The reflexivity of # follows directly from the irreflexivity assumed for "<"; the transitivity follows from the fourth rule for "<". For me, the rule "incomparability is an equivalence" is more intuitively understandable than the formulation in the RM. The RM rule is easier to state directly, however. That incomparability is an equivalence relation comes out in the name of the function Ada.Containers.Ordered_Maps.Equivalent_Keys. In practice, the fourth rule comes into play when the programmer-supplied actual "<" function depends on only a part of the compared values, for example, on only one "key" component of a record type. If two record values x and y have the same key, x.key = y.key, then neither is "<" than the other, but they can still be different if they have different values in their other components. *In practice* I expect most programmer-supplied "<" functions will compare one or a few "key" components of the operands. As long as each invocation of "<" compares the same components of the operands, in the same way, giving a complete ordering of these component values, the fourth rule holds and the container should work. So perhaps most users can get away with ignoring this rule. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ .