001: /*
002: * Copyright 2004 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.iterators;
017:
018: import java.util.Iterator;
019: import java.util.NoSuchElementException;
020:
021: import org.apache.commons.collections.ArrayStack;
022: import org.apache.commons.collections.Transformer;
023:
024: /**
025: * An Iterator that can traverse multiple iterators down an object graph.
026: * <p>
027: * This iterator can extract multiple objects from a complex tree-like object graph.
028: * The iteration starts from a single root object.
029: * It uses a <code>Transformer</code> to extract the iterators and elements.
030: * Its main benefit is that no intermediate <code>List</code> is created.
031: * <p>
032: * For example, consider an object graph:
033: * <pre>
034: * |- Branch -- Leaf
035: * | \- Leaf
036: * |- Tree | /- Leaf
037: * | |- Branch -- Leaf
038: * Forest | \- Leaf
039: * | |- Branch -- Leaf
040: * | | \- Leaf
041: * |- Tree | /- Leaf
042: * |- Branch -- Leaf
043: * |- Branch -- Leaf</pre>
044: * The following <code>Transformer</code>, used in this class, will extract all
045: * the Leaf objects without creating a combined intermediate list:
046: * <pre>
047: * public Object transform(Object input) {
048: * if (input instanceof Forest) {
049: * return ((Forest) input).treeIterator();
050: * }
051: * if (input instanceof Tree) {
052: * return ((Tree) input).branchIterator();
053: * }
054: * if (input instanceof Branch) {
055: * return ((Branch) input).leafIterator();
056: * }
057: * if (input instanceof Leaf) {
058: * return input;
059: * }
060: * throw new ClassCastException();
061: * }</pre>
062: * <p>
063: * Internally, iteration starts from the root object. When next is called,
064: * the transformer is called to examine the object. The transformer will return
065: * either an iterator or an object. If the object is an Iterator, the next element
066: * from that iterator is obtained and the process repeats. If the element is an object
067: * it is returned.
068: * <p>
069: * Under many circumstances, linking Iterators together in this manner is
070: * more efficient (and convenient) than using nested for loops to extract a list.
071: *
072: * @since Commons Collections 3.1
073: * @version $Revision: 155406 $ $Date: 2005-02-26 12:55:26 +0000 (Sat, 26 Feb 2005) $
074: *
075: * @author Stephen Colebourne
076: */
077: public class ObjectGraphIterator implements Iterator {
078:
079: /** The stack of iterators */
080: protected final ArrayStack stack = new ArrayStack(8);
081: /** The root object in the tree */
082: protected Object root;
083: /** The transformer to use */
084: protected Transformer transformer;
085:
086: /** Whether there is another element in the iteration */
087: protected boolean hasNext = false;
088: /** The current iterator */
089: protected Iterator currentIterator;
090: /** The current value */
091: protected Object currentValue;
092: /** The last used iterator, needed for remove() */
093: protected Iterator lastUsedIterator;
094:
095: //-----------------------------------------------------------------------
096: /**
097: * Constructs an ObjectGraphIterator using a root object and transformer.
098: * <p>
099: * The root object can be an iterator, in which case it will be immediately
100: * looped around.
101: *
102: * @param root the root object, null will result in an empty iterator
103: * @param transformer the transformer to use, null will use a no effect transformer
104: */
105: public ObjectGraphIterator(Object root, Transformer transformer) {
106: super ();
107: if (root instanceof Iterator) {
108: this .currentIterator = (Iterator) 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(Iterator 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: protected void findNext(Object value) {
161: if (value instanceof Iterator) {
162: // need to examine this iterator
163: findNextByIterator((Iterator) value);
164: } else {
165: // next value found
166: currentValue = value;
167: hasNext = true;
168: }
169: }
170:
171: /**
172: * Finds the next object in the iteration given an iterator.
173: *
174: * @param iterator the iterator to start from
175: */
176: protected void findNextByIterator(Iterator iterator) {
177: if (iterator != currentIterator) {
178: // recurse a level
179: if (currentIterator != null) {
180: stack.push(currentIterator);
181: }
182: currentIterator = iterator;
183: }
184:
185: while (currentIterator.hasNext() && hasNext == false) {
186: Object next = currentIterator.next();
187: if (transformer != null) {
188: next = transformer.transform(next);
189: }
190: findNext(next);
191: }
192: if (hasNext) {
193: // next value found
194: } else if (stack.isEmpty()) {
195: // all iterators exhausted
196: } else {
197: // current iterator exhausted, go up a level
198: currentIterator = (Iterator) stack.pop();
199: findNextByIterator(currentIterator);
200: }
201: }
202:
203: //-----------------------------------------------------------------------
204: /**
205: * Checks whether there are any more elements in the iteration to obtain.
206: *
207: * @return true if elements remain in the iteration
208: */
209: public boolean hasNext() {
210: updateCurrentIterator();
211: return hasNext;
212: }
213:
214: /**
215: * Gets the next element of the iteration.
216: *
217: * @return the next element from the iteration
218: * @throws NoSuchElementException if all the Iterators are exhausted
219: */
220: public Object next() {
221: updateCurrentIterator();
222: if (hasNext == false) {
223: throw new NoSuchElementException(
224: "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(
249: "Iterator remove() cannot be called at this time");
250: }
251: lastUsedIterator.remove();
252: lastUsedIterator = null;
253: }
254:
255: }
|