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