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