TreeIterator.cs revision 324c4644fee44b9898524c09511bd33c3f12e2df 
1/*
2 * [The "BSD licence"]
3 * Copyright (c) 2005-2008 Terence Parr
4 * All rights reserved.
5 *
6 * Conversion to C#:
7 * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc.
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 3. The name of the author may not be used to endorse or promote products
19 *    derived from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33namespace Antlr.Runtime.Tree {
34    using System.Collections.Generic;
35
36    /** Return a node stream from a doubly-linked tree whose nodes
37     *  know what child index they are.  No remove() is supported.
38     *
39     *  Emit navigation nodes (DOWN, UP, and EOF) to let show tree structure.
40     */
41    public class TreeIterator : IEnumerator<object> {
42        protected ITreeAdaptor adaptor;
43        protected object root;
44        protected object tree;
45        protected bool firstTime = true;
46
47        // navigation nodes to return during walk and at end
48        public object up;
49        public object down;
50        public object eof;
51
52        /** If we emit UP/DOWN nodes, we need to spit out multiple nodes per
53         *  next() call.
54         */
55        protected Queue<object> nodes;
56
57        public TreeIterator(object tree)
58            : this(new CommonTreeAdaptor(), tree) {
59        }
60
61        public TreeIterator(ITreeAdaptor adaptor, object tree) {
62            this.adaptor = adaptor;
63            this.tree = tree;
64            this.root = tree;
65            nodes = new Queue<object>();
66            down = adaptor.Create(TokenTypes.Down, "DOWN");
67            up = adaptor.Create(TokenTypes.Up, "UP");
68            eof = adaptor.Create(TokenTypes.EndOfFile, "EOF");
69        }
70
71        #region IEnumerator<object> Members
72
73        public object Current {
74            get;
75            private set;
76        }
77
78        #endregion
79
80        #region IDisposable Members
81
82        public void Dispose() {
83        }
84
85        #endregion
86
87        #region IEnumerator Members
88
89        public bool MoveNext() {
90            if (firstTime) {
91                // initial condition
92                firstTime = false;
93                if (adaptor.GetChildCount(tree) == 0) {
94                    // single node tree (special)
95                    nodes.Enqueue(eof);
96                }
97                Current = tree;
98            } else {
99                // if any queued up, use those first
100                if (nodes != null && nodes.Count > 0) {
101                    Current = nodes.Dequeue();
102                } else {
103                    // no nodes left?
104                    if (tree == null) {
105                        Current = eof;
106                    } else {
107                        // next node will be child 0 if any children
108                        if (adaptor.GetChildCount(tree) > 0) {
109                            tree = adaptor.GetChild(tree, 0);
110                            nodes.Enqueue(tree); // real node is next after DOWN
111                            Current = down;
112                        } else {
113                            // if no children, look for next sibling of tree or ancestor
114                            object parent = adaptor.GetParent(tree);
115                            // while we're out of siblings, keep popping back up towards root
116                            while (parent != null &&
117                                    adaptor.GetChildIndex(tree) + 1 >= adaptor.GetChildCount(parent)) {
118                                nodes.Enqueue(up); // we're moving back up
119                                tree = parent;
120                                parent = adaptor.GetParent(tree);
121                            }
122
123                            // no nodes left?
124                            if (parent == null) {
125                                tree = null; // back at root? nothing left then
126                                nodes.Enqueue(eof); // add to queue, might have UP nodes in there
127                                Current = nodes.Dequeue();
128                            } else {
129                                // must have found a node with an unvisited sibling
130                                // move to it and return it
131                                int nextSiblingIndex = adaptor.GetChildIndex(tree) + 1;
132                                tree = adaptor.GetChild(parent, nextSiblingIndex);
133                                nodes.Enqueue(tree); // add to queue, might have UP nodes in there
134                                Current = nodes.Dequeue();
135                            }
136                        }
137                    }
138                }
139            }
140
141            return Current != eof;
142        }
143
144        public void Reset() {
145            firstTime = true;
146            tree = root;
147            nodes.Clear();
148        }
149
150        #endregion
151    }
152}
153