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 }