Iterator over multiple SortedSet objects
In Java, I have multiple instances SortedSet
. I would like to iterate over elements from all of these sets. One simple option is to create a new one SortedSet
, such as TreeSet x
, deep copy the contents of all individual sets y_1
, ..., y_n
into it with x.addAll(y_i)
, and then loop over x
.
But is there a way to avoid deep copy? Can't I just create a type view SortedSet
that somehow encapsulates the iterators of all the inner sets, but behaves like one set?
source to share
I would prefer an existing, tested solution rather than writing my own.
I do not know of any existing solution for this task, so I took the time to write for you. I'm sure there is room for improvement there, so take this as a guide and nothing else.
As Sandor notes in his answer , there are some restrictions that need to be imposed or accepted. One such limitation is that each SortedSet
must be sorted relative to the same order, otherwise it makes no sense to compare their elements without creating a new set (representing the union of each individual set).
Here follows my sample code, which you have noticed is relatively more complex than just creating a new set and adding all the elements to it.
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);
}
}
}
}
The inner workings of this class are easy to understand. The view stores a list of sorted sets, the ones you want to iterate over. It also needs a comparator to be used to compare the elements ( null
in order to use their natural order). You can only add (different) sets to a view.
The rest of the magic happens in Iterator
this performance. This iterator stores the PriorityQueue
items to be returned from next()
, and a list of iterators from individual sets.
This queue will have at all times at most one item per set and discards duplicate items. The iterator also discards empty and used iterators. In short, it makes sure that you traverse each element exactly once (as in a set).
Here's an example on how to use this class.
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);
}
source to share
I don't think this is possible unless it is a special case that would require a special implementation.
For example, take the following two comparators:
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);
}
}
and the following code:
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()));
This will lead to:
5,3,1 2,4,6
and is useless for anyone Comparator
working on the head element of the given one Iterators
. This makes it impossible to create such a general solution. This is only possible if all sets are sorted using the same Comparator
, however this cannot be guaranteed and provided by any implementation that accepts objects SortedSet
given multiple instances SortedSet
(e.g. anything that will accept instances SortedSet<Long>
will accept both objects TreeSet
).
A slightly more formal approach:
Given y_1,..,y_n
all sorted sets if:
- the intersection of these sets is empty
- and there is an ordering of sets, where for each set it
y_i, y_(i+1)
is true thaty_i[x] <= y_(i+1)[1]
, where x is the last element of the sorted sety_i
, and<=
means the comparative function
then the sets y_1,..,y_n
can be read one after the other as SortedSet.
Now, if one of the following conditions is not met:
- If the first condition is not met, then the definition of a is
Set
not met, so it cannot beSet
until a deep merge is done and the duplicate elements are removed (see Install javadoc, first paragraph :
do not contain a pair of elements e1 and e2 such that e1.equals (e2)
- the second condition can only be met using exactly the same comparator function
<=
The first condition is more important because SortedSet
it follows that a Set
, and if the definition of a Set
cannot be satisfied, then the stronger conditions for a SortedSet
definitely cannot be satisfied.
There is a possibility that there is an implementation that mimics work SortedSet
, but it definitely won't SortedSet
.
source to share
com.google.common.collect.Sets # union from Guava will do the trick. It returns an unmodifiable form of the union of two sets. You can iterate over it. The returned set will not be sorted. Then you can create a new sorted set from the returned set ( new TreeSet()
or com.google.common.collect.ImmutableSortedSet
. I don't see any API for creating a view of a given set as a sorted set.
source to share
If your problem is a deep copy of the objects passed to the TreeSet # addAll method, you shouldn't be. The Javadoc does not indicate that this is a deep copy (and of course it is so to speak, if it were) ... and the OpenJDK implementation does not show this either . No copies - just additional references to an existing object.
Since deep copy is not a problem, I think that worrying about it if you haven't identified it as a specific performance issue falls into the category of premature optimization.
source to share