Happy Happy Joy Joy (was: On to Hydro)

[Mark S. Miller]

At 10:15 AM 8/17/00 , Mark S. Miller wrote:
>I admit the sort algorithm built into E's existing 
>container library does assume a StrictWeakOrdering (thanks for the 
>definitions page), ... So, yes, you've identified another design 
>error in the existing libraries.


At 10:34 AM 8/19/00 , Mark S. Miller wrote:
>Generalizing from pairs, Let's say we wish to write a sort function that 
>takes a set of elements and, if they are fully ordered, returns a sort of 
>them, but otherwise throws an exception.  Let's call this a full-sort. ...
>
>In order to blow up on a non-full ordering, all these full-sort functions 
>need to do is use compareTo as their comparator and blow up if the answer 
>isNaN.  ...


I now have the rare experience of retracting a bug report without having 
done anything.  I just looked, and the sort function built into E's current 
container library is already a comparison-based full-sort algorithm 
(quicksort) enhanced with the above test.  From FlexListImpl.java, in the 
partition part of the qsort function:

         //while we aren't fully partitioned
         while (nextBelow <= nextAbove) {
             Object specimen = a[nextBelow];
             double comp = func.run(specimen, pivot);
             if (comp <= 0.0) {
                 //don't need to swap, since it'll already be below
                 nextBelow++;
             } else if (comp > 0.0) {
                 a[nextBelow] = a[nextAbove];
                 a[nextAbove] = specimen;
                 nextAbove--;
             } else /* Double.isNaN(comp) */ {
                 throw new IllegalArgumentException
                     ("partial order not yet implemented");
             }
         }

Tested with an Elmer session:

     ? def NaN := 0.0/0.0
     # value: NaN
     
     ? [1.0, 0.0, -0.0, NaN, 2.0] sort
     # problem: <IllegalArgumentException: partial order not yet implemented>
     
     ? [1.0, 0.0, -0.0, 2.0] sort
     # value: [0.0, -0.0, 1.0, 2.0]

I also checked, and the publicly invokable sort methods (as above) return a 
new sorted list rather than sorting in place, so no partially sorted data 
structures are ever visible, even when we blow up.

Whether the error message is misleading or correct depends on whether we 
think sort should insist on a full-order (Tyler-style) or whether sort should 
eventually accept partial orders as input (Dean-style).


         Cheers,
         --MarkM