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

Question

我正在 Java 中实现(单枢轴)快速排序。

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

    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 选择任何分区逻辑的机会，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), hub) 部分提示。

    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？ ？扩展E？

Answer 1

问题是<E> lomuto的方法不是<E> sort的方法。您希望编译器推断 lomuto的E作为 sort 的类型参数的类型参数，因为这两个方法有两个一致的参数，但这不是类型推断的工作原理。编译器看到的只是 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;
         });
}