001: /*
002: [The "BSD licence"]
003: Copyright (c) 2005-2006 Terence Parr
004: All rights reserved.
005:
006: Redistribution and use in source and binary forms, with or without
007: modification, are permitted provided that the following conditions
008: are met:
009: 1. Redistributions of source code must retain the above copyright
010: notice, this list of conditions and the following disclaimer.
011: 2. Redistributions in binary form must reproduce the above copyright
012: notice, this list of conditions and the following disclaimer in the
013: documentation and/or other materials provided with the distribution.
014: 3. The name of the author may not be used to endorse or promote products
015: derived from this software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
018: IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
019: OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
020: IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
021: INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
022: NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
023: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
024: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
025: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
026: THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
027: */
028: package org.antlr.runtime.tree;
029:
030: import java.util.ArrayList;
031: import java.util.List;
032:
033: /** A generic tree implementation with no payload. You must subclass to
034: * actually have any user data. ANTLR v3 uses a list of children approach
035: * instead of the child-sibling approach in v2. A flat tree (a list) is
036: * an empty node whose children represent the list. An empty, but
037: * non-null node is called "nil".
038: */
039: public abstract class BaseTree implements Tree {
040: protected List children;
041:
042: public BaseTree() {
043: }
044:
045: /** Create a new node from an existing node does nothing for BaseTree
046: * as there are no fields other than the children list, which cannot
047: * be copied as the children are not considered part of this node.
048: */
049: public BaseTree(Tree node) {
050: }
051:
052: public Tree getChild(int i) {
053: if (children == null || i >= children.size()) {
054: return null;
055: }
056: return (BaseTree) children.get(i);
057: }
058:
059: public Tree getFirstChildWithType(int type) {
060: for (int i = 0; children != null && i < children.size(); i++) {
061: Tree t = (Tree) children.get(i);
062: if (t.getType() == type) {
063: return t;
064: }
065: }
066: return null;
067: }
068:
069: public int getChildCount() {
070: if (children == null) {
071: return 0;
072: }
073: return children.size();
074: }
075:
076: /** Add t as child of this node.
077: *
078: * Warning: if t has no children, but child does
079: * and child isNil then this routine moves children to t via
080: * t.children = child.children; i.e., without copying the array.
081: */
082: public void addChild(Tree t) {
083: //System.out.println("add "+t.toStringTree()+" as child to "+this.toStringTree());
084: if (t == null) {
085: return; // do nothing upon addChild(null)
086: }
087: BaseTree childTree = (BaseTree) t;
088: if (childTree.isNil()) { // t is an empty node possibly with children
089: if (this .children != null
090: && this .children == childTree.children) {
091: throw new RuntimeException(
092: "attempt to add child list to itself");
093: }
094: // just add all of childTree's children to this
095: if (childTree.children != null) {
096: if (this .children != null) { // must copy, this has children already
097: int n = childTree.children.size();
098: for (int i = 0; i < n; i++) {
099: this .children.add(childTree.children.get(i));
100: }
101: } else {
102: // no children for this but t has children; just set pointer
103: this .children = childTree.children;
104: }
105: }
106: } else { // t is not empty and might have children
107: if (children == null) {
108: children = createChildrenList(); // create children list on demand
109: }
110: children.add(t);
111: }
112: }
113:
114: /** Add all elements of kids list as children of this node */
115: public void addChildren(List kids) {
116: for (int i = 0; i < kids.size(); i++) {
117: Tree t = (Tree) kids.get(i);
118: addChild(t);
119: }
120: }
121:
122: public void setChild(int i, BaseTree t) {
123: if (children == null) {
124: children = createChildrenList();
125: }
126: children.set(i, t);
127: }
128:
129: public BaseTree deleteChild(int i) {
130: if (children == null) {
131: return null;
132: }
133: return (BaseTree) children.remove(i);
134: }
135:
136: /** Override in a subclass to change the impl of children list */
137: protected List createChildrenList() {
138: return new ArrayList();
139: }
140:
141: public boolean isNil() {
142: return false;
143: }
144:
145: /** Recursively walk this tree, dup'ing nodes until you have copy of
146: * this tree. This method should work for all subclasses as long
147: * as they override dupNode().
148: */
149: public Tree dupTree() {
150: Tree newTree = this .dupNode();
151: for (int i = 0; children != null && i < children.size(); i++) {
152: Tree t = (Tree) children.get(i);
153: Tree newSubTree = t.dupTree();
154: newTree.addChild(newSubTree);
155: }
156: return newTree;
157: }
158:
159: /** Print out a whole tree not just a node */
160: public String toStringTree() {
161: if (children == null || children.size() == 0) {
162: return this .toString();
163: }
164: StringBuffer buf = new StringBuffer();
165: if (!isNil()) {
166: buf.append("(");
167: buf.append(this .toString());
168: buf.append(' ');
169: }
170: for (int i = 0; children != null && i < children.size(); i++) {
171: BaseTree t = (BaseTree) children.get(i);
172: if (i > 0) {
173: buf.append(' ');
174: }
175: buf.append(t.toStringTree());
176: }
177: if (!isNil()) {
178: buf.append(")");
179: }
180: return buf.toString();
181: }
182:
183: public int getLine() {
184: return 0;
185: }
186:
187: public int getCharPositionInLine() {
188: return 0;
189: }
190:
191: /** Override to say how a node (not a tree) should look as text */
192: public abstract String toString();
193: }
|