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