Generic sort
Paul Govereau
paul.govereau at oracle.com
Sat Sep 13 22:29:58 UTC 2014
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
More information about the valhalla-dev
mailing list