KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > emf > common > util > AbstractTreeIterator


1 /**
2  * <copyright>
3  *
4  * Copyright (c) 2002-2004 IBM Corporation and others.
5  * All rights reserved. This program and the accompanying materials
6  * are made available under the terms of the Eclipse Public License v1.0
7  * which accompanies this distribution, and is available at
8  * http://www.eclipse.org/legal/epl-v10.html
9  *
10  * Contributors:
11  * IBM - Initial API and implementation
12  *
13  * </copyright>
14  *
15  * $Id: AbstractTreeIterator.java,v 1.4 2005/06/08 06:19:08 nickb Exp $
16  */
17 package org.eclipse.emf.common.util;
18
19
20 import java.util.Iterator JavaDoc;
21
22
23 /**
24  * An extensible tree iterator implementation
25  * that iterates over an object, it's children, their children, and so on.
26  * Clients need only implement {@link #getChildren getChildren}
27  * in order to implement a fully functional tree iterator.
28  */
29 public abstract class AbstractTreeIterator extends BasicEList implements TreeIterator
30 {
31   /**
32    * Whether the first call to next returns the initial root object
33    * or begins with the first child of the root object.
34    */
35   protected boolean includeRoot;
36
37   /**
38    * The root object for which the iteration is initiated.
39    */
40   protected Object JavaDoc object;
41
42   /**
43    * The iterator that would be cut short by a call to {@link #prune}.
44    */
45   protected Iterator JavaDoc nextPruneIterator;
46
47   /**
48    * The iterator to which a {@link #remove} call will delegated.
49    */
50   protected Iterator JavaDoc nextRemoveIterator;
51
52   /**
53    * Creates an instance that iterates over an object, it's children, their children, and so on.
54    * @param object the root object of the tree.
55    */
56   public AbstractTreeIterator(Object JavaDoc object)
57   {
58     this.object = object;
59     this.includeRoot = true;
60   }
61
62   /**
63    * Creates and instance that iterates over an object (but only if <code>includeRoot</code> is <code>true</code>),
64    * it's children, their children, and so on.
65    */
66   public AbstractTreeIterator(Object JavaDoc object, boolean includeRoot)
67   {
68     this.object = object;
69     this.includeRoot = includeRoot;
70   }
71
72   /**
73    * Returns the iterator that yields the children of the object.
74    * @param object the object for which children are required.
75    * @return the iterator that yields the children.
76    */
77   protected abstract Iterator JavaDoc getChildren(Object JavaDoc object);
78
79   /**
80    * Returns whether there are more elements.
81    * @return whether there are more elements.
82    */
83   public boolean hasNext()
84   {
85     if (data == null && !includeRoot)
86     {
87       return hasAnyChildren();
88     }
89     else
90     {
91       return hasMoreChildren();
92     }
93   }
94
95   private boolean hasAnyChildren()
96   {
97     Iterator JavaDoc nextPruneIterator = this.nextPruneIterator;
98
99     nextPruneIterator = getChildren(object);
100     add(nextPruneIterator);
101     return nextPruneIterator.hasNext();
102   }
103
104   private boolean hasMoreChildren()
105   {
106     // We don't create an iterator stack until the root mapping itself has been returned by next once.
107 // After that the stack should be non-empty and the top iterator should yield true for hasNext.
108 return data == null || !isEmpty() && ((Iterator JavaDoc)data[size - 1]).hasNext();
109   }
110
111   /**
112    * Returns the next object and advances the iterator.
113    * @return the next object.
114    */
115   public Object JavaDoc next()
116   {
117     Object JavaDoc result;
118
119     // If we are still on the root mapping itself...
120 //
121 if (data == null)
122     {
123       // Yield that mapping, create a stack, record it as the next one to prune, and add it to the stack.
124 //
125 result = object;
126       nextPruneIterator = getChildren(object);
127       add(nextPruneIterator);
128       if (includeRoot)
129       {
130         return result;
131       }
132     }
133
134     // Get the top iterator, retrieve it's result, and record it as the one to which remove will be delegated.
135 //
136 Iterator JavaDoc currentIterator = (Iterator JavaDoc)data[size - 1];
137     result = currentIterator.next();
138     nextRemoveIterator = currentIterator;
139
140     // If the result about to be returned has children...
141 //
142 Iterator JavaDoc iterator = getChildren(result);
143     if (iterator.hasNext())
144     {
145       // Record the iterator as the next one to prune, and add it to the stack.
146 //
147 nextPruneIterator = iterator;
148       add(iterator);
149     }
150     else
151     {
152       // There will be no iterator to prune.
153 //
154 nextPruneIterator = null;
155
156       // While the current iterator has no next...
157 //
158 while (!currentIterator.hasNext())
159       {
160         // Pop it from the stack.
161 //
162 data[--size] = null;
163
164         // If the stack is empty, we're done.
165 //
166 if (isEmpty())
167         {
168           break;
169         }
170
171         // Get the next one down and then test it for has next.
172 //
173 currentIterator = (Iterator JavaDoc)data[size - 1];
174       }
175     }
176
177     return result;
178   }
179
180   /**
181    * Removes the last object returned by {@link #next()} from the underlying tree;
182    * it's an optional operation.
183    * @exception IllegalStateException
184    * if <code>next</code> has not yet been called or has been called only the yield the root object,
185    * or <code>remove</code> has already been called after the last call to the <code>next</code> method.
186    *
187    */
188   public void remove()
189   {
190     if (nextRemoveIterator == null)
191     {
192       throw new IllegalStateException JavaDoc("There is no valid object to remove.");
193     }
194     nextRemoveIterator.remove();
195   }
196
197   /**
198    * Prunes the iterator so that it skips over all the nodes below the most recent result of calling {@link #next next()}.
199    */
200   public void prune()
201   {
202     // If there is an iterator to prune.
203 //
204 if (nextPruneIterator != null)
205     {
206       // If that iterator is still at the top of the stack...
207 //
208 if (!isEmpty() && data[size - 1] == nextPruneIterator)
209       {
210         // Pop it off the stack.
211 //
212 data[--size] = null;
213
214         // Keep poping the stack until an iterator that has a next is at the top.
215 //
216 while (!isEmpty() && !((Iterator JavaDoc)data[size - 1]).hasNext())
217         {
218           data[--size] = null;
219         }
220       }
221
222       // You can only prune once.
223 //
224 nextPruneIterator = null;
225     }
226   }
227 }
228
Popular Tags