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