Я хотел бы избежать мутации входного списка итераторов 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 использовал Iterable вместо Iterator?
@LouisWasserman, значит, List<Iterator<Integer>> tests =Collections.unmodifiableList(mutableTests);
не может создать немодифицируемый список для List<Iterator<Integer>>
? Интересно знать, что Java не может поймать это во время компиляции или во время выполнения. @tgdavies Я думаю о том, чтобы обернуть это List<Iterator<Integer>>
в функцию, чтобы генерировать ввод всякий раз, когда это необходимо. Может быть, в этом и заключается идея generator
в питоне?
Список не подлежит изменению. Итераторы будут модифицируемыми.
Этот вопрос, кажется, основан на недоразумении ... или двух.
Как я могу предотвратить мутацию списка итераторов?
Вам нужно различать изменчивость списка и изменчивость элементов в списке. Я думаю, вы на самом деле спрашиваете о последнем. (И как таковой, список не имеет отношения к вопросу. Как мы увидим.)
Я хотел бы избежать мутации входного списка тестов итераторов другими.
Опять же, вы, кажется, спрашиваете о списке, но я думаю, что вы на самом деле хотите спросить об итераторах.
Я только хочу, чтобы другие запускали глубокую копию тестов.
Это означает, что вы хотите, чтобы итераторы были неизменными.
Вот проблема:
Iterator
— это по своей сути объект с изменяемым состоянием. Действительно, невозможно реализовать next()
без изменения объекта итератора.
Iterator
объекты обычно не поддаются глубокому копированию. Обычно они не поддерживают clone()
или общедоступные конструкторы и обычно не реализуют Serializable
. (Действительно, если бы они были сериализуемыми, семантика сериализации/десериализации была бы проблематичной.)
Таким образом, ваша идея списка неизменяемых итераторов или списка, который (каким-то образом) создает глубокие копии итераторов, непрактична.
Вы прокомментировали:
Итак,
List<Iterator<Integer>> tests = Collections.unmodifiableList(mutableTests);
не может создать неизменяемый список дляList<Iterator<Integer>>
?
Ну да, может. Но это не решает проблему. Вам нужен список неизменяемых итераторов, а не неизменяемый список итераторов.
Возможные решения:
Вы можете просто воссоздать список итераторов из их базовых коллекций для каждого запуска теста.
Используйте 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 ...
}
Если бы ваши итераторы не могли быть воссозданы (например, если вы повторяли исходный код, который не мог быть создан или «перемотан»), вы, вероятно, могли бы реализовать кэширующую оболочку итератора, которая запоминала бы все элементы в последовательности итерации и могла бы либо сбросить до начала последовательности или сгенерировать новый итератор для воспроизведения последовательности. (Но это было бы излишеством здесь.)
Я вижу вашу точку зрения. Итератор изначально предназначен для изменения. Я вижу, как можно реализовать решение 1 и 3. Не могли бы вы привести несколько примеров решения 2?
Вы создаете API/библиотеку? Как насчет создания
getter
, в котором вы возвращаете глубокую копиюtests
и делаетеtests
приватным?