1cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com/* 2cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com * [The "BSD licence"] 3cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com * Copyright (c) 2011 Terence Parr 4cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com * All rights reserved. 5cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com * 6cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com * Conversion to C#: 7cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com * Copyright (c) 2011 Sam Harwell, Pixel Mine, Inc. 8d03c2c732e2e914f8429cfc8b077a7b9b853dd8eedisonn@google.com * All rights reserved. 9d03c2c732e2e914f8429cfc8b077a7b9b853dd8eedisonn@google.com * 10d03c2c732e2e914f8429cfc8b077a7b9b853dd8eedisonn@google.com * Redistribution and use in source and binary forms, with or without 11d03c2c732e2e914f8429cfc8b077a7b9b853dd8eedisonn@google.com * modification, are permitted provided that the following conditions 12cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com * are met: 13cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com * 1. Redistributions of source code must retain the above copyright 141be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * notice, this list of conditions and the following disclaimer. 15d906702f7812807d79eeaba65acff62235990b64scroggo@google.com * 2. Redistributions in binary form must reproduce the above copyright 161be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * notice, this list of conditions and the following disclaimer in the 173aac1f9f308192f3787265830fe86ce8874e7382edisonn@google.com * documentation and/or other materials provided with the distribution. 18b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com * 3. The name of the author may not be used to endorse or promote products 19e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com * derived from this software without specific prior written permission. 20063d7072ef45971c17045721626b3f0cd052b3b9edisonn@google.com * 21e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 221be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 231be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 241be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 251be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 261be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 271be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 281be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 291be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 301be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31596d2e26cdaa80f8721ba6b6eedf09227524f5d1edisonn@google.com */ 321be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 331be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.comnamespace Antlr.Runtime.Tree 341be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com{ 35596d2e26cdaa80f8721ba6b6eedf09227524f5d1edisonn@google.com using System; 36596d2e26cdaa80f8721ba6b6eedf09227524f5d1edisonn@google.com using System.Collections.Generic; 37596d2e26cdaa80f8721ba6b6eedf09227524f5d1edisonn@google.com 38596d2e26cdaa80f8721ba6b6eedf09227524f5d1edisonn@google.com using StringBuilder = System.Text.StringBuilder; 39596d2e26cdaa80f8721ba6b6eedf09227524f5d1edisonn@google.com 40596d2e26cdaa80f8721ba6b6eedf09227524f5d1edisonn@google.com /** <summary> 41596d2e26cdaa80f8721ba6b6eedf09227524f5d1edisonn@google.com * A generic tree implementation with no payload. You must subclass to 42596d2e26cdaa80f8721ba6b6eedf09227524f5d1edisonn@google.com * actually have any user data. ANTLR v3 uses a list of children approach 43596d2e26cdaa80f8721ba6b6eedf09227524f5d1edisonn@google.com * instead of the child-sibling approach in v2. A flat tree (a list) is 441be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * an empty node whose children represent the list. An empty, but 451be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * non-null node is called "nil". 46063d7072ef45971c17045721626b3f0cd052b3b9edisonn@google.com * </summary> 471be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com */ 483aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com [System.Serializable] 491be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com [System.Diagnostics.DebuggerTypeProxy(typeof(AntlrRuntime_BaseTreeDebugView))] 501be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com public abstract class BaseTree : ITree 511be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 521be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com private IList<ITree> _children; 531be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 541be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com public BaseTree() 553aac1f9f308192f3787265830fe86ce8874e7382edisonn@google.com { 563aac1f9f308192f3787265830fe86ce8874e7382edisonn@google.com } 575f008652f69ce7809b920b9fa573bc72216acd51scroggo@google.com 581be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com /** <summary> 591be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * Create a new node from an existing node does nothing for BaseTree 601be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * as there are no fields other than the children list, which cannot 611be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * be copied as the children are not considered part of this node. 621be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * </summary> 631be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com */ 64b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com public BaseTree( ITree node ) 65b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 66b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 671be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 681be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com /** <summary> 691be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * Get the children internal List; note that if you directly mess with 701be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * the list, do so at your own risk. 711be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * </summary> 721be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com */ 731be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com public virtual IList<ITree> Children 741be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 751be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com get 761be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 771be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com return _children; 781be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 791be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 809615f8dbf19be50c419759920e7595bcf7e5350amtklein@google.com private set 811be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 82b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com _children = value; 83b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 84b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 85063d7072ef45971c17045721626b3f0cd052b3b9edisonn@google.com 86b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com #region ITree Members 87b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com 88b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com public virtual int ChildCount 89b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 90b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com get 91b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 92b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com if ( Children == null ) 933aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com return 0; 941be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 951be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com return Children.Count; 96b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 971be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 981be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 999615f8dbf19be50c419759920e7595bcf7e5350amtklein@google.com /** <summary>BaseTree doesn't track parent pointers.</summary> */ 1001be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com public virtual ITree Parent 1011be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 1021be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com get 1031be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 1041be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com return null; 1051be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 1061be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com set 1071be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 1081be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 1091be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 1101be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 1111be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com /** <summary>BaseTree doesn't track child indexes.</summary> */ 1121be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com public virtual int ChildIndex 1131be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 1141be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com get 1151be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 1161be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com return 0; 1171be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 1181be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com set 1191be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 1206e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com } 1216e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com } 1226e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com 1239615f8dbf19be50c419759920e7595bcf7e5350amtklein@google.com public virtual bool IsNil 1246e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com { 1256e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com get 1266e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com { 1276e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com return false; 1286e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com } 1296e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com } 1306e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com 1316e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com public abstract int TokenStartIndex 1326e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com { 1336e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com get; 1346e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com set; 1356e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com } 1366e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com 1376e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com public abstract int TokenStopIndex 1386e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com { 1396e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com get; 1406e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com set; 1416e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com } 1426e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com 143b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com public abstract int Type 144b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 145b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com get; 1469615f8dbf19be50c419759920e7595bcf7e5350amtklein@google.com set; 147b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 148b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com 149b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com public abstract string Text 150571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com { 151571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com get; 152571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com set; 153b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 154b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com 155571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com public virtual int Line 156b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 157b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com get; 158b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com set; 159b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 160b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com 161b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com public virtual int CharPositionInLine 162b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 163b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com get; 164b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com set; 165b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 166b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com 1671be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com #endregion 1681be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 1691be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com public virtual ITree GetChild( int i ) 1701be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 171b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com if (i < 0) 172b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com throw new ArgumentOutOfRangeException(); 1731be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 1741be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if ( Children == null || i >= Children.Count ) 1756e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com return null; 1761be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 1777ee12ca99f4ac0aadb8c4d29ae793c411faf73dbedisonn@google.com return Children[i]; 1787ee12ca99f4ac0aadb8c4d29ae793c411faf73dbedisonn@google.com } 1797ee12ca99f4ac0aadb8c4d29ae793c411faf73dbedisonn@google.com 1807ee12ca99f4ac0aadb8c4d29ae793c411faf73dbedisonn@google.com public virtual ITree GetFirstChildWithType( int type ) 1811be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 1821be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com foreach ( ITree child in Children ) 183e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com { 184e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com if ( child.Type == type ) 1851be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com return child; 186e57c62d039cbd67a4e52776b3e95c5d002b818d2edisonn@google.com } 187e57c62d039cbd67a4e52776b3e95c5d002b818d2edisonn@google.com 188e57c62d039cbd67a4e52776b3e95c5d002b818d2edisonn@google.com return null; 189e57c62d039cbd67a4e52776b3e95c5d002b818d2edisonn@google.com } 190e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com 191e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com /** <summary>Add t as child of this node.</summary> 192e57c62d039cbd67a4e52776b3e95c5d002b818d2edisonn@google.com * 1933aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com * <remarks> 1943aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com * Warning: if t has no children, but child does 1953aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com * and child isNil then this routine moves children to t via 1963aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com * t.children = child.children; i.e., without copying the array. 197e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com * </remarks> 198e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com */ 199e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com public virtual void AddChild( ITree t ) 200e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com { 2013aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com //System.out.println("add child "+t.toStringTree()+" "+this.toStringTree()); 2023aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com //System.out.println("existing children: "+children); 2033aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com if ( t == null ) 2043aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com { 2053aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com return; // do nothing upon addChild(null) 2066e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com } 207e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com if ( t.IsNil ) 208e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com { 2091be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com // t is an empty node possibly with children 2101be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com BaseTree childTree = t as BaseTree; 2111be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if ( childTree != null && this.Children != null && this.Children == childTree.Children ) 212b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 213b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com throw new Exception( "attempt to add child list to itself" ); 214b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 215b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com // just add all of childTree's children to this 216b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com if ( t.ChildCount > 0 ) 217b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 218b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com if ( this.Children != null || childTree == null ) 219b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 220b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com if ( this.Children == null ) 221b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com this.Children = CreateChildrenList(); 222b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com 223b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com // must copy, this has children already 224b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com int n = t.ChildCount; 225b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com for ( int i = 0; i < n; i++ ) 226f68aed33819cbc98a95edeadde1da9303eca7fb2edisonn@google.com { 227b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com ITree c = t.GetChild( i ); 228b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com this.Children.Add( c ); 229b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com // handle double-link stuff for each child of nil root 230b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com c.Parent = this; 2311be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com c.ChildIndex = Children.Count - 1; 2321be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 2333aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com } 234571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com else 2351be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 236e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com // no children for this but t is a BaseTree with children; 237e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com // just set pointer call general freshener routine 238e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com this.Children = childTree.Children; 239e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com this.FreshenParentAndChildIndexes(); 240e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com } 241e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com } 242e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com } 243e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com else 244e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com { 245e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com // child is not nil (don't care about children) 246e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com if ( Children == null ) 247e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com { 248e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com Children = CreateChildrenList(); // create children list on demand 249e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com } 2506e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com Children.Add( t ); 2511be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com t.Parent = this; 252e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com t.ChildIndex = Children.Count - 1; 253e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com } 2541be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com // System.out.println("now children are: "+children); 255571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com } 256571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com 2573aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com /** <summary>Add all elements of kids list as children of this node</summary> */ 2581be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com public virtual void AddChildren( IEnumerable<ITree> kids ) 2591be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 2601be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if (kids == null) 2611be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com throw new ArgumentNullException("kids"); 2621be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 2631be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com foreach ( ITree t in kids ) 2641be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com AddChild( t ); 2651be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 2661be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 267e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com public virtual void SetChild( int i, ITree t ) 268e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com { 2691be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if (i < 0) 2701be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com throw new ArgumentOutOfRangeException("i"); 2711be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 2721be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if ( t == null ) 2731be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 2745f008652f69ce7809b920b9fa573bc72216acd51scroggo@google.com return; 2751be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 2761be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if ( t.IsNil ) 2771be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 2781be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com throw new ArgumentException( "Can't set single child to a list" ); 2796e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com } 2801be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if ( Children == null ) 2811be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 2821be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com Children = CreateChildrenList(); 2831be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 2841be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com Children[i] = t; 2851be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com t.Parent = this; 2861be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com t.ChildIndex = i; 2873aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com } 2881be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 2891be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com public virtual object DeleteChild( int i ) 2901be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com { 291e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com if (i < 0) 292e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com throw new ArgumentOutOfRangeException("i"); 2936e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com if (i >= ChildCount) 2941be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com throw new ArgumentException(); 2951be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 2961be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if ( Children == null ) 2971be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com return null; 2981be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 2991be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com ITree killed = Children[i]; 3001be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com Children.RemoveAt( i ); 3011be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com // walk rest and decrement their child indexes 3023aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com this.FreshenParentAndChildIndexes( i ); 3036e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com return killed; 304571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com } 3056e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com 306571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com /** <summary> 3076e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com * Delete children from start to stop and replace with t even if t is 3083aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com * a list (nil-root tree). num of children can increase or decrease. 3093aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com * For huge child lists, inserting children can force walking rest of 3103aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com * children to set their childindex; could be slow. 3113aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com * </summary> 3123aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com */ 3133aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com public virtual void ReplaceChildren( int startChildIndex, int stopChildIndex, object t ) 3143aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com { 3151be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if (startChildIndex < 0) 3161be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com throw new ArgumentOutOfRangeException(); 3171be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if (stopChildIndex < 0) 318e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com throw new ArgumentOutOfRangeException(); 319e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com if (t == null) 3206e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com throw new ArgumentNullException("t"); 3211be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if (stopChildIndex < startChildIndex) 3221be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com throw new ArgumentException(); 3231be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 3241be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com /* 3251be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com System.out.println("replaceChildren "+startChildIndex+", "+stopChildIndex+ 3261be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com " with "+((BaseTree)t).toStringTree()); 3271be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com System.out.println("in="+toStringTree()); 3286e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com */ 3291be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if ( Children == null ) 330e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com { 331e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com throw new ArgumentException( "indexes invalid; no children in list" ); 3326e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com } 3331be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com int replacingHowMany = stopChildIndex - startChildIndex + 1; 3346e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com int replacingWithHowMany; 3351be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com ITree newTree = (ITree)t; 336e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com IList<ITree> newChildren = null; 337e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com // normalize to a list of children to add: newChildren 3381be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if ( newTree.IsNil ) 339b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 340b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com BaseTree baseTree = newTree as BaseTree; 341b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com if ( baseTree != null && baseTree.Children != null ) 342b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 343b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com newChildren = baseTree.Children; 344b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 345b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com else 346b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 347b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com newChildren = CreateChildrenList(); 348b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com int n = newTree.ChildCount; 349b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com for ( int i = 0; i < n; i++ ) 350b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com newChildren.Add( newTree.GetChild( i ) ); 351b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 352b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 353b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com else 354b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 355b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com newChildren = new List<ITree>( 1 ); 356b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com newChildren.Add( newTree ); 357b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 358b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com replacingWithHowMany = newChildren.Count; 359b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com int numNewChildren = newChildren.Count; 360b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com int delta = replacingHowMany - replacingWithHowMany; 361b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com // if same number of nodes, do direct replace 362b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com if ( delta == 0 ) 363b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 364b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com int j = 0; // index into new children 365b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com for ( int i = startChildIndex; i <= stopChildIndex; i++ ) 366b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 367b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com ITree child = newChildren[j]; 3681be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com Children[i] = child; 3691be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com child.Parent = this; 370b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com child.ChildIndex = i; 3713aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com j++; 372b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 373b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 374b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com else if ( delta > 0 ) 375b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 376b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com // fewer new nodes than there were 377b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com // set children and then delete extra 378b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com for ( int j = 0; j < numNewChildren; j++ ) 379b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 380b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com Children[startChildIndex + j] = newChildren[j]; 381b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 382b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com int indexToDelete = startChildIndex + numNewChildren; 383b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com for ( int c = indexToDelete; c <= stopChildIndex; c++ ) 384b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 3851be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com // delete same index, shifting everybody down each time 3863aa355527a3b91d3e12b8bee49e5637d00a736caedisonn@google.com Children.RemoveAt( indexToDelete ); 387571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com } 388b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com FreshenParentAndChildIndexes( startChildIndex ); 389b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 390571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com else 391571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com { 392571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com // more new nodes than were there before 3932fd5d36ea6e134647aae0fbd35195500723851c3edisonn@google.com // fill in as many children as we can (replacingHowMany) w/o moving data 3942fd5d36ea6e134647aae0fbd35195500723851c3edisonn@google.com for ( int j = 0; j < replacingHowMany; j++ ) 395571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com { 396b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com Children[startChildIndex + j] = newChildren[j]; 397b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 398b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com int numToInsert = replacingWithHowMany - replacingHowMany; 399b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com for ( int j = replacingHowMany; j < replacingWithHowMany; j++ ) 400571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com { 401b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com Children.Insert( startChildIndex + j, newChildren[j] ); 402b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 403b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com FreshenParentAndChildIndexes( startChildIndex ); 404571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com } 405b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com //System.out.println("out="+toStringTree()); 406b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 407a3356fce903ff75dc332b53dd3a860ba810b9519edisonn@google.com 408a3356fce903ff75dc332b53dd3a860ba810b9519edisonn@google.com /** <summary>Override in a subclass to change the impl of children list</summary> */ 409571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com protected virtual IList<ITree> CreateChildrenList() 410b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 411571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com return new List<ITree>(); 412571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com } 413b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com 414b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com /** <summary>Set the parent and child index values for all child of t</summary> */ 415b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com public virtual void FreshenParentAndChildIndexes() 416b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 417b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com FreshenParentAndChildIndexes( 0 ); 418b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 419571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com 420571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com public virtual void FreshenParentAndChildIndexes( int offset ) 421ac4bedcb1098416e46f1907b03878787df6342ceedisonn@google.com { 422ac4bedcb1098416e46f1907b03878787df6342ceedisonn@google.com int n = ChildCount; 423ac4bedcb1098416e46f1907b03878787df6342ceedisonn@google.com for ( int c = offset; c < n; c++ ) 424ac4bedcb1098416e46f1907b03878787df6342ceedisonn@google.com { 425b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com ITree child = GetChild( c ); 426b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com child.ChildIndex = c; 427b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com child.Parent = this; 428571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com } 429571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com } 430571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com 431571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com public virtual void SanityCheckParentAndChildIndexes() 432a3356fce903ff75dc332b53dd3a860ba810b9519edisonn@google.com { 433571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com SanityCheckParentAndChildIndexes( null, -1 ); 434ac4bedcb1098416e46f1907b03878787df6342ceedisonn@google.com } 435ac4bedcb1098416e46f1907b03878787df6342ceedisonn@google.com 436ac4bedcb1098416e46f1907b03878787df6342ceedisonn@google.com public virtual void SanityCheckParentAndChildIndexes( ITree parent, int i ) 437ac4bedcb1098416e46f1907b03878787df6342ceedisonn@google.com { 438b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com if ( parent != this.Parent ) 439b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 440b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com throw new InvalidOperationException( "parents don't match; expected " + parent + " found " + this.Parent ); 441ac4bedcb1098416e46f1907b03878787df6342ceedisonn@google.com } 442b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com if ( i != this.ChildIndex ) 443b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 4441be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com throw new InvalidOperationException( "child indexes don't match; expected " + i + " found " + this.ChildIndex ); 4451be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com } 4461be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com int n = this.ChildCount; 447e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com for ( int c = 0; c < n; c++ ) 448e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com { 449b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com BaseTree child = (BaseTree)this.GetChild( c ); 4506e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com child.SanityCheckParentAndChildIndexes( this, c ); 451b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 452b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 453b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com 454b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com /** <summary>Walk upwards looking for ancestor with this token type.</summary> */ 455b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com public virtual bool HasAncestor( int ttype ) 456b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com { 457b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com return GetAncestor( ttype ) != null; 458b857a0c7de8cffb09281fa59591649fb1db6ad0aedisonn@google.com } 4591be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com 460571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com /** <summary>Walk upwards and get first ancestor with this token type.</summary> */ 461e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com public virtual ITree GetAncestor( int ttype ) 462e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com { 463e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com ITree t = this; 464e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com t = t.Parent; 465e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com while ( t != null ) 466e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com { 4671be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com if ( t.Type == ttype ) 4686e49c345b132ca55830c7dad746108cd3624eb8bedisonn@google.com return t; 469e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com t = t.Parent; 470e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com } 471e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com return null; 472e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com } 473571c70b95f56e22b5a7d6f4f288aa6c9a925a64fedisonn@google.com 4741be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com /** <summary> 4751be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * Return a list of all ancestors of this node. The first node of 476e50d9a1fcd9c4298079ff54f9a40c9708d30f8c6edisonn@google.com * list is the root and the last is the parent of this node. 4771be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com * </summary> 4781be794fad6bef2b1ab98158bd3ad68dc4a52dbf6edisonn@google.com */ 479cf2cfa174ca878c144e17e9fc60ca8e9070d7dededisonn@google.com public virtual IList<ITree> GetAncestors() 480 { 481 if ( Parent == null ) 482 return null; 483 484 List<ITree> ancestors = new List<ITree>(); 485 ITree t = this; 486 t = t.Parent; 487 while ( t != null ) 488 { 489 ancestors.Insert( 0, t ); // insert at start 490 t = t.Parent; 491 } 492 return ancestors; 493 } 494 495 /** <summary>Print out a whole tree not just a node</summary> */ 496 public virtual string ToStringTree() 497 { 498 if ( Children == null || Children.Count == 0 ) 499 { 500 return this.ToString(); 501 } 502 StringBuilder buf = new StringBuilder(); 503 if ( !IsNil ) 504 { 505 buf.Append( "(" ); 506 buf.Append( this.ToString() ); 507 buf.Append( ' ' ); 508 } 509 for ( int i = 0; Children != null && i < Children.Count; i++ ) 510 { 511 ITree t = Children[i]; 512 if ( i > 0 ) 513 { 514 buf.Append( ' ' ); 515 } 516 buf.Append( t.ToStringTree() ); 517 } 518 if ( !IsNil ) 519 { 520 buf.Append( ")" ); 521 } 522 return buf.ToString(); 523 } 524 525 /** <summary>Override to say how a node (not a tree) should look as text</summary> */ 526 public override abstract string ToString(); 527 528 #region Tree Members 529 public abstract ITree DupNode(); 530 #endregion 531 } 532} 533