Generic sort

[Paul Govereau]

OK, to be clear, I think you are saying that yes, the programmer must 
provide an implementation that throws exceptions. This may be in 
SortedArrayList or through a library class like Comparator.

I think you are also saying that this would be the case for the value 
type layer as well. That is, something like:

   SortedArrayList<Complex>.cmp(a,b)

can throw a CCE where Complex is a value type. This seems to imply we 
need byte code instructions: vinstanceof and vcheckcast.

This seems strange, what am I missing?

Paul

On 09/13/2014 04:42 PM, Brian Goetz wrote:
> 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