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.Map;
021 import java.util.Set;
022 import java.util.TreeSet;
023
024 /**
025 * This class represents a set of features consisting of name/value pairs.
026 *
027 * @author Tobias Kuhn
028 */
029 public class FeatureMap {
030
031 /**
032 * This counter is used for skolemization:
033 */
034 private static int skNumber = 0;
035
036 private Map<String, StringRef> features = new HashMap<String, StringRef>();
037
038 /**
039 * Creates an empty feature map.
040 */
041 public FeatureMap() {
042 }
043
044 /**
045 * Sets a feature. If the feature is already present, the feature value is overridden and not
046 * unified.
047 *
048 * @param featureName The name of the feature to set.
049 * @param featureValue The feature value.
050 */
051 public void setFeature(String featureName, StringRef featureValue) {
052 features.put(featureName, featureValue);
053 }
054
055 /**
056 * Returns a feature value.
057 *
058 * @param featureName The name of the feature.
059 * @return The value of the feature.
060 */
061 public StringRef getFeature(String featureName) {
062 StringRef featureValue = features.get(featureName);
063 if (featureValue == null) {
064 featureValue = new StringRef();
065 features.put(featureName, featureValue);
066 }
067 return featureValue;
068 }
069
070 /**
071 * Unifies this feature map with another feature map. Two feature maps can unify if and only if
072 * all values of common feature name unify. If the unification fails, a
073 * UnificationFailedException is thrown. In this case, the two feature maps remain partly unified,
074 * i.e. no backtracking is done. Thus, this operation should be perfomed only if it is certain that
075 * the unification succeeds, or if the operation is performed on copies of objects that are not
076 * used anymore afterwards.
077 *
078 * @param featureMap The feature map to be unified with this feature map.
079 * @throws UnificationFailedException If unification fails.
080 */
081 public void unify(FeatureMap featureMap) throws UnificationFailedException {
082 for (String f : features.keySet()) {
083 getFeature(f).unify(featureMap.getFeature(f));
084 }
085 for (String f : featureMap.features.keySet()) {
086 getFeature(f).unify(featureMap.getFeature(f));
087 }
088 }
089
090 /**
091 * Tries to unify this feature map with another feature map. If unification is not possible, an exception
092 * is thrown. In the case unification would be possible, the unification is not performed completely.
093 * In any case the two feature maps remain in an unconsistent state afterwards. Thus, this operation should
094 * be performed only on copies of objects that are not used anymore afterwards.
095 *
096 * @param featureMap The feature map to be unified with this feature map.
097 * @throws UnificationFailedException If unification fails.
098 */
099 public void tryToUnify(FeatureMap featureMap) throws UnificationFailedException {
100 if (featureMap == null) {
101 throw new UnificationFailedException();
102 }
103 for (String f : features.keySet()) {
104 features.get(f).unify(featureMap.getFeature(f));
105 }
106 }
107
108 /**
109 * This method detects whether this feature map can unify with the given feature map. Neither of the two
110 * feature maps are changed.
111 *
112 * @param featureMap The feature map for the unification check.
113 * @return true if the two feature map can unify.
114 */
115 public boolean canUnify(FeatureMap featureMap) {
116 if (!isSimilar(featureMap)) return false;
117 FeatureMap thisC = deepCopy();
118 FeatureMap otherC = featureMap.deepCopy();
119 try {
120 thisC.tryToUnify(otherC);
121 } catch (UnificationFailedException ex) {
122 return false;
123 }
124 return true;
125 }
126
127 /**
128 * Skolemizes the feature values of this feature map.
129 */
130 public void skolemize() {
131 for (String feature : features.keySet()) {
132 StringRef s = features.get(feature);
133 if (s.getString() == null) {
134 try {
135 s.unify(new StringRef("$SK" + skNumber++));
136 } catch (UnificationFailedException ex) {}
137 }
138 }
139 }
140
141 /**
142 * This methods checks whether two feature maps are similar. Two feature maps are similar
143 * if and only if they do not share a feature with the same name but with values that do
144 * not unify locally (i.e. without considering the unifications entailed by other features).
145 *
146 * @param fm The category for which similarity with this category should be checked.
147 * @return true if the two categories are similar.
148 */
149 public boolean isSimilar(FeatureMap fm) {
150 if (fm == null) return false;
151 for (String v : features.keySet()) {
152 String s1 = features.get(v).getString();
153 String s2 = null;
154 StringRef sr2 = fm.features.get(v);
155 if (sr2 != null) s2 = sr2.getString();
156 if (s1 != null && s2 != null && !s1.equals(s2)) return false;
157 }
158 return true;
159 }
160
161 /**
162 * Creates a deep copy of this feature map.
163 *
164 * @return A deep copy.
165 */
166 public FeatureMap deepCopy() {
167 return deepCopy(new HashMap<Integer, StringObject>());
168 }
169
170 /**
171 * Creates a deep copy of this feature map using the given string objects. This method is
172 * usually called form another deepCopy-method.
173 *
174 * @param stringObjs The string objects to be used.
175 * @return A deep copy.
176 */
177 FeatureMap deepCopy(HashMap<Integer, StringObject> stringObjs) {
178 FeatureMap fm = new FeatureMap();
179 for (String feature : features.keySet()) {
180 StringRef s = features.get(feature);
181 StringObject se = stringObjs.get(s.getID());
182 if (se != null) {
183 fm.setFeature(feature, se.newStringRef());
184 } else {
185 StringRef sr = new StringRef(s.getString());
186 fm.setFeature(feature, sr);
187 stringObjs.put(s.getID(), sr.getStringObject());
188 }
189 }
190 return fm;
191 }
192
193 /**
194 * Returns the used feature names.
195 *
196 * @return The used feature names.
197 */
198 public Set<String> getFeatureNames() {
199 return features.keySet();
200 }
201
202 /**
203 * Returns the used feature values.
204 *
205 * @return The used feature values.
206 */
207 public Collection<StringRef> getFeatureValues() {
208 return features.values();
209 }
210
211 String getIdentifier(List<Integer> mvars, String[] usedFeatureNames) {
212 String s = "(";
213 int i = 0;
214 for (String n : usedFeatureNames) {
215 i++;
216 if (!getFeatureNames().contains(n)) continue;
217 StringRef v = getFeature(n);
218 if (v.getString() == null) {
219 if (mvars.contains(v.getID())) {
220 s += i + ":" + mvars.indexOf(v.getID()) + ",";
221 }
222 } else {
223 s += i + ":" + v.getString() + ",";
224 }
225 }
226 return s + ")";
227 }
228
229 public String toString() {
230 String s = "";
231 Set<String> featureKeys = features.keySet();
232 if (featureKeys.size() > 0) s += "(";
233 for (String feature : new TreeSet<String>(features.keySet())) {
234 // traverse the feature names in alphabetical order
235 StringRef sr = features.get(feature);
236 s += feature + ":";
237 if (sr.getString() == null) {
238 s += sr.getID();
239 } else {
240 s += sr.getString();
241 }
242 s += ",";
243 }
244 if (featureKeys.size() > 0) {
245 s = s.substring(0, s.length()-1) + ")";
246 }
247 return s;
248 }
249
250 }