001 /*
002 // $Id: //open/mondrian/src/main/mondrian/olap/Walker.java#6 $
003 // This software is subject to the terms of the Common Public License
004 // Agreement, available at the following URL:
005 // http://www.opensource.org/licenses/cpl.html.
006 // Copyright (C) 1999-2002 Kana Software, Inc.
007 // Copyright (C) 2001-2008 Julian Hyde and others
008 // All Rights Reserved.
009 // You must accept the terms of that agreement to use this software.
010 //
011 // jhyde, 1 March, 1999
012 */
013
014 package mondrian.olap;
015 import java.io.PrintWriter;
016 import java.util.Enumeration;
017 import java.util.Stack;
018
019 /**
020 * Walks over a tree, returning nodes in prefix order. Objects which are an
021 * instance of {@link Walkable} supply their children using
022 * <code>getChildren()</code>; other objects are assumed to have no children.
023 *
024 * <p>If the tree is modified during the enumeration, strange things may happen.
025 *
026 * <p>Example use:<code><pre>
027 * Tree t;
028 * Walker w = new Walker(t);
029 * while (w.hasMoreElements()) {
030 * Tree node = (Tree) w.nextNode();
031 * System.out.println(node.toString());
032 * }
033 * </pre></code>
034 */
035 public class Walker implements Enumeration {
036 /**
037 * The active parts of the tree from the root to nextNode are held in a
038 * stack. When the stack is empty, the enumeration finishes. currentFrame
039 * holds the frame of the 'current node' (the node last returned from
040 * nextElement()) because it may no longer be on the stack.
041 */
042 private final Stack stack;
043 private Frame currentFrame;
044 private Object nextNode;
045
046 private class Frame {
047 Frame(Frame parent, Object node) {
048 this.parent = parent;
049 this.node = node;
050 this.children = getChildren(node);
051 this.childIndex = -1; // haven't visited first child yet
052 }
053 final Frame parent;
054 final Object node;
055 final Object[] children;
056 int childIndex;
057 }
058
059 public Walker(Walkable root)
060 {
061 stack = new Stack();
062 currentFrame = null;
063 visit(null, root);
064 }
065
066 private void moveToNext()
067 {
068 if (stack.empty())
069 return;
070
071 currentFrame = (Frame) stack.peek();
072
073 // Unwind stack until we find a level we have not completed.
074 do {
075 Frame frame = (Frame) stack.peek();
076 if (frame.children != null &&
077 ++frame.childIndex < frame.children.length) {
078 // Here is an unvisited child. Visit it.
079 visit(frame, frame.children[frame.childIndex]);
080 return;
081 }
082 stack.pop();
083 } while (!stack.empty());
084 nextNode = null;
085 }
086
087 private void visit(Frame parent, Object node)
088 {
089 nextNode = node;
090 stack.addElement(new Frame(parent, node));
091 }
092
093 public boolean hasMoreElements()
094 {
095 return nextNode != null;
096 }
097
098 public Object nextElement()
099 {
100 moveToNext();
101 return currentFrame.node;
102 }
103
104 /** Tell walker that we don't want to visit any (more) children of this
105 * node. The next node visited will be (a return visit to) the node's
106 * parent. Not valid until nextElement() has been called. */
107 public void prune()
108 {
109 if (currentFrame.children != null) {
110 currentFrame.childIndex = currentFrame.children.length;
111 }
112 //we need to make that next frame on the stack is not a child
113 //of frame we just pruned. if it is, we need to prune it too
114 if (this.hasMoreElements()) {
115 Object nextFrameParentNode = ((Frame)stack.peek()).parent.node;
116 if (nextFrameParentNode != currentFrame.node) {
117 return;
118 }
119 //delete the child of current member from the stack
120 stack.pop();
121 if (currentFrame.parent != null)
122 currentFrame = currentFrame.parent;
123 nextElement();
124 }
125 }
126
127 public void pruneSiblings()
128 {
129 prune();
130 currentFrame = currentFrame.parent;
131 if (currentFrame != null) {
132 prune();
133 }
134 }
135
136
137 /** returns the current object. Not valid until nextElement() has been
138 called. */
139 public Object currentElement()
140 {
141 return currentFrame.node;
142 }
143
144 /** returns level in the tree of the current element (that is, last element
145 * returned from nextElement()). The level of the root element is 0. */
146 public int level()
147 {
148 int i = 0;
149 for (Frame f = currentFrame; f != null; f = f.parent)
150 i++;
151 return i;
152 }
153
154 public final Object getParent()
155 {
156 return getAncestor(1);
157 }
158
159 public final Object getAncestor(int iDepth)
160 {
161 Frame f = getAncestorFrame(iDepth);
162 return f == null ? null : f.node;
163 }
164
165 /** returns the <code>iDepth</code>th ancestor of the current element */
166 private Frame getAncestorFrame(int iDepth)
167 {
168 for (Frame f = currentFrame; f != null; f = f.parent)
169 if (iDepth-- == 0)
170 return f;
171 return null;
172 }
173
174 /** get the ordinal within its parent node of the current node. Returns 0
175 for the root element. Equivalent to getAncestorOrdinal(0). */
176 public int getOrdinal()
177 {
178 // We can't use currentFrame.parent.iChild because moveToNext() may
179 // have changed it.
180 return currentFrame.parent == null ? 0 :
181 arrayFind(currentFrame.parent.children, currentFrame.node);
182 }
183
184 /** get the ordinal within its parent node of the <code>iDepth</code>th
185 * ancestor. */
186 public int getAncestorOrdinal(int iDepth)
187 {
188 Frame f = getAncestorFrame(iDepth);
189 return f == null ? -1 :
190 f.parent == null ? 0 :
191 arrayFind(f.parent.children, f.node);
192 }
193
194 /** Override this function to prune the tree, or to allow objects which are
195 * not Walkable to have children. */
196 public Object[] getChildren(Object node)
197 {
198 if (node instanceof Walkable) {
199 return ((Walkable) node).getChildren();
200 } else {
201 return null;
202 }
203 }
204
205 private static int arrayFind(Object[] array, Object o)
206 {
207 for (int i = 0; i < array.length; i++) {
208 if (array[i] == o) {
209 return i;
210 }
211 }
212 return -1;
213 }
214
215 private static class Region implements Walkable
216 {
217 String name;
218 Region[] children;
219
220 Region(String name, Region[] children)
221 {
222 this.name = name;
223 this.children = children;
224 }
225
226 public Object[] getChildren() {
227 return children;
228 }
229
230 public static void walkUntil(Walker walker, String name) {
231 while (walker.hasMoreElements()) {
232 Region region = (Region) walker.nextElement();
233 if (region.name.equals(name)) {
234 break;
235 }
236 }
237 }
238 };
239
240 public static void main(String[] args)
241 {
242 PrintWriter pw = new PrintWriter(System.out);
243 Region usa = new Region(
244 "USA", new Region[] {
245 new Region("CA", new Region[] {
246 new Region("San Francisco", new Region[]{
247 new Region("WesternAddition", new Region[]{ new Region("Haight", null)}),
248 new Region("Soma", null)
249 }),
250 new Region("Los Angeles", null)}),
251 new Region("WA", new Region[] {
252 new Region("Seattle", null),
253 new Region("Tacoma", null)})});
254
255 Walker walker = new Walker(usa);
256 if (false) {
257 while (walker.hasMoreElements()) {
258 Region region = (Region) walker.nextElement();
259 pw.println(region.name);
260 pw.flush();
261 }
262 }
263
264 Region.walkUntil(walker, "CA");
265 walker.prune();
266 Region region = (Region) walker.nextElement(); // should be WA
267 pw.println(region.name);
268 pw.flush();
269
270 walker = new Walker(usa);
271 Region.walkUntil(walker, "USA");
272 walker.prune();
273 region = (Region) walker.nextElement(); // should be null
274 if (region == null)
275 pw.println("null");
276 pw.flush();
277
278 walker = new Walker(usa);
279 Region.walkUntil(walker, "Los Angeles");
280 walker.prune();
281 region = (Region) walker.nextElement(); // should be WA
282 pw.println(region.name);
283 pw.flush();
284
285 walker = new Walker(usa);
286 Region.walkUntil(walker, "Haight");
287 walker.prune();
288 region = (Region) walker.nextElement(); // should be Soma
289 pw.println(region.name);
290 pw.flush();
291
292 walker = new Walker(usa);
293 Region.walkUntil(walker, "Soma");
294 walker.prune();
295 region = (Region) walker.nextElement(); // should be Los Angeles
296 pw.println(region.name);
297 pw.flush();
298
299 walker = new Walker(usa);
300 Region.walkUntil(walker, "CA");
301 walker.pruneSiblings();
302 region = (Region) walker.nextElement(); // should be Los Angeles
303 if (region == null) {
304 pw.println("null");
305 pw.flush();
306 }
307
308 walker = new Walker(usa);
309 Region.walkUntil(walker, "Soma");
310 walker.pruneSiblings();
311 region = (Region) walker.nextElement(); // should be Los Angeles
312 if (region == null) {
313 pw.println("null");
314 pw.flush();
315 }
316 }
317 }
318
319
320 // End Walker.java