Re: My Invention of "Bug Sort".

["Randy Brukardt" <randy@rrsoftware.com>]

"Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
news:a53o7tF6gfU1@mid.individual.net...
> On 12-06-27 01:29 , Randy Brukardt wrote:
>> "Simon Wright"<simon@pushface.org>  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.

Thanks for the detailed and complete explanation given above. For the rest 
of you, Niklas was the person who reported that the rule given in the Ada 
2005 RM was insufficient. Thus we had to add the "strict weak ordering" rule 
(and definition) given in the Ada 2012 RM. It shouldn't be surprising that 
he understands it better than I do. ;-)

                           Randy.