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.Collection;
019 import java.util.HashMap;
020 import java.util.HashSet;
021 import java.util.List;
022 import java.util.Set;
023
024 /**
025 * This class stands for backward refernces. In contrast to all other categories, backward
026 * references can have multiple feature maps. They have one or more "positive" feature
027 * maps and zero or more "negative" feature maps.
028 *
029 * @author Tobias Kuhn
030 */
031 public class BackrefCategory extends Nonterminal {
032
033 /**
034 * The positive feature maps of the backward reference.
035 */
036 protected List<FeatureMap> posFeatureMaps;
037
038 /**
039 * The negative feature maps of the backward reference.
040 */
041 protected List<FeatureMap> negFeatureMaps;
042
043 /**
044 * Creates a new backward reference. Positive and negative feature maps have to be added by
045 * using the respective methods.
046 */
047 public BackrefCategory() {
048 name = "<";
049 posFeatureMaps = new ArrayList<FeatureMap>();
050 negFeatureMaps = new ArrayList<FeatureMap>();
051 }
052
053 public List<FeatureMap> getPosFeatureMaps() {
054 return posFeatureMaps;
055 }
056
057 public List<FeatureMap> getNegFeatureMaps() {
058 return negFeatureMaps;
059 }
060
061 public void addPosFeatureMap(FeatureMap fm) {
062 posFeatureMaps.add(fm);
063 }
064
065 public void addNegFeatureMap(FeatureMap fm) {
066 negFeatureMaps.add(fm);
067 }
068
069 public void unify(Category c) throws UnificationFailedException {
070 if (!(c instanceof BackrefCategory)) {
071 throw new UnificationFailedException();
072 }
073 BackrefCategory b = (BackrefCategory) c;
074 if (b.posFeatureMaps == null) throw new UnificationFailedException();
075 if (b.posFeatureMaps.size() != posFeatureMaps.size()) throw new UnificationFailedException();
076 for (int i = 0 ; i < posFeatureMaps.size() ; i++) {
077 posFeatureMaps.get(i).unify(b.posFeatureMaps.get(i));
078 }
079 if (b.negFeatureMaps.size() != negFeatureMaps.size()) throw new UnificationFailedException();
080 for (int i = 0 ; i < negFeatureMaps.size() ; i++) {
081 negFeatureMaps.get(i).unify(b.negFeatureMaps.get(i));
082 }
083 }
084
085 public void tryToUnify(Category c) throws UnificationFailedException {
086 if (!(c instanceof BackrefCategory)) {
087 throw new UnificationFailedException();
088 }
089 BackrefCategory b = (BackrefCategory) c;
090 if (b.posFeatureMaps == null) throw new UnificationFailedException();
091 if (b.posFeatureMaps.size() != posFeatureMaps.size()) throw new UnificationFailedException();
092 for (int i = 0 ; i < posFeatureMaps.size() ; i++) {
093 posFeatureMaps.get(i).tryToUnify(b.posFeatureMaps.get(i));
094 }
095 if (b.negFeatureMaps.size() != negFeatureMaps.size()) throw new UnificationFailedException();
096 for (int i = 0 ; i < negFeatureMaps.size() ; i++) {
097 negFeatureMaps.get(i).tryToUnify(b.negFeatureMaps.get(i));
098 }
099 }
100
101 public boolean isSimilar(Category c) {
102 if (!(c instanceof BackrefCategory)) return false;
103 BackrefCategory b = (BackrefCategory) c;
104 if (posFeatureMaps.size() == b.posFeatureMaps.size()) return true;
105 return false;
106 }
107
108 public boolean subsumes(Category c) {
109 if (!(c instanceof BackrefCategory)) return false;
110
111 // Both categories are copied to keep the existing categories untouched:
112 Category category1C = deepCopy();
113 Category category2C = c.deepCopy();
114
115 // Category 1 subsumes category 2 iff 1 unifies with 2 after the skolemization of 2.
116 category2C.skolemize();
117 try {
118 category1C.tryToUnify(category2C);
119 return true;
120 } catch (UnificationFailedException ex) {
121 return false;
122 }
123 }
124
125 public void skolemize() {
126 for (FeatureMap fm : posFeatureMaps) {
127 fm.skolemize();
128 }
129 for (FeatureMap fm : negFeatureMaps) {
130 fm.skolemize();
131 }
132 }
133
134 public Set<String> getFeatureNames() {
135 Set<String> featureNames = new HashSet<String>();
136 for (FeatureMap fm : posFeatureMaps) {
137 featureNames.addAll(fm.getFeatureNames());
138 }
139 for (FeatureMap fm : negFeatureMaps) {
140 featureNames.addAll(fm.getFeatureNames());
141 }
142 return featureNames;
143 }
144
145 public Collection<StringRef> getFeatureValues() {
146 Set<StringRef> featureNames = new HashSet<StringRef>();
147 for (FeatureMap fm : posFeatureMaps) {
148 featureNames.addAll(fm.getFeatureValues());
149 }
150 for (FeatureMap fm : negFeatureMaps) {
151 featureNames.addAll(fm.getFeatureValues());
152 }
153 return featureNames;
154 }
155
156 String getIdentifier(List<Integer> mvars, String[] usedFeatureNames) {
157 String s = getName();
158 s += "+";
159 for (FeatureMap fm : getPosFeatureMaps()) {
160 s += fm.getIdentifier(mvars, usedFeatureNames);
161 }
162 s += "-";
163 for (FeatureMap fm : getNegFeatureMaps()) {
164 s += fm.getIdentifier(mvars, usedFeatureNames);
165 }
166 return s;
167 }
168
169 Category deepCopy(HashMap<Integer, StringObject> stringObjs) {
170 Category c;
171 c = new BackrefCategory();
172 for (FeatureMap fm : posFeatureMaps) {
173 c.addPosFeatureMap(fm.deepCopy(stringObjs));
174 }
175 for (FeatureMap fm : negFeatureMaps) {
176 c.addNegFeatureMap(fm.deepCopy(stringObjs));
177 }
178 return c;
179 }
180
181 protected String getType() {
182 return "bwref";
183 }
184
185 public String toString() {
186 String s = "<+";
187 for (FeatureMap fm : posFeatureMaps) {
188 s += fm.toString();
189 }
190 s += "-";
191 for (FeatureMap fm : negFeatureMaps) {
192 s += fm.toString();
193 }
194 return s;
195 }
196
197 }