KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > commons > collections > iterators > CollatingIterator


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