🧠 Хитрая Java-задача: «Клонируемый итератор с разделяемым буфером

🧠 Хитрая Java-задача: «Клонируемый итератор с разделяемым буфером»

Уровень: 💥 продвинутый (Java 17+)

🎯 Задача

Реализуйте класс CloneableIterator<T>, который:

✔ Оборачивает любой Iterator<T>

✔ Позволяет создать независимые клоны, каждый из которых продолжает чтение с текущего места

✔ Поддерживает *эффективное* разделение буфера: память O(k), где k — число активных клонов

✔ Не дублирует данные, не загружает всё в память и работает потокобезопасно (не обязательно synchronized, но без багов)

📌 Пример

CloneableIterator<Integer> base = new CloneableIterator<>(List.of(10, 20, 30, 40).iterator());

Iterator<Integer> it1 = base.clone();

Iterator<Integer> it2 = base.clone();

System.out.println(it1.next()); // 10

System.out.println(it1.next()); // 20

System.out.println(it2.next()); // 10

System.out.println(it2.next()); // 20

System.out.println(it2.next()); // 30

💡 Ограничения

• Нельзя просто скопировать Iterator или заранее собирать весь список

• Память должна освобождаться, если часть буфера уже не нужна (все клоны её прошли)

• Только стандартная библиотека Java (можно использовать Deque, ArrayList, WeakReference, Optional, AtomicInteger и т.д.)

🔍 Подсказка по архитектуре

• Ведите общий буфер типа Deque<T>

• Каждому клону сопоставляется индекс, отслеживающий позицию в буфере

• По мере продвижения всех клонов — чистим буфер до минимального индекса

• Продумайте синхронизацию доступа, если хотите потокобезопасную версию

✅ Прототип реализации (без потокобезопасности)

import java.util.*;

public class CloneableIterator<T> {

private final Iterator<T> source;

private final List<T> buffer = new ArrayList<>();

private final List<Integer> positions = new ArrayList<>();

public CloneableIterator(Iterator<T> source) {

this.source = source;

}

public Iterator<T> clone() {

int index = 0;

positions.add(index);

int myId = positions.size() - 1;

return new Iterator<T>() {

private int pos = positions.get(myId);

@Override

public boolean hasNext() {

fillBuffer();

return pos < buffer.size();

}

@Override

public T next() {

fillBuffer();

if (pos >= buffer.size()) {

throw new NoSuchElementException();

}

T value = buffer.get(pos++);

positions.set(myId, pos);

cleanupBuffer();

return value;

}

private void fillBuffer() {

if (!source.hasNext()) return;

while (buffer.size() <= pos && source.hasNext()) {

buffer.add(source.next());

}

}

private void cleanupBuffer() {

int min = Collections.min(positions);

if (min > 0) {

buffer.subList(0, min).clear();

for (int i = 0; i < positions.size(); i++) {

positions.set(i, positions.get(i) - min);

}

}

}

};

}

}

🚀 Что можно улучшить

• Потокобезопасность (ConcurrentLinkedDeque, AtomicInteger)

• Освобождение ресурсов при уничтожении клонов (WeakReference)

• Поддержка remove()

• Версия Stream<T> с spliterator() или flatMap()

@javarush