001package org.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.BitSet; 005import java.util.HashSet; 006import java.util.HashMap; 007import java.util.Iterator; 008import java.util.List; 009import java.util.Set; 010import java.util.regex.Matcher; 011import java.util.regex.Pattern; 012 013import org.cpsolver.coursett.Constants; 014import org.cpsolver.coursett.criteria.DistributionPreferences; 015import org.cpsolver.coursett.model.Lecture; 016import org.cpsolver.coursett.model.Placement; 017import org.cpsolver.coursett.model.TimeLocation; 018import org.cpsolver.coursett.model.TimetableModel; 019import org.cpsolver.ifs.assignment.Assignment; 020import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 021import org.cpsolver.ifs.assignment.context.ConstraintWithContext; 022import org.cpsolver.ifs.model.Constraint; 023import org.cpsolver.ifs.model.GlobalConstraint; 024import org.cpsolver.ifs.model.Model; 025import org.cpsolver.ifs.model.WeakeningConstraint; 026import org.cpsolver.ifs.util.DataProperties; 027import org.cpsolver.ifs.util.DistanceMetric; 028import org.cpsolver.ifs.util.ToolBox; 029 030 031/** 032 * Group constraint. <br> 033 * This constraint expresses relations between several classes, e.g., that two 034 * sections of the same lecture can not be taught at the same time, or that some 035 * classes have to be taught one immediately after another. It can be either 036 * hard or soft. <br> 037 * <br> 038 * Following constraints are now supported: 039 * <table border='1' summary='Related Solver Parameters'> 040 * <tr> 041 * <th>Constraint</th> 042 * <th>Comment</th> 043 * </tr> 044 * <tr> 045 * <td>SAME_TIME</td> 046 * <td>Same time: given classes have to be taught in the same hours. If the 047 * classes are of different length, the smaller one cannot start before the 048 * longer one and it cannot end after the longer one.</td> 049 * </tr> 050 * <tr> 051 * <td>SAME_DAYS</td> 052 * <td>Same days: given classes have to be taught in the same day. If the 053 * classes are of different time patterns, the days of one class have to form a 054 * subset of the days of the other class.</td> 055 * </tr> 056 * <tr> 057 * <td>BTB</td> 058 * <td>Back-to-back constraint: given classes have to be taught in the same room 059 * and they have to follow one strictly after another.</td> 060 * </tr> 061 * <tr> 062 * <td>BTB_TIME</td> 063 * <td>Back-to-back constraint: given classes have to follow one strictly after 064 * another, but they can be taught in different rooms.</td> 065 * </tr> 066 * <tr> 067 * <td>DIFF_TIME</td> 068 * <td>Different time: given classes cannot overlap in time.</td> 069 * </tr> 070 * <tr> 071 * <td>NHB(1), NHB(1.5), NHB(2), ... NHB(8)</td> 072 * <td>Number of hours between: between the given classes, the exact number of 073 * hours have to be kept.</td> 074 * </tr> 075 * <tr> 076 * <td>SAME_START</td> 077 * <td>Same starting hour: given classes have to start in the same hour.</td> 078 * </tr> 079 * <tr> 080 * <td>SAME_ROOM</td> 081 * <td>Same room: given classes have to be placed in the same room.</td> 082 * </tr> 083 * <tr> 084 * <td>NHB_GTE(1)</td> 085 * <td>Greater than or equal to 1 hour between: between the given classes, the 086 * number of hours have to be one or more.</td> 087 * </tr> 088 * <tr> 089 * <td>NHB_LT(6)</td> 090 * <td>Less than 6 hours between: between the given classes, the number of hours 091 * have to be less than six.</td> 092 * </tr> 093 * </table> 094 * 095 * @version CourseTT 1.3 (University Course Timetabling)<br> 096 * Copyright (C) 2006 - 2014 Tomas Muller<br> 097 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 098 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 099 * <br> 100 * This library is free software; you can redistribute it and/or modify 101 * it under the terms of the GNU Lesser General Public License as 102 * published by the Free Software Foundation; either version 3 of the 103 * License, or (at your option) any later version. <br> 104 * <br> 105 * This library is distributed in the hope that it will be useful, but 106 * WITHOUT ANY WARRANTY; without even the implied warranty of 107 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 108 * Lesser General Public License for more details. <br> 109 * <br> 110 * You should have received a copy of the GNU Lesser General Public 111 * License along with this library; if not see 112 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 113 */ 114public class GroupConstraint extends ConstraintWithContext<Lecture, Placement, GroupConstraint.GroupConstraintContext> { 115 private Long iConstraintId; 116 private int iPreference; 117 private ConstraintTypeInterface iType; 118 private boolean iIsRequired; 119 private boolean iIsProhibited; 120 private int iDayOfWeekOffset = 0; 121 private boolean iPrecedenceConsiderDatePatterns = true; 122 private boolean iMaxNHoursADayConsiderDatePatterns = true; 123 private int iForwardCheckMaxDepth = 2; 124 private int iForwardCheckMaxDomainSize = 1000; 125 private int iNrWorkDays = 5; 126 private int iFirstWorkDay = 0; 127 128 /** 129 * Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room), 130 * only need to implement this interface. 131 */ 132 public static interface PairCheck { 133 /** 134 * Check whether the constraint is satisfied for the given two assignments (required / preferred case) 135 * @param gc Calling group constraint 136 * @param plc1 First placement 137 * @param plc2 Second placement 138 * @return true if constraint is satisfied 139 */ 140 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2); 141 /** 142 * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case) 143 * @param gc Calling group constraint 144 * @param plc1 First placement 145 * @param plc2 Second placement 146 * @return true if constraint is satisfied 147 */ 148 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2); 149 } 150 151 /** 152 * Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room), 153 * only need to implement this interface. Unlike {@link PairCheck}, this check is also given current assignment. 154 */ 155 public static interface AssignmentPairCheck { 156 /** 157 * Check whether the constraint is satisfied for the given two assignments (required / preferred case) 158 * @param assignment current assignment 159 * @param gc Calling group constraint 160 * @param plc1 First placement 161 * @param plc2 Second placement 162 * @return true if constraint is satisfied 163 */ 164 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2); 165 /** 166 * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case) 167 * @param assignment current assignment 168 * @param gc Calling group constraint 169 * @param plc1 First placement 170 * @param plc2 Second placement 171 * @return true if constraint is satisfied 172 */ 173 public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2); 174 } 175 176 /** 177 * Group constraints that can have parameters need to implement this interface instead of {@link AssignmentPairCheck} or {@link PairCheck}. 178 */ 179 public static interface AssignmentParameterPairCheck<P> { 180 /** 181 * Check whether the constraint is satisfied for the given two assignments (required / preferred case) 182 * @param assignment current assignment 183 * @param parameter constraint dependent parameter(s) 184 * @param gc Calling group constraint 185 * @param plc1 First placement 186 * @param plc2 Second placement 187 * @return true if constraint is satisfied 188 */ 189 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, P parameter, GroupConstraint gc, Placement plc1, Placement plc2); 190 /** 191 * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case) 192 * @param assignment current assignment 193 * @param parameter constraint dependent parameter(s) 194 * @param gc Calling group constraint 195 * @param plc1 First placement 196 * @param plc2 Second placement 197 * @return true if constraint is satisfied 198 */ 199 public boolean isViolated(Assignment<Lecture, Placement> assignment, P parameter, GroupConstraint gc, Placement plc1, Placement plc2); 200 201 /** 202 * Create constraint type with the parameters taken from the provided reference 203 * @param reference constraint reference, including parameter(s) 204 * @param referenceRegExp reference regular expression defined on the constraint type 205 * @return constraint type with the parameter 206 */ 207 public ParametrizedConstraintType<P> create(String reference, String referenceRegExp); 208 } 209 210 /** 211 * Group constraint building blocks (individual constraints that need more than {@link PairCheck}) 212 */ 213 public static enum Flag { 214 /** Back-to-back constraint (sequence check) */ 215 BACK_TO_BACK, 216 /** Can share room flag */ 217 CAN_SHARE_ROOM, 218 /** Maximum hours a day (number of slots a day check) */ 219 MAX_HRS_DAY, 220 /** Children cannot overlap */ 221 CH_NOTOVERLAP; 222 /** Bit number (to combine flags) */ 223 int flag() { return 1 << ordinal(); } 224 } 225 226 /** 227 * Constraint type interface 228 */ 229 public static interface ConstraintTypeInterface extends AssignmentPairCheck { 230 /** Constraint type 231 * @return constraint type 232 */ 233 public ConstraintType type(); 234 235 /** Constraint reference 236 * @return constraint reference 237 **/ 238 public String reference(); 239 240 /** Constraint name 241 * @return constraint name 242 **/ 243 public String getName(); 244 245 /** Minimum (gap) parameter 246 * @return minimum gap (first constraint parameter) 247 **/ 248 public int getMin(); 249 250 /** Maximum (gap, hours a day) parameter 251 * @return maximum gap (second constraint parameter) 252 **/ 253 public int getMax(); 254 255 /** Flag check (true if contains given flag) 256 * @param f a flag to check 257 * @return true if present 258 **/ 259 public boolean is(Flag f); 260 } 261 262 /** 263 * Constraint type with a parameter 264 */ 265 public static class ParametrizedConstraintType<P> implements ConstraintTypeInterface { 266 private String iReference; 267 private ConstraintType iType; 268 private Integer iMin = null, iMax = null; 269 private String iName = null; 270 private P iParameter; 271 272 /** 273 * Constructor 274 * @param type constraint type 275 * @param parameter parameter parsed from the reference using {@link AssignmentParameterPairCheck#create(String, String)} 276 * @param reference constraint reference with parameters 277 */ 278 public ParametrizedConstraintType(ConstraintType type, P parameter, String reference) { 279 iType = type; iParameter = parameter; iReference = reference; 280 } 281 282 @Override 283 @SuppressWarnings("unchecked") 284 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 285 return ((AssignmentParameterPairCheck<P>)iType.iAssignmentPairCheck).isSatisfied(assignment, iParameter, gc, plc1, plc2); 286 } 287 288 @Override 289 @SuppressWarnings("unchecked") 290 public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 291 return ((AssignmentParameterPairCheck<P>)iType.iAssignmentPairCheck).isViolated(assignment, iParameter, gc, plc1, plc2); 292 } 293 294 /** 295 * Return constraint's parameter 296 * @return constraint's parameter 297 */ 298 public P getParameter() { return iParameter; } 299 @Override 300 public ConstraintType type() { return iType; } 301 @Override 302 public String reference() { return iReference; } 303 @Override 304 public String getName() { return (iName == null ? iType.getName() : iName); } 305 @Override 306 public int getMin() { return (iMin == null ? iType.getMin() : iMin); } 307 @Override 308 public int getMax() { return (iMax == null ? iType.getMax() : iMax); } 309 @Override 310 public boolean is(Flag f) { return iType.is(f); } 311 public ParametrizedConstraintType<P> setMin(int min) { iMin = min; return this; } 312 public ParametrizedConstraintType<P> setMax(int max) { iMax = max; return this; } 313 public ParametrizedConstraintType<P> setName(String name) { iName = name; return this; } 314 } 315 316 /** 317 * Group constraint type. 318 */ 319 public static enum ConstraintType implements ConstraintTypeInterface { 320 /** 321 * Same Time: Given classes must be taught at the same time of day (independent of the actual day the classes meet). 322 * For the classes of the same length, this is the same constraint as same start. For classes of different length, 323 * the shorter one cannot start before, nor end after, the longer one.<BR> 324 * When prohibited or (strongly) discouraged: one class may not meet on any day at a time of day that overlaps with 325 * that of the other. For example, one class can not meet M 7:30 while the other meets F 7:30. Note the difference 326 * here from the different time constraint that only prohibits the actual class meetings from overlapping. 327 */ 328 SAME_TIME("SAME_TIME", "Same Time", new PairCheck() { 329 @Override 330 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 331 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 332 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()); 333 } 334 @Override 335 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 336 return !(plc1.getTimeLocation().shareHours(plc2.getTimeLocation())); 337 }}), 338 /** 339 * Same Days: Given classes must be taught on the same days. In case of classes of different time patterns, a class 340 * with fewer meetings must meet on a subset of the days used by the class with more meetings. For example, if one 341 * class pattern is 3x50, all others given in the constraint can only be taught on Monday, Wednesday, or Friday. 342 * For a 2x100 class MW, MF, WF is allowed but TTh is prohibited.<BR> 343 * When prohibited or (strongly) discouraged: any pair of classes classes cannot be taught on the same days (cannot 344 * overlap in days). For instance, if one class is MFW, the second has to be TTh. 345 */ 346 SAME_DAYS("SAME_DAYS", "Same Days", new PairCheck() { 347 @Override 348 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 349 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 350 } 351 @Override 352 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 353 return !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()); 354 }}), 355 /** 356 * Back-To-Back & Same Room: Classes must be offered in adjacent time segments and must be placed in the same room. 357 * Given classes must also be taught on the same days.<BR> 358 * When prohibited or (strongly) discouraged: classes cannot be back-to-back. There must be at least half-hour 359 * between these classes, and they must be taught on the same days and in the same room. 360 */ 361 BTB("BTB", "Back-To-Back & Same Room", new PairCheck() { 362 @Override 363 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 364 return 365 plc1.sameRooms(plc2) && 366 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 367 } 368 @Override 369 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 370 return 371 plc1.sameRooms(plc2) && 372 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 373 }}, Flag.BACK_TO_BACK), 374 /** 375 * Back-To-Back: Classes must be offered in adjacent time segments but may be placed in different rooms. Given classes 376 * must also be taught on the same days.<BR> 377 * When prohibited or (strongly) discouraged: no pair of classes can be taught back-to-back. They may not overlap in time, 378 * but must be taught on the same days. This means that there must be at least half-hour between these classes. 379 */ 380 BTB_TIME("BTB_TIME", "Back-To-Back", new PairCheck() { 381 @Override 382 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 383 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 384 } 385 @Override 386 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 387 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 388 }}, Flag.BACK_TO_BACK), 389 /** 390 * Different Time: Given classes cannot overlap in time. They may be taught at the same time of day if they are on 391 * different days. For instance, MF 7:30 is compatible with TTh 7:30.<BR> 392 * When prohibited or (strongly) discouraged: every pair of classes in the constraint must overlap in time. 393 */ 394 DIFF_TIME("DIFF_TIME", "Different Time", new PairCheck() { 395 @Override 396 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 397 return !plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 398 } 399 @Override 400 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 401 return plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 402 }}), 403 /** 404 * 1 Hour Between: Given classes must have exactly 1 hour in between the end of one and the beginning of another. 405 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 406 * When prohibited or (strongly) discouraged: classes can not have 1 hour in between. They may not overlap in time 407 * but must be taught on the same days. 408 */ 409 NHB_1("NHB(1)", "1 Hour Between", 10, 12, BTB_TIME.check(), Flag.BACK_TO_BACK), 410 /** 411 * 2 Hours Between: Given classes must have exactly 2 hours in between the end of one and the beginning of another. 412 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 413 * When prohibited or (strongly) discouraged: classes can not have 2 hours in between. They may not overlap in time 414 * but must be taught on the same days. 415 */ 416 NHB_2("NHB(2)", "2 Hours Between", 20, 24, BTB_TIME.check(), Flag.BACK_TO_BACK), 417 /** 418 * 3 Hours Between: Given classes must have exactly 3 hours in between the end of one and the beginning of another. 419 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 420 * When prohibited or (strongly) discouraged: classes can not have 3 hours in between. They may not overlap in time 421 * but must be taught on the same days. 422 */ 423 NHB_3("NHB(3)", "3 Hours Between", 30, 36, BTB_TIME.check(), Flag.BACK_TO_BACK), 424 /** 425 * 4 Hours Between: Given classes must have exactly 4 hours in between the end of one and the beginning of another. 426 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 427 * When prohibited or (strongly) discouraged: classes can not have 4 hours in between. They may not overlap in time 428 * but must be taught on the same days. 429 */ 430 NHB_4("NHB(4)", "4 Hours Between", 40, 48, BTB_TIME.check(), Flag.BACK_TO_BACK), 431 /** 432 * 5 Hours Between: Given classes must have exactly 5 hours in between the end of one and the beginning of another. 433 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 434 * When prohibited or (strongly) discouraged: classes can not have 5 hours in between. They may not overlap in time 435 * but must be taught on the same days. 436 */ 437 NHB_5("NHB(5)", "5 Hours Between", 50, 60, BTB_TIME.check(), Flag.BACK_TO_BACK), 438 /** 439 * 6 Hours Between: Given classes must have exactly 6 hours in between the end of one and the beginning of another. 440 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 441 * When prohibited or (strongly) discouraged: classes can not have 6 hours in between. They may not overlap in time 442 * but must be taught on the same days. 443 */ 444 NHB_6("NHB(6)", "6 Hours Between", 60, 72, BTB_TIME.check(), Flag.BACK_TO_BACK), 445 /** 446 * 7 Hours Between: Given classes must have exactly 7 hours in between the end of one and the beginning of another. 447 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 448 * When prohibited or (strongly) discouraged: classes can not have 7 hours in between. They may not overlap in time 449 * but must be taught on the same days. 450 */ 451 NHB_7("NHB(7)", "7 Hours Between", 70, 84, BTB_TIME.check(), Flag.BACK_TO_BACK), 452 /** 453 * 8 Hours Between: Given classes must have exactly 8 hours in between the end of one and the beginning of another. 454 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 455 * When prohibited or (strongly) discouraged: classes can not have 8 hours in between. They may not overlap in time 456 * but must be taught on the same days. 457 */ 458 NHB_8("NHB(8)", "8 Hours Between", 80, 96, BTB_TIME.check(), Flag.BACK_TO_BACK), 459 /** 460 * Same Start Time: Given classes must start during the same half-hour period of a day (independent of the actual 461 * day the classes meet). For instance, MW 7:30 is compatible with TTh 7:30 but not with MWF 8:00.<BR> 462 * When prohibited or (strongly) discouraged: any pair of classes in the given constraint cannot start during the 463 * same half-hour period of any day of the week. 464 */ 465 SAME_START("SAME_START", "Same Start Time", new PairCheck() { 466 @Override 467 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 468 return 469 (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) == 470 (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY); 471 } 472 @Override 473 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 474 return 475 (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) != 476 (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY); 477 }}), 478 /** 479 * Same Room: Given classes must be taught in the same room.<BR> 480 * When prohibited or (strongly) discouraged: any pair of classes in the constraint cannot be taught in the same room. 481 */ 482 SAME_ROOM("SAME_ROOM", "Same Room", new PairCheck() { 483 @Override 484 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 485 return plc1.sameRooms(plc2); 486 } 487 @Override 488 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 489 return !plc1.sameRooms(plc2); 490 }}), 491 /** 492 * At Least 1 Hour Between: Given classes have to have 1 hour or more in between.<BR> 493 * When prohibited or (strongly) discouraged: given classes have to have less than 1 hour in between. 494 */ 495 NHB_GTE_1("NHB_GTE(1)", "At Least 1 Hour Between", 6, 288, BTB_TIME.check(), Flag.BACK_TO_BACK), 496 /** 497 * Less Than 6 Hours Between: Given classes must have less than 6 hours from end of first class to the beginning of 498 * the next. Given classes must also be taught on the same days.<BR> 499 * When prohibited or (strongly) discouraged: given classes must have 6 or more hours between. This constraint does 500 * not carry over from classes taught at the end of one day to the beginning of the next. 501 */ 502 NHB_LT_6("NHB_LT(6)", "Less Than 6 Hours Between", 0, 72, BTB_TIME.check(), Flag.BACK_TO_BACK), 503 /** 504 * 1.5 Hour Between: Given classes must have exactly 90 minutes in between the end of one and the beginning of another. 505 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 506 * When prohibited or (strongly) discouraged: classes can not have 90 minutes in between. They may not overlap in time 507 * but must be taught on the same days. 508 */ 509 NHB_1_5("NHB(1.5)", "1.5 Hour Between", 15, 18, BTB_TIME.check(), Flag.BACK_TO_BACK), 510 /** 511 * 4.5 Hours Between: Given classes must have exactly 4.5 hours in between the end of one and the beginning of another. 512 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 513 * When prohibited or (strongly) discouraged: classes can not have 4.5 hours in between. They may not overlap in time 514 * but must be taught on the same days. 515 */ 516 NHB_4_5("NHB(4.5)", "4.5 Hours Between", 45, 54, BTB_TIME.check(), Flag.BACK_TO_BACK), 517 /** 518 * Same Students: Given classes are treated as they are attended by the same students, i.e., they cannot overlap in time 519 * and if they are back-to-back the assigned rooms cannot be too far (student limit is used). 520 */ 521 SAME_STUDENTS("SAME_STUDENTS", "Same Students", new PairCheck() { 522 @Override 523 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 524 return !JenrlConstraint.isInConflict(plc1, plc2, ((TimetableModel)gc.getModel()).getDistanceMetric(), ((TimetableModel)gc.getModel()).getStudentWorkDayLimit()); 525 } 526 @Override 527 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 528 return true; 529 }}), 530 /** 531 * Same Instructor: Given classes are treated as they are taught by the same instructor, i.e., they cannot overlap in time 532 * and if they are back-to-back the assigned rooms cannot be too far (instructor limit is used).<BR> 533 * If the constraint is required and the classes are back-to-back, discouraged and strongly discouraged distances between 534 * assigned rooms are also considered. 535 */ 536 SAME_INSTR("SAME_INSTR", "Same Instructor", new PairCheck() { 537 @Override 538 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 539 TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation(); 540 if (t1.shareDays(t2) && t1.shareWeeks(t2)) { 541 if (t1.shareHours(t2)) return false; // overlap 542 DistanceMetric m = ((TimetableModel)gc.getModel()).getDistanceMetric(); 543 if ((t1.getStartSlot() + t1.getLength() == t2.getStartSlot() || t2.getStartSlot() + t2.getLength() == t1.getStartSlot())) { 544 if (Placement.getDistanceInMeters(m, plc1, plc2) > m.getInstructorProhibitedLimit()) 545 return false; 546 } else if (m.doComputeDistanceConflictsBetweenNonBTBClasses()) { 547 if (t1.getStartSlot() + t1.getLength() < t2.getStartSlot() && 548 Placement.getDistanceInMinutes(m, plc1, plc2) > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t2.getStartSlot() - t1.getStartSlot() - t1.getLength())) 549 return false; 550 if (t2.getStartSlot() + t2.getLength() < t1.getStartSlot() && 551 Placement.getDistanceInMinutes(m, plc1, plc2) > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t1.getStartSlot() - t2.getStartSlot() - t2.getLength())) 552 return false; 553 } 554 } 555 return true; 556 } 557 @Override 558 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 559 return true; 560 }}), 561 /** 562 * Can Share Room: Given classes can share the room (use the room in the same time) if the room is big enough. 563 */ 564 CAN_SHARE_ROOM("CAN_SHARE_ROOM", "Can Share Room", Flag.CAN_SHARE_ROOM), 565 /** 566 * Precedence: Given classes have to be taught in the given order (the first meeting of the first class has to end before 567 * the first meeting of the second class etc.)<BR> 568 * When prohibited or (strongly) discouraged: classes have to be taught in the order reverse to the given one. 569 */ 570 PRECEDENCE("PRECEDENCE", "Precedence", new PairCheck() { 571 @Override 572 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 573 return gc.isPrecedence(plc1, plc2, true, true); 574 } 575 @Override 576 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 577 return gc.isPrecedence(plc1, plc2, false, true); 578 }}), 579 /** 580 * Back-To-Back Day: Classes must be offered on adjacent days and may be placed in different rooms.<BR> 581 * When prohibited or (strongly) discouraged: classes can not be taught on adjacent days. They also can not be taught 582 * on the same days. This means that there must be at least one day between these classes. 583 */ 584 BTB_DAY("BTB_DAY", "Back-To-Back Day", new PairCheck() { 585 @Override 586 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 587 return 588 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 589 gc.isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation()); 590 } 591 @Override 592 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 593 return 594 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 595 !gc.isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation()); 596 }}), 597 /** 598 * Meet Together: Given classes are meeting together (same as if the given classes require constraints Can Share Room, 599 * Same Room, Same Time and Same Days all together). 600 */ 601 MEET_WITH("MEET_WITH", "Meet Together", new PairCheck() { 602 @Override 603 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 604 return 605 plc1.sameRooms(plc2) && 606 sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 607 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 608 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 609 610 } 611 @Override 612 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 613 return true; 614 }}, Flag.CAN_SHARE_ROOM), 615 /** 616 * More Than 1 Day Between: Given classes must have two or more days in between.<br> 617 * When prohibited or (strongly) discouraged: given classes must be offered on adjacent days or with at most one day in between. 618 */ 619 NDB_GT_1("NDB_GT_1", "More Than 1 Day Between", new PairCheck() { 620 @Override 621 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 622 return 623 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 624 gc.isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation()); 625 } 626 @Override 627 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 628 return 629 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 630 !gc.isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation()); 631 }}), 632 /** 633 * Children Cannot Overlap: If parent classes do not overlap in time, children classes can not overlap in time as well.<BR> 634 * Note: This constraint only needs to be put on the parent classes. Preferred configurations are Required All Classes 635 * or Pairwise (Strongly) Preferred. 636 */ 637 CH_NOTOVERLAP("CH_NOTOVERLAP", "Children Cannot Overlap", new AssignmentPairCheck() { 638 @Override 639 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 640 return gc.isChildrenNotOverlap(assignment, plc1.variable(), plc1, plc2.variable(), plc2); 641 } 642 @Override 643 public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 644 return true; 645 }}), 646 /** 647 * Next Day: The second class has to be placed on the following day of the first class (if the first class is on Friday, 648 * second class have to be on Monday).<br> 649 * When prohibited or (strongly) discouraged: The second class has to be placed on the previous day of the first class 650 * (if the first class is on Monday, second class have to be on Friday).<br> 651 * Note: This constraint works only between pairs of classes. 652 */ 653 FOLLOWING_DAY("FOLLOWING_DAY", "Next Day", new PairCheck() { 654 @Override 655 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 656 return gc.isFollowingDay(plc1, plc2, true); 657 } 658 @Override 659 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 660 return gc.isFollowingDay(plc1, plc2, false); 661 }}), 662 /** 663 * Two Days After: The second class has to be placed two days after the first class (Monday → Wednesday, Tuesday → 664 * Thurday, Wednesday → Friday, Thursday → Monday, Friday → Tuesday).<br> 665 * When prohibited or (strongly) discouraged: The second class has to be placed two days before the first class (Monday → 666 * Thursday, Tuesday → Friday, Wednesday → Monday, Thursday → Tuesday, Friday → Wednesday).<br> 667 * Note: This constraint works only between pairs of classes. 668 */ 669 EVERY_OTHER_DAY("EVERY_OTHER_DAY", "Two Days After", new PairCheck() { 670 @Override 671 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 672 return gc.isEveryOtherDay(plc1, plc2, true); 673 } 674 @Override 675 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 676 return gc.isEveryOtherDay(plc1, plc2, false); 677 }}), 678 /** 679 * At Most 3 Hours A Day: Classes are to be placed in a way that there is no more than three hours in any day. 680 */ 681 MAX_HRS_DAY_3("MAX_HRS_DAY(3)", "At Most 3 Hours A Day", 36, null, Flag.MAX_HRS_DAY), 682 /** 683 * At Most 4 Hours A Day: Classes are to be placed in a way that there is no more than four hours in any day. 684 */ 685 MAX_HRS_DAY_4("MAX_HRS_DAY(4)", "At Most 4 Hours A Day", 48, null, Flag.MAX_HRS_DAY), 686 /** 687 * At Most 5 Hours A Day: Classes are to be placed in a way that there is no more than five hours in any day. 688 */ 689 MAX_HRS_DAY_5("MAX_HRS_DAY(5)", "At Most 5 Hours A Day", 60, null, Flag.MAX_HRS_DAY), 690 /** 691 * At Most 6 Hours A Day: Classes are to be placed in a way that there is no more than six hours in any day. 692 */ 693 MAX_HRS_DAY_6("MAX_HRS_DAY(6)", "At Most 6 Hours A Day", 72, null, Flag.MAX_HRS_DAY), 694 /** 695 * At Most 7 Hours A Day: Classes are to be placed in a way that there is no more than seven hours in any day. 696 */ 697 MAX_HRS_DAY_7("MAX_HRS_DAY(7)", "At Most 7 Hours A Day", 84, null, Flag.MAX_HRS_DAY), 698 /** 699 * At Most 8 Hours A Day: Classes are to be placed in a way that there is no more than eight hours in any day. 700 */ 701 MAX_HRS_DAY_8("MAX_HRS_DAY(8)", "At Most 8 Hours A Day", 96, null, Flag.MAX_HRS_DAY), 702 /** 703 * At Most 9 Hours A Day: Classes are to be placed in a way that there is no more than nine hours in any day. 704 */ 705 MAX_HRS_DAY_9("MAX_HRS_DAY(9)", "At Most 9 Hours A Day", 108, null, Flag.MAX_HRS_DAY), 706 /** 707 * At Most 10 Hours A Day: Classes are to be placed in a way that there is no more than ten hours in any day. 708 */ 709 MAX_HRS_DAY_10("MAX_HRS_DAY(10)", "At Most 10 Hours A Day", 120, null, Flag.MAX_HRS_DAY), 710 /** 711 * At Most X Hours A Day: Classes are to be placed in a way that there is no more than given number of hours in any day. 712 */ 713 MAX_HRS_DAY("MAX_HRS_DAY\\(([0-9\\.]+)\\)", "At Most N Hours A Day", new AssignmentParameterPairCheck<Integer>() { 714 @Override 715 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) { 716 return true; 717 } 718 @Override 719 public boolean isViolated(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) { 720 return true; 721 } 722 @Override 723 public ParametrizedConstraintType<Integer> create(String reference, String regexp) { 724 Matcher matcher = Pattern.compile(regexp).matcher(reference); 725 if (matcher.find()) { 726 double hours = Double.parseDouble(matcher.group(1)); 727 int slots = (int)Math.round(12.0 * hours); 728 return new ParametrizedConstraintType<Integer>(ConstraintType.MAX_HRS_DAY, slots, reference) 729 .setName("At Most " + matcher.group(1) + " Hours A Day") 730 .setMin(slots).setMax(slots); 731 } 732 return null; 733 }}, Flag.MAX_HRS_DAY), 734 /** 735 * Given classes must be taught during the same weeks (i.e., must have the same date pattern).<br> 736 * When prohibited or (strongly) discouraged: any two classes must have non overlapping date patterns. 737 */ 738 SAME_WEEKS("SAME_WEEKS", "Same Weeks", new PairCheck() { 739 @Override 740 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 741 return plc1.getTimeLocation().getWeekCode().equals(plc2.getTimeLocation().getWeekCode()); 742 } 743 @Override 744 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 745 return !plc1.getTimeLocation().shareWeeks(plc2.getTimeLocation()); 746 }}), 747 /** 748 * Classes (of different courses) are to be attended by the same students. For instance, 749 * if class A1 (of a course A) and class B1 (of a course B) are linked, a student requesting 750 * both courses must attend A1 if and only if he also attends B1. This is a student sectioning 751 * constraint that is interpreted as Same Students constraint during course timetabling. 752 */ 753 LINKED_SECTIONS("LINKED_SECTIONS", "Linked Classes", SAME_STUDENTS.check()), 754 /** 755 * Back-To-Back Precedence: Given classes have to be taught in the given order, on the same days, 756 * and in adjacent time segments. 757 * When prohibited or (strongly) discouraged: Given classes have to be taught in the given order, 758 * on the same days, but cannot be back-to-back. 759 */ 760 BTB_PRECEDENCE("BTB_PRECEDENCE", "Back-To-Back Precedence", new PairCheck() { 761 @Override 762 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 763 return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 764 } 765 @Override 766 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 767 return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 768 }}, Flag.BACK_TO_BACK), 769 770 /** 771 * Same Days-Time: Given classes must be taught at the same time of day and on the same days. 772 * It is the combination of Same Days and Same Time distribution preferences. 773 * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days 774 * during the same time. 775 */ 776 SAME_DAYS_TIME("SAME_D_T", "Same Days-Time", new PairCheck() { 777 @Override 778 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 779 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 780 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 781 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 782 } 783 @Override 784 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 785 return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) || 786 !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()); 787 }}), 788 /** 789 * Same Days-Room-Time: Given classes must be taught at the same time of day, on the same days and in the same room. 790 * It is the combination of Same Days, Same Time and Same Room distribution preferences. 791 * Note that this constraint is the same as Meet Together constraint, except it does not allow room sharing. In other words, 792 * it is only useful when these classes are taught during non-overlapping date patterns. 793 * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days 794 * during the same time in the same room. 795 */ 796 SAME_DAYS_ROOM_TIME("SAME_D_R_T", "Same Days-Room-Time", new PairCheck() { 797 @Override 798 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 799 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 800 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 801 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 802 plc1.sameRooms(plc2); 803 } 804 @Override 805 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 806 return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) || 807 !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()) || 808 !plc1.sameRooms(plc2); 809 }}), 810 /** 811 * 6 Hour Work Day: Classes are to be placed in a way that there is no more than six hours between the start of the first class and the end of the class one on any day. 812 */ 813 WORKDAY_6("WORKDAY(6)", "6 Hour Work Day", 72, new PairCheck() { 814 @Override 815 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 816 TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation(); 817 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return true; 818 return Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()) <= gc.getType().getMax(); 819 } 820 @Override 821 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { return true; } 822 }), 823 /** 824 * 7 Hour Work Day: Classes are to be placed in a way that there is no more than seven hours between the start of the first class and the end of the class one on any day. 825 */ 826 WORKDAY_7("WORKDAY(7)", "7 Hour Work Day", 84, WORKDAY_6.check()), 827 /** 828 * 8 Hour Work Day: Classes are to be placed in a way that there is no more than eight hours between the start of the first class and the end of the class one on any day. 829 */ 830 WORKDAY_8("WORKDAY(8)", "8 Hour Work Day", 96, WORKDAY_6.check()), 831 /** 832 * 9 Hour Work Day: Classes are to be placed in a way that there is no more than nine hours between the start of the first class and the end of the class one on any day. 833 */ 834 WORKDAY_9("WORKDAY(9)", "9 Hour Work Day", 108, WORKDAY_6.check()), 835 /** 836 * 10 Hour Work Day: Classes are to be placed in a way that there is no more than ten hours between the start of the first class and the end of the class one on any day. 837 */ 838 WORKDAY_10("WORKDAY(10)", "10 Hour Work Day", 120, WORKDAY_6.check()), 839 /** 840 * 11 Hour Work Day: Classes are to be placed in a way that there is no more than eleven hours between the start of the first class and the end of the class one on any day. 841 */ 842 WORKDAY_11("WORKDAY(11)", "11 Hour Work Day", 132, WORKDAY_6.check()), 843 /** 844 * 12 Hour Work Day: Classes are to be placed in a way that there is no more than twelve hours between the start of the first class and the end of the class one on any day. 845 */ 846 WORKDAY_12("WORKDAY(12)", "12 Hour Work Day", 144, WORKDAY_6.check()), 847 /** 848 * 4 Hour Work Day: Classes are to be placed in a way that there is no more than four hours between the start of the first class and the end of the class one on any day. 849 */ 850 WORKDAY_4("WORKDAY(4)", "4 Hour Work Day", 48, WORKDAY_6.check()), 851 /** 852 * 5 Hour Work Day: Classes are to be placed in a way that there is no more than five hours between the start of the first class and the end of the class one on any day. 853 */ 854 WORKDAY_5("WORKDAY(5)", "5 Hour Work Day", 60, WORKDAY_6.check()), 855 /** 856 * Work Day: Classes are to be placed in a way that there is no more than given number of hours between the start of the first class and the end of the class one on any day. 857 */ 858 WORKDAY("WORKDAY\\(([0-9\\.]+)\\)", "Work Day", new AssignmentParameterPairCheck<Integer>() { 859 @Override 860 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) { 861 TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation(); 862 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return true; 863 return Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()) <= parameter; 864 } 865 @Override 866 public boolean isViolated(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) { 867 return true; 868 } 869 @Override 870 public ParametrizedConstraintType<Integer> create(String reference, String regexp) { 871 Matcher matcher = Pattern.compile(regexp).matcher(reference); 872 if (matcher.find()) { 873 double hours = Double.parseDouble(matcher.group(1)); 874 int slots = (int)Math.round(12.0 * hours); 875 return new ParametrizedConstraintType<Integer>(ConstraintType.WORKDAY, slots, reference) 876 .setName(matcher.group(1) + " Hour Work Day").setMin(slots).setMax(slots); 877 } 878 return null; 879 }}), 880 /** 881 * Meet Together & Same Weeks: Given classes are meeting together (same as if the given classes require constraints Can Share Room, 882 * Same Room, Same Time, Same Days and Same Weeks all together). 883 */ 884 MEET_WITH_WEEKS("MEET_WITH_WEEKS", "Meet Together & Same Weeks", new PairCheck() { 885 @Override 886 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 887 return 888 plc1.sameRooms(plc2) && 889 sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 890 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 891 plc1.getTimeLocation().getWeekCode().equals(plc2.getTimeLocation().getWeekCode()); 892 } 893 @Override 894 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 895 return true; 896 }}, Flag.CAN_SHARE_ROOM), 897 MIN_GAP("MIN_GAP\\(([0-9\\.]+)\\)", "Mininal Gap Between Classes", new AssignmentParameterPairCheck<Integer>() { 898 @Override 899 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) { 900 TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation(); 901 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return true; 902 return t1.getStartSlot() + t1.getLength() + parameter <= t2.getStartSlot() || 903 t2.getStartSlot() + t2.getLength() + parameter <= t1.getStartSlot(); 904 } 905 @Override 906 public boolean isViolated(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) { return true; } 907 @Override 908 public ParametrizedConstraintType<Integer> create(String reference, String regexp) { 909 Matcher matcher = Pattern.compile(regexp).matcher(reference); 910 if (matcher.find()) { 911 double hours = Double.parseDouble(matcher.group(1)); 912 int slots = (int)Math.round(12.0 * hours); 913 return new ParametrizedConstraintType<Integer>(ConstraintType.MIN_GAP, slots, reference) 914 .setName("At Least " + matcher.group(1) + " Hours Between Classes") 915 .setMin(slots).setMax(slots); 916 } 917 return null; 918 }}), 919 ; 920 921 String iReference, iName; 922 int iFlag = 0; 923 Flag[] iFlags = null; 924 int iMin = 0, iMax = 0; 925 PairCheck iCheck = null; 926 AssignmentPairCheck iAssignmentCheck = null; 927 AssignmentParameterPairCheck<?> iAssignmentPairCheck = null; 928 ConstraintType(String reference, String name, Flag... flags) { 929 iReference = reference; 930 iName = name; 931 iFlags = flags; 932 for (Flag f: flags) 933 iFlag |= f.flag(); 934 } 935 ConstraintType(String reference, String name, PairCheck check, Flag... flags) { 936 this(reference, name, flags); 937 iCheck = check; 938 } 939 ConstraintType(String reference, String name, AssignmentPairCheck check, Flag... flags) { 940 this(reference, name, flags); 941 iAssignmentCheck = check; 942 } 943 ConstraintType(String reference, String name, int limit, PairCheck check, Flag... flags) { 944 this(reference, name, check, flags); 945 iMin = iMax = limit; 946 } 947 ConstraintType(String reference, String name, int min, int max, PairCheck check, Flag... flags) { 948 this(reference, name, check, flags); 949 iMin = min; 950 iMax = max; 951 } 952 ConstraintType(String reference, String name, AssignmentParameterPairCheck<?> check, Flag... flags) { 953 this(reference, name, flags); 954 iAssignmentPairCheck = check; 955 } 956 957 /** 958 * Constraint type 959 * @return constraint type 960 */ 961 @Override 962 public ConstraintType type() { return this; } 963 964 /** Constraint reference 965 * @return constraint reference 966 **/ 967 @Override 968 public String reference() { return iReference; } 969 970 /** Constraint name 971 * @return constraint name 972 **/ 973 @Override 974 public String getName() { return iName; } 975 976 /** Minimum (gap) parameter 977 * @return minimum gap (first constraint parameter) 978 **/ 979 @Override 980 public int getMin() { return iMin; } 981 982 /** Maximum (gap, hours a day) parameter 983 * @return maximum gap (second constraint parameter) 984 **/ 985 @Override 986 public int getMax() { return iMax; } 987 988 /** Flag check (true if contains given flag) 989 * @param f a flag to check 990 * @return true if present 991 **/ 992 @Override 993 public boolean is(Flag f) { return (iFlag & f.flag()) != 0; } 994 995 /** Constraint type from reference 996 * @param reference constraint reference 997 * @return constraint of the reference 998 * @deprecated use {@link GroupConstraint#getConstraintType(String)} instead 999 **/ 1000 @Deprecated 1001 public static ConstraintType get(String reference) { 1002 for (ConstraintType t: ConstraintType.values()) 1003 if (t.reference().equals(reference)) return t; 1004 return null; 1005 } 1006 1007 /** True if a required or preferred constraint is satisfied between a pair of placements 1008 * @param assignment current assignment 1009 * @param gc current constraint 1010 * @param plc1 first placement 1011 * @param plc2 second placement 1012 * @return true if the two placements are consistent with the constraint if preferred or required 1013 **/ 1014 @Override 1015 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 1016 if (iCheck != null && !iCheck.isSatisfied(gc, plc1, plc2)) 1017 return false; 1018 if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isSatisfied(assignment, gc, plc1, plc2)) 1019 return false; 1020 return true; 1021 } 1022 1023 /** True if a prohibited or discouraged constraint is satisfied between a pair of placements 1024 * @param assignment current assignment 1025 * @param gc current constraint 1026 * @param plc1 first placement 1027 * @param plc2 second placement 1028 * @return true if the two placements are consistent with the constraint if discouraged or prohibited 1029 **/ 1030 @Override 1031 public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 1032 if (iCheck != null && !iCheck.isViolated(gc, plc1, plc2)) 1033 return false; 1034 if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isViolated(assignment, gc, plc1, plc2)) 1035 return false; 1036 return true; 1037 } 1038 /** Pair check */ 1039 private PairCheck check() { return iCheck; } 1040 } 1041 1042 /** Constraint type from reference 1043 * @param reference constraint reference 1044 * @return constraint of the reference 1045 **/ 1046 public static ConstraintTypeInterface getConstraintType(String reference) { 1047 for (ConstraintType t: ConstraintType.values()) { 1048 if (t.reference().equals(reference)) return t; 1049 if (t.iAssignmentPairCheck != null && reference.matches(t.reference())) 1050 return t.iAssignmentPairCheck.create(reference, t.reference()); 1051 } 1052 return null; 1053 } 1054 1055 public GroupConstraint() { 1056 } 1057 1058 @Override 1059 public void setModel(Model<Lecture, Placement> model) { 1060 super.setModel(model); 1061 if (model != null) { 1062 DataProperties config = ((TimetableModel)model).getProperties(); 1063 iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0); 1064 iPrecedenceConsiderDatePatterns = config.getPropertyBoolean("Precedence.ConsiderDatePatterns", true); 1065 iForwardCheckMaxDepth = config.getPropertyInt("ForwardCheck.MaxDepth", iForwardCheckMaxDepth); 1066 iForwardCheckMaxDomainSize = config.getPropertyInt("ForwardCheck.MaxDomainSize", iForwardCheckMaxDomainSize); 1067 iMaxNHoursADayConsiderDatePatterns = config.getPropertyBoolean("MaxNHoursADay.ConsiderDatePatterns", iMaxNHoursADayConsiderDatePatterns); 1068 iNrWorkDays = (config.getPropertyInt("General.LastWorkDay", 4) - config.getPropertyInt("General.FirstWorkDay", 0) + 1); 1069 if (iNrWorkDays <= 0) iNrWorkDays += 7; 1070 if (iNrWorkDays > 7) iNrWorkDays -= 7; 1071 iFirstWorkDay = config.getPropertyInt("General.FirstWorkDay", 0); 1072 } 1073 } 1074 1075 @Override 1076 public void addVariable(Lecture lecture) { 1077 if (!variables().contains(lecture)) 1078 super.addVariable(lecture); 1079 if (getType().is(Flag.CH_NOTOVERLAP)) { 1080 if (lecture.getChildrenSubpartIds() != null) { 1081 for (Long subpartId: lecture.getChildrenSubpartIds()) { 1082 for (Lecture ch : lecture.getChildren(subpartId)) { 1083 if (!variables().contains(ch)) 1084 super.addVariable(ch); 1085 } 1086 } 1087 } 1088 } 1089 } 1090 1091 @Override 1092 public void removeVariable(Lecture lecture) { 1093 if (variables().contains(lecture)) 1094 super.removeVariable(lecture); 1095 if (getType().is(Flag.CH_NOTOVERLAP)) { 1096 if (lecture.getChildrenSubpartIds() != null) { 1097 for (Long subpartId: lecture.getChildrenSubpartIds()) { 1098 for (Lecture ch : lecture.getChildren(subpartId)) { 1099 if (variables().contains(ch)) 1100 super.removeVariable(ch); 1101 } 1102 } 1103 } 1104 } 1105 } 1106 1107 /** 1108 * Constructor 1109 * 1110 * @param id 1111 * constraint id 1112 * @param type 1113 * constraString type (e.g, {@link ConstraintType#SAME_TIME}) 1114 * @param preference 1115 * time preference ("R" for required, "P" for prohibited, "-2", 1116 * "-1", "1", "2" for soft preference) 1117 */ 1118 public GroupConstraint(Long id, ConstraintTypeInterface type, String preference) { 1119 iConstraintId = id; 1120 iType = type; 1121 iIsRequired = preference.equals(Constants.sPreferenceRequired); 1122 iIsProhibited = preference.equals(Constants.sPreferenceProhibited); 1123 iPreference = Constants.preference2preferenceLevel(preference); 1124 } 1125 1126 /** Constraint id 1127 * @return constraint unique id 1128 **/ 1129 public Long getConstraintId() { 1130 return iConstraintId; 1131 } 1132 1133 @Override 1134 public long getId() { 1135 return (iConstraintId == null ? -1 : iConstraintId.longValue()); 1136 } 1137 1138 /** Generated unique id 1139 * @return generated unique id 1140 **/ 1141 protected long getGeneratedId() { 1142 return iId; 1143 } 1144 1145 /** Return constraint type (e.g, {@link ConstraintType#SAME_TIME}) 1146 * @return constraint type 1147 **/ 1148 public ConstraintTypeInterface getType() { 1149 return iType; 1150 } 1151 1152 /** 1153 * Set constraint type 1154 * @param type constraint type 1155 */ 1156 public void setType(ConstraintType type) { 1157 iType = type; 1158 } 1159 1160 /** Is constraint required 1161 * @return true if required 1162 **/ 1163 public boolean isRequired() { 1164 return iIsRequired; 1165 } 1166 1167 /** Is constraint prohibited 1168 * @return true if prohibited 1169 **/ 1170 public boolean isProhibited() { 1171 return iIsProhibited; 1172 } 1173 1174 /** 1175 * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for 1176 * preference 1177 * @return prolog preference 1178 */ 1179 public String getPrologPreference() { 1180 return Constants.preferenceLevel2preference(iPreference); 1181 } 1182 1183 @Override 1184 public boolean isConsistent(Placement value1, Placement value2) { 1185 if (!isHard()) 1186 return true; 1187 if (!isSatisfiedPair(null, value1, value2)) 1188 return false; 1189 if (getType().is(Flag.BACK_TO_BACK)) { 1190 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1191 assignments.put(value1.variable(), value1); 1192 assignments.put(value2.variable(), value2); 1193 if (!isSatisfiedSeq(null, assignments, null)) 1194 return false; 1195 } 1196 if (getType().is(Flag.MAX_HRS_DAY)) { 1197 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1198 assignments.put(value1.variable(), value1); 1199 assignments.put(value2.variable(), value2); 1200 for (int dayCode: Constants.DAY_CODES) { 1201 if (iMaxNHoursADayConsiderDatePatterns) { 1202 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1203 if (!value1.getTimeLocation().shareWeeks(week) && !value2.getTimeLocation().shareWeeks(week)) continue; 1204 if (nrSlotsADay(null, dayCode, week, assignments, null) > getType().getMax()) return false; 1205 } 1206 } else { 1207 if (nrSlotsADay(null, dayCode, null, assignments, null) > getType().getMax()) return false; 1208 } 1209 } 1210 } 1211 return true; 1212 } 1213 1214 @Override 1215 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 1216 computeConflicts(assignment, value, conflicts, true); 1217 } 1218 1219 @Override 1220 public void computeConflictsNoForwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 1221 computeConflicts(assignment, value, conflicts, false); 1222 } 1223 1224 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, boolean fwdCheck) { 1225 if (!isHard()) 1226 return; 1227 for (Lecture v : variables()) { 1228 if (v.equals(value.variable())) 1229 continue; // ignore this variable 1230 Placement p = assignment.getValue(v); 1231 if (p == null) 1232 continue; // there is an unassigned variable -- great, still a chance to get violated 1233 if (!isSatisfiedPair(assignment, p, value)) 1234 conflicts.add(p); 1235 } 1236 if (getType().is(Flag.BACK_TO_BACK)) { 1237 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1238 assignments.put(value.variable(), value); 1239 if (!isSatisfiedSeq(assignment, assignments, conflicts)) 1240 conflicts.add(value); 1241 } 1242 if (getType().is(Flag.MAX_HRS_DAY)) { 1243 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1244 assignments.put(value.variable(), value); 1245 for (int dayCode: Constants.DAY_CODES) { 1246 if (iMaxNHoursADayConsiderDatePatterns) { 1247 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1248 if (!value.getTimeLocation().shareWeeks(week)) continue; 1249 if (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax()) { 1250 List<Placement> adepts = new ArrayList<Placement>(); 1251 for (Lecture l: variables()) { 1252 if (l.equals(value.variable()) || l.isConstant()) continue; 1253 Placement p = assignment.getValue(l); 1254 if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue; 1255 if ((p.getTimeLocation().getDayCode() & dayCode) == 0 || !p.getTimeLocation().shareWeeks(week)) continue; 1256 adepts.add(p); 1257 } 1258 do { 1259 if (adepts.isEmpty()) { conflicts.add(value); break; } 1260 Placement conflict = ToolBox.random(adepts); 1261 adepts.remove(conflict); 1262 conflicts.add(conflict); 1263 } while (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax()); 1264 } 1265 } 1266 } else { 1267 if (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax()) { 1268 List<Placement> adepts = new ArrayList<Placement>(); 1269 for (Lecture l: variables()) { 1270 if (l.equals(value.variable()) || l.isConstant()) continue; 1271 Placement p = assignment.getValue(l); 1272 if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue; 1273 if ((p.getTimeLocation().getDayCode() & dayCode) == 0) continue; 1274 adepts.add(p); 1275 } 1276 do { 1277 if (adepts.isEmpty()) { conflicts.add(value); break; } 1278 Placement conflict = ToolBox.random(adepts); 1279 adepts.remove(conflict); 1280 conflicts.add(conflict); 1281 } while (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax()); 1282 } 1283 } 1284 } 1285 } 1286 1287 // Forward checking 1288 if (fwdCheck) forwardCheck(assignment, value, conflicts, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1); 1289 } 1290 1291 public void forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, Set<GroupConstraint> ignore, int depth) { 1292 try { 1293 if (depth < 0) return; 1294 ignore.add(this); 1295 1296 int neededSize = value.variable().maxRoomUse(); 1297 1298 for (Lecture lecture: variables()) { 1299 if (conflicts.contains(value)) break; // already conflicting 1300 1301 if (lecture.equals(value.variable())) continue; // Skip this lecture 1302 Placement current = assignment.getValue(lecture); 1303 if (current != null) { // Has assignment, check whether it is conflicting 1304 if (isSatisfiedPair(assignment, value, current)) { 1305 // Increase needed size if the assignment is of the same room and overlapping in time 1306 if (canShareRoom() && sameRoomAndOverlaps(value, current)) { 1307 neededSize += lecture.maxRoomUse(); 1308 } 1309 continue; 1310 } 1311 conflicts.add(current); 1312 } 1313 1314 // Look for supporting assignments assignment 1315 boolean shareRoomAndOverlaps = canShareRoom(); 1316 Placement support = null; 1317 int nrSupports = 0; 1318 if (lecture.nrValues() >= iForwardCheckMaxDomainSize) { 1319 // ignore variables with large domains 1320 return; 1321 } 1322 List<Placement> values = lecture.values(assignment); 1323 if (values.isEmpty()) { 1324 // ignore variables with empty domain 1325 return; 1326 } 1327 for (Placement other: values) { 1328 if (nrSupports < 2) { 1329 if (isSatisfiedPair(assignment, value, other)) { 1330 if (support == null) support = other; 1331 nrSupports ++; 1332 if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other)) 1333 shareRoomAndOverlaps = false; 1334 } 1335 } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) { 1336 shareRoomAndOverlaps = false; 1337 } 1338 if (nrSupports > 1 && !shareRoomAndOverlaps) 1339 break; 1340 } 1341 1342 // No supporting assignment -> fail 1343 if (nrSupports == 0) { 1344 conflicts.add(value); // other class cannot be assigned with this value 1345 return; 1346 } 1347 // Increase needed size if all supporters are of the same room and in overlapping times 1348 if (shareRoomAndOverlaps) { 1349 neededSize += lecture.maxRoomUse(); 1350 } 1351 1352 // Only one supporter -> propagate the new assignment over other hard constraints of the lecture 1353 if (nrSupports == 1) { 1354 for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) { 1355 if (other instanceof WeakeningConstraint) continue; 1356 if (other instanceof GroupConstraint) { 1357 GroupConstraint gc = (GroupConstraint)other; 1358 if (depth > 0 && !ignore.contains(gc)) 1359 gc.forwardCheck(assignment, support, conflicts, ignore, depth - 1); 1360 } else { 1361 other.computeConflicts(assignment, support, conflicts); 1362 } 1363 } 1364 for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) { 1365 if (other instanceof WeakeningConstraint) continue; 1366 other.computeConflicts(assignment, support, conflicts); 1367 } 1368 1369 if (conflicts.contains(support)) 1370 conflicts.add(value); 1371 } 1372 } 1373 1374 if (canShareRoom() && neededSize > value.getRoomSize()) { 1375 // room is too small to fit all meet with classes 1376 conflicts.add(value); 1377 } 1378 1379 } finally { 1380 ignore.remove(this); 1381 } 1382 } 1383 1384 @Override 1385 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) { 1386 if (!isHard()) 1387 return false; 1388 for (Lecture v : variables()) { 1389 if (v.equals(value.variable())) 1390 continue; // ignore this variable 1391 Placement p = assignment.getValue(v); 1392 if (p == null) 1393 continue; // there is an unassigned variable -- great, still a chance to get violated 1394 if (!isSatisfiedPair(assignment, p, value)) 1395 return true; 1396 } 1397 if (getType().is(Flag.BACK_TO_BACK)) { 1398 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1399 assignments.put(value.variable(), value); 1400 if (!isSatisfiedSeq(assignment, assignments, null)) 1401 return true; 1402 } 1403 if (getType().is(Flag.MAX_HRS_DAY)) { 1404 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1405 assignments.put(value.variable(), value); 1406 for (int dayCode: Constants.DAY_CODES) { 1407 if (iMaxNHoursADayConsiderDatePatterns) { 1408 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1409 if (!value.getTimeLocation().shareWeeks(week)) continue; 1410 if (nrSlotsADay(assignment, dayCode, week, assignments, null) > getType().getMax()) 1411 return true; 1412 } 1413 } else { 1414 if (nrSlotsADay(assignment, dayCode, null, assignments, null) > getType().getMax()) return true; 1415 } 1416 } 1417 } 1418 1419 if (!forwardCheck(assignment, value, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1)) return true; 1420 1421 return false; 1422 } 1423 1424 public boolean forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<GroupConstraint> ignore, int depth) { 1425 try { 1426 if (depth < 0) return true; 1427 ignore.add(this); 1428 1429 int neededSize = value.variable().maxRoomUse(); 1430 1431 for (Lecture lecture: variables()) { 1432 if (lecture.equals(value.variable())) continue; // Skip this lecture 1433 Placement current = assignment.getValue(lecture); 1434 if (current != null) { // Has assignment, check whether it is conflicting 1435 if (isSatisfiedPair(assignment, value, current)) { 1436 // Increase needed size if the assignment is of the same room and overlapping in time 1437 if (canShareRoom() && sameRoomAndOverlaps(value, current)) { 1438 neededSize += lecture.maxRoomUse(); 1439 } 1440 continue; 1441 } 1442 return false; 1443 } 1444 1445 // Look for supporting assignments assignment 1446 boolean shareRoomAndOverlaps = canShareRoom(); 1447 Placement support = null; 1448 int nrSupports = 0; 1449 if (lecture.nrValues() >= iForwardCheckMaxDomainSize) { 1450 // ignore variables with large domains 1451 return true; 1452 } 1453 List<Placement> values = lecture.values(assignment); 1454 if (values.isEmpty()) { 1455 // ignore variables with empty domain 1456 return true; 1457 } 1458 for (Placement other: lecture.values(assignment)) { 1459 if (nrSupports < 2) { 1460 if (isSatisfiedPair(assignment, value, other)) { 1461 if (support == null) support = other; 1462 nrSupports ++; 1463 if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other)) 1464 shareRoomAndOverlaps = false; 1465 } 1466 } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) { 1467 shareRoomAndOverlaps = false; 1468 } 1469 if (nrSupports > 1 && !shareRoomAndOverlaps) 1470 break; 1471 } 1472 1473 // No supporting assignment -> fail 1474 if (nrSupports == 0) { 1475 return false; // other class cannot be assigned with this value 1476 } 1477 // Increase needed size if all supporters are of the same room and in overlapping times 1478 if (shareRoomAndOverlaps) { 1479 neededSize += lecture.maxRoomUse(); 1480 } 1481 1482 // Only one supporter -> propagate the new assignment over other hard constraints of the lecture 1483 if (nrSupports == 1) { 1484 for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) { 1485 if (other instanceof WeakeningConstraint) continue; 1486 if (other instanceof GroupConstraint) { 1487 GroupConstraint gc = (GroupConstraint)other; 1488 if (depth > 0 && !ignore.contains(gc) && !gc.forwardCheck(assignment, support, ignore, depth - 1)) return false; 1489 } else { 1490 if (other.inConflict(assignment, support)) return false; 1491 } 1492 } 1493 for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) { 1494 if (other instanceof WeakeningConstraint) continue; 1495 if (other.inConflict(assignment, support)) return false; 1496 } 1497 } 1498 } 1499 1500 if (canShareRoom() && neededSize > value.getRoomSize()) { 1501 // room is too small to fit all meet with classes 1502 return false; 1503 } 1504 1505 return true; 1506 } finally { 1507 ignore.remove(this); 1508 } 1509 } 1510 1511 /** Constraint preference (0 if prohibited or required) 1512 * @return constraint preference (if soft) 1513 **/ 1514 public int getPreference() { 1515 return iPreference; 1516 } 1517 1518 /** 1519 * Current constraint preference (0 if prohibited or required, depends on 1520 * current satisfaction of the constraint) 1521 * @param assignment current assignment 1522 * @return current preference 1523 */ 1524 public int getCurrentPreference(Assignment<Lecture, Placement> assignment) { 1525 if (isHard()) return 0; // no preference 1526 if (countAssignedVariables(assignment) < 2) return - Math.abs(iPreference); // not enough variable 1527 if (getType().is(Flag.MAX_HRS_DAY)) { // max hours a day 1528 int over = 0; 1529 for (int dayCode: Constants.DAY_CODES) { 1530 if (iMaxNHoursADayConsiderDatePatterns) { 1531 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) 1532 over += Math.max(0, nrSlotsADay(assignment, dayCode, week, null, null) - getType().getMax()); 1533 } else { 1534 over += Math.max(0, nrSlotsADay(assignment, dayCode, null, null, null) - getType().getMax()); 1535 } 1536 } 1537 return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference)); 1538 } 1539 int nrViolatedPairs = 0; 1540 for (Lecture v1 : variables()) { 1541 Placement p1 = assignment.getValue(v1); 1542 if (p1 == null) continue; 1543 for (Lecture v2 : variables()) { 1544 Placement p2 = assignment.getValue(v2); 1545 if (p2 == null || v1.getId() >= v2.getId()) continue; 1546 if (!isSatisfiedPair(assignment, p1, p2)) nrViolatedPairs++; 1547 } 1548 } 1549 if (getType().is(Flag.BACK_TO_BACK)) { 1550 Set<Placement> conflicts = new HashSet<Placement>(); 1551 if (isSatisfiedSeq(assignment, new HashMap<Lecture, Placement>(), conflicts)) 1552 nrViolatedPairs += conflicts.size(); 1553 else 1554 nrViolatedPairs = variables().size(); 1555 } 1556 return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference)); 1557 } 1558 1559 /** Current constraint preference change (if given placement is assigned) 1560 * @param assignment current assignment 1561 * @param placement placement that is being considered 1562 * @return change in the current preference, if assigned 1563 **/ 1564 public int getCurrentPreference(Assignment<Lecture, Placement> assignment, Placement placement) { 1565 if (isHard()) return 0; // no preference 1566 if (countAssignedVariables(assignment) + (assignment.getValue(placement.variable()) == null ? 1 : 0) < 2) return 0; // not enough variable 1567 if (getType().is(Flag.MAX_HRS_DAY)) { 1568 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1569 assignments.put(placement.variable(), placement); 1570 HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>(); 1571 unassignments.put(placement.variable(), null); 1572 int after = 0; 1573 int before = 0; 1574 for (int dayCode: Constants.DAY_CODES) { 1575 if (iMaxNHoursADayConsiderDatePatterns) { 1576 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1577 after += Math.max(0, nrSlotsADay(assignment, dayCode, week, assignments, null) - getType().getMax()); 1578 before += Math.max(0, nrSlotsADay(assignment, dayCode, week, unassignments, null) - getType().getMax()); 1579 } 1580 } else { 1581 after += Math.max(0, nrSlotsADay(assignment, dayCode, null, assignments, null) - getType().getMax()); 1582 before += Math.max(0, nrSlotsADay(assignment, dayCode, null, unassignments, null) - getType().getMax()); 1583 } 1584 } 1585 return (after > 0 ? Math.abs(iPreference) * after / 12 : - Math.abs(iPreference)) - (before > 0 ? Math.abs(iPreference) * before / 12 : - Math.abs(iPreference)); 1586 } 1587 1588 int nrViolatedPairsAfter = 0; 1589 int nrViolatedPairsBefore = 0; 1590 for (Lecture v1 : variables()) { 1591 for (Lecture v2 : variables()) { 1592 if (v1.getId() >= v2.getId()) continue; 1593 Placement p1 = (v1.equals(placement.variable()) ? null : assignment.getValue(v1)); 1594 Placement p2 = (v2.equals(placement.variable()) ? null : assignment.getValue(v2)); 1595 if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2)) 1596 nrViolatedPairsBefore ++; 1597 if (v1.equals(placement.variable())) p1 = placement; 1598 if (v2.equals(placement.variable())) p2 = placement; 1599 if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2)) 1600 nrViolatedPairsAfter ++; 1601 } 1602 } 1603 1604 if (getType().is(Flag.BACK_TO_BACK)) { 1605 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1606 assignments.put(placement.variable(), placement); 1607 Set<Placement> conflicts = new HashSet<Placement>(); 1608 if (isSatisfiedSeq(assignment, assignments, conflicts)) 1609 nrViolatedPairsAfter += conflicts.size(); 1610 else 1611 nrViolatedPairsAfter = variables().size(); 1612 1613 HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>(); 1614 unassignments.put(placement.variable(), null); 1615 Set<Placement> previous = new HashSet<Placement>(); 1616 if (isSatisfiedSeq(assignment, unassignments, previous)) 1617 nrViolatedPairsBefore += previous.size(); 1618 else 1619 nrViolatedPairsBefore = variables().size(); 1620 } 1621 1622 return (nrViolatedPairsAfter > 0 ? Math.abs(iPreference) * nrViolatedPairsAfter : - Math.abs(iPreference)) - 1623 (nrViolatedPairsBefore > 0 ? Math.abs(iPreference) * nrViolatedPairsBefore : - Math.abs(iPreference)); 1624 } 1625 1626 @Override 1627 public String toString() { 1628 StringBuffer sb = new StringBuffer(); 1629 sb.append(getName()); 1630 sb.append(" between "); 1631 for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) { 1632 Lecture v = e.next(); 1633 sb.append(v.getName()); 1634 if (e.hasNext()) 1635 sb.append(", "); 1636 } 1637 return sb.toString(); 1638 } 1639 1640 @Override 1641 public boolean isHard() { 1642 return iIsRequired || iIsProhibited; 1643 } 1644 1645 @Override 1646 public String getName() { 1647 return getType().getName(); 1648 } 1649 1650 1651 private boolean isPrecedence(Placement p1, Placement p2, boolean firstGoesFirst, boolean considerDatePatterns) { 1652 int ord1 = variables().indexOf(p1.variable()); 1653 int ord2 = variables().indexOf(p2.variable()); 1654 TimeLocation t1 = null, t2 = null; 1655 if (ord1 < ord2) { 1656 if (firstGoesFirst) { 1657 t1 = p1.getTimeLocation(); 1658 t2 = p2.getTimeLocation(); 1659 } else { 1660 t2 = p1.getTimeLocation(); 1661 t1 = p2.getTimeLocation(); 1662 } 1663 } else { 1664 if (!firstGoesFirst) { 1665 t1 = p1.getTimeLocation(); 1666 t2 = p2.getTimeLocation(); 1667 } else { 1668 t2 = p1.getTimeLocation(); 1669 t1 = p2.getTimeLocation(); 1670 } 1671 } 1672 if (considerDatePatterns && iPrecedenceConsiderDatePatterns) { 1673 boolean sameDatePattern = (t1.getDatePatternId() != null ? t1.getDatePatternId().equals(t2.getDatePatternId()) : t1.getWeekCode().equals(t2.getWeekCode())); 1674 if (!sameDatePattern) { 1675 int m1 = t1.getFirstMeeting(iDayOfWeekOffset), m2 = t2.getFirstMeeting(iDayOfWeekOffset); 1676 if (m1 != m2) return m1 < m2; 1677 } 1678 } 1679 if (iFirstWorkDay != 0) { 1680 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1681 int idx = (i + iFirstWorkDay) % 7; 1682 boolean a = (t1.getDayCode() & Constants.DAY_CODES[idx]) != 0; 1683 boolean b = (t2.getDayCode() & Constants.DAY_CODES[idx]) != 0; 1684 if (b && !a) return false; // second start first 1685 if (a && !b) return true; // first start first 1686 if (a && b) return t1.getStartSlot() + t1.getLength() <= t2.getStartSlot(); // same day: check times 1687 } 1688 } 1689 return t1.getStartSlots().nextElement() + t1.getLength() <= t2.getStartSlots().nextElement(); 1690 } 1691 1692 private boolean isBackToBackDays(TimeLocation t1, TimeLocation t2) { 1693 int f1 = -1, f2 = -1, e1 = -1, e2 = -1; 1694 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1695 int idx = (i + iFirstWorkDay) % 7; 1696 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1697 if (f1 < 0) 1698 f1 = i; 1699 e1 = i; 1700 } 1701 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1702 if (f2 < 0) 1703 f2 = i; 1704 e2 = i; 1705 } 1706 } 1707 return (e1 + 1 == f2) || (e2 + 1 == f1); 1708 } 1709 1710 private boolean isNrDaysBetweenGreaterThanOne(TimeLocation t1, TimeLocation t2) { 1711 int f1 = -1, f2 = -1, e1 = -1, e2 = -1; 1712 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1713 int idx = (i + iFirstWorkDay) % 7; 1714 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1715 if (f1 < 0) 1716 f1 = i; 1717 e1 = i; 1718 } 1719 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1720 if (f2 < 0) 1721 f2 = i; 1722 e2 = i; 1723 } 1724 } 1725 return (e1 - f2 > 2) || (e2 - f1 > 2); 1726 } 1727 1728 private boolean isFollowingDay(Placement p1, Placement p2, boolean firstGoesFirst) { 1729 int ord1 = variables().indexOf(p1.variable()); 1730 int ord2 = variables().indexOf(p2.variable()); 1731 TimeLocation t1 = null, t2 = null; 1732 if (ord1 < ord2) { 1733 if (firstGoesFirst) { 1734 t1 = p1.getTimeLocation(); 1735 t2 = p2.getTimeLocation(); 1736 } else { 1737 t2 = p1.getTimeLocation(); 1738 t1 = p2.getTimeLocation(); 1739 } 1740 } else { 1741 if (!firstGoesFirst) { 1742 t1 = p1.getTimeLocation(); 1743 t2 = p2.getTimeLocation(); 1744 } else { 1745 t2 = p1.getTimeLocation(); 1746 t1 = p2.getTimeLocation(); 1747 } 1748 } 1749 int f1 = -1, f2 = -1, e1 = -1; 1750 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1751 int idx = (i + iFirstWorkDay) % 7; 1752 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1753 if (f1 < 0) 1754 f1 = i; 1755 e1 = i; 1756 } 1757 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1758 if (f2 < 0) 1759 f2 = i; 1760 } 1761 } 1762 return ((e1 + 1) % iNrWorkDays == f2); 1763 } 1764 1765 private boolean isEveryOtherDay(Placement p1, Placement p2, boolean firstGoesFirst) { 1766 int ord1 = variables().indexOf(p1.variable()); 1767 int ord2 = variables().indexOf(p2.variable()); 1768 TimeLocation t1 = null, t2 = null; 1769 if (ord1 < ord2) { 1770 if (firstGoesFirst) { 1771 t1 = p1.getTimeLocation(); 1772 t2 = p2.getTimeLocation(); 1773 } else { 1774 t2 = p1.getTimeLocation(); 1775 t1 = p2.getTimeLocation(); 1776 } 1777 } else { 1778 if (!firstGoesFirst) { 1779 t1 = p1.getTimeLocation(); 1780 t2 = p2.getTimeLocation(); 1781 } else { 1782 t2 = p1.getTimeLocation(); 1783 t1 = p2.getTimeLocation(); 1784 } 1785 } 1786 int f1 = -1, f2 = -1, e1 = -1; 1787 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1788 int idx = (i + iFirstWorkDay) % 7; 1789 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1790 if (f1 < 0) 1791 f1 = i; 1792 e1 = i; 1793 } 1794 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1795 if (f2 < 0) 1796 f2 = i; 1797 } 1798 } 1799 return ((e1 + 2) % iNrWorkDays == f2); 1800 } 1801 1802 private static boolean sameDays(int[] days1, int[] days2) { 1803 if (days2.length < days1.length) 1804 return sameDays(days2, days1); 1805 int i2 = 0; 1806 for (int i1 = 0; i1 < days1.length; i1++) { 1807 int d1 = days1[i1]; 1808 while (true) { 1809 if (i2 == days2.length) 1810 return false; 1811 int d2 = days2[i2]; 1812 if (d1 == d2) 1813 break; 1814 i2++; 1815 if (i2 == days2.length) 1816 return false; 1817 } 1818 i2++; 1819 } 1820 return true; 1821 } 1822 1823 private static boolean sameRoomAndOverlaps(Placement p1, Placement p2) { 1824 return p1.shareRooms(p2) && p1.getTimeLocation() != null && p2.getTimeLocation() != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation()); 1825 } 1826 1827 private static boolean sameHours(int start1, int len1, int start2, int len2) { 1828 if (len1 > len2) 1829 return sameHours(start2, len2, start1, len1); 1830 start1 %= Constants.SLOTS_PER_DAY; 1831 start2 %= Constants.SLOTS_PER_DAY; 1832 return (start1 >= start2 && start1 + len1 <= start2 + len2); 1833 } 1834 1835 private static boolean canFill(int totalGap, int gapMin, int gapMax, List<Integer> lengths) { 1836 if (gapMin <= totalGap && totalGap <= gapMax) 1837 return true; 1838 if (totalGap < 2 * gapMin) 1839 return false; 1840 for (int i = 0; i < lengths.size(); i++) { 1841 int length = lengths.get(i); 1842 lengths.remove(i); 1843 for (int gap = gapMin; gap <= gapMax; gap++) 1844 if (canFill(totalGap - gap - length, gapMin, gapMax, lengths)) 1845 return true; 1846 lengths.add(i, length); 1847 } 1848 return false; 1849 } 1850 1851 private boolean isSatisfiedSeq(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 1852 if (conflicts == null) 1853 return isSatisfiedSeqCheck(assignment, assignments, conflicts); 1854 else { 1855 Set<Placement> bestConflicts = isSatisfiedRecursive(assignment, 0, assignments, conflicts, 1856 new HashSet<Placement>(), null); 1857 if (bestConflicts == null) 1858 return false; 1859 conflicts.addAll(bestConflicts); 1860 return true; 1861 } 1862 } 1863 1864 private Set<Placement> isSatisfiedRecursive(Assignment<Lecture, Placement> assignment, int idx, HashMap<Lecture, Placement> assignments, 1865 Set<Placement> conflicts, Set<Placement> newConflicts, Set<Placement> bestConflicts) { 1866 if (idx == variables().size() && newConflicts.isEmpty()) 1867 return bestConflicts; 1868 if (isSatisfiedSeqCheck(assignment, assignments, conflicts)) { 1869 if (bestConflicts == null) { 1870 return new HashSet<Placement>(newConflicts); 1871 } else { 1872 int b = 0, n = 0; 1873 for (Placement value: assignments.values()) { 1874 if (value != null && bestConflicts.contains(value)) b++; 1875 if (value != null && newConflicts.contains(value)) n++; 1876 } 1877 if (n < b || (n == b && newConflicts.size() < bestConflicts.size())) 1878 return new HashSet<Placement>(newConflicts); 1879 } 1880 return bestConflicts; 1881 } 1882 if (idx == variables().size()) 1883 return bestConflicts; 1884 bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts, 1885 bestConflicts); 1886 Lecture lecture = variables().get(idx); 1887 //if (assignments != null && assignments.containsKey(lecture)) 1888 // return bestConflicts; 1889 Placement placement = null; 1890 if (assignments != null && assignments.containsKey(lecture)) 1891 placement = assignments.get(lecture); 1892 else if (assignment != null) 1893 placement = assignment.getValue(lecture); 1894 if (placement == null) 1895 return bestConflicts; 1896 if (conflicts != null && conflicts.contains(placement)) 1897 return bestConflicts; 1898 conflicts.add(placement); 1899 newConflicts.add(placement); 1900 bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts, bestConflicts); 1901 newConflicts.remove(placement); 1902 conflicts.remove(placement); 1903 return bestConflicts; 1904 } 1905 1906 private boolean isSatisfiedSeqCheck(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 1907 if (!getType().is(Flag.BACK_TO_BACK)) return true; 1908 int gapMin = getType().getMin(); 1909 int gapMax = getType().getMax(); 1910 1911 List<Integer> lengths = new ArrayList<Integer>(); 1912 1913 Placement[] res = new Placement[Constants.SLOTS_PER_DAY]; 1914 for (int i = 0; i < Constants.SLOTS_PER_DAY; i++) 1915 res[i] = null; 1916 1917 int nrLectures = 0; 1918 1919 for (Lecture lecture : variables()) { 1920 Placement placement = null; 1921 if (assignments != null && assignments.containsKey(lecture)) 1922 placement = assignments.get(lecture); 1923 else if (assignment != null) 1924 placement = assignment.getValue(lecture); 1925 if (placement == null) { 1926 if (!lecture.timeLocations().isEmpty()) 1927 lengths.add(lecture.timeLocations().get(0).getLength()); 1928 } else if (conflicts != null && conflicts.contains(placement)) { 1929 if (!lecture.timeLocations().isEmpty()) 1930 lengths.add(lecture.timeLocations().get(0).getLength()); 1931 } else { 1932 int pos = placement.getTimeLocation().getStartSlot(); 1933 int length = placement.getTimeLocation().getLength(); 1934 for (int j = pos; j < pos + length; j++) { 1935 if (res[j] != null) { 1936 if (conflicts == null) 1937 return false; 1938 if (!assignments.containsKey(lecture)) 1939 conflicts.add(placement); 1940 else if (!assignments.containsKey(res[j].variable())) 1941 conflicts.add(res[j]); 1942 } 1943 } 1944 for (int j = pos; j < pos + length; j++) 1945 res[j] = placement; 1946 nrLectures++; 1947 } 1948 } 1949 if (nrLectures <= 1) 1950 return true; 1951 1952 if (iIsRequired || (!iIsProhibited && iPreference < 0)) { 1953 int i = 0; 1954 Placement p = res[i]; 1955 while (p == null) 1956 p = res[++i]; 1957 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 1958 nrLectures--; 1959 while (nrLectures > 0) { 1960 int gap = 0; 1961 while (i < Constants.SLOTS_PER_DAY && res[i] == null) { 1962 gap++; 1963 i++; 1964 } 1965 if (i == Constants.SLOTS_PER_DAY) 1966 break; 1967 if (!canFill(gap, gapMin, gapMax, lengths)) 1968 return false; 1969 p = res[i]; 1970 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 1971 nrLectures--; 1972 } 1973 } else if (iIsProhibited || (!iIsRequired && iPreference > 0)) { 1974 int i = 0; 1975 Placement p = res[i]; 1976 while (p == null) 1977 p = res[++i]; 1978 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 1979 nrLectures--; 1980 while (nrLectures > 0) { 1981 int gap = 0; 1982 while (i < Constants.SLOTS_PER_DAY && res[i] == null) { 1983 gap++; 1984 i++; 1985 } 1986 if (i == Constants.SLOTS_PER_DAY) 1987 break; 1988 if ((gapMin == 0 || !canFill(gap, 0, gapMin - 1, lengths)) 1989 && (gapMax >= Constants.SLOTS_PER_DAY || !canFill(gap, gapMax + 1, Constants.SLOTS_PER_DAY, 1990 lengths))) { 1991 return false; 1992 } 1993 p = res[i]; 1994 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 1995 nrLectures--; 1996 } 1997 } 1998 return true; 1999 } 2000 2001 public boolean isSatisfied(Assignment<Lecture, Placement> assignment) { 2002 if (isHard()) return true; 2003 if (countAssignedVariables(assignment) < 2) return true; 2004 if (getPreference() == 0) return true; 2005 return isHard() || countAssignedVariables(assignment) < 2 || getPreference() == 0 || getCurrentPreference(assignment) < 0; 2006 } 2007 2008 public boolean isChildrenNotOverlap(Assignment<Lecture, Placement> assignment, Lecture lec1, Placement plc1, Lecture lec2, Placement plc2) { 2009 if (lec1.getSchedulingSubpartId().equals(lec2.getSchedulingSubpartId())) { 2010 // same subpart 2011 boolean overlap = plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 2012 2013 if (overlap && lec1.getParent() != null && variables().contains(lec1.getParent()) 2014 && lec2.getParent() != null && variables().contains(lec2.getParent())) { 2015 // children overlaps 2016 Placement p1 = assignment.getValue(lec1.getParent()); 2017 Placement p2 = assignment.getValue(lec2.getParent()); 2018 // parents not overlap, but children do 2019 if (p1 != null && p2 != null && !p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) 2020 return false; 2021 } 2022 2023 if (!overlap && lec1.getChildrenSubpartIds() != null && lec2.getChildrenSubpartIds() != null) { 2024 // parents not overlap 2025 for (Long subpartId: lec1.getChildrenSubpartIds()) { 2026 for (Lecture c1 : lec1.getChildren(subpartId)) { 2027 Placement p1 = assignment.getValue(c1); 2028 if (p1 == null) continue; 2029 for (Lecture c2 : lec2.getChildren(subpartId)) { 2030 Placement p2 = assignment.getValue(c2); 2031 if (p2 == null) continue; 2032 if (!c1.getSchedulingSubpartId().equals(c2.getSchedulingSubpartId())) continue; 2033 // parents not overlap, but children do 2034 if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) 2035 return false; 2036 } 2037 } 2038 } 2039 } 2040 } else { 2041 // different subpart 2042 } 2043 return true; 2044 } 2045 2046 public boolean isSatisfiedPair(Assignment<Lecture, Placement> assignment, Placement plc1, Placement plc2) { 2047 if (iIsRequired || (!iIsProhibited && iPreference <= 0)) 2048 return getType().isSatisfied(assignment, this, plc1, plc2); 2049 else if (iIsProhibited || (!iIsRequired && iPreference > 0)) 2050 return getType().isViolated(assignment, this, plc1, plc2); 2051 return true; 2052 } 2053 2054 public boolean canShareRoom() { 2055 return getType().is(Flag.CAN_SHARE_ROOM); 2056 } 2057 2058 protected int nrSlotsADay(Assignment<Lecture, Placement> assignment, int dayCode, BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 2059 Set<Integer> slots = new HashSet<Integer>(); 2060 for (Lecture lecture: variables()) { 2061 Placement placement = null; 2062 if (assignments != null && assignments.containsKey(lecture)) 2063 placement = assignments.get(lecture); 2064 else if (assignment != null) 2065 placement = assignment.getValue(lecture); 2066 if (placement == null || placement.getTimeLocation() == null) continue; 2067 if (conflicts != null && conflicts.contains(placement)) continue; 2068 TimeLocation t = placement.getTimeLocation(); 2069 if (t == null || (t.getDayCode() & dayCode) == 0 || (week != null && !t.shareWeeks(week))) continue; 2070 for (int i = 0; i < t.getLength(); i++) 2071 slots.add(i + t.getStartSlot()); 2072 } 2073 return slots.size(); 2074 } 2075 2076 @Override 2077 public boolean equals(Object o) { 2078 if (o == null || !(o instanceof GroupConstraint)) return false; 2079 return getGeneratedId() == ((GroupConstraint) o).getGeneratedId(); 2080 } 2081 2082 @Override 2083 public GroupConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 2084 return new GroupConstraintContext(assignment); 2085 } 2086 2087 public class GroupConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 2088 protected int iLastPreference = 0; 2089 2090 public GroupConstraintContext(Assignment<Lecture, Placement> assignment) { 2091 updateCriterion(assignment); 2092 } 2093 2094 @Override 2095 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 2096 updateCriterion(assignment); 2097 } 2098 2099 @Override 2100 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 2101 updateCriterion(assignment); 2102 } 2103 2104 protected void updateCriterion(Assignment<Lecture, Placement> assignment) { 2105 if (!isHard()) { 2106 getModel().getCriterion(DistributionPreferences.class).inc(assignment, -iLastPreference); 2107 iLastPreference = getCurrentPreference(assignment) + Math.abs(iPreference); 2108 getModel().getCriterion(DistributionPreferences.class).inc(assignment, iLastPreference); 2109 } 2110 } 2111 2112 public int getPreference() { return iLastPreference; } 2113 } 2114}