001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.collections.iterators;
018
019 import java.util.ArrayList;
020 import java.util.BitSet;
021 import java.util.Collection;
022 import java.util.Comparator;
023 import java.util.Iterator;
024 import java.util.List;
025 import java.util.NoSuchElementException;
026
027 import org.apache.commons.collections.list.UnmodifiableList;
028
029 /**
030 * Provides an ordered iteration over the elements contained in
031 * a collection of ordered Iterators.
032 * <p>
033 * Given two ordered {@link Iterator} instances <code>A</code> and <code>B</code>,
034 * the {@link #next} method on this iterator will return the lesser of
035 * <code>A.next()</code> and <code>B.next()</code>.
036 *
037 * @since Commons Collections 2.1
038 * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
039 *
040 * @author Rodney Waldhoff
041 * @author Stephen Colebourne
042 */
043 public class CollatingIterator implements Iterator {
044
045 /** The {@link Comparator} used to evaluate order. */
046 private Comparator comparator = null;
047
048 /** The list of {@link Iterator}s to evaluate. */
049 private ArrayList iterators = null;
050
051 /** {@link Iterator#next Next} objects peeked from each iterator. */
052 private ArrayList values = null;
053
054 /** Whether or not each {@link #values} element has been set. */
055 private BitSet valueSet = null;
056
057 /** Index of the {@link #iterators iterator} from whom the last returned value was obtained. */
058 private int lastReturned = -1;
059
060 // Constructors
061 // ----------------------------------------------------------------------
062 /**
063 * Constructs a new <code>CollatingIterator</code>. Natural sort order
064 * will be used, and child iterators will have to be manually added
065 * using the {@link #addIterator(Iterator)} method.
066 */
067 public CollatingIterator() {
068 this(null,2);
069 }
070
071 /**
072 * Constructs a new <code>CollatingIterator</code> that will used the
073 * specified comparator for ordering. Child iterators will have to be
074 * manually added using the {@link #addIterator(Iterator)} method.
075 *
076 * @param comp the comparator to use to sort, or null to use natural sort order
077 */
078 public CollatingIterator(final Comparator comp) {
079 this(comp,2);
080 }
081
082 /**
083 * Constructs a new <code>CollatingIterator</code> that will used the
084 * specified comparator for ordering and have the specified initial
085 * capacity. Child iterators will have to be
086 * manually added using the {@link #addIterator(Iterator)} method.
087 *
088 * @param comp the comparator to use to sort, or null to use natural sort order
089 * @param initIterCapacity the initial capacity for the internal list
090 * of child iterators
091 */
092 public CollatingIterator(final Comparator comp, final int initIterCapacity) {
093 iterators = new ArrayList(initIterCapacity);
094 setComparator(comp);
095 }
096
097 /**
098 * Constructs a new <code>CollatingIterator</code> that will use the
099 * 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 }