1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections.iterators;
18
19 import java.util.Iterator;
20 import java.util.NoSuchElementException;
21
22 import org.apache.commons.collections.ArrayStack;
23 import org.apache.commons.collections.Transformer;
24
25 /**
26 * An Iterator that can traverse multiple iterators down an object graph.
27 * <p>
28 * This iterator can extract multiple objects from a complex tree-like object graph.
29 * The iteration starts from a single root object.
30 * It uses a <code>Transformer</code> to extract the iterators and elements.
31 * Its main benefit is that no intermediate <code>List</code> is created.
32 * <p>
33 * For example, consider an object graph:
34 * <pre>
35 * |- Branch -- Leaf
36 * | \- Leaf
37 * |- Tree | /- Leaf
38 * | |- Branch -- Leaf
39 * Forest | \- Leaf
40 * | |- Branch -- Leaf
41 * | | \- Leaf
42 * |- Tree | /- Leaf
43 * |- Branch -- Leaf
44 * |- Branch -- Leaf</pre>
45 * The following <code>Transformer</code>, used in this class, will extract all
46 * the Leaf objects without creating a combined intermediate list:
47 * <pre>
48 * public Object transform(Object input) {
49 * if (input instanceof Forest) {
50 * return ((Forest) input).treeIterator();
51 * }
52 * if (input instanceof Tree) {
53 * return ((Tree) input).branchIterator();
54 * }
55 * if (input instanceof Branch) {
56 * return ((Branch) input).leafIterator();
57 * }
58 * if (input instanceof Leaf) {
59 * return input;
60 * }
61 * throw new ClassCastException();
62 * }</pre>
63 * <p>
64 * Internally, iteration starts from the root object. When next is called,
65 * the transformer is called to examine the object. The transformer will return
66 * either an iterator or an object. If the object is an Iterator, the next element
67 * from that iterator is obtained and the process repeats. If the element is an object
68 * it is returned.
69 * <p>
70 * Under many circumstances, linking Iterators together in this manner is
71 * more efficient (and convenient) than using nested for loops to extract a list.
72 *
73 * @since 3.1
74 * @version $Id: ObjectGraphIterator.java 1429905 2013-01-07 17:15:14Z ggregory $
75 */
76 public class ObjectGraphIterator<E> implements Iterator<E> {
77
78 /** The stack of iterators */
79 protected final ArrayStack<Iterator<? extends E>> stack = new ArrayStack<Iterator<? extends E>>(8);
80 /** The root object in the tree */
81 protected E root;
82 /** The transformer to use */
83 protected final Transformer<? super E, ? extends E> transformer;
84
85 /** Whether there is another element in the iteration */
86 protected boolean hasNext = false;
87 /** The current iterator */
88 protected Iterator<? extends E> currentIterator;
89 /** The current value */
90 protected E currentValue;
91 /** The last used iterator, needed for remove() */
92 protected Iterator<? extends E> lastUsedIterator;
93
94 //-----------------------------------------------------------------------
95 /**
96 * Constructs an ObjectGraphIterator using a root object and transformer.
97 * <p>
98 * The root object can be an iterator, in which case it will be immediately
99 * looped around.
100 *
101 * @param root the root object, null will result in an empty iterator
102 * @param transformer the transformer to use, null will use a no effect transformer
103 */
104 @SuppressWarnings("unchecked")
105 public ObjectGraphIterator(final E root, final Transformer<? super E, ? extends E> transformer) {
106 super();
107 if (root instanceof Iterator) {
108 this.currentIterator = (Iterator<? extends E>) root;
109 } else {
110 this.root = root;
111 }
112 this.transformer = transformer;
113 }
114
115 /**
116 * Constructs a ObjectGraphIterator that will handle an iterator of iterators.
117 * <p>
118 * This constructor exists for convenience to emphasise that this class can
119 * be used to iterate over nested iterators. That is to say that the iterator
120 * passed in here contains other iterators, which may in turn contain further
121 * iterators.
122 *
123 * @param rootIterator the root iterator, null will result in an empty iterator
124 */
125 public ObjectGraphIterator(final Iterator<? extends E> rootIterator) {
126 super();
127 this.currentIterator = rootIterator;
128 this.transformer = null;
129 }
130
131 //-----------------------------------------------------------------------
132 /**
133 * Loops around the iterators to find the next value to return.
134 */
135 protected void updateCurrentIterator() {
136 if (hasNext) {
137 return;
138 }
139 if (currentIterator == null) {
140 if (root == null) {
141 // do nothing, hasNext will be false
142 } else {
143 if (transformer == null) {
144 findNext(root);
145 } else {
146 findNext(transformer.transform(root));
147 }
148 root = null;
149 }
150 } else {
151 findNextByIterator(currentIterator);
152 }
153 }
154
155 /**
156 * Finds the next object in the iteration given any start object.
157 *
158 * @param value the value to start from
159 */
160 @SuppressWarnings("unchecked")
161 protected void findNext(final E value) {
162 if (value instanceof Iterator) {
163 // need to examine this iterator
164 findNextByIterator((Iterator<? extends E>) 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(final Iterator<? extends E> 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 E 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 = 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 E next() {
222 updateCurrentIterator();
223 if (hasNext == false) {
224 throw new NoSuchElementException("No more elements in the iteration");
225 }
226 lastUsedIterator = currentIterator;
227 final E 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 }