Generic sort

Joe Darcy joe.darcy at oracle.com
Sat Sep 13 16:53:07 UTC 2014


Hello,

On the topic of sorting floating-point values, note that the < operation 
does not impose a total ordering on floating-point values, primarily 
because of NaN. There is also the smaller issue of -0.0 being == to +0.0 
but the values being distinguishable.

A method like java.lang.Double.compare will serve your sorting needs though.

HTH,

-Joe

On 9/13/2014 9:26 AM, Paul Govereau wrote:
> Hello,
>
> I have been trying to write a fully generic SortedArrayList<any T>, 
> but I don't see a good way to implement sort. The difficulty has to do 
> with comparison. I am assuming that, like objects but unlike the 
> primitive types, value types will not have an implicit ordering. So, 
> objects and values must support an interface for comparison. For the 
> primitives, the bytecode needed for comparison is not easily 
> synthesized (e.g. do you choose fcmpl or fcmpg?).
>
> It seems that we need something like this:
>
> class SortedArrayList<any T> {
>   T[] array;
>   ...
>
>   <where ref T extends Comparable<T>>
>   int cmp(T x, T y) {
>      try return x.compareTo(y);
>      catch (NullPointerException e) {
>        return -1; // similar to fcmpl
>      }
>   }
>
>   <where val T extends Comparable<T>>
>   int cmp(T x, T y) {
>     return x.comapreTo(y);  // no null pointers.
>   }
>
>   <where T=int|char|byte|boolean>
>   int cmp(T x, T y) { return x < y; }  // if_icmplt
>   <where T=long>
>   int cmp(T x, T y) { return x < y; }  // lcmp; iflt
>   <where T=float>
>   int cmp(T x, T y) { return x < y; }  // fcmpl; iflt
>   <where T=double>
>   int cmp(T x, T y) { return x < y; }  // dcmpl; iflt
>
>   ...
> }
>
> Note, in this case SortedArrayList<Object> is not inhabited. Do we 
> think that the programmer must give an implementation for Object that 
> raises exceptions, or do we think the type system will disallow 
> instantiation with Object?
>
> Here is another example along the same lines.
>
> class Group<any T> {
>   ...
>   <where ref T extends Numeric<T>>
>   T add(T x, T y) { return x.add(y); } // invoke*
>
>   <where val T extends Numeric<T>>
>   T add(T x, T y) { return x.add(y); } // vinvoke*
>
>   <where prim T>
>   T add(T x, T y) { return x+y; }  // iadd/ladd/fadd/dadd
> }
>
> Group<BigInteger> OK reference type
> Group<Complex>    OK value type
> Group<int>        OK primitive
> Group<Object>     ?? not OK
>
> Paul



More information about the valhalla-dev mailing list