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