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