java - 迭代多个 SortedSet 对象

Question

在 Java 中，我有几个 SortedSet 实例。我想遍历所有这些集合中的元素。一个简单的选择是创建一个新的 SortedSet，例如 TreeSet x，深度复制所有单独集合 y_1 的内容，.. ., y_n 使用 x.addAll(y_i) 加入其中，然后遍历 x。

但是有没有办法避免深拷贝呢？难道我不能只创建一个 SortedSet 类型的 View ，它会以某种方式封装所有内部集合的迭代器，但表现为一个集合吗？

Answer 1

I'd prefer an existing, tested solution, rather than writing my own.

我不知道有任何现有的解决方案可以完成这项任务，所以我花时间为您写了一个。我确信它还有改进的余地，因此请将其作为指南，而不是其他任何东西。

正如 Sandor 在 his answer 中指出的那样, 必须施加或假设一些限制。其中一个限制是每个 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);
            }
        }
    }
}

这个类的内部工作原理很容易掌握。该 View 保留了一个已排序集合的列表，即您要迭代的集合。它还需要用于比较元素的比较器(null 以使用它们的自然顺序)。您只能向 View 添加(不同的)集合。

其余的魔法发生在这个 View 的 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);
}