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 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 TreeIterator(object tree)57 public TreeIterator(object tree) 58 : this(new CommonTreeAdaptor(), tree) { 59 } 60 TreeIterator(ITreeAdaptor adaptor, object tree)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 Dispose()82 public void Dispose() { 83 } 84 85 #endregion 86 87 #region IEnumerator Members 88 MoveNext()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 Reset()144 public void Reset() { 145 firstTime = true; 146 tree = root; 147 nodes.Clear(); 148 } 149 150 #endregion 151 } 152 } 153