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

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.NoSuchElementException;

import org.apache.commons.collections4.Transformer;

An Iterator that can traverse multiple iterators down an object graph.

This iterator can extract multiple objects from a complex tree-like object graph.
The iteration starts from a single root object.
It uses a Transformer to extract the iterators and elements.
Its main benefit is that no intermediate List is created.

For example, consider an object graph:
                |- Branch -- Leaf
                |         \- Leaf
        |- Tree |         /- Leaf
        |       |- Branch -- Leaf
 Forest |                 \- Leaf
        |       |- Branch -- Leaf
        |       |         \- Leaf
        |- Tree |         /- Leaf
                |- Branch -- Leaf
                |- Branch -- Leaf
The following Transformer, used in this class, will extract all
the Leaf objects without creating a combined intermediate list:
public Object transform(Object input) {
  if (input instanceof Forest) {
    return ((Forest) input).treeIterator();
  }
  if (input instanceof Tree) {
    return ((Tree) input).branchIterator();
  }
  if (input instanceof Branch) {
    return ((Branch) input).leafIterator();
  }
  if (input instanceof Leaf) {
    return input;
  }
  throw new ClassCastException();
}

Internally, iteration starts from the root object. When next is called,
the transformer is called to examine the object. The transformer will return
either an iterator or an object. If the object is an Iterator, the next element
from that iterator is obtained and the process repeats. If the element is an object
it is returned.

Under many circumstances, linking Iterators together in this manner is
more efficient (and convenient) than using nested for loops to extract a list.
Since:
3.1/**
 * An Iterator that can traverse multiple iterators down an object graph.
 * <p>
 * This iterator can extract multiple objects from a complex tree-like object graph.
 * The iteration starts from a single root object.
 * It uses a <code>Transformer</code> to extract the iterators and elements.
 * Its main benefit is that no intermediate <code>List</code> is created.
 * <p>
 * For example, consider an object graph:
 * <pre>
 *                 |- Branch -- Leaf
 *                 |         \- Leaf
 *         |- Tree |         /- Leaf
 *         |       |- Branch -- Leaf
 *  Forest |                 \- Leaf
 *         |       |- Branch -- Leaf
 *         |       |         \- Leaf
 *         |- Tree |         /- Leaf
 *                 |- Branch -- Leaf
 *                 |- Branch -- Leaf</pre>
 * The following <code>Transformer</code>, used in this class, will extract all
 * the Leaf objects without creating a combined intermediate list:
 * <pre>
 * public Object transform(Object input) {
 *   if (input instanceof Forest) {
 *     return ((Forest) input).treeIterator();
 *   }
 *   if (input instanceof Tree) {
 *     return ((Tree) input).branchIterator();
 *   }
 *   if (input instanceof Branch) {
 *     return ((Branch) input).leafIterator();
 *   }
 *   if (input instanceof Leaf) {
 *     return input;
 *   }
 *   throw new ClassCastException();
 * }</pre>
 * <p>
 * Internally, iteration starts from the root object. When next is called,
 * the transformer is called to examine the object. The transformer will return
 * either an iterator or an object. If the object is an Iterator, the next element
 * from that iterator is obtained and the process repeats. If the element is an object
 * it is returned.
 * <p>
 * Under many circumstances, linking Iterators together in this manner is
 * more efficient (and convenient) than using nested for loops to extract a list.
 *
 * @since 3.1
 */
public class ObjectGraphIterator<E> implements Iterator<E> {

    
The stack of iterators /** The stack of iterators */
    private final Deque<Iterator<? extends E>> stack = new ArrayDeque<>(8);
    
The root object in the tree /** The root object in the tree */
    private E root;
    
The transformer to use /** The transformer to use */
    private final Transformer<? super E, ? extends E> transformer;

    
Whether there is another element in the iteration /** Whether there is another element in the iteration */
    private boolean hasNext = false;
    
The current iterator /** The current iterator */
    private Iterator<? extends E> currentIterator;
    
The current value /** The current value */
    private E currentValue;
    
The last used iterator, needed for remove() /** The last used iterator, needed for remove() */
    private Iterator<? extends E> lastUsedIterator;

