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 using System; 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using System.Collections.Generic; 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver using StringBuilder = System.Text.StringBuilder; 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A generic tree implementation with no payload. You must subclass to 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * actually have any user data. ANTLR v3 uses a list of children approach 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * instead of the child-sibling approach in v2. A flat tree (a list) is 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * an empty node whose children represent the list. An empty, but 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * non-null node is called "nil". 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver [System.Serializable] 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract class BaseTree : ITree { 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<ITree> children; 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public BaseTree() { 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Create a new node from an existing node does nothing for BaseTree 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as there are no fields other than the children list, which cannot 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * be copied as the children are not considered part of this node. 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public BaseTree(ITree node) { 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Get the children internal List; note that if you directly mess with 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the list, do so at your own risk. 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual IList<ITree> Children { 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return children; 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #region ITree Members 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual int ChildCount { 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (Children == null) 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 0; 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return Children.Count; 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>BaseTree doesn't track parent pointers.</summary> */ 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual ITree Parent { 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set { 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>BaseTree doesn't track child indexes.</summary> */ 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual int ChildIndex { 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 0; 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set { 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual bool IsNil { 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get { 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract int TokenStartIndex { 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get; 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set; 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract int TokenStopIndex { 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get; 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set; 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract int Type { 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get; 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set; 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract string Text { 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get; 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set; 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual int Line { 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get; 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set; 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual int CharPositionInLine { 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver get; 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver set; 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #endregion 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual ITree GetChild(int i) { 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (i < 0) 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentOutOfRangeException(); 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (children == null || i >= children.Count) 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return children[i]; 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual ITree GetFirstChildWithType(int type) { 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver foreach (ITree child in children) { 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (child.Type == type) 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return child; 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Add t as child of this node.</summary> 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * <remarks> 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Warning: if t has no children, but child does 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and child isNil then this routine moves children to t via 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * t.children = child.children; i.e., without copying the array. 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </remarks> 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void AddChild(ITree t) { 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("add child "+t.toStringTree()+" "+this.toStringTree()); 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("existing children: "+children); 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t == null) { 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; // do nothing upon addChild(null) 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t.IsNil) { 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // t is an empty node possibly with children 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BaseTree childTree = t as BaseTree; 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (childTree != null && this.children != null && this.children == childTree.children) { 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Exception("attempt to add child list to itself"); 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // just add all of childTree's children to this 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t.ChildCount > 0) { 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (this.children != null || childTree == null) { 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (this.children == null) 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.children = CreateChildrenList(); 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // must copy, this has children already 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = t.ChildCount; 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) { 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ITree c = t.GetChild(i); 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.children.Add(c); 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // handle double-link stuff for each child of nil root 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.Parent = this; 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.ChildIndex = children.Count - 1; 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } else { 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // no children for this but t is a BaseTree with children; 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // just set pointer call general freshener routine 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.children = childTree.children; 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.FreshenParentAndChildIndexes(); 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } else { 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // child is not nil (don't care about children) 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (children == null) { 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children = CreateChildrenList(); // create children list on demand 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children.Add(t); 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t.Parent = this; 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t.ChildIndex = children.Count - 1; 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // System.out.println("now children are: "+children); 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Add all elements of kids list as children of this node</summary> */ 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void AddChildren(IEnumerable<ITree> kids) { 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (kids == null) 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentNullException("kids"); 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver foreach (ITree t in kids) 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver AddChild(t); 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void SetChild(int i, ITree t) { 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (i < 0) 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentOutOfRangeException("i"); 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t == null) { 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t.IsNil) { 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentException("Can't set single child to a list"); 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (children == null) { 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children = CreateChildrenList(); 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children[i] = t; 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t.Parent = this; 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t.ChildIndex = i; 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual object DeleteChild(int i) { 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (i < 0) 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentOutOfRangeException("i"); 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (i >= ChildCount) 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentException(); 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (children == null) 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ITree killed = children[i]; 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children.RemoveAt(i); 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // walk rest and decrement their child indexes 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.FreshenParentAndChildIndexes(i); 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return killed; 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Delete children from start to stop and replace with t even if t is 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a list (nil-root tree). num of children can increase or decrease. 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * For huge child lists, inserting children can force walking rest of 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * children to set their childindex; could be slow. 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void ReplaceChildren(int startChildIndex, int stopChildIndex, object t) { 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (startChildIndex < 0) 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentOutOfRangeException(); 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (stopChildIndex < 0) 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentOutOfRangeException(); 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t == null) 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentNullException("t"); 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (stopChildIndex < startChildIndex) 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentException(); 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("replaceChildren "+startChildIndex+", "+stopChildIndex+ 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver " with "+((BaseTree)t).toStringTree()); 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver System.out.println("in="+toStringTree()); 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (children == null) { 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new ArgumentException("indexes invalid; no children in list"); 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int replacingHowMany = stopChildIndex - startChildIndex + 1; 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int replacingWithHowMany; 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ITree newTree = (ITree)t; 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<ITree> newChildren = null; 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // normalize to a list of children to add: newChildren 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (newTree.IsNil) { 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BaseTree baseTree = newTree as BaseTree; 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (baseTree != null && baseTree.children != null) { 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newChildren = baseTree.children; 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } else { 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newChildren = CreateChildrenList(); 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = newTree.ChildCount; 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; i < n; i++) 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newChildren.Add(newTree.GetChild(i)); 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } else { 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newChildren = new List<ITree>(1); 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newChildren.Add(newTree); 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver replacingWithHowMany = newChildren.Count; 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numNewChildren = newChildren.Count; 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int delta = replacingHowMany - replacingWithHowMany; 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if same number of nodes, do direct replace 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (delta == 0) { 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int j = 0; // index into new children 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = startChildIndex; i <= stopChildIndex; i++) { 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ITree child = newChildren[j]; 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children[i] = child; 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child.Parent = this; 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child.ChildIndex = i; 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver j++; 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } else if (delta > 0) { 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // fewer new nodes than there were 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // set children and then delete extra 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int j = 0; j < numNewChildren; j++) { 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children[startChildIndex + j] = newChildren[j]; 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int indexToDelete = startChildIndex + numNewChildren; 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int c = indexToDelete; c <= stopChildIndex; c++) { 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // delete same index, shifting everybody down each time 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children.RemoveAt(indexToDelete); 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver FreshenParentAndChildIndexes(startChildIndex); 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } else { 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // more new nodes than were there before 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // fill in as many children as we can (replacingHowMany) w/o moving data 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int j = 0; j < replacingHowMany; j++) { 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children[startChildIndex + j] = newChildren[j]; 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numToInsert = replacingWithHowMany - replacingHowMany; 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int j = replacingHowMany; j < replacingWithHowMany; j++) { 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children.Insert(startChildIndex + j, newChildren[j]); 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver FreshenParentAndChildIndexes(startChildIndex); 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver //System.out.println("out="+toStringTree()); 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Override in a subclass to change the impl of children list</summary> */ 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected virtual List<ITree> CreateChildrenList() { 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return new List<ITree>(); 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Set the parent and child index values for all child of t</summary> */ 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void FreshenParentAndChildIndexes() { 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver FreshenParentAndChildIndexes(0); 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void FreshenParentAndChildIndexes(int offset) { 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = ChildCount; 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int c = offset; c < n; c++) { 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ITree child = GetChild(c); 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child.ChildIndex = c; 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child.Parent = this; 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void SanityCheckParentAndChildIndexes() { 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver SanityCheckParentAndChildIndexes(null, -1); 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual void SanityCheckParentAndChildIndexes(ITree parent, int i) { 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (parent != this.Parent) { 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new InvalidOperationException("parents don't match; expected " + parent + " found " + this.Parent); 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (i != this.ChildIndex) { 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new InvalidOperationException("child indexes don't match; expected " + i + " found " + this.ChildIndex); 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int n = this.ChildCount; 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int c = 0; c < n; c++) { 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver BaseTree child = (BaseTree)this.GetChild(c); 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child.SanityCheckParentAndChildIndexes(this, c); 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Walk upwards looking for ancestor with this token type.</summary> */ 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual bool HasAncestor(int ttype) { 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return GetAncestor(ttype) != null; 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Walk upwards and get first ancestor with this token type.</summary> */ 384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual ITree GetAncestor(int ttype) { 385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ITree t = this; 386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t = t.Parent; 387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (t != null) { 388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (t.Type == ttype) 389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return t; 390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t = t.Parent; 391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary> 396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Return a list of all ancestors of this node. The first node of 397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * list is the root and the last is the parent of this node. 398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * </summary> 399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual IList<ITree> GetAncestors() { 401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (Parent == null) 402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver List<ITree> ancestors = new List<ITree>(); 405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ITree t = this; 406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t = t.Parent; 407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (t != null) { 408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ancestors.Insert(0, t); // insert at start 409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t = t.Parent; 410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ancestors; 412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Print out a whole tree not just a node</summary> */ 415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public virtual string ToStringTree() { 416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (children == null || children.Count == 0) { 417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return this.ToString(); 418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver StringBuilder buf = new StringBuilder(); 420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (!IsNil) { 421324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.Append("("); 422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.Append(this.ToString()); 423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.Append(' '); 424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (int i = 0; children != null && i < children.Count; i++) { 426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ITree t = children[i]; 427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (i > 0) { 428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.Append(' '); 429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.Append(t.ToStringTree()); 431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (!IsNil) { 433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf.Append(")"); 434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf.ToString(); 436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** <summary>Override to say how a node (not a tree) should look as text</summary> */ 439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public override abstract string ToString(); 440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #region Tree Members 442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public abstract ITree DupNode(); 443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver #endregion 444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 446