    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 * <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    /** The root object in the tree */
    088    private E root;
    089    /** The transformer to use */
    090    private final Transformer<? super E, ? extends E> transformer;
    091
    092    /** Whether there is another element in the iteration */
    093    private boolean hasNext;
    094    /** The current iterator */
    095    private Iterator<? extends E> currentIterator;
    096    /** The current value */
    097    private E currentValue;
    098    /** The last used iterator, needed for remove() */
    099    private Iterator<? extends E> lastUsedIterator;
    100
    101    /**
    102     * Constructs an ObjectGraphIterator using a root object and transformer.
    103     * <p>
    104     * The root object can be an iterator, in which case it will be immediately
    105     * looped around.
    106     *
    107     * @param root  the root object, null will result in an empty iterator
    108     * @param transformer  the transformer to use, null will use a no effect transformer
    109     */
    110    @SuppressWarnings("unchecked")
    111    public ObjectGraphIterator(final E root, final Transformer<? super E, ? extends E> transformer) {
    112        if (root instanceof Iterator) {
    113            this.currentIterator = (Iterator<? extends E>) root;
    114        } else {
    115            this.root = root;
    116        }
    117        this.transformer = transformer;
    118    }
    119
    120    /**
    121     * Constructs a ObjectGraphIterator that will handle an iterator of iterators.
    122     * <p>
    123     * This constructor exists for convenience to emphasise that this class can
    124     * be used to iterate over nested iterators. That is to say that the iterator
    125     * passed in here contains other iterators, which may in turn contain further
    126     * iterators.
    127     * </p>
    128     *
    129     * @param rootIterator  the root iterator, null will result in an empty iterator
    130     */
    131    public ObjectGraphIterator(final Iterator<? extends E> rootIterator) {
    132        this.currentIterator = rootIterator;
    133        this.transformer = null;
    134    }
    135
    136    /**
    137     * Finds the next object in the iteration given any start object.
    138     *
    139     * @param value  the value to start from
    140     */
    141    @SuppressWarnings("unchecked")
    142    protected void findNext(final E value) {
    143        if (value instanceof Iterator) {
    144            // need to examine this iterator
    145            findNextByIterator((Iterator<? extends E>) value);
    146        } else {
    147            // next value found
    148            currentValue = value;
    149            hasNext = true;
    150        }
    151    }
    152
    153    /**
    154     * Finds the next object in the iteration given an iterator.
    155     *
    156     * @param iterator  the iterator to start from
    157     */
    158    protected void findNextByIterator(final Iterator<? extends E> iterator) {
    159        if (iterator != currentIterator) {
    160            // recurse a level
    161            if (currentIterator != null) {
    162                stack.push(currentIterator);
    163            }
    164            currentIterator = iterator;
    165        }
    166
    167        while (currentIterator.hasNext() && !hasNext) {
    168            E next = currentIterator.next();
    169            if (transformer != null) {
    170                next = transformer.apply(next);
    171            }
    172            findNext(next);
    173        }
    174        // if we haven't found the next value and iterators are not yet exhausted
    175        if (!hasNext && !stack.isEmpty()) {
    176            // current iterator exhausted, go up a level
    177            currentIterator = stack.pop();
    178            findNextByIterator(currentIterator);
    179        }
    180    }
    181
    182    /**
    183     * Checks whether there are any more elements in the iteration to obtain.
    184     *
    185     * @return true if elements remain in the iteration
    186     */
    187    @Override
    188    public boolean hasNext() {
    189        updateCurrentIterator();
    190        return hasNext;
    191    }
    192
    193    /**
    194     * Gets the next element of the iteration.
    195     *
    196     * @return the next element from the iteration
    197     * @throws NoSuchElementException if all the Iterators are exhausted
    198     */
    199    @Override
    200    public E next() {
    201        updateCurrentIterator();
    202        if (!hasNext) {
    203            throw new NoSuchElementException("No more elements in the iteration");
    204        }
    205        lastUsedIterator = currentIterator;
    206        final E result = currentValue;
    207        currentValue = null;
    208        hasNext = false;
    209        return result;
    210    }
    211
    212    /**
    213     * Removes from the underlying collection the last element returned.
    214     * <p>
    215     * This method calls remove() on the underlying Iterator, and it may
    216     * throw an UnsupportedOperationException if the underlying Iterator
    217     * does not support this method.
    218     * </p>
    219     *
    220     * @throws UnsupportedOperationException
    221     *   if the remove operator is not supported by the underlying Iterator
    222     * @throws IllegalStateException
    223     *   if the next method has not yet been called, or the remove method has
    224     *   already been called after the last call to the next method.
    225     */
    226    @Override
    227    public void remove() {
    228        if (lastUsedIterator == null) {
    229            throw new IllegalStateException("Iterator remove() cannot be called at this time");
    230        }
    231        lastUsedIterator.remove();
    232        lastUsedIterator = null;
    233    }
    234
    235    /**
    236     * Loops around the iterators to find the next value to return.
    237     */
    238    protected void updateCurrentIterator() {
    239        if (hasNext) {
    240            return;
    241        }
    242        if (currentIterator == null) {
    243            if (root == null) { // NOPMD
    244                // do nothing, hasNext will be false
    245            } else {
    246                if (transformer == null) {
    247                    findNext(root);
    248                } else {
    249                    findNext(transformer.apply(root));
    250                }
    251                root = null;
    252            }
    253        } else {
    254            findNextByIterator(currentIterator);
    255        }
    256    }
    257
    258}