1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package net.sf.collections15.iterators;
17
18 import java.util.ArrayList;
19 import java.util.BitSet;
20 import java.util.Collection;
21 import java.util.Comparator;
22 import java.util.Iterator;
23 import java.util.List;
24 import java.util.NoSuchElementException;
25
26 import net.sf.collections15.list.UnmodifiableList;
27
28 /***
29 * Provides an ordered iteration over the elements contained in a collection of
30 * ordered Iterators.
31 * <p>
32 * Given two ordered {@link java.util.Iterator Iterator} instances
33 * <code>A</code> and <code>B</code>, the {@link #next()} method on this
34 * iterator will return the lesser of <code>A.next()</code> and
35 * <code>B.next()</code>.
36 *
37 * @since Commons Collections 2.1
38 * @version $Revision: 1.1 $ $Date: 2005/02/27 15:43:00 $
39 *
40 * @author Rodney Waldhoff
41 * @author Stephen Colebourne
42 * @author Mauro Franceschini (port to 5.0)
43 */
44 public class CollatingIterator<E> implements Iterator<E> {
45
46
47
48
49 /*** The {@link Comparator} used to evaluate order. */
50 private Comparator<E> comparator = null;
51
52 /*** The list of {@link Iterator}s to evaluate. */
53 private List<Iterator<E>> iterators = null;
54
55 /*** {@link Iterator#next() Next} objects peeked from each iterator. */
56 private List<E> values = null;
57
58 /*** Whether or not each {@link #values} element has been set. */
59 private BitSet valueSet = null;
60
61 /***
62 * Index of the {@link #iterators iterator} from whom the last returned
63 * value was obtained.
64 */
65 private int lastReturned = -1;
66
67
68
69
70 /***
71 * Constructs a new <code>CollatingIterator</code>.
72 * <p>
73 * Natural sort order will be used, and child iterators will have to be
74 * manually added using the {@link #addIterator(Iterator<E>)} method.
75 */
76 public CollatingIterator() {
77 this(null, 2);
78 }
79
80 /***
81 * Constructs a new <code>CollatingIterator</code> that will used the
82 * specified comparator for ordering.
83 * <p>
84 * Child iterators will have to be manually added using the
85 * {@link #addIterator(Iterator<E>)} method.
86 *
87 * @param comp the comparator to use to sort, or <code>null</code> to use
88 * natural sort order
89 */
90 public CollatingIterator(final Comparator<E> comp) {
91 this(comp, 2);
92 }
93
94 /***
95 * Constructs a new <code>CollatingIterator</code> that will used the
96 * specified comparator for ordering and have the specified initial
97 * capacity.
98 * <p>
99 * Child iterators will have to be manually added using the
100 * {@link #addIterator(Iterator<E>)} method.
101 *
102 * @param comp the comparator to use to sort, or <code>null</code> to use
103 * natural sort order
104 * @param initIterCapacity the initial capacity for the internal list of
105 * child iterators
106 */
107 public CollatingIterator(final Comparator<E> comp,
108 final int initIterCapacity) {
109 iterators = new ArrayList<Iterator<E>>(initIterCapacity);
110 setComparator(comp);
111 }
112
113 /***
114 * Constructs a new <code>CollatingIterator</code> that will use the
115 * specified comparator to provide ordered iteration over the two given
116 * iterators.
117 *
118 * @param comp the comparator to use to sort, or <code>null</code> to use
119 * natural sort order
120 * @param a the first child ordered iterator
121 * @param b the second child ordered iterator
122 *
123 * @throws NullPointerException if either iterator is <code>null</code>
124 */
125 public CollatingIterator(final Comparator<E> comp, final Iterator<E> a,
126 final Iterator<E> b) {
127 this(comp,2);
128 addIterator(a);
129 addIterator(b);
130 }
131
132 /***
133 * Constructs a new <code>CollatingIterator</code> that will use the
134 * specified comparator to provide ordered iteration over the array
135 * of iterators.
136 *
137 * @param comp the comparator to use to sort, or <code>null</code> to use
138 * natural sort order
139 * @param a the first child ordered iterator
140 * @param b the second child ordered iterator
141 * @param iterators the other iterators
142 *
143 * @throws NullPointerException if one of the iterators contains the
144 * <code>null</code> value
145 */
146 public CollatingIterator(final Comparator<E> comp, final Iterator<E> a,
147 final Iterator<E> b, final Iterator<E>... iterators) {
148 this(comp, iterators.length + 2);
149 addIterator(a);
150 addIterator(b);
151 for (int i = 0; i < iterators.length; i++) {
152 addIterator(iterators[i]);
153 }
154 }
155
156 /***
157 * Constructs a new <code>CollatingIterator</code> that will use the
158 * specified comparator to provide ordered iteration over the collection
159 * of iterators.
160 *
161 * @param comp the comparator to use to sort, or <code>null</code> to use
162 * natural sort order
163 * @param iterators a collection of iterators
164 *
165 * @throws NullPointerException if the iterators collection is or contains
166 * <code>null</code>
167 */
168 public CollatingIterator(final Comparator<E> comp,
169 final Collection<Iterator<E>> iterators) {
170 this(comp, iterators.size());
171 for (Iterator<E> item : iterators) {
172 addIterator(item);
173 }
174 }
175
176
177
178
179 /***
180 * Adds the given {@link Iterator<E>} to the iterators being collated.
181 *
182 * @param iterator the iterator to add to the collation, must not be
183 * <code>null</code>
184 *
185 * @throws IllegalStateException if iteration has started
186 * @throws NullPointerException if the iterator is <code>null</code>
187 */
188 public void addIterator(final Iterator<E> iterator) {
189 checkNotStarted();
190 if (iterator == null) {
191 throw new NullPointerException("Iterator must not be null");
192 }
193 iterators.add(iterator);
194 }
195
196 /***
197 * Sets the iterator at the given index.
198 *
199 * @param index index of the <code>Iterator</code> to replace
200 * @param iterator <code>Iterator</code> to place at the given index
201 *
202 * @throws IndexOutOfBoundsException if index < 0 or index > size()
203 * @throws IllegalStateException if iteration has started
204 * @throws NullPointerException if the iterator is <code>null</code>
205 */
206 public void setIterator(final int index, final Iterator<E> iterator) {
207 checkNotStarted();
208 if (iterator == null) {
209 throw new NullPointerException("Iterator must not be null");
210 }
211 iterators.set(index, iterator);
212 }
213
214 /***
215 * Gets the list of Iterators (unmodifiable).
216 *
217 * @return the unmodifiable list of iterators added
218 */
219 public List<Iterator<E>> getIterators() {
220 return UnmodifiableList.decorate(iterators);
221 }
222
223 /***
224 * Gets the {@link Comparator} by which collatation occurs.
225 */
226 public Comparator<E> getComparator() {
227 return comparator;
228 }
229
230 /***
231 * Sets the {@link Comparator} by which collation occurs.
232 *
233 * @throws IllegalStateException if iteration has started
234 */
235 public void setComparator(final Comparator<E> comp) {
236 checkNotStarted();
237 comparator = comp;
238 }
239
240
241
242
243 /***
244 * Returns <code>true</code> if any child iterator has remaining elements.
245 *
246 * @return <code>true</code> if this iterator has remaining elements
247 */
248 public boolean hasNext() {
249 start();
250 return anyValueSet(valueSet) || anyHasNext(iterators);
251 }
252
253 /***
254 * Returns the next ordered element from a child iterator.
255 *
256 * @return the next ordered element
257 *
258 * @throws NoSuchElementException if no child iterator has any more elements
259 */
260 public E next() throws NoSuchElementException {
261 if (hasNext() == false) {
262 throw new NoSuchElementException();
263 }
264 int leastIndex = least();
265 if (leastIndex == -1) {
266 throw new NoSuchElementException();
267 } else {
268 E val = values.get(leastIndex);
269 clear(leastIndex);
270 lastReturned = leastIndex;
271 return val;
272 }
273 }
274
275 /***
276 * Removes the last returned element from the child iterator that
277 * produced it.
278 *
279 * @throws IllegalStateException if there is no last returned element,
280 * or if the last returned element has already been removed
281 */
282 public void remove() {
283 if (lastReturned == -1) {
284 throw new IllegalStateException("No value can be removed at present");
285 }
286 Iterator<E> it = iterators.get(lastReturned);
287 it.remove();
288 }
289
290
291
292
293 /***
294 * Initializes the collating state if it hasn't been already.
295 */
296 private void start() {
297 if (values == null) {
298 values = new ArrayList<E>(iterators.size());
299 valueSet = new BitSet(iterators.size());
300 for (int i = 0; i < iterators.size(); i++) {
301 values.add(null);
302 valueSet.clear(i);
303 }
304 }
305 }
306
307 /***
308 * Sets the {@link #values} and {@link #valueSet} attributes
309 * at position <i>i</i> to the next value of the
310 * {@link #iterators iterator} at position <i>i</i>, or
311 * clear them if the <i>i</i><sup>th</sup> iterator
312 * has no next value.
313 *
314 * @return <code>false</code> if there was no value to set
315 */
316 private boolean set(final int i) {
317 Iterator<E> it = iterators.get(i);
318 if (it.hasNext()) {
319 values.set(i, it.next());
320 valueSet.set(i);
321 return true;
322 } else {
323 values.set(i, null);
324 valueSet.clear(i);
325 return false;
326 }
327 }
328
329 /***
330 * Clears the {@link #values} and {@link #valueSet} attributes
331 * at position <i>i</i>.
332 */
333 private void clear(final int i) {
334 values.set(i, null);
335 valueSet.clear(i);
336 }
337
338 /***
339 * Throws {@link IllegalStateException} if iteration has started
340 * via {@link #start}.
341 *
342 * @throws IllegalStateException if iteration started
343 */
344 private void checkNotStarted() throws IllegalStateException {
345 if (values != null) {
346 throw new IllegalStateException(
347 "Can't do that after next or hasNext has been called.");
348 }
349 }
350
351 /***
352 * Returns the index of the least element in {@link #values},
353 * {@link #set(int) setting} any uninitialized values.
354 *
355 * @throws IllegalStateException
356 */
357 private int least() {
358 int leastIndex = -1;
359 E leastObject = null;
360 for (int i = 0; i < values.size(); i++) {
361 if (valueSet.get(i) == false) {
362 set(i);
363 }
364 if (valueSet.get(i)) {
365 if (leastIndex == -1) {
366 leastIndex = i;
367 leastObject = values.get(i);
368 } else {
369 E curObject = values.get(i);
370 if (comparator.compare(curObject,leastObject) < 0) {
371 leastObject = curObject;
372 leastIndex = i;
373 }
374 }
375 }
376 }
377 return leastIndex;
378 }
379
380 /***
381 * Returns <code>true</code> if any bit in the given set is
382 * <code>true</code>.
383 */
384 private boolean anyValueSet(final BitSet set) {
385 for (int i = 0; i < set.size(); i++) {
386 if (set.get(i)) {
387 return true;
388 }
389 }
390 return false;
391 }
392
393 /***
394 * Returns <code>true</code> if any {@link Iterator}
395 * in the given list has a next value.
396 */
397 private boolean anyHasNext(final List<Iterator<E>> iters) {
398 for (Iterator<E> it: iters) {
399 if (it.hasNext()) {
400 return true;
401 }
402 }
403 return false;
404 }
405 }