java - 如何重新绑定(bind)通配符？

我正在用Java实现（单轴）Quicksort。

我读到有一个分区术语，我认为我可以编写具有扩展性的方法。

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

对我来说似乎很好。最初的意图是利用BiFunction选择任何分区逻辑，该逻辑采用未排序的列表和比较器并返回分区索引。

我尝试为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;
             });
    }

编译器抱怨c.compare(l.get(j), pivot)部分。

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

我发现我可以解决

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

如何仍然使用lomuto方法进行PECS？ ? extends E？

最佳答案

问题是<E>方法的lomuto不是<E>方法的sort。您希望编译器将lomuto的E用作sort的type参数的类型参数，因为这两个方法具有两个相同的参数，但这不是类型推断的工作原理。编译器看到的只是sort方法的三个参数，List<? extends E>，Comparator<? super E>和多边形表达式。它将引入特殊的推断类型，然后将其传播到poly表达式。

当您使用显式类型参数来匹配两个E时，代码将编译：

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

另外，您可以为lambda表达式提供显式的参数类型，因此它不再是poly表达式：

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