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 */ 017package org.apache.commons.collections4.iterators; 018 019import java.util.ArrayList; 020import java.util.BitSet; 021import java.util.Collection; 022import java.util.Comparator; 023import java.util.Iterator; 024import java.util.List; 025import java.util.NoSuchElementException; 026import java.util.Objects; 027 028import org.apache.commons.collections4.list.UnmodifiableList; 029 030/** 031 * Provides an ordered iteration over the elements contained in a collection of 032 * ordered Iterators. 033 * <p> 034 * Given two ordered {@link Iterator} instances {@code A} and 035 * {@code B}, the {@link #next} method on this iterator will return the 036 * lesser of {@code A.next()} and {@code B.next()}. 037 * 038 * @param <E> the type of elements returned by this iterator. 039 * @since 2.1 040 */ 041public class CollatingIterator<E> implements Iterator<E> { 042 043 /** The {@link Comparator} used to evaluate order. */ 044 private Comparator<? super E> comparator; 045 046 /** The list of {@link Iterator}s to evaluate. */ 047 private final List<Iterator<? extends E>> iterators; 048 049 /** {@link Iterator#next Next} objects peeked from each iterator. */ 050 private List<E> values; 051 052 /** Whether or not each {@link #values} element has been set. */ 053 private BitSet valueSet; 054 055 /** 056 * Index of the {@link #iterators iterator} from whom the last returned 057 * value was obtained. 058 */ 059 private int lastReturned = -1; 060 061 /** 062 * Constructs a new {@code CollatingIterator}. A comparator must be 063 * set by calling {@link #setComparator(Comparator)} before invoking 064 * {@link #hasNext()}, or {@link #next()} for the first time. Child 065 * iterators will have to be manually added using the 066 * {@link #addIterator(Iterator)} method. 067 */ 068 public CollatingIterator() { 069 this(null, 2); 070 } 071 072 /** 073 * Constructs a new {@code CollatingIterator} that will use the 074 * specified comparator for ordering. Child iterators will have to be 075 * manually added using the {@link #addIterator(Iterator)} method. 076 * 077 * @param comp the comparator to use to sort; must not be null, 078 * unless you'll be invoking {@link #setComparator(Comparator)} later on. 079 */ 080 public CollatingIterator(final Comparator<? super E> comp) { 081 this(comp, 2); 082 } 083 084 /** 085 * Constructs a new {@code CollatingIterator} that will use the 086 * specified comparator to provide ordered iteration over the collection of 087 * iterators. 088 * 089 * @param comp the comparator to use to sort; must not be null, 090 * unless you'll be invoking {@link #setComparator(Comparator)} later on. 091 * @param iterators the collection of iterators 092 * @throws NullPointerException if the iterators collection is or contains null 093 * @throws ClassCastException if the iterators collection contains an 094 * element that's not an {@link Iterator} 095 */ 096 public CollatingIterator(final Comparator<? super E> comp, final Collection<Iterator<? extends E>> iterators) { 097 this(comp, iterators.size()); 098 for (final Iterator<? extends E> iterator : iterators) { 099 addIterator(iterator); 100 } 101 } 102 103 /** 104 * Constructs a new {@code CollatingIterator} that will use the 105 * specified comparator for ordering and have the specified initial 106 * capacity. Child iterators will have to be manually added using the 107 * {@link #addIterator(Iterator)} method. 108 * 109 * @param comp the comparator to use to sort; must not be null, 110 * unless you'll be invoking {@link #setComparator(Comparator)} later on. 111 * @param initIterCapacity the initial capacity for the internal list of 112 * child iterators 113 */ 114 public CollatingIterator(final Comparator<? super E> comp, final int initIterCapacity) { 115 iterators = new ArrayList<>(initIterCapacity); 116 setComparator(comp); 117 } 118 119 /** 120 * Constructs a new {@code CollatingIterator} that will use the 121 * specified comparator to provide ordered iteration over the two given 122 * iterators. 123 * 124 * @param comp the comparator to use to sort; must not be null, 125 * unless you'll be invoking {@link #setComparator(Comparator)} later on. 126 * @param a the first child ordered iterator 127 * @param b the second child ordered iterator 128 * @throws NullPointerException if either iterator is null 129 */ 130 public CollatingIterator(final Comparator<? super E> comp, final Iterator<? extends E> a, 131 final Iterator<? extends E> b) { 132 this(comp, 2); 133 addIterator(a); 134 addIterator(b); 135 } 136 137 /** 138 * Constructs a new {@code CollatingIterator} that will use the 139 * specified comparator to provide ordered iteration over the array of 140 * iterators. 141 * 142 * @param comp the comparator to use to sort; must not be null, 143 * unless you'll be invoking {@link #setComparator(Comparator)} later on. 144 * @param iterators the array of iterators 145 * @throws NullPointerException if iterators array is or contains null 146 */ 147 public CollatingIterator(final Comparator<? super E> comp, final Iterator<? extends E>[] iterators) { 148 this(comp, iterators.length); 149 for (final Iterator<? extends E> iterator : iterators) { 150 addIterator(iterator); 151 } 152 } 153 154 /** 155 * Adds the given {@link Iterator} to the iterators being collated. 156 * 157 * @param iterator the iterator to add to the collation, must not be null 158 * @throws IllegalStateException if iteration has started 159 * @throws NullPointerException if the iterator is null 160 */ 161 public void addIterator(final Iterator<? extends E> iterator) { 162 checkNotStarted(); 163 Objects.requireNonNull(iterator, "iterator"); 164 iterators.add(iterator); 165 } 166 167 /** 168 * Returns {@code true} iff any {@link Iterator} in the given list has 169 * a next value. 170 */ 171 private boolean anyHasNext(final List<Iterator<? extends E>> iterators) { 172 for (final Iterator<? extends E> iterator : iterators) { 173 if (iterator.hasNext()) { 174 return true; 175 } 176 } 177 return false; 178 } 179 180 /** 181 * Returns {@code true} iff any bit in the given set is 182 * {@code true}. 183 */ 184 private boolean anyValueSet(final BitSet set) { 185 for (int i = 0; i < set.size(); i++) { 186 if (set.get(i)) { 187 return true; 188 } 189 } 190 return false; 191 } 192 193 /** 194 * Throws {@link IllegalStateException} if iteration has started via 195 * {@link #start}. 196 * 197 * @throws IllegalStateException if iteration started 198 */ 199 private void checkNotStarted() throws IllegalStateException { 200 if (values != null) { 201 throw new IllegalStateException("Can't do that after next or hasNext has been called."); 202 } 203 } 204 205 /** 206 * Clears the {@link #values} and {@link #valueSet} attributes at position 207 * <i>i</i>. 208 */ 209 private void clear(final int i) { 210 values.set(i, null); 211 valueSet.clear(i); 212 } 213 214 /** 215 * Gets the {@link Comparator} by which collation occurs. 216 * 217 * @return the {@link Comparator} 218 */ 219 public Comparator<? super E> getComparator() { 220 return comparator; 221 } 222 223 /** 224 * Returns the index of the iterator that returned the last element. 225 * 226 * @return the index of the iterator that returned the last element 227 * @throws IllegalStateException if there is no last returned element 228 */ 229 public int getIteratorIndex() { 230 if (lastReturned == -1) { 231 throw new IllegalStateException("No value has been returned yet"); 232 } 233 234 return lastReturned; 235 } 236 237 /** 238 * Gets the list of Iterators (unmodifiable). 239 * 240 * @return the unmodifiable list of iterators added 241 */ 242 public List<Iterator<? extends E>> getIterators() { 243 return UnmodifiableList.unmodifiableList(iterators); 244 } 245 246 /** 247 * Returns {@code true} if any child iterator has remaining elements. 248 * 249 * @return true if this iterator has remaining elements 250 */ 251 @Override 252 public boolean hasNext() { 253 start(); 254 return anyValueSet(valueSet) || anyHasNext(iterators); 255 } 256 257 /** 258 * Returns the index of the least element in {@link #values}, 259 * {@link #set(int) setting} any uninitialized values. 260 * 261 * @throws NullPointerException if no comparator is set 262 */ 263 private int least() { 264 int leastIndex = -1; 265 E leastObject = null; 266 for (int i = 0; i < values.size(); i++) { 267 if (!valueSet.get(i)) { 268 set(i); 269 } 270 if (valueSet.get(i)) { 271 if (leastIndex == -1) { 272 leastIndex = i; 273 leastObject = values.get(i); 274 } else { 275 final E curObject = values.get(i); 276 Objects.requireNonNull(comparator, "You must invoke setComparator() to set a comparator first."); 277 if (comparator.compare(curObject, leastObject) < 0) { 278 leastObject = curObject; 279 leastIndex = i; 280 } 281 } 282 } 283 } 284 return leastIndex; 285 } 286 287 /** 288 * Returns the next ordered element from a child iterator. 289 * 290 * @return the next ordered element 291 * @throws NoSuchElementException if no child iterator has any more elements 292 */ 293 @Override 294 public E next() throws NoSuchElementException { 295 if (!hasNext()) { 296 throw new NoSuchElementException(); 297 } 298 final int leastIndex = least(); 299 if (leastIndex == -1) { 300 throw new NoSuchElementException(); 301 } 302 final E val = values.get(leastIndex); 303 clear(leastIndex); 304 lastReturned = leastIndex; 305 return val; 306 } 307 308 /** 309 * Removes the last returned element from the child iterator that produced it. 310 * 311 * @throws IllegalStateException if there is no last returned element, or if 312 * the last returned element has already been removed 313 */ 314 @Override 315 public void remove() { 316 if (lastReturned == -1) { 317 throw new IllegalStateException("No value can be removed at present"); 318 } 319 iterators.get(lastReturned).remove(); 320 } 321 322 /** 323 * Sets the {@link #values} and {@link #valueSet} attributes at position 324 * <i>i</i> to the next value of the {@link #iterators iterator} at position 325 * <i>i</i>, or clear them if the <i>i</i><sup>th</sup> iterator has no next 326 * value. 327 * 328 * @return {@code false} iff there was no value to set 329 */ 330 private boolean set(final int i) { 331 final Iterator<? extends E> it = iterators.get(i); 332 if (it.hasNext()) { 333 values.set(i, it.next()); 334 valueSet.set(i); 335 return true; 336 } 337 values.set(i, null); 338 valueSet.clear(i); 339 return false; 340 } 341 342 /** 343 * Sets the {@link Comparator} by which collation occurs. If you 344 * would like to use the natural sort order (or, in other words, 345 * if the elements in the iterators are implementing the 346 * {@link Comparable} interface), then use the 347 * {@link org.apache.commons.collections4.comparators.ComparableComparator}. 348 * 349 * @param comp the {@link Comparator} to set 350 * @throws IllegalStateException if iteration has started 351 */ 352 public void setComparator(final Comparator<? super E> comp) { 353 checkNotStarted(); 354 comparator = comp; 355 } 356 357 /** 358 * Sets the iterator at the given index. 359 * 360 * @param index index of the Iterator to replace 361 * @param iterator Iterator to place at the given index 362 * @throws IndexOutOfBoundsException if index < 0 or index >= size() 363 * @throws IllegalStateException if iteration has started 364 * @throws NullPointerException if the iterator is null 365 */ 366 public void setIterator(final int index, final Iterator<? extends E> iterator) { 367 checkNotStarted(); 368 Objects.requireNonNull(iterator, "iterator"); 369 iterators.set(index, iterator); 370 } 371 372 /** 373 * Initializes the collating state if it hasn't been already. 374 */ 375 private void start() { 376 if (values == null) { 377 values = new ArrayList<>(iterators.size()); 378 valueSet = new BitSet(iterators.size()); 379 for (int i = 0; i < iterators.size(); i++) { 380 values.add(null); 381 valueSet.clear(i); 382 } 383 } 384 } 385 386}