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