Как я могу повторно привязать шаблон? - PullRequest
Новая
       27

Как я могу повторно привязать шаблон?

0 голосов
/ 15 января 2020

Я реализую (единую сводную) быструю сортировку в 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);
    }

Это показалось мне хорошим. Первоначальное намерение - дать возможность выбрать любую логику секционирования c с помощью BiFunction, которая берет несортированный список и компаратор и возвращает индекс секционирования.

И я попытался добавить другой метод для Схема разбиения Lomuto . 

   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) part. 

    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) {

Как я все еще могу сделать PECS методом lomuto? ? extends E

Ответы [ 2 ]

4 голосов
/ 15 января 2020

Проблема в том, что <E> метода lomuto не является <E> метода sort. Вы будете sh компилятором выводить lomuto s E в качестве аргумента типа для параметра типа sort, так как два метода имеют два совпадающих параметра, но это не так, как работает вывод типа. Все, что видит компилятор, - это три аргумента для метода sort, List<? extends E>, Comparator<? super E> и выражение poly. Он будет вводить специальные типы вывода, которые затем будут распространяться на выражение 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;
         });
}

В качестве альтернативы вы можете предоставить явные типы аргументов для лямбда-выражения, чтобы оно больше не являлось поли-выражением: 

// 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;
         });
}
0 голосов
/ 15 января 2020

Я отвечаю за себя.

Как прокомментировал Андреас , ? extends E из List не является необходимым и даже неправильным.

Аргумент 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);
    }

И метод для конкретной c схемы разбиения должен выглядеть так. 

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