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 */ 017package org.apache.commons.collections4.iterators; 018 019import java.util.ArrayDeque; 020import java.util.Deque; 021import java.util.Iterator; 022import java.util.NoSuchElementException; 023 024import org.apache.commons.collections4.Transformer; 025 026/** 027 * An Iterator that can traverse multiple iterators down an object graph. 028 * <p> 029 * This iterator can extract multiple objects from a complex tree-like object graph. 030 * The iteration starts from a single root object. 031 * It uses a {@code Transformer} to extract the iterators and elements. 032 * Its main benefit is that no intermediate {@code List} is created. 033 * <p> 034 * For example, consider an object graph: 035 * <pre> 036 * |- Branch -- Leaf 037 * | \- Leaf 038 * |- Tree | /- Leaf 039 * | |- Branch -- Leaf 040 * Forest | \- Leaf 041 * | |- Branch -- Leaf 042 * | | \- Leaf 043 * |- Tree | /- Leaf 044 * |- Branch -- Leaf 045 * |- Branch -- Leaf</pre> 046 * The following {@code Transformer}, used in this class, will extract all 047 * the Leaf objects without creating a combined intermediate list: 048 * <pre> 049 * public Object transform(Object input) { 050 * if (input instanceof Forest) { 051 * return ((Forest) input).treeIterator(); 052 * } 053 * if (input instanceof Tree) { 054 * return ((Tree) input).branchIterator(); 055 * } 056 * if (input instanceof Branch) { 057 * return ((Branch) input).leafIterator(); 058 * } 059 * if (input instanceof Leaf) { 060 * return input; 061 * } 062 * throw new ClassCastException(); 063 * }</pre> 064 * <p> 065 * Internally, iteration starts from the root object. When next is called, 066 * the transformer is called to examine the object. The transformer will return 067 * either an iterator or an object. If the object is an Iterator, the next element 068 * from that iterator is obtained and the process repeats. If the element is an object 069 * it is returned. 070 * <p> 071 * Under many circumstances, linking Iterators together in this manner is 072 * more efficient (and convenient) than using nested for loops to extract a list. 073 * 074 * @param <E> the type of elements returned by this iterator. 075 * @since 3.1 076 */ 077public class ObjectGraphIterator<E> implements Iterator<E> { 078 079 /** The stack of iterators */ 080 private final Deque<Iterator<? extends E>> stack = new ArrayDeque<>(8); 081 /** The root object in the tree */ 082 private E root; 083 /** The transformer to use */ 084 private final Transformer<? super E, ? extends E> transformer; 085 086 /** Whether there is another element in the iteration */ 087 private boolean hasNext; 088 /** The current iterator */ 089 private Iterator<? extends E> currentIterator; 090 /** The current value */ 091 private E currentValue; 092 /** The last used iterator, needed for remove() */ 093 private Iterator<? extends E> lastUsedIterator; 094 095 /** 096 * Constructs an ObjectGraphIterator using a root object and transformer. 097 * <p> 098 * The root object can be an iterator, in which case it will be immediately 099 * 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 if (root instanceof Iterator) { 107 this.currentIterator = (Iterator<? extends E>) root; 108 } else { 109 this.root = root; 110 } 111 this.transformer = transformer; 112 } 113 114 /** 115 * Constructs a ObjectGraphIterator that will handle an iterator of iterators. 116 * <p> 117 * This constructor exists for convenience to emphasise that this class can 118 * be used to iterate over nested iterators. That is to say that the iterator 119 * passed in here contains other iterators, which may in turn contain further 120 * iterators. 121 * 122 * @param rootIterator the root iterator, null will result in an empty iterator 123 */ 124 public ObjectGraphIterator(final Iterator<? extends E> rootIterator) { 125 this.currentIterator = rootIterator; 126 this.transformer = null; 127 } 128 129 /** 130 * Finds the next object in the iteration given any start object. 131 * 132 * @param value the value to start from 133 */ 134 @SuppressWarnings("unchecked") 135 protected void findNext(final E value) { 136 if (value instanceof Iterator) { 137 // need to examine this iterator 138 findNextByIterator((Iterator<? extends E>) value); 139 } else { 140 // next value found 141 currentValue = value; 142 hasNext = true; 143 } 144 } 145 146 /** 147 * Finds the next object in the iteration given an iterator. 148 * 149 * @param iterator the iterator to start from 150 */ 151 protected void findNextByIterator(final Iterator<? extends E> iterator) { 152 if (iterator != currentIterator) { 153 // recurse a level 154 if (currentIterator != null) { 155 stack.push(currentIterator); 156 } 157 currentIterator = iterator; 158 } 159 160 while (currentIterator.hasNext() && !hasNext) { 161 E next = currentIterator.next(); 162 if (transformer != null) { 163 next = transformer.transform(next); 164 } 165 findNext(next); 166 } 167 // if we haven't found the next value and iterators are not yet exhausted 168 if (!hasNext && !stack.isEmpty()) { 169 // current iterator exhausted, go up a level 170 currentIterator = stack.pop(); 171 findNextByIterator(currentIterator); 172 } 173 } 174 175 /** 176 * Checks whether there are any more elements in the iteration to obtain. 177 * 178 * @return true if elements remain in the iteration 179 */ 180 @Override 181 public boolean hasNext() { 182 updateCurrentIterator(); 183 return hasNext; 184 } 185 186 /** 187 * Gets the next element of the iteration. 188 * 189 * @return the next element from the iteration 190 * @throws NoSuchElementException if all the Iterators are exhausted 191 */ 192 @Override 193 public E next() { 194 updateCurrentIterator(); 195 if (!hasNext) { 196 throw new NoSuchElementException("No more elements in the iteration"); 197 } 198 lastUsedIterator = currentIterator; 199 final E result = currentValue; 200 currentValue = null; 201 hasNext = false; 202 return result; 203 } 204 205 /** 206 * Removes from the underlying collection the last element returned. 207 * <p> 208 * This method calls remove() on the underlying Iterator, and it may 209 * throw an UnsupportedOperationException if the underlying Iterator 210 * does not support this method. 211 * 212 * @throws UnsupportedOperationException 213 * if the remove operator is not supported by the underlying Iterator 214 * @throws IllegalStateException 215 * if the next method has not yet been called, or the remove method has 216 * already been called after the last call to the next method. 217 */ 218 @Override 219 public void remove() { 220 if (lastUsedIterator == null) { 221 throw new IllegalStateException("Iterator remove() cannot be called at this time"); 222 } 223 lastUsedIterator.remove(); 224 lastUsedIterator = null; 225 } 226 227 /** 228 * Loops around the iterators to find the next value to return. 229 */ 230 protected void updateCurrentIterator() { 231 if (hasNext) { 232 return; 233 } 234 if (currentIterator == null) { 235 if (root == null) { // NOPMD 236 // do nothing, hasNext will be false 237 } else { 238 if (transformer == null) { 239 findNext(root); 240 } else { 241 findNext(transformer.transform(root)); 242 } 243 root = null; 244 } 245 } else { 246 findNextByIterator(currentIterator); 247 } 248 } 249 250}