    //-----------------------------------------------------------------------
    
Constructs an ObjectGraphIterator using a root object and transformer.

The root object can be an iterator, in which case it will be immediately
looped around.
Params:
root –  the root object, null will result in an empty iterator
transformer –  the transformer to use, null will use a no effect transformer/**
     * Constructs an ObjectGraphIterator using a root object and transformer.
     * <p>
     * The root object can be an iterator, in which case it will be immediately
     * looped around.
     *
     * @param root  the root object, null will result in an empty iterator
     * @param transformer  the transformer to use, null will use a no effect transformer
     */
    @SuppressWarnings("unchecked")
    public ObjectGraphIterator(final E root, final Transformer<? super E, ? extends E> transformer) {
        super();
        if (root instanceof Iterator) {
            this.currentIterator = (Iterator<? extends E>) root;
        } else {
            this.root = root;
        }
        this.transformer = transformer;
    }

    
Constructs a ObjectGraphIterator that will handle an iterator of iterators.

This constructor exists for convenience to emphasise that this class can
be used to iterate over nested iterators. That is to say that the iterator
passed in here contains other iterators, which may in turn contain further
iterators.
Params:
rootIterator –  the root iterator, null will result in an empty iterator/**
     * Constructs a ObjectGraphIterator that will handle an iterator of iterators.
     * <p>
     * This constructor exists for convenience to emphasise that this class can
     * be used to iterate over nested iterators. That is to say that the iterator
     * passed in here contains other iterators, which may in turn contain further
     * iterators.
     *
     * @param rootIterator  the root iterator, null will result in an empty iterator
     */
    public ObjectGraphIterator(final Iterator<? extends E> rootIterator) {
        super();
        this.currentIterator = rootIterator;
        this.transformer = null;
    }

    //-----------------------------------------------------------------------
    
Loops around the iterators to find the next value to return.
/**
     * Loops around the iterators to find the next value to return.
     */
    protected void updateCurrentIterator() {
        if (hasNext) {
            return;
        }
        if (currentIterator == null) {
            if (root == null) { // NOPMD
                // do nothing, hasNext will be false
            } else {
                if (transformer == null) {
                    findNext(root);
                } else {
                    findNext(transformer.transform(root));
                }
                root = null;
            }
        } else {
            findNextByIterator(currentIterator);
        }
    }

    
Finds the next object in the iteration given any start object.
Params:
value –  the value to start from/**
     * Finds the next object in the iteration given any start object.
     *
     * @param value  the value to start from
     */
    @SuppressWarnings("unchecked")
    protected void findNext(final E value) {
        if (value instanceof Iterator) {
            // need to examine this iterator
            findNextByIterator((Iterator<? extends E>) value);
        } else {
            // next value found
            currentValue = value;
            hasNext = true;
        }
    }

    
Finds the next object in the iteration given an iterator.
Params:
iterator –  the iterator to start from/**
     * Finds the next object in the iteration given an iterator.
     *
     * @param iterator  the iterator to start from
     */
    protected void findNextByIterator(final Iterator<? extends E> iterator) {
        if (iterator != currentIterator) {
            // recurse a level
            if (currentIterator != null) {
                stack.push(currentIterator);
            }
            currentIterator = iterator;
        }

        while (currentIterator.hasNext() && hasNext == false) {
            E next = currentIterator.next();
            if (transformer != null) {
                next = transformer.transform(next);
            }
            findNext(next);
        }
        // if we havn't found the next value and iterators are not yet exhausted
        if (!hasNext && !stack.isEmpty()) {
            // current iterator exhausted, go up a level
            currentIterator = stack.pop();
            findNextByIterator(currentIterator);
        }
    }

    //-----------------------------------------------------------------------
    
Checks whether there are any more elements in the iteration to obtain.
Returns:
true if elements remain in the iteration/**
     * Checks whether there are any more elements in the iteration to obtain.
     *
     * @return true if elements remain in the iteration
     */
    @Override
    public boolean hasNext() {
        updateCurrentIterator();
        return hasNext;
    }

    
Gets the next element of the iteration.
Throws:
NoSuchElementException – if all the Iterators are exhausted
Returns:
the next element from the iteration/**
     * Gets the next element of the iteration.
     *
     * @return the next element from the iteration
     * @throws NoSuchElementException if all the Iterators are exhausted
     */
    @Override
    public E next() {
        updateCurrentIterator();
        if (hasNext == false) {
            throw new NoSuchElementException("No more elements in the iteration");
        }
        lastUsedIterator = currentIterator;
        final E result = currentValue;
        currentValue = null;
        hasNext = false;
        return result;
    }

    
Removes from the underlying collection the last element returned.

This method calls remove() on the underlying Iterator and it may
throw an UnsupportedOperationException if the underlying Iterator
does not support this method.
Throws:
UnsupportedOperationException – 
  if the remove operator is not supported by the underlying Iterator
IllegalStateException – 
  if the next method has not yet been called, or the remove method has
  already been called after the last call to the next method./**
     * Removes from the underlying collection the last element returned.
     * <p>
     * This method calls remove() on the underlying Iterator and it may
     * throw an UnsupportedOperationException if the underlying Iterator
     * does not support this method.
     *
     * @throws UnsupportedOperationException
     *   if the remove operator is not supported by the underlying Iterator
     * @throws IllegalStateException
     *   if the next method has not yet been called, or the remove method has
     *   already been called after the last call to the next method.
     */
    @Override
    public void remove() {
        if (lastUsedIterator == null) {
            throw new IllegalStateException("Iterator remove() cannot be called at this time");
        }
        lastUsedIterator.remove();
        lastUsedIterator = null;
    }

}