antlr-3.4/runtime/ActionScript/project/src/org/antlr/runtime/tree/BaseTree.as - platform/external/antlr - Git at Google

 /*
  [The "BSD licence"]
  Copyright (c) 2005-2006 Terence Parr
  All rights reserved.

  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions
  are met:
  1. Redistributions of source code must retain the above copyright
     notice, this list of conditions and the following disclaimer.
  2. Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions and the following disclaimer in the
     documentation and/or other materials provided with the distribution.
  3. The name of the author may not be used to endorse or promote products
     derived from this software without specific prior written permission.

  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 package org.antlr.runtime.tree {
 	/** A generic tree implementation with no payload.  You must subclass to
 	 *  actually have any user data.  ANTLR v3 uses a list of children approach
 	 *  instead of the child-sibling approach in v2.  A flat tree (a list) is
 	 *  an empty node whose children represent the list.  An empty, but
 	 *  non-null node is called "nil".
 	 */
 	public class BaseTree implements Tree {
 		protected var _children:Array;

 		/** Create a new node from an existing node does nothing for BaseTree
 		 *  as there are no fields other than the children list, which cannot
 		 *  be copied as the children are not considered part of this node.
 		 */
 		public function BaseTree(node:Tree = null) {
 		}

 		public function getChild(i:int):Tree {
 			if ( _children==null || i>=_children.length ) {
 				return null;
 			}
 			return BaseTree(_children[i]);
 		}

 		/** Get the children internal List; note that if you directly mess with
 		 *  the list, do so at your own risk.
 		 */
 		public function get children():Array {
 			return _children;
 		}

 		public function getFirstChildWithType(type:int):Tree {
 			for (var i:int = 0; _children!=null && i < _children.length; i++) {
 				var t:Tree = Tree(_children[i]);
 				if ( t.type==type ) {
 					return t;
 				}
 			}
 			return null;
 		}

 		public function get childCount():int {
 			if ( _children==null ) {
 				return 0;
 			}
 			return _children.length;
 		}

 		/** Add t as child of this node.
 		 *
 		 *  Warning: if t has no children, but child does
 		 *  and child isNil then this routine moves children to t via
 		 *  t.children = child.children; i.e., without copying the array.
 		 */
 		public function addChild(t:Tree):void {
 			if ( t==null ) {
 				return; // do nothing upon addChild(null)
 			}
 			var childTree:BaseTree = BaseTree(t);
 			if ( childTree.isNil ) { // t is an empty node possibly with children
 				if ( this._children!=null && this._children == childTree._children ) {
 					throw new Error("attempt to add child list to itself");
 				}
 				// just add all of childTree's children to this
 				if ( childTree._children!=null ) {
 					if ( this._children!=null ) { // must copy, this has children already
 						var n:int = childTree._children.length;
 						for (var i:int = 0; i < n; i++) {
 							var c:Tree = Tree(childTree._children[i]);
 							this.children.push(c);
 							// handle double-link stuff for each child of nil root
 							c.parent = this;
 							c.childIndex = children.length-1;
 						}
 					}
 					else {
 						// no children for this but t has children; just set pointer
 						// call general freshener routine
 						this._children = childTree.children;
 						this.freshenParentAndChildIndexes();
 					}
 				}
 			}
 			else { // child is not nil (don't care about children)
 				if ( _children==null ) {
 					_children = new Array(); // create children list on demand
 				}
 				_children.push(t);
 				childTree.parent = this;
 				childTree.childIndex = children.length-1;
 			}
 		}

 		/** Add all elements of kids list as children of this node */
 		public function addChildren(kids:Array):void {
 			for (var i:int = 0; i < kids.length; i++) {
 				var t:Tree = Tree(kids[i]);
 				addChild(t);
 			}
 		}

 		public function setChild(i:int, t:Tree):void {
 			if ( t==null ) {
 				return;
 			}
 			if ( t.isNil ) {
 				throw new Error("Can't set single child to a list");
 			}
 			if ( _children==null ) {
 				_children = new Array();
 			}
 			_children[i] = t;
 			t.parent = this;
 			t.childIndex = i;
 		}

 		public function deleteChild(i:int):Object {
 			if ( _children==null ) {
 				return null;
 			}
 			var killed:BaseTree = BaseTree(children.remove(i));
 			// walk rest and decrement their child indexes
 			this.freshenParentAndChildIndexesFrom(i);
 			return killed;
 		}

 		/** Delete children from start to stop and replace with t even if t is
 		 *  a list (nil-root tree).  num of children can increase or decrease.
 		 *  For huge child lists, inserting children can force walking rest of
 		 *  children to set their childindex; could be slow.
 		 */
 		public function replaceChildren(startChildIndex:int, stopChildIndex:int, t:Object):void {
 			if ( children==null ) {
 				throw new Error("indexes invalid; no children in list");
 			}
 			var replacingHowMany:int = stopChildIndex - startChildIndex + 1;
 			var replacingWithHowMany:int;
 			var newTree:BaseTree = BaseTree(t);
 			var newChildren:Array = null;
 			// normalize to a list of children to add: newChildren
 			if ( newTree.isNil ) {
 				newChildren = newTree.children;
 			}
 			else {
 				newChildren = new Array();
 				newChildren.push(newTree);
 			}
 			replacingWithHowMany = newChildren.length;
 			var numNewChildren:int = newChildren.length;
 			var delta:int = replacingHowMany - replacingWithHowMany;
 			// if same number of nodes, do direct replace
 			if ( delta == 0 ) {
 				var j:int = 0; // index into new children
 				for (var i:int=startChildIndex; i<=stopChildIndex; i++) {
 					var child:BaseTree = BaseTree(newChildren[j]);
 					children[i] = child;
 					child.parent = this;
 					child.childIndex= i;
 	                j++;
 	            }
 			}
 			else if ( delta > 0 ) { // fewer new nodes than there were
 				// set children and then delete extra
 				for (j=0; j<numNewChildren; j++) {
 					children[startChildIndex+j] = newChildren[j];
 				}
 				var indexToDelete:int = startChildIndex+numNewChildren;
 				for (var c:int=indexToDelete; c<=stopChildIndex; c++) {
 					// delete same index, shifting everybody down each time
 					var killed:BaseTree = BaseTree(children.remove(indexToDelete));
 				}
 				freshenParentAndChildIndexesFrom(startChildIndex);
 			}
 			else { // more new nodes than were there before
 				// fill in as many children as we can (replacingHowMany) w/o moving data
 				for (j=0; j<replacingHowMany; j++) {
 					children[startChildIndex+j] = newChildren[j];
 				}
 				var numToInsert:int = replacingWithHowMany-replacingHowMany;
 				for (j=replacingHowMany; j<replacingWithHowMany; j++) {
 					children.splice(startChildIndex+j, 0, newChildren[j]);
 				}
 				freshenParentAndChildIndexesFrom(startChildIndex);
 			}
 		}

 		public function get isNil():Boolean {
 			return false;
 		}

 		/** Set the parent and child index values for all child of t */
 		public function freshenParentAndChildIndexes():void {
 			freshenParentAndChildIndexesFrom(0);
 		}

 		public function freshenParentAndChildIndexesFrom(offset:int):void {
 			var n:int = childCount;
 			for (var c:int = offset; c < n; c++) {
 				var child:Tree = Tree(getChild(c));
 				child.childIndex = c;
 				child.parent = this;
 			}
 		}

 		public function sanityCheckParentAndChildIndexes():void {
 			sanityCheckParentAndChildIndexesFrom(null, -1);
 		}

 		public function sanityCheckParentAndChildIndexesFrom(parent:Tree, i:int):void {
 			if ( parent!=this.parent ) {
 				throw new Error("parents don't match; expected "+parent+" found "+this.parent);
 			}
 			if ( i!=this.childIndex ) {
 				throw new Error("child indexes don't match; expected "+i+" found "+this.childIndex);
 			}
 			var n:int = this.childCount;
 			for (var c:int = 0; c < n; c++) {
 				var child:CommonTree = CommonTree(this.getChild(c));
 				child.sanityCheckParentAndChildIndexesFrom(this, c);
 			}
 		}

 		/** BaseTree doesn't track child indexes. */
 		public function get childIndex():int {
 			return 0;
 		}

 		public function set childIndex(index:int):void {
 		}

 		/** BaseTree doesn't track parent pointers. */
 		public function get parent():Tree {
 			return null;
 		}
 		public function set parent(t:Tree):void {
 		}

         /** Walk upwards looking for ancestor with this token type. */
         public function hasAncestor(ttype:int):Boolean { return getAncestor(ttype)!=null; }

         /** Walk upwards and get first ancestor with this token type. */
         public function getAncestor(ttype:int):Tree {
             var t:Tree = this;
             t = t.parent;
             while ( t!=null ) {
                 if ( t.type==ttype ) return t;
                 t = t.parent;
             }
             return null;
         }

         /** Return a list of all ancestors of this node.  The first node of
          *  list is the root and the last is the parent of this node.
          */
         public function get ancestors():Array {
             if ( parent==null ) return null;
             var ancestors:Array = new Array();
             var t:Tree = this;
             t = t.parent;
             while ( t!=null ) {
                 ancestors.unshift(t); // insert at start
                 t = t.parent;
             }
             return ancestors;
         }

 		/** Print out a whole tree not just a node */
 	    public function toStringTree():String {
 			if ( _children==null || _children.length==0 ) {
 				return String(this);
 			}
 			var buf:String = "";
 			if ( !isNil ) {
 				buf += "(";
 				buf += String(this);
 				buf += ' ';
 			}
 			for (var i:int = 0; _children!=null && i < _children.length; i++) {
 				var t:BaseTree = BaseTree(_children[i]);
 				if ( i>0 ) {
 					buf += ' ';
 				}
 				buf += t.toStringTree();
 			}
 			if ( !isNil ) {
 				buf += ")";
 			}
 			return buf;
 		}

 	    public function get line():int {
 			return 0;
 		}

 		public function get charPositionInLine():int {
 			return 0;
 		}

 		// "Abstract" functions since there are no abstract classes in actionscript

 		public function dupNode():Tree {
 			throw new Error("Not implemented");
 		}

 		public function get type():int {
 			throw new Error("Not implemented");
 		}

 		public function get text():String {
 			throw new Error("Not implemented");
 		}

 		public function get tokenStartIndex():int {
 			throw new Error("Not implemented");
 		}

 		public function set tokenStartIndex(index:int):void {
 			throw new Error("Not implemented");
 		}

 		public function get tokenStopIndex():int {
 			throw new Error("Not implemented");
 		}

 		public function set tokenStopIndex(index:int):void {
 			throw new Error("Not implemented");
 		}

 	}
 }
	/*
	[The "BSD licence"]
	Copyright (c) 2005-2006 Terence Parr
	All rights reserved.

	Redistribution and use in source and binary forms, with or without
	modification, are permitted provided that the following conditions
	are met:
	1. Redistributions of source code must retain the above copyright
	notice, this list of conditions and the following disclaimer.
	2. Redistributions in binary form must reproduce the above copyright
	notice, this list of conditions and the following disclaimer in the
	documentation and/or other materials provided with the distribution.
	3. The name of the author may not be used to endorse or promote products
	derived from this software without specific prior written permission.

	THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
	IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
	OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
	IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
	INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
	NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
	THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/
	package org.antlr.runtime.tree {
	/** A generic tree implementation with no payload. You must subclass to
	* actually have any user data. ANTLR v3 uses a list of children approach
	* instead of the child-sibling approach in v2. A flat tree (a list) is
	* an empty node whose children represent the list. An empty, but
	* non-null node is called "nil".
	*/
	public class BaseTree implements Tree {
	protected var _children:Array;

	/** Create a new node from an existing node does nothing for BaseTree
	* as there are no fields other than the children list, which cannot
	* be copied as the children are not considered part of this node.
	*/
	public function BaseTree(node:Tree = null) {
	}

	public function getChild(i:int):Tree {
	if ( _children==null \|\| i>=_children.length ) {
	return null;
	}
	return BaseTree(_children[i]);
	}

	/** Get the children internal List; note that if you directly mess with
	* the list, do so at your own risk.
	*/
	public function get children():Array {
	return _children;
	}

	public function getFirstChildWithType(type:int):Tree {
	for (var i:int = 0; _children!=null && i < _children.length; i++) {
	var t:Tree = Tree(_children[i]);
	if ( t.type==type ) {
	return t;
	}
	}
	return null;
	}

	public function get childCount():int {
	if ( _children==null ) {
	return 0;
	}
	return _children.length;
	}

	/** Add t as child of this node.
	*
	* Warning: if t has no children, but child does
	* and child isNil then this routine moves children to t via
	* t.children = child.children; i.e., without copying the array.
	*/
	public function addChild(t:Tree):void {
	if ( t==null ) {
	return; // do nothing upon addChild(null)
	}
	var childTree:BaseTree = BaseTree(t);
	if ( childTree.isNil ) { // t is an empty node possibly with children
	if ( this._children!=null && this._children == childTree._children ) {
	throw new Error("attempt to add child list to itself");
	}
	// just add all of childTree's children to this
	if ( childTree._children!=null ) {
	if ( this._children!=null ) { // must copy, this has children already
	var n:int = childTree._children.length;
	for (var i:int = 0; i < n; i++) {
	var c:Tree = Tree(childTree._children[i]);
	this.children.push(c);
	// handle double-link stuff for each child of nil root
	c.parent = this;
	c.childIndex = children.length-1;
	}
	}
	else {
	// no children for this but t has children; just set pointer
	// call general freshener routine
	this._children = childTree.children;
	this.freshenParentAndChildIndexes();
	}
	}
	}
	else { // child is not nil (don't care about children)
	if ( _children==null ) {
	_children = new Array(); // create children list on demand
	}
	_children.push(t);
	childTree.parent = this;
	childTree.childIndex = children.length-1;
	}
	}

	/** Add all elements of kids list as children of this node */
	public function addChildren(kids:Array):void {
	for (var i:int = 0; i < kids.length; i++) {
	var t:Tree = Tree(kids[i]);
	addChild(t);
	}
	}

	public function setChild(i:int, t:Tree):void {
	if ( t==null ) {
	return;
	}
	if ( t.isNil ) {
	throw new Error("Can't set single child to a list");
	}
	if ( _children==null ) {
	_children = new Array();
	}
	_children[i] = t;
	t.parent = this;
	t.childIndex = i;
	}

	public function deleteChild(i:int):Object {
	if ( _children==null ) {
	return null;
	}
	var killed:BaseTree = BaseTree(children.remove(i));
	// walk rest and decrement their child indexes
	this.freshenParentAndChildIndexesFrom(i);
	return killed;
	}

	/** Delete children from start to stop and replace with t even if t is
	* a list (nil-root tree). num of children can increase or decrease.
	* For huge child lists, inserting children can force walking rest of
	* children to set their childindex; could be slow.
	*/
	public function replaceChildren(startChildIndex:int, stopChildIndex:int, t:Object):void {
	if ( children==null ) {
	throw new Error("indexes invalid; no children in list");
	}
	var replacingHowMany:int = stopChildIndex - startChildIndex + 1;
	var replacingWithHowMany:int;
	var newTree:BaseTree = BaseTree(t);
	var newChildren:Array = null;
	// normalize to a list of children to add: newChildren
	if ( newTree.isNil ) {
	newChildren = newTree.children;
	}
	else {
	newChildren = new Array();
	newChildren.push(newTree);
	}
	replacingWithHowMany = newChildren.length;
	var numNewChildren:int = newChildren.length;
	var delta:int = replacingHowMany - replacingWithHowMany;
	// if same number of nodes, do direct replace
	if ( delta == 0 ) {
	var j:int = 0; // index into new children
	for (var i:int=startChildIndex; i<=stopChildIndex; i++) {
	var child:BaseTree = BaseTree(newChildren[j]);
	children[i] = child;
	child.parent = this;
	child.childIndex= i;
	j++;
	}
	}
	else if ( delta > 0 ) { // fewer new nodes than there were
	// set children and then delete extra
	for (j=0; j<numNewChildren; j++) {
	children[startChildIndex+j] = newChildren[j];
	}
	var indexToDelete:int = startChildIndex+numNewChildren;
	for (var c:int=indexToDelete; c<=stopChildIndex; c++) {
	// delete same index, shifting everybody down each time
	var killed:BaseTree = BaseTree(children.remove(indexToDelete));
	}
	freshenParentAndChildIndexesFrom(startChildIndex);
	}
	else { // more new nodes than were there before
	// fill in as many children as we can (replacingHowMany) w/o moving data
	for (j=0; j<replacingHowMany; j++) {
	children[startChildIndex+j] = newChildren[j];
	}
	var numToInsert:int = replacingWithHowMany-replacingHowMany;
	for (j=replacingHowMany; j<replacingWithHowMany; j++) {
	children.splice(startChildIndex+j, 0, newChildren[j]);
	}
	freshenParentAndChildIndexesFrom(startChildIndex);
	}
	}

	public function get isNil():Boolean {
	return false;
	}

	/** Set the parent and child index values for all child of t */
	public function freshenParentAndChildIndexes():void {
	freshenParentAndChildIndexesFrom(0);
	}

	public function freshenParentAndChildIndexesFrom(offset:int):void {
	var n:int = childCount;
	for (var c:int = offset; c < n; c++) {
	var child:Tree = Tree(getChild(c));
	child.childIndex = c;
	child.parent = this;
	}
	}

	public function sanityCheckParentAndChildIndexes():void {
	sanityCheckParentAndChildIndexesFrom(null, -1);
	}

	public function sanityCheckParentAndChildIndexesFrom(parent:Tree, i:int):void {
	if ( parent!=this.parent ) {
	throw new Error("parents don't match; expected "+parent+" found "+this.parent);
	}
	if ( i!=this.childIndex ) {
	throw new Error("child indexes don't match; expected "+i+" found "+this.childIndex);
	}
	var n:int = this.childCount;
	for (var c:int = 0; c < n; c++) {
	var child:CommonTree = CommonTree(this.getChild(c));
	child.sanityCheckParentAndChildIndexesFrom(this, c);
	}
	}

	/** BaseTree doesn't track child indexes. */
	public function get childIndex():int {
	return 0;
	}

	public function set childIndex(index:int):void {
	}

	/** BaseTree doesn't track parent pointers. */
	public function get parent():Tree {
	return null;
	}
	public function set parent(t:Tree):void {
	}

	/** Walk upwards looking for ancestor with this token type. */
	public function hasAncestor(ttype:int):Boolean { return getAncestor(ttype)!=null; }

	/** Walk upwards and get first ancestor with this token type. */
	public function getAncestor(ttype:int):Tree {
	var t:Tree = this;
	t = t.parent;
	while ( t!=null ) {
	if ( t.type==ttype ) return t;
	t = t.parent;
	}
	return null;
	}

	/** Return a list of all ancestors of this node. The first node of
	* list is the root and the last is the parent of this node.
	*/
	public function get ancestors():Array {
	if ( parent==null ) return null;
	var ancestors:Array = new Array();
	var t:Tree = this;
	t = t.parent;
	while ( t!=null ) {
	ancestors.unshift(t); // insert at start
	t = t.parent;
	}
	return ancestors;
	}

	/** Print out a whole tree not just a node */
	public function toStringTree():String {
	if ( _children==null \|\| _children.length==0 ) {
	return String(this);
	}
	var buf:String = "";
	if ( !isNil ) {
	buf += "(";
	buf += String(this);
	buf += ' ';
	}
	for (var i:int = 0; _children!=null && i < _children.length; i++) {
	var t:BaseTree = BaseTree(_children[i]);
	if ( i>0 ) {
	buf += ' ';
	}
	buf += t.toStringTree();
	}
	if ( !isNil ) {
	buf += ")";
	}
	return buf;
	}

	public function get line():int {
	return 0;
	}

	public function get charPositionInLine():int {
	return 0;
	}

	// "Abstract" functions since there are no abstract classes in actionscript

	public function dupNode():Tree {
	throw new Error("Not implemented");
	}

	public function get type():int {
	throw new Error("Not implemented");
	}

	public function get text():String {
	throw new Error("Not implemented");
	}

	public function get tokenStartIndex():int {
	throw new Error("Not implemented");
	}

	public function set tokenStartIndex(index:int):void {
	throw new Error("Not implemented");
	}

	public function get tokenStopIndex():int {
	throw new Error("Not implemented");
	}

	public function set tokenStopIndex(index:int):void {
	throw new Error("Not implemented");
	}

	}
	}