    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.ArrayDeque;
    020import java.util.Deque;
    021import java.util.Iterator;
    022import java.util.NoSuchElementException;
    023
    024import org.apache.commons.collections4.Transformer;
    025
    026/**
    027 * An Iterator that can traverse multiple iterators down an object graph.
    028 * <p>
    029 * This iterator can extract multiple objects from a complex tree-like object graph.
    030 * The iteration starts from a single root object.
    031 * It uses a {@code Transformer} to extract the iterators and elements.
    032 * Its main benefit is that no intermediate {@code List} is created.
    033 * </p>
    034 * <p>
    035 * For example, consider an object graph:
    036 * </p>
    037 * <pre>
    038 *                 |- Branch -- Leaf
    039 *                 |         \- Leaf
    040 *         |- Tree |         /- Leaf
    041 *         |       |- Branch -- Leaf
    042 *  Forest |                 \- Leaf
    043 *         |       |- Branch -- Leaf
    044 *         |       |         \- Leaf
    045 *         |- Tree |         /- Leaf
    046 *                 |- Branch -- Leaf
    047 *                 |- Branch -- Leaf</pre>
    048 * <p>
    049 * The following {@code Transformer}, used in this class, will extract all
    050 * the Leaf objects without creating a combined intermediate list:
    051 * </p>
    052 * <pre>
    053 * public Object transform(Object input) {
    054 *   if (input instanceof Forest) {
    055 *     return ((Forest) input).treeIterator();
    056 *   }
    057 *   if (input instanceof Tree) {
    058 *     return ((Tree) input).branchIterator();
    059 *   }
    060 *   if (input instanceof Branch) {
    061 *     return ((Branch) input).leafIterator();
    062 *   }
    063 *   if (input instanceof Leaf) {
    064 *     return input;
    065 *   }
    066 *   throw new ClassCastException();
    067 * }</pre>
    068 * <p>
    069 * Internally, iteration starts from the root object. When next is called,
    070 * the transformer is called to examine the object. The transformer will return
    071 * either an iterator or an object. If the object is an Iterator, the next element
    072 * from that iterator is obtained and the process repeats. If the element is an object
    073 * it is returned.
    074 * </p>
    075 * <p>
    076 * Under many circumstances, linking Iterators together in this manner is
    077 * more efficient (and convenient) than using nested for loops to extract a list.
    078 * </p>
    079 *
    080 * @param <E> The type of elements returned by this iterator.
    081 * @since 3.1
    082 */
    083public class ObjectGraphIterator<E> implements Iterator<E> {
    084
    085    /** The stack of iterators */
    086    private final Deque<Iterator<? extends E>> stack = new ArrayDeque<>(8);
    087
    088    /** The root object in the tree */
    089    private E root;
    090
    091    /** The transformer to use */
    092    private final Transformer<? super E, ? extends E> transformer;
    093
    094    /** Whether there is another element in the iteration */
    095    private boolean hasNext;
    096
    097    /** The current iterator */
    098    private Iterator<? extends E> currentIterator;
    099
    100    /** The current value */
    101    private E currentValue;
    102
    103    /** The last used iterator, needed for remove() */
    104    private Iterator<? extends E> lastUsedIterator;
    105
    106    /**
    107     * Constructs an ObjectGraphIterator using a root object and transformer.
    108     * <p>
    109     * The root object can be an iterator, in which case it will be immediately
    110     * looped around.
    111     *
    112     * @param root  The root object, null will result in an empty iterator
    113     * @param transformer  The transformer to use, null will use a no effect transformer
    114     */
    115    @SuppressWarnings("unchecked")
    116    public ObjectGraphIterator(final E root, final Transformer<? super E, ? extends E> transformer) {
    117        if (root instanceof Iterator) {
    118            this.currentIterator = (Iterator<? extends E>) root;
    119        } else {
    120            this.root = root;
    121        }
    122        this.transformer = transformer;
    123    }
    124
    125    /**
    126     * Constructs a ObjectGraphIterator that will handle an iterator of iterators.
    127     * <p>
    128     * This constructor exists for convenience to emphasise that this class can
    129     * be used to iterate over nested iterators. That is to say that the iterator
    130     * passed in here contains other iterators, which may in turn contain further
    131     * iterators.
    132     * </p>
    133     *
    134     * @param rootIterator  The root iterator, null will result in an empty iterator
    135     */
    136    public ObjectGraphIterator(final Iterator<? extends E> rootIterator) {
    137        this.currentIterator = rootIterator;
    138        this.transformer = null;
    139    }
    140
    141    /**
    142     * Finds the next object in the iteration given any start object.
    143     *
    144     * @param value  The value to start from
    145     */
    146    @SuppressWarnings("unchecked")
    147    protected void findNext(final E value) {
    148        if (value instanceof Iterator) {
    149            // need to examine this iterator
    150            findNextByIterator((Iterator<? extends E>) value);
    151        } else {
    152            // next value found
    153            currentValue = value;
    154            hasNext = true;
    155        }
    156    }
    157
    158    /**
    159     * Finds the next object in the iteration given an iterator.
    160     *
    161     * @param iterator  The iterator to start from
    162     */
    163    protected void findNextByIterator(final Iterator<? extends E> iterator) {
    164        if (iterator != currentIterator) {
    165            // recurse a level
    166            if (currentIterator != null) {
    167                stack.push(currentIterator);
    168            }
    169            currentIterator = iterator;
    170        }
    171
    172        while (currentIterator.hasNext() && !hasNext) {
    173            E next = currentIterator.next();
    174            if (transformer != null) {
    175                next = transformer.apply(next);
    176            }
    177            findNext(next);
    178        }
    179        // if we haven't found the next value and iterators are not yet exhausted
    180        if (!hasNext && !stack.isEmpty()) {
    181            // current iterator exhausted, go up a level
    182            currentIterator = stack.pop();
    183            findNextByIterator(currentIterator);
    184        }
    185    }
    186
    187    /**
    188     * Checks whether there are any more elements in the iteration to obtain.
    189     *
    190     * @return true if elements remain in the iteration
    191     */
    192    @Override
    193    public boolean hasNext() {
    194        updateCurrentIterator();
    195        return hasNext;
    196    }
    197
    198    /**
    199     * Gets the next element of the iteration.
    200     *
    201     * @return The next element from the iteration
    202     * @throws NoSuchElementException if all the Iterators are exhausted
    203     */
    204    @Override
    205    public E next() {
    206        updateCurrentIterator();
    207        if (!hasNext) {
    208            throw new NoSuchElementException("No more elements in the iteration");
    209        }
    210        lastUsedIterator = currentIterator;
    211        final E result = currentValue;
    212        currentValue = null;
    213        hasNext = false;
    214        return result;
    215    }
    216
    217    /**
    218     * Removes from the underlying collection the last element returned.
    219     * <p>
    220     * This method calls remove() on the underlying Iterator, and it may
    221     * throw an UnsupportedOperationException if the underlying Iterator
    222     * does not support this method.
    223     * </p>
    224     *
    225     * @throws UnsupportedOperationException
    226     *   if the remove operator is not supported by the underlying Iterator
    227     * @throws IllegalStateException
    228     *   if the next method has not yet been called, or the remove method has
    229     *   already been called after the last call to the next method.
    230     */
    231    @Override
    232    public void remove() {
    233        if (lastUsedIterator == null) {
    234            throw new IllegalStateException("Iterator remove() cannot be called at this time");
    235        }
    236        lastUsedIterator.remove();
    237        lastUsedIterator = null;
    238    }
    239
    240    /**
    241     * Loops around the iterators to find the next value to return.
    242     */
    243    protected void updateCurrentIterator() {
    244        if (hasNext) {
    245            return;
    246        }
    247        if (currentIterator == null) {
    248            if (root == null) { // NOPMD
    249                // do nothing, hasNext will be false
    250            } else {
    251                if (transformer == null) {
    252                    findNext(root);
    253                } else {
    254                    findNext(transformer.apply(root));
    255                }
    256                root = null;
    257            }
    258        } else {
    259            findNextByIterator(currentIterator);
    260        }
    261    }
    262
    263}