CollatingIterator

/*
 * 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()}.
 * </p>
 *
 * @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;

    /**
     * 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 use 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 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);
        }
    }

    /**
     * Constructs a new {@code CollatingIterator} that will use 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);
        }
    }

    /**
     * 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);
    }

    /**
     * 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;
    }

    /**
     * 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;
    }

    /**
     * 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.");
        }
    }

    /**
     * Clears the {@link #values} and {@link #valueSet} attributes at position
     * <em>i</em>.
     */
    private void clear(final int i) {
        values.set(i, null);
        valueSet.clear(i);
    }

    /**
     * Gets the {@link Comparator} by which collation occurs.
     *
     * @return the {@link Comparator}
     */
    public Comparator<? super E> getComparator() {
        return comparator;
    }

    /**
     * Gets 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;
    }

    /**
     * Gets the list of Iterators (unmodifiable).
     *
     * @return the unmodifiable list of iterators added
     */
    public List<Iterator<? extends E>> getIterators() {
        return UnmodifiableList.unmodifiableList(iterators);
    }

    /**
     * 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 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)) {
                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 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()) {
            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();
    }

    /**
     * Sets the {@link #values} and {@link #valueSet} attributes at position
     * <em>i</em> to the next value of the {@link #iterators iterator} at position
     * <em>i</em>, or clear them if the <em>i</em><sup>th</sup> iterator has no next
     * value.
     *
     * @return {@code false} iff there was no value to set
     */
    private boolean set(final int index) {
        final Iterator<? extends E> it = iterators.get(index);
        if (it.hasNext()) {
            values.set(index, it.next());
            valueSet.set(index);
            return true;
        }
        values.set(index, null);
        valueSet.clear(index);
        return false;
    }

    /**
     * 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 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;
    }

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

    /**
     * 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);
            }
        }
    }

}