1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * [The "BSD licence"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2005-2008 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Conversion to C#: 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Copyright (c) 2008-2009 Sam Harwell, Pixel Mine, Inc. 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * All rights reserved. 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Redistribution and use in source and binary forms, with or without 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * modification, are permitted provided that the following conditions 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * are met: 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1. Redistributions of source code must retain the above copyright 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer. 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2. Redistributions in binary form must reproduce the above copyright 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * notice, this list of conditions and the following disclaimer in the 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * documentation and/or other materials provided with the distribution. 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3. The name of the author may not be used to endorse or promote products 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * derived from this software without specific prior written permission. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvernamespace Antlr.Runtime.Tree 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using System.Collections.Generic; 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return a node stream from a doubly-linked tree whose nodes 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * know what child index they are. No remove() is supported. 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Emit navigation nodes (DOWN, UP, and EOF) to let show tree structure. 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public class TreeIterator : IEnumerator<object> 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected ITreeAdaptor adaptor; 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected object root; 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected object tree; 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected bool firstTime = true; 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private bool reachedEof; 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // navigation nodes to return during walk and at end 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public object up; 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public object down; 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public object eof; 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** If we emit UP/DOWN nodes, we need to spit out multiple nodes per 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * next() call. 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected Queue<object> nodes; 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public TreeIterator( CommonTree tree ) 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver : this( new CommonTreeAdaptor(), tree ) 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public TreeIterator( ITreeAdaptor adaptor, object tree ) 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.adaptor = adaptor; 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.tree = tree; 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.root = tree; 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodes = new Queue<object>(); 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver down = adaptor.Create( TokenTypes.Down, "DOWN" ); 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver up = adaptor.Create( TokenTypes.Up, "UP" ); 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver eof = adaptor.Create( TokenTypes.EndOfFile, "EOF" ); 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #region IEnumerator<object> Members 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public object Current 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get; 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver private set; 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #endregion 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #region IDisposable Members 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void Dispose() 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #endregion 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #region IEnumerator Members 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public bool MoveNext() 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( firstTime ) 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // initial condition 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver firstTime = false; 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( adaptor.GetChildCount( tree ) == 0 ) 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // single node tree (special) 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodes.Enqueue( eof ); 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Current = tree; 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if any queued up, use those first 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( nodes != null && nodes.Count > 0 ) 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Current = nodes.Dequeue(); 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // no nodes left? 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( tree == null ) 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Current = eof; 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // next node will be child 0 if any children 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( adaptor.GetChildCount( tree ) > 0 ) 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tree = adaptor.GetChild( tree, 0 ); 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodes.Enqueue( tree ); // real node is next after DOWN 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Current = down; 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if no children, look for next sibling of tree or ancestor 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver object parent = adaptor.GetParent( tree ); 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // while we're out of siblings, keep popping back up towards root 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( parent != null && 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver adaptor.GetChildIndex( tree ) + 1 >= adaptor.GetChildCount( parent ) ) 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodes.Enqueue( up ); // we're moving back up 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tree = parent; 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver parent = adaptor.GetParent( tree ); 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // no nodes left? 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( parent == null ) 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tree = null; // back at root? nothing left then 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodes.Enqueue( eof ); // add to queue, might have UP nodes in there 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Current = nodes.Dequeue(); 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // must have found a node with an unvisited sibling 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // move to it and return it 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int nextSiblingIndex = adaptor.GetChildIndex( tree ) + 1; 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tree = adaptor.GetChild( parent, nextSiblingIndex ); 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodes.Enqueue( tree ); // add to queue, might have UP nodes in there 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Current = nodes.Dequeue(); 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bool result = Current != eof || !reachedEof; 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver reachedEof = Current == eof; 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return result; 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public void Reset() 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver firstTime = true; 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver tree = root; 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nodes.Clear(); 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #endregion 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 181