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     */
017    package org.apache.commons.collections.iterators;
018    
019    import java.util.Iterator;
020    import java.util.NoSuchElementException;
021    
022    import org.apache.commons.collections.ArrayStack;
023    import org.apache.commons.collections.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 Commons Collections 3.1
074     * @version $Revision: 647116 $ $Date: 2008-04-11 12:23:08 +0100 (Fri, 11 Apr 2008) $
075     * 
076     * @author Stephen Colebourne
077     */
078    public class ObjectGraphIterator implements Iterator {
079    
080        /** The stack of iterators */
081        protected final ArrayStack stack = new ArrayStack(8);
082        /** The root object in the tree */
083        protected Object root;
084        /** The transformer to use */
085        protected Transformer transformer;
086    
087        /** Whether there is another element in the iteration */
088        protected boolean hasNext = false;    
089        /** The current iterator */
090        protected Iterator currentIterator;
091        /** The current value */
092        protected Object currentValue;
093        /** The last used iterator, needed for remove() */
094        protected Iterator lastUsedIterator;
095    
096        //-----------------------------------------------------------------------
097        /**
098         * Constructs an ObjectGraphIterator using a root object and transformer.
099         * <p>
100         * The root object can be an iterator, in which case it will be immediately
101         * looped around.
102         * 
103         * @param root  the root object, null will result in an empty iterator
104         * @param transformer  the transformer to use, null will use a no effect transformer
105         */
106        public ObjectGraphIterator(Object root, Transformer transformer) {
107            super();
108            if (root instanceof Iterator) {
109                this.currentIterator = (Iterator) 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(Iterator 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) {
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        protected void findNext(Object value) {
162            if (value instanceof Iterator) {
163                // need to examine this iterator
164                findNextByIterator((Iterator) value);
165            } else {
166                // next value found
167                currentValue = value;
168                hasNext = true;
169            }
170        }
171        
172        /**
173         * Finds the next object in the iteration given an iterator.
174         * 
175         * @param iterator  the iterator to start from
176         */
177        protected void findNextByIterator(Iterator iterator) {
178            if (iterator != currentIterator) {
179                // recurse a level
180                if (currentIterator != null) {
181                    stack.push(currentIterator);
182                }
183                currentIterator = iterator;
184            }
185            
186            while (currentIterator.hasNext() && hasNext == false) {
187                Object next = currentIterator.next();
188                if (transformer != null) {
189                    next = transformer.transform(next);
190                }
191                findNext(next);
192            }
193            if (hasNext) {
194                // next value found
195            } else if (stack.isEmpty()) {
196                // all iterators exhausted
197            } else {
198                // current iterator exhausted, go up a level
199                currentIterator = (Iterator) stack.pop();
200                findNextByIterator(currentIterator);
201            }
202        }
203    
204        //-----------------------------------------------------------------------
205        /**
206         * Checks whether there are any more elements in the iteration to obtain.
207         * 
208         * @return true if elements remain in the iteration
209         */
210        public boolean hasNext() {
211            updateCurrentIterator();
212            return hasNext;
213        }
214    
215        /**
216         * Gets the next element of the iteration.
217         * 
218         * @return the next element from the iteration
219         * @throws NoSuchElementException if all the Iterators are exhausted
220         */
221        public Object next() {
222            updateCurrentIterator();
223            if (hasNext == false) {
224                throw new NoSuchElementException("No more elements in the iteration");
225            }
226            lastUsedIterator = currentIterator;
227            Object result = currentValue;
228            currentValue = null;
229            hasNext = false;
230            return result;
231        }
232    
233        /**
234         * Removes from the underlying collection the last element returned.
235         * <p>
236         * This method calls remove() on the underlying Iterator and it may
237         * throw an UnsupportedOperationException if the underlying Iterator
238         * does not support this method. 
239         * 
240         * @throws UnsupportedOperationException
241         *   if the remove operator is not supported by the underlying Iterator
242         * @throws IllegalStateException
243         *   if the next method has not yet been called, or the remove method has
244         *   already been called after the last call to the next method.
245         */
246        public void remove() {
247            if (lastUsedIterator == null) {
248                throw new IllegalStateException("Iterator remove() cannot be called at this time");
249            }
250            lastUsedIterator.remove();
251            lastUsedIterator = null;
252        }
253    
254    }