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 }