ObjectGraphIterator


1   /*
2    *  Copyright 2004 The Apache Software Foundation
3    *
4    *  Licensed under the Apache License, Version 2.0 (the "License");
5    *  you may not use this file except in compliance with the License.
6    *  You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   *  Unless required by applicable law or agreed to in writing, software
11   *  distributed under the License is distributed on an "AS IS" BASIS,
12   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   *  See the License for the specific language governing permissions and
14   *  limitations under the License.
15   */
16  package org.apache.commons.collections.iterators;
17  
18  import java.util.Iterator  ;
19  import java.util.NoSuchElementException  ;
20  
21  import org.apache.commons.collections.ArrayStack;
22  import org.apache.commons.collections.Transformer;
23  
24  /**
25   * An Iterator that can traverse multiple iterators down an object graph.
26   * <p>
27   * This iterator can extract multiple objects from a complex tree-like object graph.
28   * The iteration starts from a single root object.
29   * It uses a <code>Transformer</code> to extract the iterators and elements.
30   * Its main benefit is that no intermediate <code>List</code> is created.
31   * <p>
32   * For example, consider an object graph:
33   * <pre>
34   *                 |- Branch -- Leaf
35   *                 |         \- Leaf
36   *         |- Tree |         /- Leaf
37   *         |       |- Branch -- Leaf
38   *  Forest |                 \- Leaf
39   *         |       |- Branch -- Leaf
40   *         |       |         \- Leaf
41   *         |- Tree |         /- Leaf
42   *                 |- Branch -- Leaf
43   *                 |- Branch -- Leaf</pre>
44   * The following <code>Transformer</code>, used in this class, will extract all
45   * the Leaf objects without creating a combined intermediate list:
46   * <pre>
47   * public Object transform(Object input) {
48   *   if (input instanceof Forest) {
49   *     return ((Forest) input).treeIterator();
50   *   }
51   *   if (input instanceof Tree) {
52   *     return ((Tree) input).branchIterator();
53   *   }
54   *   if (input instanceof Branch) {
55   *     return ((Branch) input).leafIterator();
56   *   }
57   *   if (input instanceof Leaf) {
58   *     return input;
59   *   }
60   *   throw new ClassCastException();
61   * }</pre>
62   * <p>
63   * Internally, iteration starts from the root object. When next is called,
64   * the transformer is called to examine the object. The transformer will return
65   * either an iterator or an object. If the object is an Iterator, the next element
66   * from that iterator is obtained and the process repeats. If the element is an object
67   * it is returned.
68   * <p>
69   * Under many circumstances, linking Iterators together in this manner is
70   * more efficient (and convenient) than using nested for loops to extract a list.
71   * 
72   * @since Commons Collections 3.1
73   * @version $Revision: 1.3 $ $Date: 2004/05/03 11:50:30 $
74   * 
75   * @author Stephen Colebourne
76   */
77  public class ObjectGraphIterator implements Iterator   {
78  
79      /** The stack of iterators */
80      protected final ArrayStack stack = new ArrayStack(8);
81      /** The root object in the tree */
82      protected Object   root;
83      /** The transformer to use */
84      protected Transformer transformer;
85  
86      /** Whether there is another element in the iteration */
87      protected boolean hasNext = false;    
88      /** The current iterator */
89      protected Iterator   currentIterator;
90      /** The current value */
91      protected Object   currentValue;
92      /** The last used iterator, needed for remove() */
93      protected Iterator   lastUsedIterator;
94  
95      //-----------------------------------------------------------------------
96      /**
97       * Constructs an ObjectGraphIterator using a root object and transformer.
98       * <p>
99       * 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  ("No more elements in the iteration");
224         }
225         lastUsedIterator = currentIterator;
226         Object   result = currentValue;
227         currentValue = null;
228         hasNext = false;
229         return result;
230     }
231 
232     /**
233      * Removes from the underlying collection the last element returned.
234      * <p>
235      * This method calls remove() on the underlying Iterator and it may
236      * throw an UnsupportedOperationException if the underlying Iterator
237      * does not support this method. 
238      * 
239      * @throws UnsupportedOperationException
240      *   if the remove operator is not supported by the underlying Iterator
241      * @throws IllegalStateException
242      *   if the next method has not yet been called, or the remove method has
243      *   already been called after the last call to the next method.
244      */
245     public void remove() {
246         if (lastUsedIterator == null) {
247             throw new IllegalStateException  ("Iterator remove() cannot be called at this time");
248         }
249         lastUsedIterator.remove();
250         lastUsedIterator = null;
251     }
252 
253 }
254
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags