Как я могу предотвратить мутацию списка итераторов?

Я хотел бы избежать мутации входного списка итераторов tests другими. Я только хочу, чтобы другие работали на глубокой копии tests.

Как это может быть достигнуто в Java?

Вот пример, показывающий влияние мутации на tests. Обе части сортируют ввод. А вот во второй части сортировать нечего, так как мутация из первой части перебрала итераторы до конца.

Вы можете запустить следующий пример онлайн здесь: https://onlinegdb.com/NC4WzLzmt


import java.util.*;

public class ImmutableExample {
    public static void main(String[] args) {

        System.out.println("sort on demand");

        List<Iterator<Integer>> mutableTests = Arrays.asList(
                Arrays.asList(1, 2).iterator(),
                Arrays.asList(0).iterator(),
                Collections.emptyIterator()
        );

        List<Iterator<Integer>> tests = Collections.unmodifiableList(mutableTests);

        MergingIterator mergingIterator = new MergingIterator(tests);
        while (mergingIterator.hasNext()) {
            System.out.println(mergingIterator.next());
        }

        System.out.println("sort all at once");

        /*       uncomment the following will see the same result:*/
//        tests = Arrays.asList(
//                Arrays.asList(1, 2).iterator(),
//                Arrays.asList(0).iterator(),
//                Collections.emptyIterator()
//        );

        MergeKSortedIterators sol = new MergeKSortedIterators();
        Iterable<Integer> result = sol.mergeKSortedIterators(tests);

        for (Integer num : result) {
            System.out.println(num);
        }


    }
}

class PeekingIterator implements Iterator<Integer>, Comparable<PeekingIterator> {
    Iterator<Integer> iterator;
    Integer peekedElement;
    boolean hasPeeked;

    public PeekingIterator(Iterator<Integer> iterator) {
        this.iterator = iterator;
    }


    public boolean hasNext() {
        return hasPeeked || iterator.hasNext();
    }

    public Integer next() {
        int nextElem = hasPeeked ? peekedElement : iterator.next();
        hasPeeked = false;
        return nextElem;
    }

    public Integer peek() {
        peekedElement = hasPeeked ? peekedElement : iterator.next();
        hasPeeked = true;
        return peekedElement;
    }

    @Override
    public int compareTo(PeekingIterator that) {
        return this.peek() - that.peek();
    }


}


class MergingIterator implements Iterator<Integer> {
    Queue<PeekingIterator> minHeap;

    public MergingIterator(List<Iterator<Integer>> iterators) {
//        minHeap = new PriorityQueue<>((x, y) -> x.peek().compareTo(y.peek()));
        minHeap = new PriorityQueue<>();
        for (Iterator<Integer> iterator : iterators) {
            if (iterator.hasNext()) {
                minHeap.offer(new PeekingIterator(iterator));
            }
        }
    }

    public boolean hasNext() {
        return !minHeap.isEmpty();
    }

    public Integer next() {
        PeekingIterator nextIter = minHeap.poll();
        Integer next = nextIter.next();
        if (nextIter.hasNext()) {
            minHeap.offer(nextIter);
        }
        return next;
    }
}

class MergeKSortedIterators {


    public Iterable<Integer> mergeKSortedIterators(List<Iterator<Integer>> iteratorList) {
        List<Integer> result = new ArrayList<>();
        if (iteratorList.isEmpty()) {
            return result;
        }

        PriorityQueue<PeekingIterator> pq = new PriorityQueue<>();

        for (Iterator<Integer> iterator : iteratorList) {
            if (iterator.hasNext()) {
                pq.add(new PeekingIterator(iterator));
            }
        }

        while (!pq.isEmpty()) {
            PeekingIterator curr = pq.poll();
//            result.add(curr.peek());
// cannot use this one as hasNext() checks on `hasPeeked`
            result.add(curr.next());
            if (curr.hasNext()) {
                pq.add(curr);
            }
        }

        return result;
    }


}

Вы создаете API/библиотеку? Как насчет создания getter, в котором вы возвращаете глубокую копию tests и делаете tests приватным?

