如何重新绑定通配符？

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

我觉得不错。初衷是给 select 任何带有 BiFunction 的分区逻辑一个机会，它采用未排序的列表和比较器以及 returns 分区索引。

我尝试为 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?

Answer 1

我正在为我自己回答。

正如Andreas评论的那样，List的? extends E没有必要，甚至是错误的。

list 参数同时具有 consumer 和 producer 的作用。

方法应该是这样的。

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

具体分区方案的方法应该是这样的。

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

Answer 2

问题是lomuto方法的<E>不是sort方法的<E>。您希望编译器将 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 表达式提供显式参数类型，这样它就不再是一个多边形表达式了：

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

如何重新绑定通配符？

How can I re-bound a wildcard?

java

generics

java-8

bounded-wildcard