Re: My Invention of "Bug Sort".

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

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.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .