001 package net.sf.cpsolver.exam.model;
002
003 import java.util.Enumeration;
004 import java.util.HashSet;
005 import java.util.Iterator;
006 import java.util.Set;
007
008 import net.sf.cpsolver.ifs.model.Constraint;
009 import net.sf.cpsolver.ifs.model.Value;
010
011 /**
012 * Distribution binary constraint.
013 * <br><br>
014 * The following binary distribution constraints are implemented
015 * <ul>
016 * <li> Same room
017 * <li> Different room
018 * <li> Same period
019 * <li> Different period
020 * <li> Precedence
021 * </ul>
022 * <br><br>
023 *
024 * @version
025 * ExamTT 1.1 (Examination Timetabling)<br>
026 * Copyright (C) 2008 Tomáš Müller<br>
027 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
028 * Lazenska 391, 76314 Zlin, Czech Republic<br>
029 * <br>
030 * This library is free software; you can redistribute it and/or
031 * modify it under the terms of the GNU Lesser General Public
032 * License as published by the Free Software Foundation; either
033 * version 2.1 of the License, or (at your option) any later version.
034 * <br><br>
035 * This library is distributed in the hope that it will be useful,
036 * but WITHOUT ANY WARRANTY; without even the implied warranty of
037 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
038 * Lesser General Public License for more details.
039 * <br><br>
040 * You should have received a copy of the GNU Lesser General Public
041 * License along with this library; if not, write to the Free Software
042 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
043 */
044 public class ExamDistributionConstraint extends Constraint {
045 /** Same room constraint type */
046 public static final int sDistSameRoom = 0;
047 /** Different room constraint type */
048 public static final int sDistDifferentRoom = 1;
049 /** Same period constraint type */
050 public static final int sDistSamePeriod = 2;
051 /** Different period constraint type */
052 public static final int sDistDifferentPeriod = 3;
053 /** Precedence constraint type */
054 public static final int sDistPrecedence = 4;
055 /** Precedence constraint type (reverse order) */
056 public static final int sDistPrecedenceRev = 5;
057 /** Distribution type name */
058 public static final String[] sDistType = new String[] {
059 "same-room",
060 "different-room",
061 "same-period",
062 "different-period",
063 "precedence",
064 "precedence-rev"
065 };
066
067 private int iType = -1;
068 private boolean iHard = true;
069 private int iWeight = 0;
070
071 /**
072 * Constructor
073 * @param id constraint unique id
074 * @param type constraint type
075 * @param hard true if the constraint is hard (cannot be violated)
076 * @param weight if not hard, penalty for violation
077 */
078 public ExamDistributionConstraint(long id, int type, boolean hard, int weight) {
079 iId = id;
080 iType = type;
081 iHard = hard;
082 iWeight = weight;
083 }
084
085 /**
086 * Constructor
087 * @param id constraint unique id
088 * @param type constraint type (EX_SAME_PREF, EX_SAME_ROOM, or EX_PRECEDENCE)
089 * @param pref preference (R/P for required/prohibited, or -2, -1, 0, 1, 2 for preference (from preferred to discouraged))
090 */
091 public ExamDistributionConstraint(long id, String type, String pref) {
092 iId = id;
093 boolean neg = "P".equals(pref) || "2".equals(pref) || "1".equals(pref);
094 if ("EX_SAME_PER".equals(type)) {
095 iType = (neg?sDistDifferentPeriod:sDistSamePeriod);
096 } else if ("EX_SAME_ROOM".equals(type)) {
097 iType = (neg?sDistDifferentRoom:sDistSameRoom);
098 } else if ("EX_PRECEDENCE".equals(type)) {
099 iType = (neg?sDistPrecedenceRev:sDistPrecedence);
100 } else
101 throw new RuntimeException("Unkown type "+type);
102 if ("P".equals(pref) || "R".equals(pref))
103 iHard = true;
104 else {
105 iHard = false;
106 iWeight = Integer.parseInt(pref) * Integer.parseInt(pref);
107 }
108 }
109
110 /**
111 * Constructor
112 * @param id constraint unique id
113 * @param type constraint type name
114 */
115 public ExamDistributionConstraint(long id, String type, boolean hard, int weight) {
116 iId = id;
117 for (int i=0;i<sDistType.length;i++)
118 if (sDistType[i].equals(type)) iType = i;
119 if (iType<0)
120 throw new RuntimeException("Unknown type '"+type+"'.");
121 iHard = hard;
122 iWeight = weight;
123 }
124
125 /**
126 * True if hard (must be satisfied), false for soft (should be satisfied)
127 */
128 public boolean isHard() { return iHard; }
129
130 /**
131 * If not hard, penalty for violation
132 */
133 public int getWeight() { return iWeight; }
134
135 /**
136 * Constraint type
137 */
138 public int getType() {
139 return iType;
140 }
141
142 /**
143 * Constraint type name
144 */
145 public String getTypeString() {
146 return sDistType[iType];
147 }
148
149 /**
150 * String representation -- constraint type name (exam 1, exam 2)
151 */
152 public String toString() {
153 return getTypeString()+" ("+variables()+")";
154 }
155
156 /**
157 * Compute conflicts -- there is a conflict if the other variable is
158 * assigned and {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is false
159 */
160 public void computeConflicts(Value value, Set conflicts) {
161 boolean before = true;
162 ExamPlacement givenPlacement = (ExamPlacement)value;
163 for (Enumeration e=variables().elements();e.hasMoreElements();) {
164 Exam exam = (Exam)e.nextElement();
165 if (exam.equals(value.variable())) {
166 before = false; continue;
167 }
168 ExamPlacement placement = (ExamPlacement)exam.getAssignment();
169 if (placement==null) continue;
170 if (!check(before?placement:givenPlacement, before?givenPlacement:placement))
171 conflicts.add(placement);
172 }
173 }
174
175 /**
176 * Check for conflict -- there is a conflict if the other variable is
177 * assigned and {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is false
178 */
179 public boolean inConflict(Value value) {
180 boolean before = true;
181 ExamPlacement givenPlacement = (ExamPlacement)value;
182 for (Enumeration e=variables().elements();e.hasMoreElements();) {
183 Exam exam = (Exam)e.nextElement();
184 if (exam.equals(value.variable())) {
185 before = false; continue;
186 }
187 ExamPlacement placement = (ExamPlacement)exam.getAssignment();
188 if (placement==null) continue;
189 if (!check(before?placement:givenPlacement, before?givenPlacement:placement)) return true;
190 }
191 return false;
192 }
193
194 /**
195 * Consistency check -- {@link ExamDistributionConstraint#check(ExamPlacement, ExamPlacement)} is called
196 */
197 public boolean isConsistent(Value value1, Value value2) {
198 ExamPlacement first = (ExamPlacement)value1;
199 ExamPlacement second = (ExamPlacement)value2;
200 boolean before = (variables().indexOf(value1.variable())<variables().indexOf(value2.variable()));
201 return check(before?first:second, before?second:first);
202 }
203
204 /**
205 * Check assignments of the given exams
206 * @param first assignment of the first exam
207 * @param second assignment of the second exam
208 * @return true, if the constraint is satisfied
209 */
210 public boolean check(ExamPlacement first, ExamPlacement second) {
211 switch (getType()) {
212 case sDistPrecedence :
213 return first.getPeriod().getIndex()<second.getPeriod().getIndex();
214 case sDistPrecedenceRev :
215 return first.getPeriod().getIndex()>second.getPeriod().getIndex();
216 case sDistSamePeriod :
217 return first.getPeriod().getIndex()==second.getPeriod().getIndex();
218 case sDistDifferentPeriod :
219 return first.getPeriod().getIndex()!=second.getPeriod().getIndex();
220 case sDistSameRoom :
221 return first.getRoomPlacements().containsAll(second.getRoomPlacements()) || second.getRoomPlacements().containsAll(first.getRoomPlacements());
222 case sDistDifferentRoom :
223 for (Iterator i=first.getRoomPlacements().iterator();i.hasNext();)
224 if (second.getRoomPlacements().contains(i.next())) return false;
225 return true;
226 default :
227 return false;
228 }
229 }
230
231 /**
232 * Compare with other constraint for equality
233 */
234 public boolean equals(Object o) {
235 if (o==null || !(o instanceof ExamDistributionConstraint)) return false;
236 ExamDistributionConstraint c = (ExamDistributionConstraint)o;
237 return getType()==c.getType() && getId()==c.getId();
238 }
239
240 /**
241 * Return true if this is hard constraint or this is a soft constraint without any violation
242 */
243 public boolean isSatisfied() {
244 return isSatisfied(null);
245 }
246
247 /**
248 * Return true if this is hard constraint or this is a soft constraint without any violation
249 * @param p exam assignment to be made
250 */
251 public boolean isSatisfied(ExamPlacement p) {
252 if (isHard()) return true;
253 switch (getType()) {
254 case sDistPrecedence :
255 ExamPeriod last = null;
256 for (Enumeration e=variables().elements();e.hasMoreElements();) {
257 Exam exam = (Exam)e.nextElement();
258 ExamPlacement placement = (p!=null && exam.equals(p.variable())?p:(ExamPlacement)exam.getAssignment());
259 if (placement==null) continue;
260 if (last==null || last.getIndex()<placement.getPeriod().getIndex())
261 last = placement.getPeriod();
262 else
263 return false;
264 }
265 return true;
266 case sDistPrecedenceRev :
267 last = null;
268 for (Enumeration e=variables().elements();e.hasMoreElements();) {
269 Exam exam = (Exam)e.nextElement();
270 ExamPlacement placement = (p!=null && exam.equals(p.variable())?p:(ExamPlacement)exam.getAssignment());
271 if (placement==null) continue;
272 if (last==null || last.getIndex()>placement.getPeriod().getIndex())
273 last = placement.getPeriod();
274 else
275 return false;
276 }
277 return true;
278 case sDistSamePeriod :
279 ExamPeriod period = null;
280 for (Enumeration e=variables().elements();e.hasMoreElements();) {
281 Exam exam = (Exam)e.nextElement();
282 ExamPlacement placement = (p!=null && exam.equals(p.variable())?p:(ExamPlacement)exam.getAssignment());
283 if (placement==null) continue;
284 if (period==null)
285 period = placement.getPeriod();
286 else if (period.getIndex()!=placement.getPeriod().getIndex())
287 return false;
288 }
289 return true;
290 case sDistDifferentPeriod :
291 HashSet periods = new HashSet();
292 for (Enumeration e=variables().elements();e.hasMoreElements();) {
293 Exam exam = (Exam)e.nextElement();
294 ExamPlacement placement = (p!=null && exam.equals(p.variable())?p:(ExamPlacement)exam.getAssignment());
295 if (placement==null) continue;
296 if (!periods.add(placement.getPeriod())) return false;
297 }
298 return true;
299 case sDistSameRoom :
300 Set rooms = null;
301 for (Enumeration e=variables().elements();e.hasMoreElements();) {
302 Exam exam = (Exam)e.nextElement();
303 ExamPlacement placement = (p!=null && exam.equals(p.variable())?p:(ExamPlacement)exam.getAssignment());
304 if (placement==null) continue;
305 if (rooms==null)
306 rooms = placement.getRoomPlacements();
307 else if (!rooms.containsAll(placement.getRoomPlacements()) || !placement.getRoomPlacements().containsAll(rooms))
308 return false;
309 }
310 return true;
311 case sDistDifferentRoom :
312 HashSet allRooms = new HashSet();
313 for (Enumeration e=variables().elements();e.hasMoreElements();) {
314 Exam exam = (Exam)e.nextElement();
315 ExamPlacement placement = (p!=null && exam.equals(p.variable())?p:(ExamPlacement)exam.getAssignment());
316 if (placement==null) continue;
317 for (Iterator i=placement.getRoomPlacements().iterator();i.hasNext();) {
318 ExamRoomPlacement room = (ExamRoomPlacement)i.next();
319 if (!allRooms.add(room)) return false;
320 }
321 }
322 return true;
323 default :
324 return false;
325 }
326 }
327
328
329 boolean iIsSatisfied = true;
330 public void assigned(long iteration, Value value) {
331 super.assigned(iteration, value);
332 if (!isHard() && iIsSatisfied!=isSatisfied()) {
333 iIsSatisfied = !iIsSatisfied;
334 ((ExamModel)value.variable().getModel()).addDistributionPenalty(iIsSatisfied?-getWeight():getWeight());
335 }
336 }
337
338 public void unassigned(long iteration, Value value) {
339 super.unassigned(iteration, value);
340 if (!isHard() && iIsSatisfied!=isSatisfied()) {
341 iIsSatisfied = !iIsSatisfied;
342 ((ExamModel)value.variable().getModel()).addDistributionPenalty(iIsSatisfied?-getWeight():getWeight());
343 }
344 }
345
346 /** True if the constraint is related to rooms */
347 public boolean isRoomRelated() {
348 return iType==sDistSameRoom || iType==sDistDifferentRoom;
349 }
350
351 /** True if the constraint is related to periods */
352 public boolean isPeriodRelated() {
353 return !isRoomRelated();
354 }
355 }