Блог

Я хотел бы избежать мутации входного списка итераторов 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 resu<
        }

        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 resu<
    }


}
 

Этот вопрос , по — видимому , основан на недоразумении … или два.

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

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

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

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

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

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

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

• An 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. Если ваши итераторы не удалось воссоздать (например, если вы повторяли исходный код, который нельзя было создать или «перемотать»), вы могли бы реализовать оболочку кэширующего итератора, которая запоминала все элементы в последовательности итераций и могла либо сбрасываться в начало последовательности, либо генерироватьновый итератор для воспроизведения последовательности. (Но здесь это было бы излишним.)