/*
    * 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.
   * <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} to extract the iterators and elements.
   * Its main benefit is that no intermediate {@code List} is created.
   * </p>
   * <p>
   * For example, consider an object graph:
   * </p>
   * <pre>
   *                 |- Branch -- Leaf
   *                 |         \- Leaf
   *         |- Tree |         /- Leaf
   *         |       |- Branch -- Leaf
   *  Forest |                 \- Leaf
   *         |       |- Branch -- Leaf
   *         |       |         \- Leaf
   *         |- Tree |         /- Leaf
   *                 |- Branch -- Leaf
   *                 |- Branch -- Leaf</pre>
   * <p>
   * The following {@code Transformer}, used in this class, will extract all
   * the Leaf objects without creating a combined intermediate list:
   * </p>
   * <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>
   * <p>
   * Under many circumstances, linking Iterators together in this manner is
   * more efficient (and convenient) than using nested for loops to extract a list.
   * </p>
   *
   * @param <E> the type of elements returned by this iterator.
   * @since 3.1
   */
  public class ObjectGraphIterator<E> implements Iterator<E> {
  
      /** The stack of iterators */
      private final Deque<Iterator<? extends E>> stack = new ArrayDeque<>(8);
      /** The root object in the tree */
      private E root;
      /** The transformer to use */
      private final Transformer<? super E, ? extends E> transformer;
  
      /** Whether there is another element in the iteration */
      private boolean hasNext;
      /** The current iterator */
      private Iterator<? extends E> currentIterator;
      /** The current value */
      private E currentValue;
      /** The last used iterator, needed for remove() */
      private Iterator<? extends E> lastUsedIterator;
 
     /**
      * 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) {
         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.
      * <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.
      * </p>
      *
      * @param rootIterator  the root iterator, null will result in an empty iterator
      */
     public ObjectGraphIterator(final Iterator<? extends E> rootIterator) {
         this.currentIterator = rootIterator;
         this.transformer = null;
     }
 
     /**
      * 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.
      *
      * @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) {
             E next = currentIterator.next();
             if (transformer != null) {
                 next = transformer.apply(next);
             }
             findNext(next);
         }
         // if we haven'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.
      *
      * @return true if elements remain in the iteration
      */
     @Override
     public boolean hasNext() {
         updateCurrentIterator();
         return hasNext;
     }
 
     /**
      * 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) {
             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.
      * <p>
      * This method calls remove() on the underlying Iterator, and it may
      * throw an UnsupportedOperationException if the underlying Iterator
      * does not support this method.
      * </p>
      *
      * @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;
     }
 
     /**
      * 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.apply(root));
                 }
                 root = null;
             }
         } else {
             findNextByIterator(currentIterator);
         }
     }
 
 }