Generic sort

[Remi Forax]

On 09/14/2014 12:29 AM, Paul Govereau wrote:
> 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

The idea is more that SortedArrayList is written like this.
public class SortedArrayList<any T> {
   private /*true*/ final Comparator<T> comparator;

   public SortedArrayList(Comparator<T> comparator) {
     this.comparator = Objects.requireNonNull(comparator);
   }
   ...
}

with a String:
   new SortedArrayList<String>(String::compareTo)
with an int
    new SortedArrayList<int>(Integer::compare)

if T is an object and the comparator is not able to compare T with 
itselft, the comparator code
(exactly either the bridge inserted by the compiler or the code of the 
lambda proxy) will throw a CCE.

BTW, what Comparator<? super T> means if T is declared any T ?
Is it illegal because Comparator should use declaration site variance ?

Rémi

>
> 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