Generic sort

[Brian Goetz]

Let's ignore for now whether conditional methods can be conditioned on 
"T extends U".  (Being able to do so adds complexity to the meet rule, 
among other issues.)

It is likely that common operations like comparison or array creation 
can be "pre-peeled" into library code so this logic does not have to be 
duplicated in user code (which just pushes the problem into our code.)

Existing sorted data structures do not impose the T-extends-Comparable 
constraint; they just risk throwing CCE, or require that you provide a 
Comparator.  The latter route might be better; just require a 
Comparator<T> all the time.

On 9/13/2014 12:26 PM, 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