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