| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.commons.collections4.iterators; |
| |
| import java.util.ArrayList; |
| import java.util.BitSet; |
| import java.util.Collection; |
| import java.util.Comparator; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.NoSuchElementException; |
| import java.util.Objects; |
| |
| import org.apache.commons.collections4.list.UnmodifiableList; |
| |
| |
| /** |
| * Provides an ordered iteration over the elements contained in a collection of |
| * ordered Iterators. |
| * <p> |
| * Given two ordered {@link Iterator} instances {@code A} and |
| * {@code B}, the {@link #next} method on this iterator will return the |
| * lesser of {@code A.next()} and {@code B.next()}. |
| * |
| * @param <E> the type of elements returned by this iterator. |
| * @since 2.1 |
| */ |
| public class CollatingIterator<E> implements Iterator<E> { |
| |
| /** The {@link Comparator} used to evaluate order. */ |
| private Comparator<? super E> comparator; |
| |
| /** The list of {@link Iterator}s to evaluate. */ |
| private final List<Iterator<? extends E>> iterators; |
| |
| /** {@link Iterator#next Next} objects peeked from each iterator. */ |
| private List<E> values; |
| |
| /** Whether or not each {@link #values} element has been set. */ |
| private BitSet valueSet; |
| |
| /** |
| * Index of the {@link #iterators iterator} from whom the last returned |
| * value was obtained. |
| */ |
| private int lastReturned = -1; |
| |
| // Constructors |
| // ---------------------------------------------------------------------- |
| /** |
| * Constructs a new {@code CollatingIterator}. A comparator must be |
| * set by calling {@link #setComparator(Comparator)} before invoking |
| * {@link #hasNext()}, or {@link #next()} for the first time. Child |
| * iterators will have to be manually added using the |
| * {@link #addIterator(Iterator)} method. |
| */ |
| public CollatingIterator() { |
| this(null, 2); |
| } |
| |
| /** |
| * Constructs a new {@code CollatingIterator} that will used the |
| * specified comparator for ordering. Child iterators will have to be |
| * manually added using the {@link #addIterator(Iterator)} method. |
| * |
| * @param comp the comparator to use to sort; must not be null, |
| * unless you'll be invoking {@link #setComparator(Comparator)} later on. |
| */ |
| public CollatingIterator(final Comparator<? super E> comp) { |
| this(comp, 2); |
| } |
| |
| /** |
| * Constructs a new {@code CollatingIterator} that will used the |
| * specified comparator for ordering and have the specified initial |
| * capacity. Child iterators will have to be manually added using the |
| * {@link #addIterator(Iterator)} method. |
| * |
| * @param comp the comparator to use to sort; must not be null, |
| * unless you'll be invoking {@link #setComparator(Comparator)} later on. |
| * @param initIterCapacity the initial capacity for the internal list of |
| * child iterators |
| */ |
| public CollatingIterator(final Comparator<? super E> comp, final int initIterCapacity) { |
| iterators = new ArrayList<>(initIterCapacity); |
| setComparator(comp); |
| } |
| |
| /** |
| * Constructs a new {@code CollatingIterator} that will use the |
| * specified comparator to provide ordered iteration over the two given |
| * iterators. |
| * |
| * @param comp the comparator to use to sort; must not be null, |
| * unless you'll be invoking {@link #setComparator(Comparator)} later on. |
| * @param a the first child ordered iterator |
| * @param b the second child ordered iterator |
| * @throws NullPointerException if either iterator is null |
| */ |
| public CollatingIterator(final Comparator<? super E> comp, final Iterator<? extends E> a, |
| final Iterator<? extends E> b) { |
| this(comp, 2); |
| addIterator(a); |
| addIterator(b); |
| } |
| |
| /** |
| * Constructs a new {@code CollatingIterator} that will use the |
| * specified comparator to provide ordered iteration over the array of |
| * iterators. |
| * |
| * @param comp the comparator to use to sort; must not be null, |
| * unless you'll be invoking {@link #setComparator(Comparator)} later on. |
| * @param iterators the array of iterators |
| * @throws NullPointerException if iterators array is or contains null |
| */ |
| public CollatingIterator(final Comparator<? super E> comp, final Iterator<? extends E>[] iterators) { |
| this(comp, iterators.length); |
| for (final Iterator<? extends E> iterator : iterators) { |
| addIterator(iterator); |
| } |
| } |
| |
| /** |
| * Constructs a new {@code CollatingIterator} that will use the |
| * specified comparator to provide ordered iteration over the collection of |
| * iterators. |
| * |
| * @param comp the comparator to use to sort; must not be null, |
| * unless you'll be invoking {@link #setComparator(Comparator)} later on. |
| * @param iterators the collection of iterators |
| * @throws NullPointerException if the iterators collection is or contains null |
| * @throws ClassCastException if the iterators collection contains an |
| * element that's not an {@link Iterator} |
| */ |
| public CollatingIterator(final Comparator<? super E> comp, final Collection<Iterator<? extends E>> iterators) { |
| this(comp, iterators.size()); |
| for (final Iterator<? extends E> iterator : iterators) { |
| addIterator(iterator); |
| } |
| } |
| |
| // Public Methods |
| // ---------------------------------------------------------------------- |
| /** |
| * Adds the given {@link Iterator} to the iterators being collated. |
| * |
| * @param iterator the iterator to add to the collation, must not be null |
| * @throws IllegalStateException if iteration has started |
| * @throws NullPointerException if the iterator is null |
| */ |
| public void addIterator(final Iterator<? extends E> iterator) { |
| checkNotStarted(); |
| Objects.requireNonNull(iterator, "iterator"); |
| iterators.add(iterator); |
| } |
| |
| /** |
| * Sets the iterator at the given index. |
| * |
| * @param index index of the Iterator to replace |
| * @param iterator Iterator to place at the given index |
| * @throws IndexOutOfBoundsException if index < 0 or index >= size() |
| * @throws IllegalStateException if iteration has started |
| * @throws NullPointerException if the iterator is null |
| */ |
| public void setIterator(final int index, final Iterator<? extends E> iterator) { |
| checkNotStarted(); |
| Objects.requireNonNull(iterator, "iterator"); |
| iterators.set(index, iterator); |
| } |
| |
| /** |
| * Gets the list of Iterators (unmodifiable). |
| * |
| * @return the unmodifiable list of iterators added |
| */ |
| public List<Iterator<? extends E>> getIterators() { |
| return UnmodifiableList.unmodifiableList(iterators); |
| } |
| |
| /** |
| * Gets the {@link Comparator} by which collation occurs. |
| * |
| * @return the {@link Comparator} |
| */ |
| public Comparator<? super E> getComparator() { |
| return comparator; |
| } |
| |
| /** |
| * Sets the {@link Comparator} by which collation occurs. If you |
| * would like to use the natural sort order (or, in other words, |
| * if the elements in the iterators are implementing the |
| * {@link java.lang.Comparable} interface), then use the |
| * {@link org.apache.commons.collections4.comparators.ComparableComparator}. |
| * |
| * @param comp the {@link Comparator} to set |
| * @throws IllegalStateException if iteration has started |
| */ |
| public void setComparator(final Comparator<? super E> comp) { |
| checkNotStarted(); |
| comparator = comp; |
| } |
| |
| // Iterator Methods |
| // ------------------------------------------------------------------- |
| /** |
| * Returns {@code true} if any child iterator has remaining elements. |
| * |
| * @return true if this iterator has remaining elements |
| */ |
| @Override |
| public boolean hasNext() { |
| start(); |
| return anyValueSet(valueSet) || anyHasNext(iterators); |
| } |
| |
| /** |
| * Returns the next ordered element from a child iterator. |
| * |
| * @return the next ordered element |
| * @throws NoSuchElementException if no child iterator has any more elements |
| */ |
| @Override |
| public E next() throws NoSuchElementException { |
| if (hasNext() == false) { |
| throw new NoSuchElementException(); |
| } |
| final int leastIndex = least(); |
| if (leastIndex == -1) { |
| throw new NoSuchElementException(); |
| } |
| final E val = values.get(leastIndex); |
| clear(leastIndex); |
| lastReturned = leastIndex; |
| return val; |
| } |
| |
| /** |
| * Removes the last returned element from the child iterator that produced it. |
| * |
| * @throws IllegalStateException if there is no last returned element, or if |
| * the last returned element has already been removed |
| */ |
| @Override |
| public void remove() { |
| if (lastReturned == -1) { |
| throw new IllegalStateException("No value can be removed at present"); |
| } |
| iterators.get(lastReturned).remove(); |
| } |
| |
| /** |
| * Returns the index of the iterator that returned the last element. |
| * |
| * @return the index of the iterator that returned the last element |
| * @throws IllegalStateException if there is no last returned element |
| */ |
| public int getIteratorIndex() { |
| if (lastReturned == -1) { |
| throw new IllegalStateException("No value has been returned yet"); |
| } |
| |
| return lastReturned; |
| } |
| |
| // Private Methods |
| // ------------------------------------------------------------------- |
| /** |
| * Initializes the collating state if it hasn't been already. |
| */ |
| private void start() { |
| if (values == null) { |
| values = new ArrayList<>(iterators.size()); |
| valueSet = new BitSet(iterators.size()); |
| for (int i = 0; i < iterators.size(); i++) { |
| values.add(null); |
| valueSet.clear(i); |
| } |
| } |
| } |
| |
| /** |
| * Sets the {@link #values} and {@link #valueSet} attributes at position |
| * <i>i</i> to the next value of the {@link #iterators iterator} at position |
| * <i>i</i>, or clear them if the <i>i</i><sup>th</sup> iterator has no next |
| * value. |
| * |
| * @return {@code false} iff there was no value to set |
| */ |
| private boolean set(final int i) { |
| final Iterator<? extends E> it = iterators.get(i); |
| if (it.hasNext()) { |
| values.set(i, it.next()); |
| valueSet.set(i); |
| return true; |
| } |
| values.set(i, null); |
| valueSet.clear(i); |
| return false; |
| } |
| |
| /** |
| * Clears the {@link #values} and {@link #valueSet} attributes at position |
| * <i>i</i>. |
| */ |
| private void clear(final int i) { |
| values.set(i, null); |
| valueSet.clear(i); |
| } |
| |
| /** |
| * Throws {@link IllegalStateException} if iteration has started via |
| * {@link #start}. |
| * |
| * @throws IllegalStateException if iteration started |
| */ |
| private void checkNotStarted() throws IllegalStateException { |
| if (values != null) { |
| throw new IllegalStateException("Can't do that after next or hasNext has been called."); |
| } |
| } |
| |
| /** |
| * Returns the index of the least element in {@link #values}, |
| * {@link #set(int) setting} any uninitialized values. |
| * |
| * @throws NullPointerException if no comparator is set |
| */ |
| private int least() { |
| int leastIndex = -1; |
| E leastObject = null; |
| for (int i = 0; i < values.size(); i++) { |
| if (valueSet.get(i) == false) { |
| set(i); |
| } |
| if (valueSet.get(i)) { |
| if (leastIndex == -1) { |
| leastIndex = i; |
| leastObject = values.get(i); |
| } else { |
| final E curObject = values.get(i); |
| Objects.requireNonNull(comparator, "You must invoke setComparator() to set a comparator first."); |
| if (comparator.compare(curObject, leastObject) < 0) { |
| leastObject = curObject; |
| leastIndex = i; |
| } |
| } |
| } |
| } |
| return leastIndex; |
| } |
| |
| /** |
| * Returns {@code true} iff any bit in the given set is |
| * {@code true}. |
| */ |
| private boolean anyValueSet(final BitSet set) { |
| for (int i = 0; i < set.size(); i++) { |
| if (set.get(i)) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * Returns {@code true} iff any {@link Iterator} in the given list has |
| * a next value. |
| */ |
| private boolean anyHasNext(final List<Iterator<? extends E>> iterators) { |
| for (final Iterator<? extends E> iterator : iterators) { |
| if (iterator.hasNext()) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| } |