# 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;
});
}
``````

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;
});
}
``````