Generic sort

Paul Govereau paul.govereau at oracle.com
Sat Sep 13 16:26:50 UTC 2014


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