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.Collection;
018 import java.util.HashMap;
019 import java.util.List;
020 import java.util.Set;
021
022 import org.apache.commons.lang.ArrayUtils;
023
024 /**
025 * This class represents a grammatical category.
026 *
027 * @author Tobias Kuhn
028 */
029 public abstract class Category {
030
031 /**
032 * This static array contains all category names that denote special categories. These special
033 * category names are ">" and ">>" for forward references, "<" and "/<" for backward references,
034 * "//" for scope openers, and "#" for position operators.
035 */
036 public static final String[] specialCategories = new String[] {">", ">>", "<", "/<", "//", "#"};
037
038 /**
039 * The name of the category.
040 */
041 protected String name;
042
043 /**
044 * The feature map of the category. Backward references do not use this field, since they can
045 * have multiple feature maps.
046 */
047 protected FeatureMap featureMap;
048
049 /**
050 * This method returns the type of the category. For example, "term" is returned for terminal
051 * categories and "nonterm" for non-terminal ones.
052 *
053 * @return The type of the category.
054 */
055 protected abstract String getType();
056
057 /**
058 * Returns the name of the category.
059 *
060 * @return The name of the category.
061 */
062 public String getName() {
063 return name;
064 }
065
066 /**
067 * Returns true if this category is a special category. Special categories are references, scope
068 * openers, and position operators.
069 *
070 * @return true if this category is a special category.
071 */
072 public boolean isSpecialCategory() {
073 return ArrayUtils.contains(specialCategories, name);
074 }
075
076 /**
077 * Returns the map of features of this category. It returns null in the case of backward
078 * references, where the methods for positive and negative feature maps have to be used.
079 *
080 * @return The feature map.
081 */
082 public FeatureMap getFeatureMap() {
083 return featureMap;
084 }
085
086 /**
087 * This method returns the list of positive feature maps for backward references, or null
088 * for all other categories.
089 *
090 * @return The list of positive feature maps in the case of backward references.
091 */
092 public List<FeatureMap> getPosFeatureMaps() {
093 return null;
094 }
095
096 /**
097 * This method returns the list of negative feature maps for backward references, or null
098 * for all other categories.
099 *
100 * @return The list of negative feature maps in the case of backward references.
101 */
102 public List<FeatureMap> getNegFeatureMaps() {
103 return null;
104 }
105
106 /**
107 * Adds a positive feature map in the case of backward references, or does nothing for all
108 * other categories.
109 *
110 * @param fm The positive feature map to be added.
111 */
112 public void addPosFeatureMap(FeatureMap fm) {
113 }
114
115 /**
116 * Adds a negative feature map in the case of backward references, or does nothing for all
117 * other categories.
118 *
119 * @param fm The negative feature map to be added.
120 */
121 public void addNegFeatureMap(FeatureMap fm) {
122 }
123
124 /**
125 * Sets a feature. This method cannot be used for backward references, which can have more than
126 * one feature map.
127 *
128 * @param featureName The feature name
129 * @param featureValue The string reference that points to the value of the feature.
130 */
131 public void setFeature(String featureName, StringRef featureValue) {
132 featureMap.setFeature(featureName, featureValue);
133 }
134
135 /**
136 * Sets a feature. This method cannot be used for backward references, which can have more than
137 * one feature map.
138 *
139 * @param featureName The feature name
140 * @param featureValue The value of the feature.
141 */
142 public void setFeature(String featureName, String featureValue) {
143 featureMap.setFeature(featureName, new StringRef(featureValue));
144 }
145
146 /**
147 * Returns a feature value. This method cannot be used for backward references, which can have
148 * more than one feature map.
149 *
150 * @param featureName The name of the feature.
151 * @return The value of the feature.
152 */
153 public StringRef getFeature(String featureName) {
154 return featureMap.getFeature(featureName);
155 }
156
157 /**
158 * Unifies this category with another category. Two categories can unify if and only if they have
159 * the same names and the same types and they have no features with conflicting values. If the
160 * unification fails, a UnificationFailedException is thrown. In this case, the two categories
161 * remain partly unified, i.e. no backtracking is done. Thus, this operation should be perfomed
162 * only if it is certain that the unification succeeds, or if the operation is performed on
163 * copies of objects that are not used anymore afterwards.
164 *
165 * @param c The category to be unified with this category.
166 * @throws UnificationFailedException If unification fails.
167 */
168 public void unify(Category c) throws UnificationFailedException {
169 if (!name.equals(c.name) || !getType().equals(c.getType())) {
170 throw new UnificationFailedException();
171 }
172 featureMap.unify(c.featureMap);
173 }
174
175 /**
176 * Tries to unify this category with another category. If unification is not possible, an exception
177 * is thrown. In the case unification would be possible, the unification is not performed completely.
178 * In any case the two categories remain in an unconsistent state afterwards. Thus, this operation
179 * should be performed only on copies of objects that are not used anymore afterwards.
180 *
181 * @param c The category to be unified with this category.
182 * @throws UnificationFailedException If unification fails.
183 */
184 public void tryToUnify(Category c) throws UnificationFailedException {
185 if (!name.equals(c.name) || !getType().equals(c.getType())) {
186 throw new UnificationFailedException();
187 }
188 featureMap.tryToUnify(c.featureMap);
189 }
190
191 /**
192 * This method detects whether this category can unify with the given category. Neither of the two
193 * categories are changed.
194 *
195 * @param category The category for the unification check.
196 * @return true if the two categories can unify.
197 */
198 public boolean canUnify(Category category) {
199 if (!isSimilar(category)) return false;
200 Category thisC = deepCopy();
201 Category otherC = category.deepCopy();
202 try {
203 thisC.tryToUnify(otherC);
204 } catch (UnificationFailedException ex) {
205 return false;
206 }
207 return true;
208 }
209
210 /**
211 * This methods checks whether two categories are similar. Two categories are similar if and
212 * only if the categories have the same name and the same type and no feature with the same
213 * name is present in both categories with values that do not unify locally. Two categories
214 * that are unifiable are always similar, but not necessarily vice versa. This check for
215 * similarity is computationally less expensive than the check for unification.
216 *
217 * @param c The category for which similarity with this category should be checked.
218 * @return true if the two categories are similar.
219 */
220 public boolean isSimilar(Category c) {
221 if (!name.equals(c.name) || !getType().equals(c.getType())) return false;
222 if (c.featureMap == null) return false;
223 if (featureMap.getFeatureNames().isEmpty()) return true;
224 if (c.featureMap.getFeatureNames().isEmpty()) return true;
225 return featureMap.isSimilar(c.featureMap);
226 }
227
228 /**
229 * This method returns true if this category subsumes (in other words "is more general than")
230 * the given category, or false otherwise.
231 *
232 * @param c The category for which it is checked whether this category subsumes it.
233 * @return true if this category subsumes the given category.
234 */
235 public boolean subsumes(Category c) {
236 if (!name.equals(c.name) || !getType().equals(c.getType())) return false;
237
238 // Some quick checks before doing the expensive copying of the categories:
239 if (c.featureMap == null) return false;
240 if (featureMap.getFeatureNames().isEmpty()) return true;
241 if (!featureMap.isSimilar(c.featureMap)) return false;
242
243 // Both categories are copied to keep the existing categories untouched:
244 Category category1C = deepCopy();
245 Category category2C = c.deepCopy();
246
247 // Category 1 subsumes category 2 iff 1 unifies with 2 after the skolemization of 2.
248 category2C.skolemize();
249 try {
250 category1C.tryToUnify(category2C);
251 return true;
252 } catch (UnificationFailedException ex) {
253 return false;
254 }
255 }
256
257 /**
258 * Skolemizes the feature values of this category.
259 */
260 public void skolemize() {
261 featureMap.skolemize();
262 }
263
264 /**
265 * Returns the used feature names within the feature map.
266 *
267 * @return The used feature names.
268 */
269 public Set<String> getFeatureNames() {
270 return featureMap.getFeatureNames();
271 }
272
273 /**
274 * Returns the used feature values within the feature map.
275 *
276 * @return The used feature values.
277 */
278 public Collection<StringRef> getFeatureValues() {
279 return featureMap.getFeatureValues();
280 }
281
282 void collectVars(List<Integer> vars, List<Integer> mvars) {
283 if (this instanceof Terminal) return;
284 Collection<StringRef> fvalues = getFeatureValues();
285 if (fvalues == null) return;
286 for (StringRef v : fvalues) {
287 if (v.getString() == null) {
288 int id = v.getID();
289 if (vars.contains(id)) {
290 if (!mvars.contains(id)) {
291 mvars.add(id);
292 }
293 } else {
294 vars.add(id);
295 }
296 }
297 }
298 }
299
300 String getIdentifier(List<Integer> mvars, String[] usedFeatureNames) {
301 return getName() + featureMap.getIdentifier(mvars, usedFeatureNames);
302 }
303
304 /**
305 * Creates a deep copy of this category.
306 *
307 * @return A deep copy.
308 */
309 public Category deepCopy() {
310 return deepCopy(new HashMap<Integer, StringObject>());
311 }
312
313 /**
314 * Creates a deep copy of this category using the given string objects. This method is
315 * usually called form another deepCopy-method.
316 *
317 * @param stringObjs The string objects to be used.
318 * @return A deep copy.
319 */
320 Category deepCopy(HashMap<Integer, StringObject> stringObjs) {
321 Category c;
322 if (this instanceof Terminal) {
323 c = new Terminal(name);
324 } else if (this instanceof Preterminal) {
325 c = new Preterminal(name);
326 } else if (this instanceof Nonterminal) {
327 c = new Nonterminal(name);
328 } else {
329 throw new RuntimeException("Unknown category type: " + this.getClass().toString());
330 }
331 c.featureMap = featureMap.deepCopy(stringObjs);
332 return c;
333 }
334
335 public boolean equals(Object obj) {
336 if (!(obj instanceof Category)) return false;
337 if (!getType().equals(((Category) obj).getType())) return false;
338 return toString().equals(obj.toString());
339 }
340
341 public abstract String toString();
342
343 }