001: /*
002: * Copyright 1999-2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.iterators;
017:
018: import java.util.ArrayList;
019: import java.util.BitSet;
020: import java.util.Collection;
021: import java.util.Comparator;
022: import java.util.Iterator;
023: import java.util.List;
024: import java.util.NoSuchElementException;
025:
026: import org.apache.commons.collections.list.UnmodifiableList;
027:
028: /**
029: * Provides an ordered iteration over the elements contained in
030: * a collection of ordered Iterators.
031: * <p>
032: * Given two ordered {@link Iterator} instances <code>A</code> and <code>B</code>,
033: * the {@link #next} method on this iterator will return the lesser of
034: * <code>A.next()</code> and <code>B.next()</code>.
035: *
036: * @since Commons Collections 2.1
037: * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
038: *
039: * @author Rodney Waldhoff
040: * @author Stephen Colebourne
041: */
042: public class CollatingIterator implements Iterator {
043:
044: /** The {@link Comparator} used to evaluate order. */
045: private Comparator comparator = null;
046:
047: /** The list of {@link Iterator}s to evaluate. */
048: private ArrayList iterators = null;
049:
050: /** {@link Iterator#next Next} objects peeked from each iterator. */
051: private ArrayList values = null;
052:
053: /** Whether or not each {@link #values} element has been set. */
054: private BitSet valueSet = null;
055:
056: /** Index of the {@link #iterators iterator} from whom the last returned value was obtained. */
057: private int lastReturned = -1;
058:
059: // Constructors
060: // ----------------------------------------------------------------------
061: /**
062: * Constructs a new <code>CollatingIterator</code>. Natural sort order
063: * will be used, and child iterators will have to be manually added
064: * using the {@link #addIterator(Iterator)} method.
065: */
066: public CollatingIterator() {
067: this (null, 2);
068: }
069:
070: /**
071: * Constructs a new <code>CollatingIterator</code> that will used the
072: * specified comparator for ordering. Child iterators will have to be
073: * manually added using the {@link #addIterator(Iterator)} method.
074: *
075: * @param comp the comparator to use to sort, or null to use natural sort order
076: */
077: public CollatingIterator(final Comparator comp) {
078: this (comp, 2);
079: }
080:
081: /**
082: * Constructs a new <code>CollatingIterator</code> that will used the
083: * specified comparator for ordering and have the specified initial
084: * capacity. Child iterators will have to be
085: * manually added using the {@link #addIterator(Iterator)} method.
086: *
087: * @param comp the comparator to use to sort, or null to use natural sort order
088: * @param initIterCapacity the initial capacity for the internal list
089: * of child iterators
090: */
091: public CollatingIterator(final Comparator comp,
092: 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,
108: final Iterator b) {
109: this (comp, 2);
110: addIterator(a);
111: addIterator(b);
112: }
113:
114: /**
115: * Constructs a new <code>CollatingIterator</code> that will use the
116: * specified comparator to provide ordered iteration over the array
117: * of iterators.
118: *
119: * @param comp the comparator to use to sort, or null to use natural sort order
120: * @param iterators the array of iterators
121: * @throws NullPointerException if iterators array is or contains null
122: */
123: public CollatingIterator(final Comparator comp,
124: final Iterator[] iterators) {
125: this (comp, iterators.length);
126: for (int i = 0; i < iterators.length; i++) {
127: addIterator(iterators[i]);
128: }
129: }
130:
131: /**
132: * Constructs a new <code>CollatingIterator</code> that will use the
133: * specified comparator to provide ordered iteration over the collection
134: * of iterators.
135: *
136: * @param comp the comparator to use to sort, or null to use natural sort order
137: * @param iterators the collection of iterators
138: * @throws NullPointerException if the iterators collection is or contains null
139: * @throws ClassCastException if the iterators collection contains an
140: * element that's not an {@link Iterator}
141: */
142: public CollatingIterator(final Comparator comp,
143: final Collection iterators) {
144: this (comp, iterators.size());
145: for (Iterator it = iterators.iterator(); it.hasNext();) {
146: Iterator item = (Iterator) it.next();
147: addIterator(item);
148: }
149: }
150:
151: // Public Methods
152: // ----------------------------------------------------------------------
153: /**
154: * Adds the given {@link Iterator} to the iterators being collated.
155: *
156: * @param iterator the iterator to add to the collation, must not be null
157: * @throws IllegalStateException if iteration has started
158: * @throws NullPointerException if the iterator is null
159: */
160: public void addIterator(final Iterator iterator) {
161: checkNotStarted();
162: if (iterator == null) {
163: throw new NullPointerException("Iterator must not be null");
164: }
165: iterators.add(iterator);
166: }
167:
168: /**
169: * Sets the iterator at the given index.
170: *
171: * @param index index of the Iterator to replace
172: * @param iterator Iterator to place at the given index
173: * @throws IndexOutOfBoundsException if index < 0 or index > size()
174: * @throws IllegalStateException if iteration has started
175: * @throws NullPointerException if the iterator is null
176: */
177: public void setIterator(final int index, final Iterator iterator) {
178: checkNotStarted();
179: if (iterator == null) {
180: throw new NullPointerException("Iterator must not be null");
181: }
182: iterators.set(index, iterator);
183: }
184:
185: /**
186: * Gets the list of Iterators (unmodifiable).
187: *
188: * @return the unmodifiable list of iterators added
189: */
190: public List getIterators() {
191: return UnmodifiableList.decorate(iterators);
192: }
193:
194: /**
195: * Gets the {@link Comparator} by which collatation occurs.
196: */
197: public Comparator getComparator() {
198: return comparator;
199: }
200:
201: /**
202: * Sets the {@link Comparator} by which collation occurs.
203: *
204: * @throws IllegalStateException if iteration has started
205: */
206: public void setComparator(final Comparator comp) {
207: checkNotStarted();
208: comparator = comp;
209: }
210:
211: // Iterator Methods
212: // -------------------------------------------------------------------
213: /**
214: * Returns <code>true</code> if any child iterator has remaining elements.
215: *
216: * @return true if this iterator has remaining elements
217: */
218: public boolean hasNext() {
219: start();
220: return anyValueSet(valueSet) || anyHasNext(iterators);
221: }
222:
223: /**
224: * Returns the next ordered element from a child iterator.
225: *
226: * @return the next ordered element
227: * @throws NoSuchElementException if no child iterator has any more elements
228: */
229: public Object next() throws NoSuchElementException {
230: if (hasNext() == false) {
231: throw new NoSuchElementException();
232: }
233: int leastIndex = least();
234: if (leastIndex == -1) {
235: throw new NoSuchElementException();
236: } else {
237: Object val = values.get(leastIndex);
238: clear(leastIndex);
239: lastReturned = leastIndex;
240: return val;
241: }
242: }
243:
244: /**
245: * Removes the last returned element from the child iterator that
246: * produced it.
247: *
248: * @throws IllegalStateException if there is no last returned element,
249: * or if the last returned element has already been removed
250: */
251: public void remove() {
252: if (lastReturned == -1) {
253: throw new IllegalStateException(
254: "No value can be removed at present");
255: }
256: Iterator it = (Iterator) (iterators.get(lastReturned));
257: it.remove();
258: }
259:
260: // Private Methods
261: // -------------------------------------------------------------------
262: /**
263: * Initializes the collating state if it hasn't been already.
264: */
265: private void start() {
266: if (values == null) {
267: values = new ArrayList(iterators.size());
268: valueSet = new BitSet(iterators.size());
269: for (int i = 0; i < iterators.size(); i++) {
270: values.add(null);
271: valueSet.clear(i);
272: }
273: }
274: }
275:
276: /**
277: * Sets the {@link #values} and {@link #valueSet} attributes
278: * at position <i>i</i> to the next value of the
279: * {@link #iterators iterator} at position <i>i</i>, or
280: * clear them if the <i>i</i><sup>th</sup> iterator
281: * has no next value.
282: *
283: * @return <tt>false</tt> iff there was no value to set
284: */
285: private boolean set(int i) {
286: Iterator it = (Iterator) (iterators.get(i));
287: if (it.hasNext()) {
288: values.set(i, it.next());
289: valueSet.set(i);
290: return true;
291: } else {
292: values.set(i, null);
293: valueSet.clear(i);
294: return false;
295: }
296: }
297:
298: /**
299: * Clears the {@link #values} and {@link #valueSet} attributes
300: * at position <i>i</i>.
301: */
302: private void clear(int i) {
303: values.set(i, null);
304: valueSet.clear(i);
305: }
306:
307: /**
308: * Throws {@link IllegalStateException} if iteration has started
309: * via {@link #start}.
310: *
311: * @throws IllegalStateException if iteration started
312: */
313: private void checkNotStarted() throws IllegalStateException {
314: if (values != null) {
315: throw new IllegalStateException(
316: "Can't do that after next or hasNext has been called.");
317: }
318: }
319:
320: /**
321: * Returns the index of the least element in {@link #values},
322: * {@link #set(int) setting} any uninitialized values.
323: *
324: * @throws IllegalStateException
325: */
326: private int least() {
327: int leastIndex = -1;
328: Object leastObject = null;
329: for (int i = 0; i < values.size(); i++) {
330: if (valueSet.get(i) == false) {
331: set(i);
332: }
333: if (valueSet.get(i)) {
334: if (leastIndex == -1) {
335: leastIndex = i;
336: leastObject = values.get(i);
337: } else {
338: Object curObject = values.get(i);
339: if (comparator.compare(curObject, leastObject) < 0) {
340: leastObject = curObject;
341: leastIndex = i;
342: }
343: }
344: }
345: }
346: return leastIndex;
347: }
348:
349: /**
350: * Returns <code>true</code> iff any bit in the given set is
351: * <code>true</code>.
352: */
353: private boolean anyValueSet(BitSet set) {
354: for (int i = 0; i < set.size(); i++) {
355: if (set.get(i)) {
356: return true;
357: }
358: }
359: return false;
360: }
361:
362: /**
363: * Returns <code>true</code> iff any {@link Iterator}
364: * in the given list has a next value.
365: */
366: private boolean anyHasNext(ArrayList iters) {
367: for (int i = 0; i < iters.size(); i++) {
368: Iterator it = (Iterator) iters.get(i);
369: if (it.hasNext()) {
370: return true;
371: }
372: }
373: return false;
374: }
375:
376: }
|