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    }