Итератор для нескольких объектов SortedSet
В Java у меня есть несколько SortedSet экземпляров. Я хотел бы перебрать элементы всех этих наборов. Один простой вариант - создать новый SortedSet, такие как TreeSet x, глубоко скопируйте содержимое всех отдельных наборов y_1,..., y_n в это с помощью x.addAll(y_i)и затем перебрать x,
Но есть ли способ избежать глубокого копирования? Не могу ли я просто создать представление типа SortedSet который каким-то образом инкапсулирует итераторы всех внутренних наборов, но ведет себя как один набор?
4 ответа
Я предпочел бы существующее, проверенное решение, а не писать свое собственное.
Я не знаю ни одного существующего решения для выполнения этой задачи, поэтому я нашел время написать его для вас. Я уверен, что есть место для улучшения, так что примите это как руководство и ничего больше.
Как указывает Сандор в своем ответе, существуют некоторые ограничения, которые должны быть наложены или приняты. Одним из таких ограничений является то, что каждый SortedSet должны быть отсортированы относительно того же порядка, иначе нет смысла сравнивать их элементы без создания нового набора (представляющего объединение каждого отдельного набора).
Ниже следует мой пример кода, который, как вы заметите, является относительно более сложным, чем просто создание нового набора и добавление в него всех элементов.
import java.util.*;
final class MultiSortedSetView<E> implements Iterable<E> {
private final List<SortedSet<E>> sets = new ArrayList<>();
private final Comparator<? super E> comparator;
MultiSortedSetView() {
comparator = null;
}
MultiSortedSetView(final Comparator<? super E> comp) {
comparator = comp;
}
@Override
public Iterator<E> iterator() {
return new MultiSortedSetIterator<E>(sets, comparator);
}
MultiSortedSetView<E> add(final SortedSet<E> set) {
// You may remove this `if` if you already know
// every set uses the same comparator.
if (comparator != set.comparator()) {
throw new IllegalArgumentException("Different Comparator!");
}
sets.add(set);
return this;
}
@Override
public boolean equals(final Object o) {
if (this == o) { return true; }
if (!(o instanceof MultiSortedSetView)) { return false; }
final MultiSortedSetView<?> n = (MultiSortedSetView<?>) o;
return sets.equals(n.sets) &&
(comparator == n.comparator ||
(comparator != null ? comparator.equals(n.comparator) :
n.comparator.equals(comparator)));
}
@Override
public int hashCode() {
int hash = comparator == null ? 0 : comparator.hashCode();
return 37 * hash + sets.hashCode();
}
@Override
public String toString() {
return sets.toString();
}
private final static class MultiSortedSetIterator<E>
implements Iterator<E> {
private final List<Iterator<E>> iterators;
private final PriorityQueue<Element<E>> queue;
private MultiSortedSetIterator(final List<SortedSet<E>> sets,
final Comparator<? super E> comparator) {
final int n = sets.size();
queue = new PriorityQueue<Element<E>>(n,
new ElementComparator<E>(comparator));
iterators = new ArrayList<Iterator<E>>(n);
for (final SortedSet<E> s: sets) {
iterators.add(s.iterator());
}
prepareQueue();
}
@Override
public E next() {
final Element<E> e = queue.poll();
if (e == null) {
throw new NoSuchElementException();
}
if (!insertFromIterator(e.iterator)) {
iterators.remove(e.iterator);
}
return e.element;
}
@Override
public boolean hasNext() {
return !queue.isEmpty();
}
private void prepareQueue() {
final Iterator<Iterator<E>> iterator = iterators.iterator();
while (iterator.hasNext()) {
if (!insertFromIterator(iterator.next())) {
iterator.remove();
}
}
}
private boolean insertFromIterator(final Iterator<E> i) {
while (i.hasNext()) {
final Element<E> e = new Element<>(i.next(), i);
if (!queue.contains(e)) {
queue.add(e);
return true;
}
}
return false;
}
private static final class Element<E> {
final E element;
final Iterator<E> iterator;
Element(final E e, final Iterator<E> i) {
element = e;
iterator = i;
}
@Override
public boolean equals(final Object o) {
if (o == this) { return true; }
if (!(o instanceof Element)) { return false; }
final Element<?> e = (Element<?>) o;
return element.equals(e.element);
}
}
private static final class ElementComparator<E>
implements Comparator<Element<E>> {
final Comparator<? super E> comparator;
ElementComparator(final Comparator<? super E> comp) {
comparator = comp;
}
@Override
@SuppressWarnings("unchecked")
public int compare(final Element<E> e1, final Element<E> e2) {
if (comparator != null) {
return comparator.compare(e1.element, e2.element);
}
return ((Comparable<? super E>) e1.element)
.compareTo(e2.element);
}
}
}
}
Внутренняя работа этого класса проста для понимания. Представление содержит список отсортированных наборов, которые вы хотите перебрать. Также нужен компаратор, который будет использоваться для сравнения элементов (null использовать их естественный порядок). Вы можете добавлять только (различные) наборы в представление.
Остальная магия происходит в Iterator этого взгляда. Этот итератор хранит PriorityQueue элементов, которые будут возвращены из next() и список итераторов из отдельных наборов.
Эта очередь всегда будет содержать не более одного элемента в наборе и отбрасывает повторяющиеся элементы. Итератор также отбрасывает пустые и использованные итераторы. Короче говоря, это гарантирует, что вы пройдете каждый элемент ровно один раз (как в наборе).
Вот пример того, как использовать этот класс.
SortedSet<Integer> s1 = new TreeSet<>();
SortedSet<Integer> s2 = new TreeSet<>();
SortedSet<Integer> s3 = new TreeSet<>();
SortedSet<Integer> s4 = new TreeSet<>();
// ...
MultiSortedSetView<Integer> v =
new MultiSortedSetView<Integer>()
.add(s1)
.add(s2)
.add(s3)
.add(s4);
for (final Integer i: v) {
System.out.println(i);
}
Я не думаю, что это возможно, если это не какой-то особый случай, который потребует индивидуальной реализации.
Например, возьмем следующие два компаратора:
public class Comparator1 implements Comparator<Long> {
@Override
public int compare(Long o1, Long o2) {
return o1.compareTo(o2);
}
}
public class Comparator2 implements Comparator<Long> {
@Override
public int compare(Long o1, Long o2) {
return -o1.compareTo(o2);
}
}
и следующий код:
TreeSet<Long> set1 = new TreeSet<Long>(new Comparator1());
TreeSet<Long> set2 = new TreeSet<Long>(new Comparator2());
set1.addAll(Arrays.asList(new Long[] {1L, 3L, 5L}));
set2.addAll(Arrays.asList(new Long[] {2L, 4L, 6L}));
System.out.println(Joiner.on(",").join(set1.descendingIterator()));
System.out.println(Joiner.on(",").join(set2.descendingIterator()));
Это приведет к:
5,3,1
2,4,6
и бесполезен для любого Comparator действующий на головной элемент данного Iterators, Это делает невозможным создание такого общего решения. Это возможно, только если все наборы отсортированы с использованием одного и того же ComparatorОднако это не может быть гарантировано и обеспечено любой реализацией, которая принимает SortedSet объекты, заданные несколько SortedSet экземпляры (например, все, что может принять SortedSet<Long> экземпляры, приняли бы оба TreeSet объекты).
Чуть более формальный подход:
Дано y_1,..,y_n все отсортированные наборы, если:
- пересечение этих множеств пустое множество
- и есть порядок наборов, где для каждого
y_i, y_(i+1)установить это правда, чтоy_i[x] <= y_(i+1)[1]где х - последний элементy_iотсортированный набор и<=означает сравнительную функцию
тогда наборы y_1,..,y_n могут быть прочитаны друг за другом как SortedSet.
Теперь, если любое из следующих условий не выполнено:
- если первое условие не выполняется, то определение
Setне выполняется, поэтому не может бытьSetпока глубокое слияние копий не будет завершено и дублированные элементы не будут удалены (см. " Установка javadoc", первый абзац:
множества не содержат пары элементов e1 и e2, для которых e1.equals(e2)
- второе условие может быть обеспечено только с использованием того же компаратора
<=функция
Первое условие является более важным, потому что быть SortedSet подразумевает быть Setи если определение быть Set не может быть выполнено, то более сильные условия SortedSet определенно не может быть выполнено.
Существует возможность того, что может существовать реализация, которая имитирует работу SortedSet, но это точно не будет SortedSet,
Если вас интересует точная копия объектов, переданных в метод TreeSet # addAll, вам не следует этого делать. Javadoc не указывает, что это глубокая копия (и, конечно, так бы и было, если бы это было так)... и реализация OpenJDK также не показывает этого. Нет копий - просто дополнительные ссылки на существующий объект.
Поскольку глубокое копирование не является проблемой, я думаю, что беспокойство по этому поводу, если вы не определили это как конкретную проблему производительности, попадает в категорию преждевременной оптимизации.
com.google.common.collect.Sets# союз из Гуавы добьется цели. Возвращает неизменяемое представление объединения двух множеств. Вы можете повторить это. Возвращенный набор не будет отсортирован. Затем вы можете создать новый отсортированный набор из возвращенного набора (new TreeSet() или же com.google.common.collect.ImmutableSortedSet, Я не вижу API для создания представления данного набора как отсортированного набора.