How to convert a Comparable[] to a List<T>?

Question

I need to sort the data of type List, so I converted it to Comparable[] by means of map, then sorted, and now I need to convert it back to T and return data of type List. I tried to convert it to object and then to T, but it didn't work. Can anyone help plz? :)

@SuppressWarnings("rawtypes")
public static <T> void sort(List<T> data, Function<Object, Comparable> map) {
    Comparable[] a = convertDataToComparable(data, map);
    quickSort(a);
    //convertComparableToData(); //here
}

Answer 1

To solve this in your current code you need an additional class which is comparable by the mapped comparison key, but holds original elements as well:

private static class ComparableValue<T, K extends Comparable<K>> 
                        implements Comparable<ComparableValue<T, K>> {
    final K sortKey;
    final T origValue;

    public ComparableValue(K value, T origValue) {
        this.sortKey = value;
        this.origValue = origValue;
    }

    @Override
    public int compareTo(ComparableValue<T, K> o) {
        return sortKey.compareTo(o.sortKey);
    }
}

Now you can do the following:

public static <T, K extends Comparable<K>> void sort(List<T> data, 
                                                     Function<? super T, K> map) {
    @SuppressWarnings("unchecked")
    ComparableValue<T, K>[] a = new ComparableValue[data.size()];
    int i=0;
    for(T element : data) {
        a[i++] = new ComparableValue<>(map.apply(element), element);
    }
    quickSort(a);
    for(i=0; i<a.length; i++) {
        data.set(i, a[i].origValue);
    }
}

Note that I also fixed the signature of your method and a array to remove rawtypes (rawtypes are evil, don't use them).

Actually the whole problem rises from the fact that your sorting method is unable to accept the custom comparator. Were it supported, things would be much simpler:

public static <T, K extends Comparable<K>> void sort(List<T> data, 
                                                     Function<? super T, K> map) {
    @SuppressWarnings("unchecked")
    T[] array = (T[]) data.toArray();
    // Comparator.comparing appeared in Java-8
    quickSort(array, Comparator.comparing(map));
    for(int i=0; i<array.length; i++) {
        data.set(i, array[i]);
    }
}