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 
33 namespace 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 
TreeIterator( CommonTree tree )60         public TreeIterator( CommonTree tree )
61             : this( new CommonTreeAdaptor(), tree )
62         {
63         }
64 
TreeIterator( ITreeAdaptor adaptor, object tree )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 
Dispose()88         public void Dispose()
89         {
90         }
91 
92         #endregion
93 
94         #region IEnumerator Members
95 
MoveNext()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 
Reset()171         public void Reset()
172         {
173             firstTime = true;
174             tree = root;
175             nodes.Clear();
176         }
177 
178         #endregion
179     }
180 }
181