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