Sal 25.12.2020 00:39

Я хочу, чтобы люди не использовали предоставленные методы для своих входных данных, не осознавая, что предоставленные методы могут потенциально изменить их входные данные. @Сал

cpchung 25.12.2020 00:45

Обычно вы не можете копировать итераторы и не можете сделать их неизменяемыми. Они в значительной степени неизбежно изменчивы. Вы можете копировать коллекции, на которых они основаны.

Louis Wasserman 25.12.2020 02:21

Как насчет того, чтобы ваш API использовал Iterable вместо Iterator?

tgdavies 25.12.2020 03:48

@LouisWasserman, значит, List<Iterator<Integer>> tests =Collections.unmodifiableList(mutableTests); не может создать немодифицируемый список для List<Iterator<Integer>>? Интересно знать, что Java не может поймать это во время компиляции или во время выполнения. @tgdavies Я думаю о том, чтобы обернуть это List<Iterator<Integer>> в функцию, чтобы генерировать ввод всякий раз, когда это необходимо. Может быть, в этом и заключается идея generator в питоне?

cpchung 25.12.2020 05:27

Список не подлежит изменению. Итераторы будут модифицируемыми.

Louis Wasserman 25.12.2020 07:04
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
6
196
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Этот вопрос, кажется, основан на недоразумении ... или двух.

Как я могу предотвратить мутацию списка итераторов?

Вам нужно различать изменчивость списка и изменчивость элементов в списке. Я думаю, вы на самом деле спрашиваете о последнем. (И как таковой, список не имеет отношения к вопросу. Как мы увидим.)

Я хотел бы избежать мутации входного списка тестов итераторов другими.

Опять же, вы, кажется, спрашиваете о списке, но я думаю, что вы на самом деле хотите спросить об итераторах.

Я только хочу, чтобы другие запускали глубокую копию тестов.

Это означает, что вы хотите, чтобы итераторы были неизменными.

Вот проблема:

  • Iterator — это по своей сути объект с изменяемым состоянием. Действительно, невозможно реализовать next() без изменения объекта итератора.

  • Iterator объекты обычно не поддаются глубокому копированию. Обычно они не поддерживают clone() или общедоступные конструкторы и обычно не реализуют Serializable. (Действительно, если бы они были сериализуемыми, семантика сериализации/десериализации была бы проблематичной.)

Таким образом, ваша идея списка неизменяемых итераторов или списка, который (каким-то образом) создает глубокие копии итераторов, непрактична.


Вы прокомментировали:

Итак, List<Iterator<Integer>> tests = Collections.unmodifiableList(mutableTests); не может создать неизменяемый список для List<Iterator<Integer>>?

Ну да, может. Но это не решает проблему. Вам нужен список неизменяемых итераторов, а не неизменяемый список итераторов.


Возможные решения:

  1. Вы можете просто воссоздать список итераторов из их базовых коллекций для каждого запуска теста.

  2. Используйте Iterable вместо Iterator. Все типы коллекций, которые вы используете, реализуют Iterable, а третий итератор можно создать из пустого списка.

    List<Iterable<Integer>> tests = Arrays.asList(
            Arrays.asList(1, 2),
            Arrays.asList(0),
            Collections.emptyList()
    );
    
    // to use them ...
    
    for (Iterable<Integer> iterable : tests) {
        Iterator<Integer> iterator = iterable.iterator();
        // etc ...
    }
    
  3. Если бы ваши итераторы не могли быть воссозданы (например, если вы повторяли исходный код, который не мог быть создан или «перемотан»), вы, вероятно, могли бы реализовать кэширующую оболочку итератора, которая запоминала бы все элементы в последовательности итерации и могла бы либо сбросить до начала последовательности или сгенерировать новый итератор для воспроизведения последовательности. (Но это было бы излишеством здесь.)

Я вижу вашу точку зрения. Итератор изначально предназначен для изменения. Я вижу, как можно реализовать решение 1 и 3. Не могли бы вы привести несколько примеров решения 2?

cpchung 25.12.2020 14:55

Другие вопросы по теме