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{
35    using System.Collections.Generic;
36
37    /** Return a node stream from a doubly-linked tree whose nodes
38     *  know what child index they are.  No remove() is supported.
39     *
40     *  Emit navigation nodes (DOWN, UP, and EOF) to let show tree structure.
41     */
42    public class TreeIterator : IEnumerator<object>
43    {
44        protected ITreeAdaptor adaptor;
45        protected object root;
46        protected object tree;
47        protected bool firstTime = true;
48        private bool reachedEof;
49
50        // navigation nodes to return during walk and at end
51        public object up;
52        public object down;
53        public object eof;
54
55        /** If we emit UP/DOWN nodes, we need to spit out multiple nodes per
56         *  next() call.
57         */
58        protected Queue<object> nodes;
59
60        public TreeIterator( CommonTree tree )
61            : this( new CommonTreeAdaptor(), tree )
62        {
63        }
64
65        public TreeIterator( ITreeAdaptor adaptor, object tree )
66        {
67            this.adaptor = adaptor;
68            this.tree = tree;
69            this.root = tree;
70            nodes = new Queue<object>();
71            down = adaptor.Create( TokenTypes.Down, "DOWN" );
72            up = adaptor.Create( TokenTypes.Up, "UP" );
73            eof = adaptor.Create( TokenTypes.EndOfFile, "EOF" );
74        }
75
76        #region IEnumerator<object> Members
77
78        public object Current
79        {
80            get;
81            private set;
82        }
83
84        #endregion
85
86        #region IDisposable Members
87
88        public void Dispose()
89        {
90        }
91
92        #endregion
93
94        #region IEnumerator Members
95
96        public bool MoveNext()
97        {
98            if ( firstTime )
99            {
100                // initial condition
101                firstTime = false;
102                if ( adaptor.GetChildCount( tree ) == 0 )
103                {
104                    // single node tree (special)
105                    nodes.Enqueue( eof );
106                }
107                Current = tree;
108            }
109            else
110            {
111                // if any queued up, use those first
112                if ( nodes != null && nodes.Count > 0 )
113                {
114                    Current = nodes.Dequeue();
115                }
116                else
117                {
118                    // no nodes left?
119                    if ( tree == null )
120                    {
121                        Current = eof;
122                    }
123                    else
124                    {
125                        // next node will be child 0 if any children
126                        if ( adaptor.GetChildCount( tree ) > 0 )
127                        {
128                            tree = adaptor.GetChild( tree, 0 );
129                            nodes.Enqueue( tree ); // real node is next after DOWN
130                            Current = down;
131                        }
132                        else
133                        {
134                            // if no children, look for next sibling of tree or ancestor
135                            object parent = adaptor.GetParent( tree );
136                            // while we're out of siblings, keep popping back up towards root
137                            while ( parent != null &&
138                                    adaptor.GetChildIndex( tree ) + 1 >= adaptor.GetChildCount( parent ) )
139                            {
140                                nodes.Enqueue( up ); // we're moving back up
141                                tree = parent;
142                                parent = adaptor.GetParent( tree );
143                            }
144
145                            // no nodes left?
146                            if ( parent == null )
147                            {
148                                tree = null; // back at root? nothing left then
149                                nodes.Enqueue( eof ); // add to queue, might have UP nodes in there
150                                Current = nodes.Dequeue();
151                            }
152                            else
153                            {
154                                // must have found a node with an unvisited sibling
155                                // move to it and return it
156                                int nextSiblingIndex = adaptor.GetChildIndex( tree ) + 1;
157                                tree = adaptor.GetChild( parent, nextSiblingIndex );
158                                nodes.Enqueue( tree ); // add to queue, might have UP nodes in there
159                                Current = nodes.Dequeue();
160                            }
161                        }
162                    }
163                }
164            }
165
166            bool result = Current != eof || !reachedEof;
167            reachedEof = Current == eof;
168            return result;
169        }
170
171        public void Reset()
172        {
173            firstTime = true;
174            tree = root;
175            nodes.Clear();
176        }
177
178        #endregion
179    }
180}
181