001 // This file is part of the Attempto Java Packages. 002 // Copyright 2008-2009, Attempto Group, University of Zurich (see http://attempto.ifi.uzh.ch). 003 // 004 // The Attempto Java Packages is free software: you can redistribute it and/or modify it under the 005 // terms of the GNU Lesser General Public License as published by the Free Software Foundation, 006 // either version 3 of the License, or (at your option) any later version. 007 // 008 // The Attempto Java Packages is distributed in the hope that it will be useful, but WITHOUT ANY 009 // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 010 // PURPOSE. See the GNU Lesser General Public License for more details. 011 // 012 // You should have received a copy of the GNU Lesser General Public License along with the Attempto 013 // Java Packages. If not, see http://www.gnu.org/licenses/. 014 015 package ch.uzh.ifi.attempto.chartparser; 016 017 import java.util.HashMap; 018 import java.util.Set; 019 import java.util.TreeSet; 020 021 /** 022 * This class represents a set of features consisting of name/value pairs. 023 * 024 * @author Tobias Kuhn 025 */ 026 public class FeatureMap { 027 028 // This counter is used for skolemization: 029 private static int skNumber = 0; 030 031 private HashMap<String, StringRef> features = new HashMap<String, StringRef>(); 032 033 /** 034 * Creates an empty feature map. 035 */ 036 public FeatureMap() { 037 } 038 039 /** 040 * Sets a feature. 041 * 042 * @param featureName The feature name 043 * @param featureValue 044 */ 045 public void setFeature(String featureName, StringRef featureValue) { 046 features.put(featureName, featureValue); 047 } 048 049 /** 050 * Returns a feature value. 051 * 052 * @param featureName The name of the feature. 053 * @return The value of the feature. 054 */ 055 public StringRef getFeature(String featureName) { 056 StringRef featureValue = features.get(featureName); 057 if (featureValue == null) { 058 featureValue = new StringRef(); 059 features.put(featureName, featureValue); 060 } 061 return featureValue; 062 } 063 064 /** 065 * Unifies this feature map with another feature map. Two feature maps can unify if and only if 066 * they have no features with conflicting values. If the unification fails, a 067 * UnificationFailedException is thrown. In this case, the two feature maps remain partly unified, 068 * i.e. no backtracking is done. Thus, this operation should be perfomed only if it is certain that 069 * the unification succeeds, or if the operation is performed on copies of objects that are not 070 * used anymore afterwards. 071 * 072 * @param featureMap The feature map to be unified with this feature map. 073 * @throws UnificationFailedException If unification fails. 074 */ 075 public void unify(FeatureMap featureMap) throws UnificationFailedException { 076 for (String f : features.keySet()) { 077 getFeature(f).unify(featureMap.getFeature(f)); 078 } 079 for (String f : featureMap.features.keySet()) { 080 getFeature(f).unify(featureMap.getFeature(f)); 081 } 082 } 083 084 /** 085 * Tries to unify this feature map with another feature map. If unification is not possible, an exception 086 * is thrown. In the case unification would be possible, the unification is not performed completely. 087 * In any case the two feature maps remain in an unconsistent state afterwards. Thus, this operation should 088 * be performed only on copies of objects that are not used anymore afterwards. 089 * 090 * @param featureMap The feature map to be unified with this feature map. 091 * @throws UnificationFailedException If unification fails. 092 */ 093 public void tryToUnify(FeatureMap featureMap) throws UnificationFailedException { 094 for (String f : features.keySet()) { 095 features.get(f).unify(featureMap.getFeature(f)); 096 } 097 } 098 099 /** 100 * This method detects whether this feature map can unify with the given feature map. Neither of the two 101 * feature maps are changed. 102 * 103 * @param featureMap The feature map for the unification check. 104 * @return true if the two feature map can unify. 105 */ 106 public boolean canUnify(FeatureMap featureMap) { 107 if (!isSimilar(featureMap)) return false; 108 FeatureMap thisC = deepCopy(); 109 FeatureMap otherC = featureMap.deepCopy(); 110 try { 111 thisC.tryToUnify(otherC); 112 } catch (UnificationFailedException ex) { 113 return false; 114 } 115 return true; 116 } 117 118 /** 119 * Skolemizes the feature values of this feature map. 120 */ 121 public void skolemize() { 122 for (String feature : features.keySet()) { 123 StringRef s = features.get(feature); 124 if (s.getString() == null) { 125 try { 126 s.unify(new StringRef("$SK" + skNumber++)); 127 } catch (UnificationFailedException ex) {} 128 } 129 } 130 } 131 132 /** 133 * This methods checks whether two feature maps are similar. Two feature maps are similar 134 * if and only if they don't share a feature with the same name but with values that do 135 * not unify locally. 136 * 137 * @param fm The category for which similarity with this category should be checked. 138 * @return true if the two categories are similar. 139 */ 140 public boolean isSimilar(FeatureMap fm) { 141 for (String v : features.keySet()) { 142 String s1 = features.get(v).getString(); 143 String s2 = null; 144 StringRef sr2 = fm.features.get(v); 145 if (sr2 != null) s2 = sr2.getString(); 146 if (s1 != null && s2 != null && !s1.equals(s2)) return false; 147 } 148 return true; 149 } 150 151 /** 152 * Creates a deep copy of this feature map. 153 * 154 * @return A deep copy. 155 */ 156 public FeatureMap deepCopy() { 157 return deepCopy(new HashMap<Integer, StringEntity>()); 158 } 159 160 /** 161 * Creates a deep copy of this feature map using the given string entities. This method is 162 * usually called form another deepCopy-method. 163 * 164 * @param entities The string entities to be used. 165 * @return A deep copy. 166 */ 167 FeatureMap deepCopy(HashMap<Integer, StringEntity> entities) { 168 FeatureMap fm = new FeatureMap(); 169 for (String feature : features.keySet()) { 170 StringRef s = features.get(feature); 171 StringEntity se = entities.get(s.getID()); 172 if (se != null) { 173 fm.setFeature(feature, se.newStringRef()); 174 } else { 175 StringRef sr = new StringRef(s.getString()); 176 fm.setFeature(feature, sr); 177 entities.put(s.getID(), sr.getStringEntity()); 178 } 179 } 180 return fm; 181 } 182 183 public String toString() { 184 String s = ""; 185 Set<String> featureKeys = features.keySet(); 186 if (featureKeys.size() > 0) s += "("; 187 for (String feature : new TreeSet<String>(features.keySet())) { 188 // traverse the feature names in alphabetical order 189 StringRef sr = features.get(feature); 190 s += feature + ":"; 191 if (sr.getString() == null) { 192 s += sr.getID(); 193 } else { 194 s += sr.getString(); 195 } 196 s += ","; 197 } 198 if (featureKeys.size() > 0) { 199 s = s.substring(0, s.length()-1) + ")"; 200 } 201 return s; 202 } 203 204 }