1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver [The "BSD licence"] 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Copyright (c) 2005-2006 Terence Parr 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver All rights reserved. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver Redistribution and use in source and binary forms, with or without 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver modification, are permitted provided that the following conditions 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver are met: 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 1. Redistributions of source code must retain the above copyright 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver notice, this list of conditions and the following disclaimer. 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 2. Redistributions in binary form must reproduce the above copyright 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver notice, this list of conditions and the following disclaimer in the 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver documentation and/or other materials provided with the distribution. 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 3. The name of the author may not be used to endorse or promote products 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver derived from this software without specific prior written permission. 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver*/ 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverpackage org.antlr.runtime.tree { 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** A generic tree implementation with no payload. You must subclass to 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * actually have any user data. ANTLR v3 uses a list of children approach 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * instead of the child-sibling approach in v2. A flat tree (a list) is 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * an empty node whose children represent the list. An empty, but 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * non-null node is called "nil". 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public class BaseTree implements Tree { 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver protected var _children:Array; 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Create a new node from an existing node does nothing for BaseTree 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as there are no fields other than the children list, which cannot 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * be copied as the children are not considered part of this node. 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function BaseTree(node:Tree = null) { 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function getChild(i:int):Tree { 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( _children==null || i>=_children.length ) { 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return BaseTree(_children[i]); 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Get the children internal List; note that if you directly mess with 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the list, do so at your own risk. 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get children():Array { 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _children; 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function getFirstChildWithType(type:int):Tree { 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var i:int = 0; _children!=null && i < _children.length; i++) { 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var t:Tree = Tree(_children[i]); 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t.type==type ) { 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return t; 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get childCount():int { 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( _children==null ) { 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 0; 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return _children.length; 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Add t as child of this node. 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Warning: if t has no children, but child does 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and child isNil then this routine moves children to t via 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * t.children = child.children; i.e., without copying the array. 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function addChild(t:Tree):void { 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t==null ) { 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; // do nothing upon addChild(null) 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var childTree:BaseTree = BaseTree(t); 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( childTree.isNil ) { // t is an empty node possibly with children 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( this._children!=null && this._children == childTree._children ) { 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("attempt to add child list to itself"); 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // just add all of childTree's children to this 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( childTree._children!=null ) { 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( this._children!=null ) { // must copy, this has children already 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var n:int = childTree._children.length; 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var i:int = 0; i < n; i++) { 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var c:Tree = Tree(childTree._children[i]); 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.children.push(c); 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // handle double-link stuff for each child of nil root 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.parent = this; 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver c.childIndex = children.length-1; 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // no children for this but t has children; just set pointer 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // call general freshener routine 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this._children = childTree.children; 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.freshenParentAndChildIndexes(); 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { // child is not nil (don't care about children) 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( _children==null ) { 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _children = new Array(); // create children list on demand 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _children.push(t); 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver childTree.parent = this; 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver childTree.childIndex = children.length-1; 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Add all elements of kids list as children of this node */ 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function addChildren(kids:Array):void { 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var i:int = 0; i < kids.length; i++) { 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var t:Tree = Tree(kids[i]); 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver addChild(t); 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function setChild(i:int, t:Tree):void { 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t==null ) { 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t.isNil ) { 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("Can't set single child to a list"); 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( _children==null ) { 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _children = new Array(); 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver _children[i] = t; 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t.parent = this; 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t.childIndex = i; 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function deleteChild(i:int):Object { 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( _children==null ) { 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var killed:BaseTree = BaseTree(children.remove(i)); 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // walk rest and decrement their child indexes 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver this.freshenParentAndChildIndexesFrom(i); 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return killed; 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Delete children from start to stop and replace with t even if t is 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * a list (nil-root tree). num of children can increase or decrease. 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * For huge child lists, inserting children can force walking rest of 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * children to set their childindex; could be slow. 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function replaceChildren(startChildIndex:int, stopChildIndex:int, t:Object):void { 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( children==null ) { 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("indexes invalid; no children in list"); 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var replacingHowMany:int = stopChildIndex - startChildIndex + 1; 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var replacingWithHowMany:int; 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var newTree:BaseTree = BaseTree(t); 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var newChildren:Array = null; 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // normalize to a list of children to add: newChildren 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( newTree.isNil ) { 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newChildren = newTree.children; 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newChildren = new Array(); 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newChildren.push(newTree); 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver replacingWithHowMany = newChildren.length; 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var numNewChildren:int = newChildren.length; 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var delta:int = replacingHowMany - replacingWithHowMany; 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // if same number of nodes, do direct replace 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( delta == 0 ) { 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var j:int = 0; // index into new children 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var i:int=startChildIndex; i<=stopChildIndex; i++) { 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var child:BaseTree = BaseTree(newChildren[j]); 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children[i] = child; 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child.parent = this; 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child.childIndex= i; 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver j++; 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if ( delta > 0 ) { // fewer new nodes than there were 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // set children and then delete extra 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (j=0; j<numNewChildren; j++) { 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children[startChildIndex+j] = newChildren[j]; 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var indexToDelete:int = startChildIndex+numNewChildren; 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var c:int=indexToDelete; c<=stopChildIndex; c++) { 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // delete same index, shifting everybody down each time 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var killed:BaseTree = BaseTree(children.remove(indexToDelete)); 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver freshenParentAndChildIndexesFrom(startChildIndex); 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else { // more new nodes than were there before 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // fill in as many children as we can (replacingHowMany) w/o moving data 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (j=0; j<replacingHowMany; j++) { 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children[startChildIndex+j] = newChildren[j]; 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var numToInsert:int = replacingWithHowMany-replacingHowMany; 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (j=replacingHowMany; j<replacingWithHowMany; j++) { 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver children.splice(startChildIndex+j, 0, newChildren[j]); 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver freshenParentAndChildIndexesFrom(startChildIndex); 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get isNil():Boolean { 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return false; 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Set the parent and child index values for all child of t */ 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function freshenParentAndChildIndexes():void { 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver freshenParentAndChildIndexesFrom(0); 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function freshenParentAndChildIndexesFrom(offset:int):void { 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var n:int = childCount; 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var c:int = offset; c < n; c++) { 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var child:Tree = Tree(getChild(c)); 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child.childIndex = c; 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child.parent = this; 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function sanityCheckParentAndChildIndexes():void { 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver sanityCheckParentAndChildIndexesFrom(null, -1); 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function sanityCheckParentAndChildIndexesFrom(parent:Tree, i:int):void { 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( parent!=this.parent ) { 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("parents don't match; expected "+parent+" found "+this.parent); 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( i!=this.childIndex ) { 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("child indexes don't match; expected "+i+" found "+this.childIndex); 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var n:int = this.childCount; 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var c:int = 0; c < n; c++) { 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var child:CommonTree = CommonTree(this.getChild(c)); 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver child.sanityCheckParentAndChildIndexesFrom(this, c); 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** BaseTree doesn't track child indexes. */ 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get childIndex():int { 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 0; 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function set childIndex(index:int):void { 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** BaseTree doesn't track parent pointers. */ 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get parent():Tree { 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function set parent(t:Tree):void { 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Walk upwards looking for ancestor with this token type. */ 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function hasAncestor(ttype:int):Boolean { return getAncestor(ttype)!=null; } 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Walk upwards and get first ancestor with this token type. */ 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function getAncestor(ttype:int):Tree { 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var t:Tree = this; 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t = t.parent; 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( t!=null ) { 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( t.type==ttype ) return t; 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t = t.parent; 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return null; 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Return a list of all ancestors of this node. The first node of 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * list is the root and the last is the parent of this node. 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get ancestors():Array { 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( parent==null ) return null; 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var ancestors:Array = new Array(); 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var t:Tree = this; 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t = t.parent; 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while ( t!=null ) { 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ancestors.unshift(t); // insert at start 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver t = t.parent; 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ancestors; 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Print out a whole tree not just a node */ 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function toStringTree():String { 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( _children==null || _children.length==0 ) { 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return String(this); 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var buf:String = ""; 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !isNil ) { 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf += "("; 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf += String(this); 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf += ' '; 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (var i:int = 0; _children!=null && i < _children.length; i++) { 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver var t:BaseTree = BaseTree(_children[i]); 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( i>0 ) { 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf += ' '; 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf += t.toStringTree(); 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ( !isNil ) { 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver buf += ")"; 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return buf; 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get line():int { 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 0; 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get charPositionInLine():int { 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return 0; 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // "Abstract" functions since there are no abstract classes in actionscript 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function dupNode():Tree { 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("Not implemented"); 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get type():int { 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("Not implemented"); 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get text():String { 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("Not implemented"); 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get tokenStartIndex():int { 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("Not implemented"); 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function set tokenStartIndex(index:int):void { 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("Not implemented"); 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function get tokenStopIndex():int { 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("Not implemented"); 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver public function set tokenStopIndex(index:int):void { 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver throw new Error("Not implemented"); 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver}