CollatingIterator.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.collections4.iterators;

  18. import java.util.ArrayList;
  19. import java.util.BitSet;
  20. import java.util.Collection;
  21. import java.util.Comparator;
  22. import java.util.Iterator;
  23. import java.util.List;
  24. import java.util.NoSuchElementException;
  25. import java.util.Objects;

  26. import org.apache.commons.collections4.list.UnmodifiableList;

  27. /**
  28.  * Provides an ordered iteration over the elements contained in a collection of
  29.  * ordered Iterators.
  30.  * <p>
  31.  * Given two ordered {@link Iterator} instances {@code A} and
  32.  * {@code B}, the {@link #next} method on this iterator will return the
  33.  * lesser of {@code A.next()} and {@code B.next()}.
  34.  * </p>
  35.  *
  36.  * @param <E> the type of elements returned by this iterator.
  37.  * @since 2.1
  38.  */
  39. public class CollatingIterator<E> implements Iterator<E> {

  40.     /** The {@link Comparator} used to evaluate order. */
  41.     private Comparator<? super E> comparator;

  42.     /** The list of {@link Iterator}s to evaluate. */
  43.     private final List<Iterator<? extends E>> iterators;

  44.     /** {@link Iterator#next Next} objects peeked from each iterator. */
  45.     private List<E> values;

  46.     /** Whether or not each {@link #values} element has been set. */
  47.     private BitSet valueSet;

  48.     /**
  49.      * Index of the {@link #iterators iterator} from whom the last returned
  50.      * value was obtained.
  51.      */
  52.     private int lastReturned = -1;

  53.     /**
  54.      * Constructs a new {@code CollatingIterator}. A comparator must be
  55.      * set by calling {@link #setComparator(Comparator)} before invoking
  56.      * {@link #hasNext()}, or {@link #next()} for the first time. Child
  57.      * iterators will have to be manually added using the
  58.      * {@link #addIterator(Iterator)} method.
  59.      */
  60.     public CollatingIterator() {
  61.         this(null, 2);
  62.     }

  63.     /**
  64.      * Constructs a new {@code CollatingIterator} that will use the
  65.      * specified comparator for ordering. Child iterators will have to be
  66.      * manually added using the {@link #addIterator(Iterator)} method.
  67.      *
  68.      * @param comp the comparator to use to sort; must not be null,
  69.      *   unless you'll be invoking {@link #setComparator(Comparator)} later on.
  70.      */
  71.     public CollatingIterator(final Comparator<? super E> comp) {
  72.         this(comp, 2);
  73.     }

  74.     /**
  75.      * Constructs a new {@code CollatingIterator} that will use the
  76.      * specified comparator to provide ordered iteration over the collection of
  77.      * iterators.
  78.      *
  79.      * @param comp the comparator to use to sort; must not be null,
  80.      *   unless you'll be invoking {@link #setComparator(Comparator)} later on.
  81.      * @param iterators the collection of iterators
  82.      * @throws NullPointerException if the iterators collection is or contains null
  83.      * @throws ClassCastException if the iterators collection contains an
  84.      *   element that's not an {@link Iterator}
  85.      */
  86.     public CollatingIterator(final Comparator<? super E> comp, final Collection<Iterator<? extends E>> iterators) {
  87.         this(comp, iterators.size());
  88.         for (final Iterator<? extends E> iterator : iterators) {
  89.             addIterator(iterator);
  90.         }
  91.     }

  92.     /**
  93.      * Constructs a new {@code CollatingIterator} that will use the
  94.      * specified comparator for ordering and have the specified initial
  95.      * capacity. Child iterators will have to be manually added using the
  96.      * {@link #addIterator(Iterator)} method.
  97.      *
  98.      * @param comp the comparator to use to sort; must not be null,
  99.      *   unless you'll be invoking {@link #setComparator(Comparator)} later on.
  100.      * @param initIterCapacity the initial capacity for the internal list of
  101.      *   child iterators
  102.      */
  103.     public CollatingIterator(final Comparator<? super E> comp, final int initIterCapacity) {
  104.         iterators = new ArrayList<>(initIterCapacity);
  105.         setComparator(comp);
  106.     }

  107.     /**
  108.      * Constructs a new {@code CollatingIterator} that will use the
  109.      * specified comparator to provide ordered iteration over the two given
  110.      * iterators.
  111.      *
  112.      * @param comp the comparator to use to sort; must not be null,
  113.      *   unless you'll be invoking {@link #setComparator(Comparator)} later on.
  114.      * @param a the first child ordered iterator
  115.      * @param b the second child ordered iterator
  116.      * @throws NullPointerException if either iterator is null
  117.      */
  118.     public CollatingIterator(final Comparator<? super E> comp, final Iterator<? extends E> a,
  119.                              final Iterator<? extends E> b) {
  120.         this(comp, 2);
  121.         addIterator(a);
  122.         addIterator(b);
  123.     }

  124.     /**
  125.      * Constructs a new {@code CollatingIterator} that will use the
  126.      * specified comparator to provide ordered iteration over the array of
  127.      * iterators.
  128.      *
  129.      * @param comp the comparator to use to sort; must not be null,
  130.      *   unless you'll be invoking {@link #setComparator(Comparator)} later on.
  131.      * @param iterators the array of iterators
  132.      * @throws NullPointerException if iterators array is or contains null
  133.      */
  134.     public CollatingIterator(final Comparator<? super E> comp, final Iterator<? extends E>[] iterators) {
  135.         this(comp, iterators.length);
  136.         for (final Iterator<? extends E> iterator : iterators) {
  137.             addIterator(iterator);
  138.         }
  139.     }

  140.     /**
  141.      * Adds the given {@link Iterator} to the iterators being collated.
  142.      *
  143.      * @param iterator the iterator to add to the collation, must not be null
  144.      * @throws IllegalStateException if iteration has started
  145.      * @throws NullPointerException if the iterator is null
  146.      */
  147.     public void addIterator(final Iterator<? extends E> iterator) {
  148.         checkNotStarted();
  149.         Objects.requireNonNull(iterator, "iterator");
  150.         iterators.add(iterator);
  151.     }

  152.     /**
  153.      * Returns {@code true} iff any {@link Iterator} in the given list has
  154.      * a next value.
  155.      */
  156.     private boolean anyHasNext(final List<Iterator<? extends E>> iterators) {
  157.         for (final Iterator<? extends E> iterator : iterators) {
  158.             if (iterator.hasNext()) {
  159.                 return true;
  160.             }
  161.         }
  162.         return false;
  163.     }

  164.     /**
  165.      * Returns {@code true} iff any bit in the given set is
  166.      * {@code true}.
  167.      */
  168.     private boolean anyValueSet(final BitSet set) {
  169.         for (int i = 0; i < set.size(); i++) {
  170.             if (set.get(i)) {
  171.                 return true;
  172.             }
  173.         }
  174.         return false;
  175.     }

  176.     /**
  177.      * Throws {@link IllegalStateException} if iteration has started via
  178.      * {@link #start}.
  179.      *
  180.      * @throws IllegalStateException if iteration started
  181.      */
  182.     private void checkNotStarted() throws IllegalStateException {
  183.         if (values != null) {
  184.             throw new IllegalStateException("Can't do that after next or hasNext has been called.");
  185.         }
  186.     }

  187.     /**
  188.      * Clears the {@link #values} and {@link #valueSet} attributes at position
  189.      * <em>i</em>.
  190.      */
  191.     private void clear(final int i) {
  192.         values.set(i, null);
  193.         valueSet.clear(i);
  194.     }

  195.     /**
  196.      * Gets the {@link Comparator} by which collation occurs.
  197.      *
  198.      * @return the {@link Comparator}
  199.      */
  200.     public Comparator<? super E> getComparator() {
  201.         return comparator;
  202.     }

  203.     /**
  204.      * Gets the index of the iterator that returned the last element.
  205.      *
  206.      * @return the index of the iterator that returned the last element
  207.      * @throws IllegalStateException if there is no last returned element
  208.      */
  209.     public int getIteratorIndex() {
  210.         if (lastReturned == -1) {
  211.             throw new IllegalStateException("No value has been returned yet");
  212.         }

  213.         return lastReturned;
  214.     }

  215.     /**
  216.      * Gets the list of Iterators (unmodifiable).
  217.      *
  218.      * @return the unmodifiable list of iterators added
  219.      */
  220.     public List<Iterator<? extends E>> getIterators() {
  221.         return UnmodifiableList.unmodifiableList(iterators);
  222.     }

  223.     /**
  224.      * Returns {@code true} if any child iterator has remaining elements.
  225.      *
  226.      * @return true if this iterator has remaining elements
  227.      */
  228.     @Override
  229.     public boolean hasNext() {
  230.         start();
  231.         return anyValueSet(valueSet) || anyHasNext(iterators);
  232.     }

  233.     /**
  234.      * Returns the index of the least element in {@link #values},
  235.      * {@link #set(int) setting} any uninitialized values.
  236.      *
  237.      * @throws NullPointerException if no comparator is set
  238.      */
  239.     private int least() {
  240.         int leastIndex = -1;
  241.         E leastObject = null;
  242.         for (int i = 0; i < values.size(); i++) {
  243.             if (!valueSet.get(i)) {
  244.                 set(i);
  245.             }
  246.             if (valueSet.get(i)) {
  247.                 if (leastIndex == -1) {
  248.                     leastIndex = i;
  249.                     leastObject = values.get(i);
  250.                 } else {
  251.                     final E curObject = values.get(i);
  252.                     Objects.requireNonNull(comparator, "You must invoke setComparator() to set a comparator first.");
  253.                     if (comparator.compare(curObject, leastObject) < 0) {
  254.                         leastObject = curObject;
  255.                         leastIndex = i;
  256.                     }
  257.                 }
  258.             }
  259.         }
  260.         return leastIndex;
  261.     }

  262.     /**
  263.      * Returns the next ordered element from a child iterator.
  264.      *
  265.      * @return the next ordered element
  266.      * @throws NoSuchElementException if no child iterator has any more elements
  267.      */
  268.     @Override
  269.     public E next() throws NoSuchElementException {
  270.         if (!hasNext()) {
  271.             throw new NoSuchElementException();
  272.         }
  273.         final int leastIndex = least();
  274.         if (leastIndex == -1) {
  275.             throw new NoSuchElementException();
  276.         }
  277.         final E val = values.get(leastIndex);
  278.         clear(leastIndex);
  279.         lastReturned = leastIndex;
  280.         return val;
  281.     }

  282.     /**
  283.      * Removes the last returned element from the child iterator that produced it.
  284.      *
  285.      * @throws IllegalStateException if there is no last returned element, or if
  286.      * the last returned element has already been removed
  287.      */
  288.     @Override
  289.     public void remove() {
  290.         if (lastReturned == -1) {
  291.             throw new IllegalStateException("No value can be removed at present");
  292.         }
  293.         iterators.get(lastReturned).remove();
  294.     }

  295.     /**
  296.      * Sets the {@link #values} and {@link #valueSet} attributes at position
  297.      * <em>i</em> to the next value of the {@link #iterators iterator} at position
  298.      * <em>i</em>, or clear them if the <em>i</em><sup>th</sup> iterator has no next
  299.      * value.
  300.      *
  301.      * @return {@code false} iff there was no value to set
  302.      */
  303.     private boolean set(final int index) {
  304.         final Iterator<? extends E> it = iterators.get(index);
  305.         if (it.hasNext()) {
  306.             values.set(index, it.next());
  307.             valueSet.set(index);
  308.             return true;
  309.         }
  310.         values.set(index, null);
  311.         valueSet.clear(index);
  312.         return false;
  313.     }

  314.     /**
  315.      * Sets the {@link Comparator} by which collation occurs. If you
  316.      * would like to use the natural sort order (or, in other words,
  317.      * if the elements in the iterators are implementing the
  318.      * {@link Comparable} interface), then use the
  319.      * {@link org.apache.commons.collections4.comparators.ComparableComparator}.
  320.      *
  321.      * @param comp the {@link Comparator} to set
  322.      * @throws IllegalStateException if iteration has started
  323.      */
  324.     public void setComparator(final Comparator<? super E> comp) {
  325.         checkNotStarted();
  326.         comparator = comp;
  327.     }

  328.     /**
  329.      * Sets the iterator at the given index.
  330.      *
  331.      * @param index index of the Iterator to replace
  332.      * @param iterator Iterator to place at the given index
  333.      * @throws IndexOutOfBoundsException if index &lt; 0 or index &gt;= size()
  334.      * @throws IllegalStateException if iteration has started
  335.      * @throws NullPointerException if the iterator is null
  336.      */
  337.     public void setIterator(final int index, final Iterator<? extends E> iterator) {
  338.         checkNotStarted();
  339.         Objects.requireNonNull(iterator, "iterator");
  340.         iterators.set(index, iterator);
  341.     }

  342.     /**
  343.      * Initializes the collating state if it hasn't been already.
  344.      */
  345.     private void start() {
  346.         if (values == null) {
  347.             values = new ArrayList<>(iterators.size());
  348.             valueSet = new BitSet(iterators.size());
  349.             for (int i = 0; i < iterators.size(); i++) {
  350.                 values.add(null);
  351.                 valueSet.clear(i);
  352.             }
  353.         }
  354.     }

  355. }