java - Iterator over multiple SortedSet objects -

java - Iterator over multiple SortedSet objects -

in java, have several sortedset instances. iterate on elements these sets. 1 simple alternative create new sortedset, such treeset x, deep-copy contents of individual sets y_1, ..., y_n using x.addall(y_i), , iterate on x.

but there way avoid deep copy? couldn't create view of type sortedset somehow encapsulate iterators of inner sets, behave single set?

i'd prefer existing, tested solution, rather writing own.

i'm not aware of existing solution accomplish task, took time write 1 you. i'm sure there's room improvement on it, take guideline , nil else.

as sandor points out in his answer, there limitations must imposed or assumed. 1 such limitation every sortedset must sorted relative same order, otherwise there's no point in comparing elements without creating new set (representing union of every individual set).

here follows code illustration which, you'll notice, relatively more complex creating new set , adding elements 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() { homecoming new multisortedsetiterator<e>(sets, comparator); } multisortedsetview<e> add(final sortedset<e> set) { // may remove `if` if know // every set uses same comparator. if (comparator != set.comparator()) { throw new illegalargumentexception("different comparator!"); } sets.add(set); homecoming this; } @override public boolean equals(final object o) { if (this == o) { homecoming true; } if (!(o instanceof multisortedsetview)) { homecoming false; } final multisortedsetview<?> n = (multisortedsetview<?>) o; homecoming 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(); homecoming 37 * hash + sets.hashcode(); } @override public string tostring() { homecoming 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); (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); } homecoming e.element; } @override public boolean hasnext() { homecoming !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); homecoming true; } } homecoming 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) { homecoming true; } if (!(o instanceof element)) { homecoming false; } final element<?> e = (element<?>) o; homecoming 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) { homecoming comparator.compare(e1.element, e2.element); } homecoming ((comparable<? super e>) e1.element) .compareto(e2.element); } } } }

the inner workings of class simple grasp. view keeps list of sorted sets, ones want iterate over. needs comparator used compare elements (null utilize natural ordering). can add together (distinct) sets view.

the rest of magic happens in iterator of view. iterator keeps priorityqueue of elements returned next() , list of iterators individual sets. queue have, @ times, @ 1 element per set, , discards repeating elements. iterator discards empty , used iterators. in short, guarantees traverse every element 1 time (as in set).

here's illustration on how utilize 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); (final integer i: v) { system.out.println(i); }

java iterator set sortedset