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