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