001 /**
002 * <copyright>
003 *
004 * Copyright (c) 2002-2006 IBM Corporation and others.
005 * All rights reserved. This program and the accompanying materials
006 * are made available under the terms of the Eclipse Public License v1.0
007 * which accompanies this distribution, and is available at
008 * http://www.eclipse.org/legal/epl-v10.html
009 *
010 * Contributors:
011 * IBM - Initial API and implementation
012 *
013 * </copyright>
014 *
015 * $Id: AbstractTreeIterator.java,v 1.7 2007/11/03 13:15:38 emerks Exp $
016 */
017 package org.eclipse.emf.common.util;
018
019
020 import java.util.Iterator;
021
022
023 /**
024 * An extensible tree iterator implementation
025 * that iterates over an object, it's children, their children, and so on.
026 * Clients need only implement {@link #getChildren getChildren}
027 * in order to implement a fully functional tree iterator.
028 */
029 public abstract class AbstractTreeIterator<E> extends BasicEList<Iterator<? extends E>> implements TreeIterator<E>
030 {
031 private static final long serialVersionUID = 1L;
032
033 /**
034 * Whether the first call to next returns the initial root object
035 * or begins with the first child of the root object.
036 */
037 protected boolean includeRoot;
038
039 /**
040 * The root object for which the iteration is initiated.
041 */
042 protected Object object;
043
044 /**
045 * The iterator that would be cut short by a call to {@link #prune}.
046 */
047 protected Iterator<? extends E> nextPruneIterator;
048
049 /**
050 * The iterator to which a {@link #remove} call will delegated.
051 */
052 protected Iterator<? extends E> nextRemoveIterator;
053
054 /**
055 * Creates an instance that iterates over an object, it's children, their children, and so on.
056 * @param object the root object of the tree.
057 */
058 public AbstractTreeIterator(E object)
059 {
060 this.object = object;
061 this.includeRoot = true;
062 }
063
064 /**
065 * <p>Creates and instance that iterates over an object (but only if <code>includeRoot</code> is <code>true</code>),
066 * it's children, their children, and so on.<p>
067 * <p>If <code>includeRoot</code> is <code>true</code>, the <code>object</code> is expected
068 * to be of the type <code>E</code>.
069 */
070 public AbstractTreeIterator(Object object, boolean includeRoot)
071 {
072 this.object = object;
073 this.includeRoot = includeRoot;
074 }
075
076 /**
077 * Returns the iterator that yields the children of the object.
078 * @param object the object for which children are required.
079 * @return the iterator that yields the children.
080 */
081 protected abstract Iterator<? extends E> getChildren(Object object);
082
083 /**
084 * Returns whether there are more elements.
085 * @return whether there are more elements.
086 */
087 public boolean hasNext()
088 {
089 if (data == null && !includeRoot)
090 {
091 return hasAnyChildren();
092 }
093 else
094 {
095 return hasMoreChildren();
096 }
097 }
098
099 private boolean hasAnyChildren()
100 {
101 Iterator<? extends E> nextPruneIterator = this.nextPruneIterator;
102
103 nextPruneIterator = getChildren(object);
104 add(nextPruneIterator);
105 return nextPruneIterator.hasNext();
106 }
107
108 private boolean hasMoreChildren()
109 {
110 // We don't create an iterator stack until the root mapping itself has been returned by next once.
111 // After that the stack should be non-empty and the top iterator should yield true for hasNext.
112 return data == null || !isEmpty() && ((Iterator<?>)data[size - 1]).hasNext();
113 }
114
115 /**
116 * Returns the next object and advances the iterator.
117 * @return the next object.
118 */
119 public E next()
120 {
121 // If we are still on the root mapping itself...
122 //
123 if (data == null)
124 {
125 // Yield that mapping, create a stack, record it as the next one to prune, and add it to the stack.
126 //
127 nextPruneIterator = getChildren(object);
128 add(nextPruneIterator);
129 if (includeRoot)
130 {
131 @SuppressWarnings("unchecked") E result = (E)object;
132 return result;
133 }
134 }
135
136 // Get the top iterator, retrieve it's result, and record it as the one to which remove will be delegated.
137 //
138 @SuppressWarnings("unchecked") Iterator<? extends E> currentIterator = (Iterator<? extends E>)data[size - 1];
139 E result = currentIterator.next();
140 nextRemoveIterator = currentIterator;
141
142 // If the result about to be returned has children...
143 //
144 Iterator<? extends E> iterator = getChildren(result);
145 if (iterator.hasNext())
146 {
147 // Record the iterator as the next one to prune, and add it to the stack.
148 //
149 nextPruneIterator = iterator;
150 add(iterator);
151 }
152 else
153 {
154 // There will be no iterator to prune.
155 //
156 nextPruneIterator = null;
157
158 // While the current iterator has no next...
159 //
160 while (!currentIterator.hasNext())
161 {
162 // Pop it from the stack.
163 //
164 data[--size] = null;
165
166 // If the stack is empty, we're done.
167 //
168 if (isEmpty())
169 {
170 break;
171 }
172
173 // Get the next one down and then test it for has next.
174 //
175 @SuppressWarnings("unchecked") Iterator<? extends E> nextIterator = (Iterator<? extends E>)data[size - 1];
176 currentIterator = nextIterator;
177 }
178 }
179
180 return result;
181 }
182
183 /**
184 * Removes the last object returned by {@link #next()} from the underlying tree;
185 * it's an optional operation.
186 * @exception IllegalStateException
187 * if <code>next</code> has not yet been called or has been called only the yield the root object,
188 * or <code>remove</code> has already been called after the last call to the <code>next</code> method.
189 *
190 */
191 public void remove()
192 {
193 if (nextRemoveIterator == null)
194 {
195 throw new IllegalStateException("There is no valid object to remove.");
196 }
197 nextRemoveIterator.remove();
198 }
199
200 /**
201 * Prunes the iterator so that it skips over all the nodes below the most recent result of calling {@link #next next()}.
202 */
203 public void prune()
204 {
205 // If there is an iterator to prune.
206 //
207 if (nextPruneIterator != null)
208 {
209 // If that iterator is still at the top of the stack...
210 //
211 if (!isEmpty() && data[size - 1] == nextPruneIterator)
212 {
213 // Pop it off the stack.
214 //
215 data[--size] = null;
216
217 // Keep popping the stack until an iterator that has a next is at the top.
218 //
219 while (!isEmpty() && !((Iterator<?>)data[size - 1]).hasNext())
220 {
221 data[--size] = null;
222 }
223 }
224
225 // You can only prune once.
226 //
227 nextPruneIterator = null;
228 }
229 }
230 }