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