001 // This file is part of AceWiki.
002 // Copyright 2008-2012, AceWiki developers.
003 //
004 // AceWiki is free software: you can redistribute it and/or modify it under the terms of the GNU
005 // Lesser General Public License as published by the Free Software Foundation, either version 3 of
006 // the License, or (at your option) any later version.
007 //
008 // AceWiki is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without
009 // even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
010 // Lesser General Public License for more details.
011 //
012 // You should have received a copy of the GNU Lesser General Public License along with AceWiki. If
013 // not, see http://www.gnu.org/licenses/.
014
015 package ch.uzh.ifi.attempto.chartparser;
016
017 import java.util.ArrayList;
018 import java.util.List;
019
020 /**
021 * This class represents a node of the parse tree. Each node has a category and an annotation
022 * object that are carried over from the edge in the chart parser and originate from the respective
023 * grammar rule. Additionally, each parse node has start and end positions denoting the covered
024 * part of the input text.
025 *
026 * @author Tobias Kuhn
027 */
028 public class ParseTreeNode {
029
030 private final Category category;
031 private final int startPos;
032 private final int endPos;
033 private final Annotation annotation;
034 private final List<ParseTreeNode> children = new ArrayList<ParseTreeNode>();
035
036 /**
037 * Creates a new parse tree node out of the given edge.
038 *
039 * @param edge The edge.
040 */
041 ParseTreeNode(Edge edge) {
042 this.category = edge.getHead();
043 this.startPos = edge.getStartPos();
044 this.endPos = edge.getEndPos();
045 this.annotation = edge.getAnnotation();
046 int pos = edge.getStartPos();
047 for (int i = 0 ; i < edge.getBody().length ; i++) {
048 Edge e = edge.getLinks().get(i);
049 if (e != null) {
050 try {
051 e.getHead().unify(edge.getBody()[i]);
052 children.add(new ParseTreeNode(e));
053 } catch (UnificationFailedException ex) {
054 throw new RuntimeException("Unexpected unification error", ex);
055 }
056 pos = e.getEndPos();
057 } else {
058 children.add(new ParseTreeNode(edge.getBody()[i], pos));
059 }
060 }
061 }
062
063 /**
064 * Creates a new parse tree node (without children) out of the given category.
065 *
066 * @param category The category.
067 */
068 private ParseTreeNode(Category category, int pos) {
069 this.category = category;
070 this.startPos = pos;
071 this.endPos = pos;
072 this.annotation = new Annotation();
073 }
074
075 /**
076 * Returns the category of this node.
077 *
078 * @return The category.
079 */
080 public Category getCategory() {
081 return category;
082 }
083
084 /**
085 * Returns the start position. 0 is the position before the first token, 1 the position after
086 * the first token, 2 the position after the second token, and so on.
087 *
088 * @return The start position.
089 */
090 public int getStartPos() {
091 return startPos;
092 }
093
094 /**
095 * Returns the end position. 0 is the position before the first token, 1 the position after
096 * the first token, 2 the position after the second token, and so on.
097 *
098 * @return The end position.
099 */
100 public int getEndPos() {
101 return endPos;
102 }
103
104 /**
105 * Returns the annotation object of this node.
106 *
107 * @return The annotation object.
108 */
109 public Annotation getAnnotation() {
110 return annotation;
111 }
112
113 /**
114 * Returns the annotation item for the given annotation item name.
115 *
116 * @param name The name of the annotation item.
117 * @return The value of the annotation item.
118 */
119 public Object getAnnotationItem(String name) {
120 return annotation.getItem(name);
121 }
122
123 /**
124 * Returns the children of this node.
125 *
126 * @return The children.
127 */
128 public List<ParseTreeNode> getChildren() {
129 return children;
130 }
131
132 /**
133 * Returns the child at the given position.
134 *
135 * @param i The position.
136 * @return The child.
137 */
138 public ParseTreeNode getChild(int i) {
139 return children.get(i);
140 }
141
142 /**
143 * Returns the list of terminals that are descendants of this node.
144 *
145 * @return The list of terminals.
146 */
147 public List<Terminal> getTerminals() {
148 List<Terminal> terminals = new ArrayList<Terminal>();
149 collectTerminals(terminals);
150 return terminals;
151 }
152
153 private void collectTerminals(List<Terminal> terminals) {
154 if (category instanceof Terminal) {
155 terminals.add((Terminal) category);
156 } else {
157 for (ParseTreeNode n : getChildren()) {
158 n.collectTerminals(terminals);
159 }
160 }
161 }
162
163 }