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 }