LaVOZs

The World’s Largest Online Community for Developers

'; java - How can I re-bound a wildcard? - LavOzs.Com

I'm implementing (single-pivot) Quicksort in Java.

I read there is a term of partitioning and I thought I can write a method with extensibility.

    public static <E> void sort(
            final List<? extends E> list,
            final Comparator<? super E> comparator,
            final BiFunction<List<? extends E>, Comparator<? super E>, Integer> partitioner) {
        if (list.size() < 2) {
            return;
        }
        final int p = partitioner.apply(list, comparator);
        sort(list.subList(0, p), comparator, partitioner);
        sort(list.subList(p + 1, list.size()), comparator, partitioner);
    }

It seemed good to me. The original intention is giving a chance to select any partitioning logic with the BiFunction which takes the unsorted list and the comparator and returns the partitioning index.

And I tried to add another method for Lomuto partition scheme.

   static <E> void lomuto(final List<? extends E> list,
                          final Comparator<? super E> comparator) {
        sort(list,
             comparator,
             (l, c) -> {
                 final E pivot = l.get(l.size() - 1);
                 int i = 0;
                 for (int j = 0; j < l.size() - 1; j++) {
                     if (c.compare(l.get(j), pivot) <= 0) {
                         swap(l, j, i++);
                     }
                 }
                 swap(l, l.size() - 1, i);
                 return i;
             });
    }

And the compiler complains at c.compare(l.get(j), pivot) part.

    Required type                                Provided
o1: capture of ? super capture of ? extends E    E
o2: capture of ? super capture of ? extends E    E

I found I can work around with

static <E> void lomuto(final List<E> list, final Comparator<? super E> comparator) {

How can I still do the PECS with lomuto method? ? extends E?

The problem is that the <E> of the lomuto method is not the <E> of the sort method. You wish the compiler to infer lomuto’s E as the type argument for sort’s type parameter, as the two methods have two congruent parameters, but that’s not how type inference works. All the compiler sees, are the three arguments for the sort method, a List<? extends E>, a Comparator<? super E>, and a poly expression. It will introduce special inference types which will then propagate to the poly expression.

When you use an explicit type argument to match the two E’s, the code compiles:

public static <E> void sort(
        final List<? extends E> list,
        final Comparator<? super E> comparator,
        final BiFunction<List<? extends E>, Comparator<? super E>, Integer> partitioner) {
    if (list.size() < 2) {
        return;
    }
    final int p = partitioner.apply(list, comparator);
    sort(list.subList(0, p), comparator, partitioner);
    sort(list.subList(p + 1, list.size()), comparator, partitioner);
}

static <E> void lomuto(final List<? extends E> list,
                      final Comparator<? super E> comparator) {
    ContainingClass.<E>sort(list,
         comparator,
         (l,c) -> {
             final E pivot = l.get(l.size() - 1);
             int i = 0;
             for (int j = 0; j < l.size() - 1; j++) {
                 if (c.compare(l.get(j), pivot) <= 0) {
                     swap(l, j, i++);
                 }
             }
             swap(l, l.size() - 1, i);
             return i;
         });
}

Alternatively, you can provide explicit argument types for the lambda expression, so it isn’t a poly expression anymore:

// keep the sort method unchanged

static <E> void lomuto(final List<? extends E> list,
                      final Comparator<? super E> comparator) {
    sort(list,
         comparator,
         (List<? extends E> l, Comparator<? super E> c) -> {
             final E pivot = l.get(l.size() - 1);
             int i = 0;
             for (int j = 0; j < l.size() - 1; j++) {
                 if (c.compare(l.get(j), pivot) <= 0) {
                     swap(l, j, i++);
                 }
             }
             swap(l, l.size() - 1, i);
             return i;
         });
}

I'm answering for my own.

As Andreas commented, the ? extends E of the List is not necessary and even wrong.

The list argument has both role of consumer and producer.

And the method should look look this.

    public static <E> void sort(
            final List<E> list,
            final Comparator<? super E> comparator,
            final BiFunction<? super List<E>, ? super Comparator<? super E>, Integer> partitioner) {
        if (list.size() < 2) {
            return;
        }
        final int p = partitioner.apply(list, comparator);
        assert p >= 0;
        assert p < list.size();
        sort(list.subList(0, p), comparator, partitioner);
        sort(list.subList(p + 1, list.size()), comparator, partitioner);
    }

And the method for a specific partition scheme should look like this.

    public static <E> void lomuto(final List<E> list,
                                  final Comparator<? super E> comparator) {
        sort(list,
             comparator,
             (l, c) -> {
                 assert !l.isEmpty();
                 final int p = l.size() - 1;
                 int i = 0; // the index to be swapped with the pivot
                 for (int j = 0; j < l.size() - 1; j++) {
                     if (c.compare(l.get(j), l.get(p)) <= 0) {
                         swap(l, j, i++);
                     }
                 }
                 swap(l, p, i);
                 return i;
             });
    }
Related
How do I efficiently iterate over each entry in a Java Map?
How can I concatenate two arrays in Java?
How do I read / convert an InputStream into a String in Java?
How do I generate random integers within a specific range in Java?
How can I create an executable JAR with dependencies using Maven?
Java Generics Wildcarding With Multiple Classes
How can I convert a stack trace to a string?
How do I convert a String to an int in Java?
How to fix 'android.os.NetworkOnMainThreadException'?
How to create a memory leak in Java?