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 &lt; 0 or index &gt; 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    }