1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/* 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * [The "BSD licence"] 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Copyright (c) 2011 Terence Parr 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * All rights reserved. 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Conversion to C#: 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Copyright (c) 2011 Sam Harwell, Pixel Mine, Inc. 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * All rights reserved. 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Redistribution and use in source and binary forms, with or without 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * modification, are permitted provided that the following conditions 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * are met: 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 1. Redistributions of source code must retain the above copyright 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * notice, this list of conditions and the following disclaimer. 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 2. Redistributions in binary form must reproduce the above copyright 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * notice, this list of conditions and the following disclaimer in the 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * documentation and/or other materials provided with the distribution. 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 3. The name of the author may not be used to endorse or promote products 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * derived from this software without specific prior written permission. 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgnamespace Antlr.Runtime.Tree 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org{ 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org using System; 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org using System.Collections.Generic; 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org using StringBuilder = System.Text.StringBuilder; 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary> 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * A generic tree implementation with no payload. You must subclass to 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * actually have any user data. ANTLR v3 uses a list of children approach 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * instead of the child-sibling approach in v2. A flat tree (a list) is 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * an empty node whose children represent the list. An empty, but 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * non-null node is called "nil". 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * </summary> 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org [System.Serializable] 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org [System.Diagnostics.DebuggerTypeProxy(typeof(AntlrRuntime_BaseTreeDebugView))] 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public abstract class BaseTree : ITree 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org private IList<ITree> _children; 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public BaseTree() 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary> 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Create a new node from an existing node does nothing for BaseTree 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * as there are no fields other than the children list, which cannot 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * be copied as the children are not considered part of this node. 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * </summary> 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public BaseTree( ITree node ) 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary> 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Get the children internal List; note that if you directly mess with 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the list, do so at your own risk. 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * </summary> 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual IList<ITree> Children 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return _children; 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org private set 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org _children = value; 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org #region ITree Members 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual int ChildCount 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( Children == null ) 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0; 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return Children.Count; 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary>BaseTree doesn't track parent pointers.</summary> */ 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual ITree Parent 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return null; 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org set 107f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 108f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 109f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 110f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 111f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary>BaseTree doesn't track child indexes.</summary> */ 112f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual int ChildIndex 113f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 114f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get 115f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 116f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return 0; 117f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 118f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org set 119f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 120f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 121f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 122f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 123f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual bool IsNil 124f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 125f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get 126f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 127f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return false; 128f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 129f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 130f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 131f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public abstract int TokenStartIndex 132f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 133f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get; 134f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org set; 135f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 136f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 137f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public abstract int TokenStopIndex 138f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 139f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get; 140f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org set; 141f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 142f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 143f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public abstract int Type 144f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 145f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get; 146f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org set; 147f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 148f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 149f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public abstract string Text 150f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 151f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get; 152f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org set; 153f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 154f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 155f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual int Line 156f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 157f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get; 158f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org set; 159f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 160f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 161f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual int CharPositionInLine 162f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 163f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org get; 164f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org set; 165f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 166f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 167f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org #endregion 168f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 169f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual ITree GetChild( int i ) 170f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 171f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (i < 0) 172f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentOutOfRangeException(); 173f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 174f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( Children == null || i >= Children.Count ) 175f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return null; 176f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 177f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return Children[i]; 178f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 179f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 180f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual ITree GetFirstChildWithType( int type ) 181f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 182f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org foreach ( ITree child in Children ) 183f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 184f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( child.Type == type ) 185f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return child; 186f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 187f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 188f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return null; 189f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 190f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 191f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary>Add t as child of this node.</summary> 192f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 193f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * <remarks> 194f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Warning: if t has no children, but child does 195f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * and child isNil then this routine moves children to t via 196f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * t.children = child.children; i.e., without copying the array. 197f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * </remarks> 198f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 199f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual void AddChild( ITree t ) 200f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 201f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org //System.out.println("add child "+t.toStringTree()+" "+this.toStringTree()); 202f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org //System.out.println("existing children: "+children); 203f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( t == null ) 204f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 205f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return; // do nothing upon addChild(null) 206f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 207f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( t.IsNil ) 208f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 209f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // t is an empty node possibly with children 210f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BaseTree childTree = t as BaseTree; 211f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( childTree != null && this.Children != null && this.Children == childTree.Children ) 212f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 213f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new Exception( "attempt to add child list to itself" ); 214f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 215f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // just add all of childTree's children to this 216f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( t.ChildCount > 0 ) 217f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 218f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( this.Children != null || childTree == null ) 219f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 220f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( this.Children == null ) 221f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this.Children = CreateChildrenList(); 222f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 223f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // must copy, this has children already 224f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int n = t.ChildCount; 225f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for ( int i = 0; i < n; i++ ) 226f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 227f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ITree c = t.GetChild( i ); 228f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this.Children.Add( c ); 229f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // handle double-link stuff for each child of nil root 230f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org c.Parent = this; 231f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org c.ChildIndex = Children.Count - 1; 232f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 233f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 234f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 235f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 236f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // no children for this but t is a BaseTree with children; 237f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // just set pointer call general freshener routine 238f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this.Children = childTree.Children; 239f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this.FreshenParentAndChildIndexes(); 240f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 241f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 242f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 243f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 244f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 245f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // child is not nil (don't care about children) 246f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( Children == null ) 247f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 248f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Children = CreateChildrenList(); // create children list on demand 249f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 250f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Children.Add( t ); 251f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org t.Parent = this; 252f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org t.ChildIndex = Children.Count - 1; 253f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 254f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // System.out.println("now children are: "+children); 255f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 256f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 257f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary>Add all elements of kids list as children of this node</summary> */ 258f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual void AddChildren( IEnumerable<ITree> kids ) 259f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 260f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (kids == null) 261f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentNullException("kids"); 262f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 263f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org foreach ( ITree t in kids ) 264f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org AddChild( t ); 265f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 266f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 267f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual void SetChild( int i, ITree t ) 268f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 269f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (i < 0) 270f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentOutOfRangeException("i"); 271f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 272f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( t == null ) 273f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 274f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return; 275f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 276f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( t.IsNil ) 277f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 278f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentException( "Can't set single child to a list" ); 279f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 280f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( Children == null ) 281f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 282f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Children = CreateChildrenList(); 283f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 284f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Children[i] = t; 285f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org t.Parent = this; 286f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org t.ChildIndex = i; 287f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 288f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 289f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual object DeleteChild( int i ) 290f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 291f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (i < 0) 292f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentOutOfRangeException("i"); 293f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (i >= ChildCount) 294f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentException(); 295f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 296f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( Children == null ) 297f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return null; 298f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 299f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ITree killed = Children[i]; 300f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Children.RemoveAt( i ); 301f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // walk rest and decrement their child indexes 302f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org this.FreshenParentAndChildIndexes( i ); 303f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return killed; 304f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 305f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 306f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary> 307f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Delete children from start to stop and replace with t even if t is 308f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * a list (nil-root tree). num of children can increase or decrease. 309f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * For huge child lists, inserting children can force walking rest of 310f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * children to set their childindex; could be slow. 311f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * </summary> 312f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 313f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual void ReplaceChildren( int startChildIndex, int stopChildIndex, object t ) 314f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 315f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (startChildIndex < 0) 316f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentOutOfRangeException(); 317f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (stopChildIndex < 0) 318f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentOutOfRangeException(); 319f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (t == null) 320f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentNullException("t"); 321f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if (stopChildIndex < startChildIndex) 322f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentException(); 323f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 324f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /* 325f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org System.out.println("replaceChildren "+startChildIndex+", "+stopChildIndex+ 326f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org " with "+((BaseTree)t).toStringTree()); 327f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org System.out.println("in="+toStringTree()); 328f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 329f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( Children == null ) 330f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 331f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new ArgumentException( "indexes invalid; no children in list" ); 332f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 333f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int replacingHowMany = stopChildIndex - startChildIndex + 1; 334f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int replacingWithHowMany; 335f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ITree newTree = (ITree)t; 336f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org IList<ITree> newChildren = null; 337f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // normalize to a list of children to add: newChildren 338f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( newTree.IsNil ) 339f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 340f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BaseTree baseTree = newTree as BaseTree; 341f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( baseTree != null && baseTree.Children != null ) 342f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 343f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org newChildren = baseTree.Children; 344f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 345f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 346f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 347f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org newChildren = CreateChildrenList(); 348f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int n = newTree.ChildCount; 349f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for ( int i = 0; i < n; i++ ) 350f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org newChildren.Add( newTree.GetChild( i ) ); 351f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 352f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 353f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 354f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 355f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org newChildren = new List<ITree>( 1 ); 356f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org newChildren.Add( newTree ); 357f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 358f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org replacingWithHowMany = newChildren.Count; 359f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int numNewChildren = newChildren.Count; 360f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int delta = replacingHowMany - replacingWithHowMany; 361f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // if same number of nodes, do direct replace 362f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( delta == 0 ) 363f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 364f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int j = 0; // index into new children 365f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for ( int i = startChildIndex; i <= stopChildIndex; i++ ) 366f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 367f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ITree child = newChildren[j]; 368f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Children[i] = child; 369f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org child.Parent = this; 370f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org child.ChildIndex = i; 371f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org j++; 372f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 373f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 374f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else if ( delta > 0 ) 375f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 376f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // fewer new nodes than there were 377f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // set children and then delete extra 378f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for ( int j = 0; j < numNewChildren; j++ ) 379f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 380f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Children[startChildIndex + j] = newChildren[j]; 381f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 382f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int indexToDelete = startChildIndex + numNewChildren; 383f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for ( int c = indexToDelete; c <= stopChildIndex; c++ ) 384f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 385f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // delete same index, shifting everybody down each time 386f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Children.RemoveAt( indexToDelete ); 387f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 388f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FreshenParentAndChildIndexes( startChildIndex ); 389f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 390f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org else 391f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 392f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // more new nodes than were there before 393f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org // fill in as many children as we can (replacingHowMany) w/o moving data 394f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for ( int j = 0; j < replacingHowMany; j++ ) 395f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 396f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Children[startChildIndex + j] = newChildren[j]; 397f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 398f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int numToInsert = replacingWithHowMany - replacingHowMany; 399f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for ( int j = replacingHowMany; j < replacingWithHowMany; j++ ) 400f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 401f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org Children.Insert( startChildIndex + j, newChildren[j] ); 402f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 403f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FreshenParentAndChildIndexes( startChildIndex ); 404f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 405f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org //System.out.println("out="+toStringTree()); 406f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 407f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 408f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary>Override in a subclass to change the impl of children list</summary> */ 409f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org protected virtual IList<ITree> CreateChildrenList() 410f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 411f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return new List<ITree>(); 412f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 413f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 414f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary>Set the parent and child index values for all child of t</summary> */ 415f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual void FreshenParentAndChildIndexes() 416f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 417f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org FreshenParentAndChildIndexes( 0 ); 418f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 419f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 420f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual void FreshenParentAndChildIndexes( int offset ) 421f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 422f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int n = ChildCount; 423f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for ( int c = offset; c < n; c++ ) 424f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 425f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ITree child = GetChild( c ); 426f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org child.ChildIndex = c; 427f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org child.Parent = this; 428f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 429f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 430f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 431f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual void SanityCheckParentAndChildIndexes() 432f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 433f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org SanityCheckParentAndChildIndexes( null, -1 ); 434f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 435f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 436f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual void SanityCheckParentAndChildIndexes( ITree parent, int i ) 437f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 438f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( parent != this.Parent ) 439f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 440f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new InvalidOperationException( "parents don't match; expected " + parent + " found " + this.Parent ); 441f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 442f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( i != this.ChildIndex ) 443f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 444f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org throw new InvalidOperationException( "child indexes don't match; expected " + i + " found " + this.ChildIndex ); 445f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 446f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org int n = this.ChildCount; 447f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for ( int c = 0; c < n; c++ ) 448f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 449f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org BaseTree child = (BaseTree)this.GetChild( c ); 450f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org child.SanityCheckParentAndChildIndexes( this, c ); 451f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 452f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 453f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 454f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary>Walk upwards looking for ancestor with this token type.</summary> */ 455f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual bool HasAncestor( int ttype ) 456f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 457f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return GetAncestor( ttype ) != null; 458f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 459f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 460f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary>Walk upwards and get first ancestor with this token type.</summary> */ 461f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual ITree GetAncestor( int ttype ) 462f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 463f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ITree t = this; 464f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org t = t.Parent; 465f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while ( t != null ) 466f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 467f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( t.Type == ttype ) 468f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return t; 469f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org t = t.Parent; 470f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 471f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return null; 472f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 473f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 474f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary> 475f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Return a list of all ancestors of this node. The first node of 476f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * list is the root and the last is the parent of this node. 477f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * </summary> 478f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 479f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual IList<ITree> GetAncestors() 480f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 481f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( Parent == null ) 482f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return null; 483f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 484f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org List<ITree> ancestors = new List<ITree>(); 485f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ITree t = this; 486f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org t = t.Parent; 487f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org while ( t != null ) 488f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 489f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ancestors.Insert( 0, t ); // insert at start 490f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org t = t.Parent; 491f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 492f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return ancestors; 493f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 494f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 495f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary>Print out a whole tree not just a node</summary> */ 496f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public virtual string ToStringTree() 497f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 498f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( Children == null || Children.Count == 0 ) 499f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 500f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return this.ToString(); 501f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 502f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org StringBuilder buf = new StringBuilder(); 503f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( !IsNil ) 504f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 505f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buf.Append( "(" ); 506f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buf.Append( this.ToString() ); 507f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buf.Append( ' ' ); 508f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 509f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for ( int i = 0; Children != null && i < Children.Count; i++ ) 510f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 511f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org ITree t = Children[i]; 512f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( i > 0 ) 513f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 514f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buf.Append( ' ' ); 515f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 516f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buf.Append( t.ToStringTree() ); 517f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 518f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org if ( !IsNil ) 519f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org { 520f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org buf.Append( ")" ); 521f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 522f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org return buf.ToString(); 523f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 524f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 525f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org /** <summary>Override to say how a node (not a tree) should look as text</summary> */ 526f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public override abstract string ToString(); 527f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 528f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org #region Tree Members 529f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org public abstract ITree DupNode(); 530f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org #endregion 531f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org } 532f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 533f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org