KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > mondrian > olap > Walker


1 /*
2 // $Id: //open/mondrian/src/main/mondrian/olap/Walker.java#5 $
3 // This software is subject to the terms of the Common Public License
4 // Agreement, available at the following URL:
5 // http://www.opensource.org/licenses/cpl.html.
6 // Copyright (C) 1999-2002 Kana Software, Inc.
7 // Copyright (C) 2001-2005 Julian Hyde and others
8 // All Rights Reserved.
9 // You must accept the terms of that agreement to use this software.
10 //
11 // jhyde, 1 March, 1999
12 */
13
14 package mondrian.olap;
15 import java.io.PrintWriter JavaDoc;
16 import java.util.Enumeration JavaDoc;
17 import java.util.Stack JavaDoc;
18
19 /**
20  * Walks over a tree, returning nodes in prefix order. Objects which are an
21  * instance of {@link Walkable} supply their children using
22  * <code>getChildren()</code>; other objects are assumed to have no children.
23  *
24  * <p>If the tree is modified during the enumeration, strange things may happen.
25  *
26  * <p>Example use:<code><pre>
27  * Tree t;
28  * Walker w = new Walker(t);
29  * while (w.hasMoreElements()) {
30  * Tree node = (Tree) w.nextNode();
31  * System.out.println(node.toString());
32  * }
33  * </pre></code>
34  */
35 public class Walker implements Enumeration JavaDoc {
36     /**
37      * The active parts of the tree from the root to nextNode are held in a
38      * stack. When the stack is empty, the enumeration finishes. currentFrame
39      * holds the frame of the 'current node' (the node last returned from
40      * nextElement()) because it may no longer be on the stack.
41      */
42     private final Stack JavaDoc stack;
43     private Frame currentFrame;
44     private Object JavaDoc nextNode;
45
46     private class Frame {
47         Frame(Frame parent, Object JavaDoc node) {
48             this.parent = parent;
49             this.node = node;
50             this.children = getChildren(node);
51             this.childIndex = -1; // haven't visited first child yet
52 }
53         final Frame parent;
54         final Object JavaDoc node;
55         final Object JavaDoc[] children;
56         int childIndex;
57     }
58
59     public Walker(Walkable root)
60     {
61         stack = new Stack JavaDoc();
62         currentFrame = null;
63         visit(null, root);
64     }
65
66     private void moveToNext()
67     {
68         if (stack.empty())
69             return;
70
71         currentFrame = (Frame) stack.peek();
72
73         // Unwind stack until we find a level we have not completed.
74 do {
75             Frame frame = (Frame) stack.peek();
76             if (frame.children != null &&
77                 ++frame.childIndex < frame.children.length) {
78                 // Here is an unvisited child. Visit it.
79 visit(frame, frame.children[frame.childIndex]);
80                 return;
81             }
82             stack.pop();
83         } while (!stack.empty());
84         nextNode = null;
85     }
86
87     private void visit(Frame parent, Object JavaDoc node)
88     {
89         nextNode = node;
90         stack.addElement(new Frame(parent, node));
91     }
92
93     public boolean hasMoreElements()
94     {
95         return nextNode != null;
96     }
97
98     public Object JavaDoc nextElement()
99     {
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 JavaDoc nextFrameParentNode = ((Frame )stack.peek()).parent.node;
116             if( nextFrameParentNode != currentFrame.node )
117                 return;
118             //delete the child of current member from the stack
119 stack.pop();
120             if( currentFrame.parent != null)
121                 currentFrame = currentFrame.parent;
122             nextElement();
123         }
124     }
125
126     public void pruneSiblings()
127     {
128         prune();
129         currentFrame = currentFrame.parent;
130         if( currentFrame != null ){
131             prune();
132         }
133     }
134
135
136     /** returns the current object. Not valid until nextElement() has been
137         called. */
138     public Object JavaDoc currentElement()
139     {
140         return currentFrame.node;
141     }
142
143     /** returns level in the tree of the current element (that is, last element
144      * returned from nextElement()). The level of the root element is 0. */
145     public int level()
146     {
147         int i = 0;
148         for (Frame f = currentFrame; f != null; f = f.parent)
149             i++;
150         return i;
151     }
152
153     public final Object JavaDoc getParent()
154     {
155         return getAncestor(1);
156     }
157
158     public final Object JavaDoc getAncestor(int iDepth)
159     {
160         Frame f = getAncestorFrame(iDepth);
161         return f == null ? null : f.node;
162     }
163
164     /** returns the <code>iDepth</code>th ancestor of the current element */
165     private Frame getAncestorFrame(int iDepth)
166     {
167         for (Frame f = currentFrame; f != null; f = f.parent)
168             if (iDepth-- == 0)
169                 return f;
170         return null;
171     }
172
173     /** get the ordinal within its parent node of the current node. Returns 0
174         for the root element. Equivalent to getAncestorOrdinal(0). */
175     public int getOrdinal()
176     {
177         // We can't use currentFrame.parent.iChild because moveToNext() may
178 // have changed it.
179 return currentFrame.parent == null ? 0 :
180             arrayFind(currentFrame.parent.children, currentFrame.node);
181     }
182
183     /** get the ordinal within its parent node of the <code>iDepth</code>th
184      * ancestor. */
185     public int getAncestorOrdinal(int iDepth)
186     {
187         Frame f = getAncestorFrame(iDepth);
188         return f == null ? -1 :
189             f.parent == null ? 0 :
190             arrayFind(f.parent.children, f.node);
191     }
192
193     /** Override this function to prune the tree, or to allow objects which are
194      * not Walkable to have children. */
195     public Object JavaDoc[] getChildren(Object JavaDoc node)
196     {
197         if (node instanceof Walkable)
198             return ((Walkable) node).getChildren();
199         else
200             return null;
201     }
202
203     private static int arrayFind(Object JavaDoc[] array, Object JavaDoc o)
204     {
205         for (int i = 0; i < array.length; i++)
206             if (array[i] == o)
207                 return i;
208         return -1;
209     }
210
211     private static class Region implements Walkable
212     {
213         String JavaDoc name;
214         Region[] children;
215
216         Region(String JavaDoc name, Region[] children)
217         {
218             this.name = name;
219             this.children = children;
220         }
221
222         public Object JavaDoc[] getChildren() { return children; }
223
224         public static void walkUntil(Walker walker, String JavaDoc name) {
225             while (walker.hasMoreElements()) {
226                 Region region = (Region) walker.nextElement();
227                 if (region.name.equals(name)) {
228                     break;
229                 }
230             }
231         }
232     };
233
234     public static void main(String JavaDoc[] args)
235     {
236         PrintWriter JavaDoc pw = new PrintWriter JavaDoc(System.out);
237         Region usa = new Region(
238             "USA", new Region[] {
239             new Region("CA", new Region[] {
240                 new Region("San Francisco", new Region[]{
241             new Region("WesternAddition", new Region[]{ new Region("Haight", null)}),
242                     new Region("Soma", null)
243                 }),
244                 new Region("Los Angeles", null)}),
245             new Region("WA", new Region[] {
246                 new Region("Seattle", null),
247                 new Region("Tacoma", null)})});
248
249         Walker walker = new Walker(usa);
250         if (false) {
251             while (walker.hasMoreElements()) {
252                 Region region = (Region) walker.nextElement();
253                 pw.println(region.name);
254                 pw.flush();
255             }
256         }
257
258         Region.walkUntil(walker, "CA");
259         walker.prune();
260         Region region = (Region) walker.nextElement(); // should be WA
261 pw.println(region.name);
262         pw.flush();
263
264         walker = new Walker(usa);
265         Region.walkUntil(walker, "USA");
266         walker.prune();
267         region = (Region) walker.nextElement(); // should be null
268 if( region == null )
269             pw.println("null");
270         pw.flush();
271
272         walker = new Walker(usa);
273         Region.walkUntil(walker, "Los Angeles");
274         walker.prune();
275         region = (Region) walker.nextElement(); // should be WA
276 pw.println(region.name);
277         pw.flush();
278
279         walker = new Walker(usa);
280         Region.walkUntil(walker, "Haight");
281         walker.prune();
282         region = (Region) walker.nextElement(); // should be Soma
283 pw.println(region.name);
284         pw.flush();
285
286         walker = new Walker(usa);
287         Region.walkUntil(walker, "Soma");
288         walker.prune();
289         region = (Region) walker.nextElement(); // should be Los Angeles
290 pw.println(region.name);
291         pw.flush();
292
293         walker = new Walker(usa);
294         Region.walkUntil(walker, "CA");
295         walker.pruneSiblings();
296         region = (Region) walker.nextElement(); // should be Los Angeles
297 if (region == null ){
298             pw.println("null");
299             pw.flush();
300         }
301
302         walker = new Walker(usa);
303         Region.walkUntil(walker, "Soma");
304         walker.pruneSiblings();
305         region = (Region) walker.nextElement(); // should be Los Angeles
306 if (region == null ){
307             pw.println("null");
308             pw.flush();
309         }
310     }
311 }
312
313
314 // End Walker.java
315
Popular Tags