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 991 String iReference, iName; 992 int iFlag = 0; 993 Flag[] iFlags = null; 994 int iMin = 0, iMax = 0; 995 PairCheck iCheck = null; 996 AssignmentPairCheck iAssignmentCheck = null; 997 AssignmentParameterPairCheck<?> iAssignmentPairCheck = null; 998 ConstraintType(String reference, String name, Flag... flags) { 999 iReference = reference; 1000 iName = name; 1001 iFlags = flags; 1002 for (Flag f: flags) 1003 iFlag |= f.flag(); 1004 } 1005 ConstraintType(String reference, String name, PairCheck check, Flag... flags) { 1006 this(reference, name, flags); 1007 iCheck = check; 1008 } 1009 ConstraintType(String reference, String name, AssignmentPairCheck check, Flag... flags) { 1010 this(reference, name, flags); 1011 iAssignmentCheck = check; 1012 } 1013 ConstraintType(String reference, String name, int limit, PairCheck check, Flag... flags) { 1014 this(reference, name, check, flags); 1015 iMin = iMax = limit; 1016 } 1017 ConstraintType(String reference, String name, int min, int max, PairCheck check, Flag... flags) { 1018 this(reference, name, check, flags); 1019 iMin = min; 1020 iMax = max; 1021 } 1022 ConstraintType(String reference, String name, AssignmentParameterPairCheck<?> check, Flag... flags) { 1023 this(reference, name, flags); 1024 iAssignmentPairCheck = check; 1025 } 1026 1027 /** 1028 * Constraint type 1029 * @return constraint type 1030 */ 1031 @Override 1032 public ConstraintType type() { return this; } 1033 1034 /** Constraint reference 1035 * @return constraint reference 1036 **/ 1037 @Override 1038 public String reference() { return iReference; } 1039 1040 /** Constraint name 1041 * @return constraint name 1042 **/ 1043 @Override 1044 public String getName() { return iName; } 1045 1046 /** Minimum (gap) parameter 1047 * @return minimum gap (first constraint parameter) 1048 **/ 1049 @Override 1050 public int getMin() { return iMin; } 1051 1052 /** Maximum (gap, hours a day) parameter 1053 * @return maximum gap (second constraint parameter) 1054 **/ 1055 @Override 1056 public int getMax() { return iMax; } 1057 1058 /** Flag check (true if contains given flag) 1059 * @param f a flag to check 1060 * @return true if present 1061 **/ 1062 @Override 1063 public boolean is(Flag f) { return (iFlag & f.flag()) != 0; } 1064 1065 /** Constraint type from reference 1066 * @param reference constraint reference 1067 * @return constraint of the reference 1068 * @deprecated use {@link GroupConstraint#getConstraintType(String)} instead 1069 **/ 1070 @Deprecated 1071 public static ConstraintType get(String reference) { 1072 for (ConstraintType t: ConstraintType.values()) 1073 if (t.reference().equals(reference)) return t; 1074 return null; 1075 } 1076 1077 /** True if a required or preferred constraint is satisfied between a pair of placements 1078 * @param assignment current assignment 1079 * @param gc current constraint 1080 * @param plc1 first placement 1081 * @param plc2 second placement 1082 * @return true if the two placements are consistent with the constraint if preferred or required 1083 **/ 1084 @Override 1085 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 1086 if (iCheck != null && !iCheck.isSatisfied(gc, plc1, plc2)) 1087 return false; 1088 if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isSatisfied(assignment, gc, plc1, plc2)) 1089 return false; 1090 return true; 1091 } 1092 1093 /** True if a prohibited or discouraged constraint is satisfied between a pair of placements 1094 * @param assignment current assignment 1095 * @param gc current constraint 1096 * @param plc1 first placement 1097 * @param plc2 second placement 1098 * @return true if the two placements are consistent with the constraint if discouraged or prohibited 1099 **/ 1100 @Override 1101 public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 1102 if (iCheck != null && !iCheck.isViolated(gc, plc1, plc2)) 1103 return false; 1104 if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isViolated(assignment, gc, plc1, plc2)) 1105 return false; 1106 return true; 1107 } 1108 /** Pair check */ 1109 private PairCheck check() { return iCheck; } 1110 } 1111 1112 /** Constraint type from reference 1113 * @param reference constraint reference 1114 * @return constraint of the reference 1115 **/ 1116 public static ConstraintTypeInterface getConstraintType(String reference) { 1117 for (ConstraintType t: ConstraintType.values()) { 1118 if (t.reference().equals(reference)) return t; 1119 if (t.iAssignmentPairCheck != null && reference.matches(t.reference())) 1120 return t.iAssignmentPairCheck.create(reference, t.reference()); 1121 } 1122 return null; 1123 } 1124 1125 public GroupConstraint() { 1126 } 1127 1128 @Override 1129 public void setModel(Model<Lecture, Placement> model) { 1130 super.setModel(model); 1131 if (model != null) { 1132 DataProperties config = ((TimetableModel)model).getProperties(); 1133 iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0); 1134 iPrecedenceConsiderDatePatterns = config.getPropertyBoolean("Precedence.ConsiderDatePatterns", true); 1135 iPrecedenceSkipSameDatePatternCheck = config.getPropertyBoolean("Precedence.SkipSameDatePatternCheck", true); 1136 iForwardCheckMaxDepth = config.getPropertyInt("ForwardCheck.MaxDepth", iForwardCheckMaxDepth); 1137 iForwardCheckMaxDomainSize = config.getPropertyInt("ForwardCheck.MaxDomainSize", iForwardCheckMaxDomainSize); 1138 iMaxNHoursADayConsiderDatePatterns = config.getPropertyBoolean("MaxNHoursADay.ConsiderDatePatterns", iMaxNHoursADayConsiderDatePatterns); 1139 iNrWorkDays = (config.getPropertyInt("General.LastWorkDay", 4) - config.getPropertyInt("General.FirstWorkDay", 0) + 1); 1140 if (iNrWorkDays <= 0) iNrWorkDays += 7; 1141 if (iNrWorkDays > 7) iNrWorkDays -= 7; 1142 iFirstWorkDay = config.getPropertyInt("General.FirstWorkDay", 0); 1143 } 1144 } 1145 1146 @Override 1147 public void addVariable(Lecture lecture) { 1148 if (!variables().contains(lecture)) 1149 super.addVariable(lecture); 1150 if (getType().is(Flag.CH_NOTOVERLAP)) { 1151 if (lecture.getChildrenSubpartIds() != null) { 1152 for (Long subpartId: lecture.getChildrenSubpartIds()) { 1153 for (Lecture ch : lecture.getChildren(subpartId)) { 1154 if (!variables().contains(ch)) 1155 super.addVariable(ch); 1156 } 1157 } 1158 } 1159 } 1160 } 1161 1162 @Override 1163 public void removeVariable(Lecture lecture) { 1164 if (variables().contains(lecture)) 1165 super.removeVariable(lecture); 1166 if (getType().is(Flag.CH_NOTOVERLAP)) { 1167 if (lecture.getChildrenSubpartIds() != null) { 1168 for (Long subpartId: lecture.getChildrenSubpartIds()) { 1169 for (Lecture ch : lecture.getChildren(subpartId)) { 1170 if (variables().contains(ch)) 1171 super.removeVariable(ch); 1172 } 1173 } 1174 } 1175 } 1176 } 1177 1178 /** 1179 * Constructor 1180 * 1181 * @param id 1182 * constraint id 1183 * @param type 1184 * constraString type (e.g, {@link ConstraintType#SAME_TIME}) 1185 * @param preference 1186 * time preference ("R" for required, "P" for prohibited, "-2", 1187 * "-1", "1", "2" for soft preference) 1188 */ 1189 public GroupConstraint(Long id, ConstraintTypeInterface type, String preference) { 1190 iConstraintId = id; 1191 iType = type; 1192 iIsRequired = preference.equals(Constants.sPreferenceRequired); 1193 iIsProhibited = preference.equals(Constants.sPreferenceProhibited); 1194 iPreference = Constants.preference2preferenceLevel(preference); 1195 } 1196 1197 /** Constraint id 1198 * @return constraint unique id 1199 **/ 1200 public Long getConstraintId() { 1201 return iConstraintId; 1202 } 1203 1204 @Override 1205 public long getId() { 1206 return (iConstraintId == null ? -1 : iConstraintId.longValue()); 1207 } 1208 1209 /** Generated unique id 1210 * @return generated unique id 1211 **/ 1212 protected long getGeneratedId() { 1213 return iId; 1214 } 1215 1216 /** Return constraint type (e.g, {@link ConstraintType#SAME_TIME}) 1217 * @return constraint type 1218 **/ 1219 public ConstraintTypeInterface getType() { 1220 return iType; 1221 } 1222 1223 /** 1224 * Set constraint type 1225 * @param type constraint type 1226 */ 1227 public void setType(ConstraintType type) { 1228 iType = type; 1229 } 1230 1231 /** Is constraint required 1232 * @return true if required 1233 **/ 1234 public boolean isRequired() { 1235 return iIsRequired; 1236 } 1237 1238 /** Is constraint prohibited 1239 * @return true if prohibited 1240 **/ 1241 public boolean isProhibited() { 1242 return iIsProhibited; 1243 } 1244 1245 /** 1246 * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for 1247 * preference 1248 * @return prolog preference 1249 */ 1250 public String getPrologPreference() { 1251 return Constants.preferenceLevel2preference(iPreference); 1252 } 1253 1254 @Override 1255 public boolean isConsistent(Placement value1, Placement value2) { 1256 if (!isHard()) 1257 return true; 1258 if (!isSatisfiedPair(null, value1, value2)) 1259 return false; 1260 if (getType().is(Flag.BACK_TO_BACK)) { 1261 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1262 assignments.put(value1.variable(), value1); 1263 assignments.put(value2.variable(), value2); 1264 if (!isSatisfiedSeq(null, assignments, null)) 1265 return false; 1266 } 1267 if (getType().is(Flag.MAX_HRS_DAY)) { 1268 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1269 assignments.put(value1.variable(), value1); 1270 assignments.put(value2.variable(), value2); 1271 for (int dayCode: Constants.DAY_CODES) { 1272 if (iMaxNHoursADayConsiderDatePatterns) { 1273 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1274 if (!value1.getTimeLocation().shareWeeks(week) && !value2.getTimeLocation().shareWeeks(week)) continue; 1275 if (nrSlotsADay(null, dayCode, week, assignments, null) > getType().getMax()) return false; 1276 } 1277 } else { 1278 if (nrSlotsADay(null, dayCode, null, assignments, null) > getType().getMax()) return false; 1279 } 1280 } 1281 } 1282 return true; 1283 } 1284 1285 @Override 1286 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 1287 computeConflicts(assignment, value, conflicts, true); 1288 } 1289 1290 @Override 1291 public void computeConflictsNoForwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 1292 computeConflicts(assignment, value, conflicts, false); 1293 } 1294 1295 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, boolean fwdCheck) { 1296 if (!isHard()) 1297 return; 1298 for (Lecture v : variables()) { 1299 if (v.equals(value.variable())) 1300 continue; // ignore this variable 1301 Placement p = assignment.getValue(v); 1302 if (p == null) 1303 continue; // there is an unassigned variable -- great, still a chance to get violated 1304 if (!isSatisfiedPair(assignment, p, value)) 1305 conflicts.add(p); 1306 } 1307 if (getType().is(Flag.BACK_TO_BACK)) { 1308 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1309 assignments.put(value.variable(), value); 1310 if (!isSatisfiedSeq(assignment, assignments, conflicts)) 1311 conflicts.add(value); 1312 } 1313 if (getType().is(Flag.MAX_HRS_DAY)) { 1314 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1315 assignments.put(value.variable(), value); 1316 for (int dayCode: Constants.DAY_CODES) { 1317 if (iMaxNHoursADayConsiderDatePatterns) { 1318 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1319 if (!value.getTimeLocation().shareWeeks(week)) continue; 1320 if (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax()) { 1321 List<Placement> adepts = new ArrayList<Placement>(); 1322 for (Lecture l: variables()) { 1323 if (l.equals(value.variable()) || l.isConstant()) continue; 1324 Placement p = assignment.getValue(l); 1325 if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue; 1326 if ((p.getTimeLocation().getDayCode() & dayCode) == 0 || !p.getTimeLocation().shareWeeks(week)) continue; 1327 adepts.add(p); 1328 } 1329 do { 1330 if (adepts.isEmpty()) { conflicts.add(value); break; } 1331 Placement conflict = ToolBox.random(adepts); 1332 adepts.remove(conflict); 1333 conflicts.add(conflict); 1334 } while (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax()); 1335 } 1336 } 1337 } else { 1338 if (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax()) { 1339 List<Placement> adepts = new ArrayList<Placement>(); 1340 for (Lecture l: variables()) { 1341 if (l.equals(value.variable()) || l.isConstant()) continue; 1342 Placement p = assignment.getValue(l); 1343 if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue; 1344 if ((p.getTimeLocation().getDayCode() & dayCode) == 0) continue; 1345 adepts.add(p); 1346 } 1347 do { 1348 if (adepts.isEmpty()) { conflicts.add(value); break; } 1349 Placement conflict = ToolBox.random(adepts); 1350 adepts.remove(conflict); 1351 conflicts.add(conflict); 1352 } while (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax()); 1353 } 1354 } 1355 } 1356 } 1357 1358 // Forward checking 1359 if (fwdCheck) forwardCheck(assignment, value, conflicts, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1); 1360 } 1361 1362 public void forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, Set<GroupConstraint> ignore, int depth) { 1363 try { 1364 if (depth < 0) return; 1365 ignore.add(this); 1366 1367 List<Placement> neededSize = null; 1368 1369 for (Lecture lecture: variables()) { 1370 if (conflicts.contains(value)) break; // already conflicting 1371 1372 if (lecture.equals(value.variable())) continue; // Skip this lecture 1373 Placement current = assignment.getValue(lecture); 1374 if (current != null) { // Has assignment, check whether it is conflicting 1375 if (isSatisfiedPair(assignment, value, current)) { 1376 // Increase needed size if the assignment is of the same room and overlapping in time 1377 if (canShareRoom() && sameRoomAndOverlaps(value, current)) { 1378 if (neededSize == null) neededSize = new ArrayList<Placement>(); 1379 neededSize.add(current); 1380 } 1381 continue; 1382 } 1383 conflicts.add(current); 1384 } 1385 1386 // Look for supporting assignments assignment 1387 boolean shareRoomAndOverlaps = canShareRoom(); 1388 Placement support = null; 1389 int nrSupports = 0; 1390 if (lecture.nrValues() >= iForwardCheckMaxDomainSize) { 1391 // ignore variables with large domains 1392 return; 1393 } 1394 List<Placement> values = lecture.values(assignment); 1395 if (values.isEmpty()) { 1396 // ignore variables with empty domain 1397 return; 1398 } 1399 for (Placement other: values) { 1400 if (nrSupports < 2) { 1401 if (isSatisfiedPair(assignment, value, other)) { 1402 if (support == null) support = other; 1403 nrSupports ++; 1404 if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other)) 1405 shareRoomAndOverlaps = false; 1406 } 1407 } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) { 1408 shareRoomAndOverlaps = false; 1409 } 1410 if (nrSupports > 1 && !shareRoomAndOverlaps) 1411 break; 1412 } 1413 1414 // No supporting assignment -> fail 1415 if (nrSupports == 0) { 1416 conflicts.add(value); // other class cannot be assigned with this value 1417 return; 1418 } 1419 // Increase needed size if all supporters are of the same room and in overlapping times 1420 if (shareRoomAndOverlaps && support != null) { 1421 if (neededSize == null) neededSize = new ArrayList<Placement>(); 1422 neededSize.add(support); 1423 } 1424 1425 // Only one supporter -> propagate the new assignment over other hard constraints of the lecture 1426 if (nrSupports == 1) { 1427 for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) { 1428 if (other instanceof WeakeningConstraint) continue; 1429 if (other instanceof GroupConstraint) { 1430 GroupConstraint gc = (GroupConstraint)other; 1431 if (depth > 0 && !ignore.contains(gc)) 1432 gc.forwardCheck(assignment, support, conflicts, ignore, depth - 1); 1433 } else { 1434 other.computeConflicts(assignment, support, conflicts); 1435 } 1436 } 1437 for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) { 1438 if (other instanceof WeakeningConstraint) continue; 1439 other.computeConflicts(assignment, support, conflicts); 1440 } 1441 1442 if (conflicts.contains(support)) 1443 conflicts.add(value); 1444 } 1445 } 1446 1447 if (canShareRoom() && neededSize != null) { 1448 if (value.getRoomLocations() != null) { 1449 for (RoomLocation room: value.getRoomLocations()) 1450 if (room.getRoomConstraint() != null && !room.getRoomConstraint().checkRoomSize(value, neededSize)) { 1451 // room is too small to fit all meet with classes 1452 conflicts.add(value); 1453 } 1454 } else if (value.getRoomLocation() != null) { 1455 RoomLocation room = value.getRoomLocation(); 1456 if (room.getRoomConstraint() != null && !room.getRoomConstraint().checkRoomSize(value, neededSize)) { 1457 // room is too small to fit all meet with classes 1458 conflicts.add(value); 1459 } 1460 } 1461 } 1462 } finally { 1463 ignore.remove(this); 1464 } 1465 } 1466 1467 @Override 1468 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) { 1469 if (!isHard()) 1470 return false; 1471 for (Lecture v : variables()) { 1472 if (v.equals(value.variable())) 1473 continue; // ignore this variable 1474 Placement p = assignment.getValue(v); 1475 if (p == null) 1476 continue; // there is an unassigned variable -- great, still a chance to get violated 1477 if (!isSatisfiedPair(assignment, p, value)) 1478 return true; 1479 } 1480 if (getType().is(Flag.BACK_TO_BACK)) { 1481 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1482 assignments.put(value.variable(), value); 1483 if (!isSatisfiedSeq(assignment, assignments, null)) 1484 return true; 1485 } 1486 if (getType().is(Flag.MAX_HRS_DAY)) { 1487 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1488 assignments.put(value.variable(), value); 1489 for (int dayCode: Constants.DAY_CODES) { 1490 if (iMaxNHoursADayConsiderDatePatterns) { 1491 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1492 if (!value.getTimeLocation().shareWeeks(week)) continue; 1493 if (nrSlotsADay(assignment, dayCode, week, assignments, null) > getType().getMax()) 1494 return true; 1495 } 1496 } else { 1497 if (nrSlotsADay(assignment, dayCode, null, assignments, null) > getType().getMax()) return true; 1498 } 1499 } 1500 } 1501 1502 if (!forwardCheck(assignment, value, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1)) return true; 1503 1504 return false; 1505 } 1506 1507 public boolean forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<GroupConstraint> ignore, int depth) { 1508 try { 1509 if (depth < 0) return true; 1510 ignore.add(this); 1511 1512 int neededSize = value.variable().maxRoomUse(); 1513 1514 for (Lecture lecture: variables()) { 1515 if (lecture.equals(value.variable())) continue; // Skip this lecture 1516 Placement current = assignment.getValue(lecture); 1517 if (current != null) { // Has assignment, check whether it is conflicting 1518 if (isSatisfiedPair(assignment, value, current)) { 1519 // Increase needed size if the assignment is of the same room and overlapping in time 1520 if (canShareRoom() && sameRoomAndOverlaps(value, current)) { 1521 neededSize += lecture.maxRoomUse(); 1522 } 1523 continue; 1524 } 1525 return false; 1526 } 1527 1528 // Look for supporting assignments assignment 1529 boolean shareRoomAndOverlaps = canShareRoom(); 1530 Placement support = null; 1531 int nrSupports = 0; 1532 if (lecture.nrValues() >= iForwardCheckMaxDomainSize) { 1533 // ignore variables with large domains 1534 return true; 1535 } 1536 List<Placement> values = lecture.values(assignment); 1537 if (values.isEmpty()) { 1538 // ignore variables with empty domain 1539 return true; 1540 } 1541 for (Placement other: lecture.values(assignment)) { 1542 if (nrSupports < 2) { 1543 if (isSatisfiedPair(assignment, value, other)) { 1544 if (support == null) support = other; 1545 nrSupports ++; 1546 if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other)) 1547 shareRoomAndOverlaps = false; 1548 } 1549 } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) { 1550 shareRoomAndOverlaps = false; 1551 } 1552 if (nrSupports > 1 && !shareRoomAndOverlaps) 1553 break; 1554 } 1555 1556 // No supporting assignment -> fail 1557 if (nrSupports == 0) { 1558 return false; // other class cannot be assigned with this value 1559 } 1560 // Increase needed size if all supporters are of the same room and in overlapping times 1561 if (shareRoomAndOverlaps) { 1562 neededSize += lecture.maxRoomUse(); 1563 } 1564 1565 // Only one supporter -> propagate the new assignment over other hard constraints of the lecture 1566 if (nrSupports == 1) { 1567 for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) { 1568 if (other instanceof WeakeningConstraint) continue; 1569 if (other instanceof GroupConstraint) { 1570 GroupConstraint gc = (GroupConstraint)other; 1571 if (depth > 0 && !ignore.contains(gc) && !gc.forwardCheck(assignment, support, ignore, depth - 1)) return false; 1572 } else { 1573 if (other.inConflict(assignment, support)) return false; 1574 } 1575 } 1576 for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) { 1577 if (other instanceof WeakeningConstraint) continue; 1578 if (other.inConflict(assignment, support)) return false; 1579 } 1580 } 1581 } 1582 1583 if (canShareRoom() && neededSize > value.getRoomSize()) { 1584 // room is too small to fit all meet with classes 1585 return false; 1586 } 1587 1588 return true; 1589 } finally { 1590 ignore.remove(this); 1591 } 1592 } 1593 1594 /** Constraint preference (0 if prohibited or required) 1595 * @return constraint preference (if soft) 1596 **/ 1597 public int getPreference() { 1598 return iPreference; 1599 } 1600 1601 /** 1602 * Current constraint preference (0 if prohibited or required, depends on 1603 * current satisfaction of the constraint) 1604 * @param assignment current assignment 1605 * @return current preference 1606 */ 1607 public int getCurrentPreference(Assignment<Lecture, Placement> assignment) { 1608 if (isHard()) return 0; // no preference 1609 if (countAssignedVariables(assignment) < 2) return - Math.abs(iPreference); // not enough variable 1610 if (getType().is(Flag.MAX_HRS_DAY)) { // max hours a day 1611 int over = 0; 1612 for (int dayCode: Constants.DAY_CODES) { 1613 if (iMaxNHoursADayConsiderDatePatterns) { 1614 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) 1615 over += Math.max(0, nrSlotsADay(assignment, dayCode, week, null, null) - getType().getMax()); 1616 } else { 1617 over += Math.max(0, nrSlotsADay(assignment, dayCode, null, null, null) - getType().getMax()); 1618 } 1619 } 1620 return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference)); 1621 } 1622 int nrViolatedPairs = 0; 1623 for (Lecture v1 : variables()) { 1624 Placement p1 = assignment.getValue(v1); 1625 if (p1 == null) continue; 1626 for (Lecture v2 : variables()) { 1627 Placement p2 = assignment.getValue(v2); 1628 if (p2 == null || v1.getId() >= v2.getId()) continue; 1629 if (!isSatisfiedPair(assignment, p1, p2)) nrViolatedPairs++; 1630 } 1631 } 1632 if (getType().is(Flag.BACK_TO_BACK)) { 1633 Set<Placement> conflicts = new HashSet<Placement>(); 1634 if (isSatisfiedSeq(assignment, new HashMap<Lecture, Placement>(), conflicts)) 1635 nrViolatedPairs += conflicts.size(); 1636 else 1637 nrViolatedPairs = variables().size(); 1638 } 1639 return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference)); 1640 } 1641 1642 /** Current constraint preference change (if given placement is assigned) 1643 * @param assignment current assignment 1644 * @param placement placement that is being considered 1645 * @return change in the current preference, if assigned 1646 **/ 1647 public int getCurrentPreference(Assignment<Lecture, Placement> assignment, Placement placement) { 1648 if (isHard()) return 0; // no preference 1649 if (countAssignedVariables(assignment) + (assignment.getValue(placement.variable()) == null ? 1 : 0) < 2) return 0; // not enough variable 1650 if (getType().is(Flag.MAX_HRS_DAY)) { 1651 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1652 assignments.put(placement.variable(), placement); 1653 HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>(); 1654 unassignments.put(placement.variable(), null); 1655 int after = 0; 1656 int before = 0; 1657 for (int dayCode: Constants.DAY_CODES) { 1658 if (iMaxNHoursADayConsiderDatePatterns) { 1659 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1660 after += Math.max(0, nrSlotsADay(assignment, dayCode, week, assignments, null) - getType().getMax()); 1661 before += Math.max(0, nrSlotsADay(assignment, dayCode, week, unassignments, null) - getType().getMax()); 1662 } 1663 } else { 1664 after += Math.max(0, nrSlotsADay(assignment, dayCode, null, assignments, null) - getType().getMax()); 1665 before += Math.max(0, nrSlotsADay(assignment, dayCode, null, unassignments, null) - getType().getMax()); 1666 } 1667 } 1668 return (after > 0 ? Math.abs(iPreference) * after / 12 : - Math.abs(iPreference)) - (before > 0 ? Math.abs(iPreference) * before / 12 : - Math.abs(iPreference)); 1669 } 1670 1671 int nrViolatedPairsAfter = 0; 1672 int nrViolatedPairsBefore = 0; 1673 for (Lecture v1 : variables()) { 1674 for (Lecture v2 : variables()) { 1675 if (v1.getId() >= v2.getId()) continue; 1676 Placement p1 = (v1.equals(placement.variable()) ? null : assignment.getValue(v1)); 1677 Placement p2 = (v2.equals(placement.variable()) ? null : assignment.getValue(v2)); 1678 if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2)) 1679 nrViolatedPairsBefore ++; 1680 if (v1.equals(placement.variable())) p1 = placement; 1681 if (v2.equals(placement.variable())) p2 = placement; 1682 if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2)) 1683 nrViolatedPairsAfter ++; 1684 } 1685 } 1686 1687 if (getType().is(Flag.BACK_TO_BACK)) { 1688 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1689 assignments.put(placement.variable(), placement); 1690 Set<Placement> conflicts = new HashSet<Placement>(); 1691 if (isSatisfiedSeq(assignment, assignments, conflicts)) 1692 nrViolatedPairsAfter += conflicts.size(); 1693 else 1694 nrViolatedPairsAfter = variables().size(); 1695 1696 HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>(); 1697 unassignments.put(placement.variable(), null); 1698 Set<Placement> previous = new HashSet<Placement>(); 1699 if (isSatisfiedSeq(assignment, unassignments, previous)) 1700 nrViolatedPairsBefore += previous.size(); 1701 else 1702 nrViolatedPairsBefore = variables().size(); 1703 } 1704 1705 return (nrViolatedPairsAfter > 0 ? Math.abs(iPreference) * nrViolatedPairsAfter : - Math.abs(iPreference)) - 1706 (nrViolatedPairsBefore > 0 ? Math.abs(iPreference) * nrViolatedPairsBefore : - Math.abs(iPreference)); 1707 } 1708 1709 @Override 1710 public String toString() { 1711 StringBuffer sb = new StringBuffer(); 1712 sb.append(getName()); 1713 sb.append(" between "); 1714 for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) { 1715 Lecture v = e.next(); 1716 sb.append(v.getName()); 1717 if (e.hasNext()) 1718 sb.append(", "); 1719 } 1720 return sb.toString(); 1721 } 1722 1723 @Override 1724 public boolean isHard() { 1725 return iIsRequired || iIsProhibited; 1726 } 1727 1728 @Override 1729 public String getName() { 1730 return getType().getName(); 1731 } 1732 1733 1734 private boolean isPrecedence(Placement p1, Placement p2, boolean firstGoesFirst, boolean considerDatePatterns) { 1735 int ord1 = variables().indexOf(p1.variable()); 1736 int ord2 = variables().indexOf(p2.variable()); 1737 TimeLocation t1 = null, t2 = null; 1738 if (ord1 < ord2) { 1739 if (firstGoesFirst) { 1740 t1 = p1.getTimeLocation(); 1741 t2 = p2.getTimeLocation(); 1742 } else { 1743 t2 = p1.getTimeLocation(); 1744 t1 = p2.getTimeLocation(); 1745 } 1746 } else { 1747 if (!firstGoesFirst) { 1748 t1 = p1.getTimeLocation(); 1749 t2 = p2.getTimeLocation(); 1750 } else { 1751 t2 = p1.getTimeLocation(); 1752 t1 = p2.getTimeLocation(); 1753 } 1754 } 1755 if (considerDatePatterns && iPrecedenceConsiderDatePatterns) { 1756 if (iPrecedenceSkipSameDatePatternCheck) { 1757 int m1 = t1.getFirstMeeting(iDayOfWeekOffset), m2 = t2.getFirstMeeting(iDayOfWeekOffset); 1758 if (m1 != m2) return m1 < m2; 1759 } else { 1760 boolean sameDatePattern = (t1.getDatePatternId() != null ? t1.getDatePatternId().equals(t2.getDatePatternId()) : t1.getWeekCode().equals(t2.getWeekCode())); 1761 if (!sameDatePattern) { 1762 int m1 = t1.getFirstMeeting(iDayOfWeekOffset), m2 = t2.getFirstMeeting(iDayOfWeekOffset); 1763 if (m1 != m2) return m1 < m2; 1764 } 1765 } 1766 } 1767 if (iFirstWorkDay != 0) { 1768 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1769 int idx = (i + iFirstWorkDay) % 7; 1770 boolean a = (t1.getDayCode() & Constants.DAY_CODES[idx]) != 0; 1771 boolean b = (t2.getDayCode() & Constants.DAY_CODES[idx]) != 0; 1772 if (b && !a) return false; // second start first 1773 if (a && !b) return true; // first start first 1774 if (a && b) return t1.getStartSlot() + t1.getLength() <= t2.getStartSlot(); // same day: check times 1775 } 1776 } 1777 return t1.getStartSlots().nextElement() + t1.getLength() <= t2.getStartSlots().nextElement(); 1778 } 1779 1780 private boolean isBackToBackDays(TimeLocation t1, TimeLocation t2) { 1781 int f1 = -1, f2 = -1, e1 = -1, e2 = -1; 1782 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1783 int idx = (i + iFirstWorkDay) % 7; 1784 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1785 if (f1 < 0) 1786 f1 = i; 1787 e1 = i; 1788 } 1789 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1790 if (f2 < 0) 1791 f2 = i; 1792 e2 = i; 1793 } 1794 } 1795 return (e1 + 1 == f2) || (e2 + 1 == f1); 1796 } 1797 1798 private boolean isNrDaysBetweenGreaterThanOne(TimeLocation t1, TimeLocation t2) { 1799 int f1 = -1, f2 = -1, e1 = -1, e2 = -1; 1800 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1801 int idx = (i + iFirstWorkDay) % 7; 1802 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1803 if (f1 < 0) 1804 f1 = i; 1805 e1 = i; 1806 } 1807 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1808 if (f2 < 0) 1809 f2 = i; 1810 e2 = i; 1811 } 1812 } 1813 return (e1 - f2 > 2) || (e2 - f1 > 2); 1814 } 1815 1816 private boolean isFollowingDay(Placement p1, Placement p2, boolean firstGoesFirst) { 1817 int ord1 = variables().indexOf(p1.variable()); 1818 int ord2 = variables().indexOf(p2.variable()); 1819 TimeLocation t1 = null, t2 = null; 1820 if (ord1 < ord2) { 1821 if (firstGoesFirst) { 1822 t1 = p1.getTimeLocation(); 1823 t2 = p2.getTimeLocation(); 1824 } else { 1825 t2 = p1.getTimeLocation(); 1826 t1 = p2.getTimeLocation(); 1827 } 1828 } else { 1829 if (!firstGoesFirst) { 1830 t1 = p1.getTimeLocation(); 1831 t2 = p2.getTimeLocation(); 1832 } else { 1833 t2 = p1.getTimeLocation(); 1834 t1 = p2.getTimeLocation(); 1835 } 1836 } 1837 int f1 = -1, f2 = -1, e1 = -1; 1838 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1839 int idx = (i + iFirstWorkDay) % 7; 1840 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1841 if (f1 < 0) 1842 f1 = i; 1843 e1 = i; 1844 } 1845 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1846 if (f2 < 0) 1847 f2 = i; 1848 } 1849 } 1850 return ((e1 + 1) % iNrWorkDays == f2); 1851 } 1852 1853 private boolean isEveryOtherDay(Placement p1, Placement p2, boolean firstGoesFirst) { 1854 int ord1 = variables().indexOf(p1.variable()); 1855 int ord2 = variables().indexOf(p2.variable()); 1856 TimeLocation t1 = null, t2 = null; 1857 if (ord1 < ord2) { 1858 if (firstGoesFirst) { 1859 t1 = p1.getTimeLocation(); 1860 t2 = p2.getTimeLocation(); 1861 } else { 1862 t2 = p1.getTimeLocation(); 1863 t1 = p2.getTimeLocation(); 1864 } 1865 } else { 1866 if (!firstGoesFirst) { 1867 t1 = p1.getTimeLocation(); 1868 t2 = p2.getTimeLocation(); 1869 } else { 1870 t2 = p1.getTimeLocation(); 1871 t1 = p2.getTimeLocation(); 1872 } 1873 } 1874 int f1 = -1, f2 = -1, e1 = -1; 1875 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1876 int idx = (i + iFirstWorkDay) % 7; 1877 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1878 if (f1 < 0) 1879 f1 = i; 1880 e1 = i; 1881 } 1882 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1883 if (f2 < 0) 1884 f2 = i; 1885 } 1886 } 1887 return ((e1 + 2) % iNrWorkDays == f2); 1888 } 1889 1890 private static boolean sameDays(int[] days1, int[] days2) { 1891 if (days2.length < days1.length) 1892 return sameDays(days2, days1); 1893 int i2 = 0; 1894 for (int i1 = 0; i1 < days1.length; i1++) { 1895 int d1 = days1[i1]; 1896 while (true) { 1897 if (i2 == days2.length) 1898 return false; 1899 int d2 = days2[i2]; 1900 if (d1 == d2) 1901 break; 1902 i2++; 1903 if (i2 == days2.length) 1904 return false; 1905 } 1906 i2++; 1907 } 1908 return true; 1909 } 1910 1911 private static boolean sameRoomAndOverlaps(Placement p1, Placement p2) { 1912 return p1.shareRooms(p2) && p1.getTimeLocation() != null && p2.getTimeLocation() != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation()); 1913 } 1914 1915 private static boolean sameHours(int start1, int len1, int start2, int len2) { 1916 if (len1 > len2) 1917 return sameHours(start2, len2, start1, len1); 1918 start1 %= Constants.SLOTS_PER_DAY; 1919 start2 %= Constants.SLOTS_PER_DAY; 1920 return (start1 >= start2 && start1 + len1 <= start2 + len2); 1921 } 1922 1923 private static boolean canFill(int totalGap, int gapMin, int gapMax, List<Integer> lengths) { 1924 if (gapMin <= totalGap && totalGap <= gapMax) 1925 return true; 1926 if (totalGap < 2 * gapMin) 1927 return false; 1928 for (int i = 0; i < lengths.size(); i++) { 1929 int length = lengths.get(i); 1930 lengths.remove(i); 1931 for (int gap = gapMin; gap <= gapMax; gap++) 1932 if (canFill(totalGap - gap - length, gapMin, gapMax, lengths)) 1933 return true; 1934 lengths.add(i, length); 1935 } 1936 return false; 1937 } 1938 1939 private boolean isSatisfiedSeq(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 1940 if (conflicts == null) 1941 return isSatisfiedSeqCheck(assignment, assignments, conflicts); 1942 else { 1943 Set<Placement> bestConflicts = isSatisfiedRecursive(assignment, 0, assignments, conflicts, 1944 new HashSet<Placement>(), null); 1945 if (bestConflicts == null) 1946 return false; 1947 conflicts.addAll(bestConflicts); 1948 return true; 1949 } 1950 } 1951 1952 private Set<Placement> isSatisfiedRecursive(Assignment<Lecture, Placement> assignment, int idx, HashMap<Lecture, Placement> assignments, 1953 Set<Placement> conflicts, Set<Placement> newConflicts, Set<Placement> bestConflicts) { 1954 if (idx == variables().size() && newConflicts.isEmpty()) 1955 return bestConflicts; 1956 if (isSatisfiedSeqCheck(assignment, assignments, conflicts)) { 1957 if (bestConflicts == null) { 1958 return new HashSet<Placement>(newConflicts); 1959 } else { 1960 int b = 0, n = 0; 1961 for (Placement value: assignments.values()) { 1962 if (value != null && bestConflicts.contains(value)) b++; 1963 if (value != null && newConflicts.contains(value)) n++; 1964 } 1965 if (n < b || (n == b && newConflicts.size() < bestConflicts.size())) 1966 return new HashSet<Placement>(newConflicts); 1967 } 1968 return bestConflicts; 1969 } 1970 if (idx == variables().size()) 1971 return bestConflicts; 1972 bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts, 1973 bestConflicts); 1974 Lecture lecture = variables().get(idx); 1975 //if (assignments != null && assignments.containsKey(lecture)) 1976 // return bestConflicts; 1977 Placement placement = null; 1978 if (assignments != null && assignments.containsKey(lecture)) 1979 placement = assignments.get(lecture); 1980 else if (assignment != null) 1981 placement = assignment.getValue(lecture); 1982 if (placement == null) 1983 return bestConflicts; 1984 if (conflicts != null && conflicts.contains(placement)) 1985 return bestConflicts; 1986 conflicts.add(placement); 1987 newConflicts.add(placement); 1988 bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts, bestConflicts); 1989 newConflicts.remove(placement); 1990 conflicts.remove(placement); 1991 return bestConflicts; 1992 } 1993 1994 private boolean isSatisfiedSeqCheck(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 1995 if (!getType().is(Flag.BACK_TO_BACK)) return true; 1996 int gapMin = getType().getMin(); 1997 int gapMax = getType().getMax(); 1998 1999 List<Integer> lengths = new ArrayList<Integer>(); 2000 2001 Placement[] res = new Placement[Constants.SLOTS_PER_DAY]; 2002 for (int i = 0; i < Constants.SLOTS_PER_DAY; i++) 2003 res[i] = null; 2004 2005 int nrLectures = 0; 2006 2007 for (Lecture lecture : variables()) { 2008 Placement placement = null; 2009 if (assignments != null && assignments.containsKey(lecture)) 2010 placement = assignments.get(lecture); 2011 else if (assignment != null) 2012 placement = assignment.getValue(lecture); 2013 if (placement == null) { 2014 if (!lecture.timeLocations().isEmpty()) 2015 lengths.add(lecture.timeLocations().get(0).getLength()); 2016 } else if (conflicts != null && conflicts.contains(placement)) { 2017 if (!lecture.timeLocations().isEmpty()) 2018 lengths.add(lecture.timeLocations().get(0).getLength()); 2019 } else { 2020 int pos = placement.getTimeLocation().getStartSlot(); 2021 int length = placement.getTimeLocation().getLength(); 2022 for (int j = pos; j < pos + length; j++) { 2023 if (res[j] != null) { 2024 if (conflicts == null) 2025 return false; 2026 if (!assignments.containsKey(lecture)) 2027 conflicts.add(placement); 2028 else if (!assignments.containsKey(res[j].variable())) 2029 conflicts.add(res[j]); 2030 } 2031 } 2032 for (int j = pos; j < pos + length; j++) 2033 res[j] = placement; 2034 nrLectures++; 2035 } 2036 } 2037 if (nrLectures <= 1) 2038 return true; 2039 2040 if (iIsRequired || (!iIsProhibited && iPreference < 0)) { 2041 int i = 0; 2042 Placement p = res[i]; 2043 while (p == null) 2044 p = res[++i]; 2045 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 2046 nrLectures--; 2047 while (nrLectures > 0) { 2048 int gap = 0; 2049 while (i < Constants.SLOTS_PER_DAY && res[i] == null) { 2050 gap++; 2051 i++; 2052 } 2053 if (i == Constants.SLOTS_PER_DAY) 2054 break; 2055 if (!canFill(gap, gapMin, gapMax, lengths)) 2056 return false; 2057 p = res[i]; 2058 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 2059 nrLectures--; 2060 } 2061 } else if (iIsProhibited || (!iIsRequired && iPreference > 0)) { 2062 int i = 0; 2063 Placement p = res[i]; 2064 while (p == null) 2065 p = res[++i]; 2066 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 2067 nrLectures--; 2068 while (nrLectures > 0) { 2069 int gap = 0; 2070 while (i < Constants.SLOTS_PER_DAY && res[i] == null) { 2071 gap++; 2072 i++; 2073 } 2074 if (i == Constants.SLOTS_PER_DAY) 2075 break; 2076 if ((gapMin == 0 || !canFill(gap, 0, gapMin - 1, lengths)) 2077 && (gapMax >= Constants.SLOTS_PER_DAY || !canFill(gap, gapMax + 1, Constants.SLOTS_PER_DAY, 2078 lengths))) { 2079 return false; 2080 } 2081 p = res[i]; 2082 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 2083 nrLectures--; 2084 } 2085 } 2086 return true; 2087 } 2088 2089 public boolean isSatisfied(Assignment<Lecture, Placement> assignment) { 2090 if (isHard()) return true; 2091 if (countAssignedVariables(assignment) < 2) return true; 2092 if (getPreference() == 0) return true; 2093 return isHard() || countAssignedVariables(assignment) < 2 || getPreference() == 0 || getCurrentPreference(assignment) < 0; 2094 } 2095 2096 public boolean isChildrenNotOverlap(Assignment<Lecture, Placement> assignment, Lecture lec1, Placement plc1, Lecture lec2, Placement plc2) { 2097 if (lec1.getSchedulingSubpartId().equals(lec2.getSchedulingSubpartId())) { 2098 // same subpart 2099 boolean overlap = plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 2100 2101 if (overlap && lec1.getParent() != null && variables().contains(lec1.getParent()) 2102 && lec2.getParent() != null && variables().contains(lec2.getParent())) { 2103 // children overlaps 2104 Placement p1 = assignment.getValue(lec1.getParent()); 2105 Placement p2 = assignment.getValue(lec2.getParent()); 2106 // parents not overlap, but children do 2107 if (p1 != null && p2 != null && !p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) 2108 return false; 2109 } 2110 2111 if (!overlap && lec1.getChildrenSubpartIds() != null && lec2.getChildrenSubpartIds() != null) { 2112 // parents not overlap 2113 for (Long subpartId: lec1.getChildrenSubpartIds()) { 2114 for (Lecture c1 : lec1.getChildren(subpartId)) { 2115 Placement p1 = assignment.getValue(c1); 2116 if (p1 == null) continue; 2117 for (Lecture c2 : lec2.getChildren(subpartId)) { 2118 Placement p2 = assignment.getValue(c2); 2119 if (p2 == null) continue; 2120 if (!c1.getSchedulingSubpartId().equals(c2.getSchedulingSubpartId())) continue; 2121 // parents not overlap, but children do 2122 if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) 2123 return false; 2124 } 2125 } 2126 } 2127 } 2128 } else { 2129 // different subpart 2130 } 2131 return true; 2132 } 2133 2134 public boolean isSatisfiedPair(Assignment<Lecture, Placement> assignment, Placement plc1, Placement plc2) { 2135 if (iIsRequired || (!iIsProhibited && iPreference <= 0)) 2136 return getType().isSatisfied(assignment, this, plc1, plc2); 2137 else if (iIsProhibited || (!iIsRequired && iPreference > 0)) 2138 return getType().isViolated(assignment, this, plc1, plc2); 2139 return true; 2140 } 2141 2142 public boolean canShareRoom() { 2143 return getType().is(Flag.CAN_SHARE_ROOM); 2144 } 2145 2146 protected int nrSlotsADay(Assignment<Lecture, Placement> assignment, int dayCode, BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 2147 Set<Integer> slots = new HashSet<Integer>(); 2148 for (Lecture lecture: variables()) { 2149 Placement placement = null; 2150 if (assignments != null && assignments.containsKey(lecture)) 2151 placement = assignments.get(lecture); 2152 else if (assignment != null) 2153 placement = assignment.getValue(lecture); 2154 if (placement == null || placement.getTimeLocation() == null) continue; 2155 if (conflicts != null && conflicts.contains(placement)) continue; 2156 TimeLocation t = placement.getTimeLocation(); 2157 if (t == null || (t.getDayCode() & dayCode) == 0 || (week != null && !t.shareWeeks(week))) continue; 2158 for (int i = 0; i < t.getLength(); i++) 2159 slots.add(i + t.getStartSlot()); 2160 } 2161 return slots.size(); 2162 } 2163 2164 @Override 2165 public boolean equals(Object o) { 2166 if (o == null || !(o instanceof GroupConstraint)) return false; 2167 return getGeneratedId() == ((GroupConstraint) o).getGeneratedId(); 2168 } 2169 2170 @Override 2171 public GroupConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 2172 return new GroupConstraintContext(assignment); 2173 } 2174 2175 public class GroupConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 2176 protected int iLastPreference = 0; 2177 2178 public GroupConstraintContext(Assignment<Lecture, Placement> assignment) { 2179 updateCriterion(assignment); 2180 } 2181 2182 @Override 2183 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 2184 updateCriterion(assignment); 2185 } 2186 2187 @Override 2188 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 2189 updateCriterion(assignment); 2190 } 2191 2192 protected void updateCriterion(Assignment<Lecture, Placement> assignment) { 2193 if (!isHard()) { 2194 getModel().getCriterion(DistributionPreferences.class).inc(assignment, -iLastPreference); 2195 iLastPreference = getCurrentPreference(assignment) + Math.abs(iPreference); 2196 getModel().getCriterion(DistributionPreferences.class).inc(assignment, iLastPreference); 2197 } 2198 } 2199 2200 public int getPreference() { return iLastPreference; } 2201 } 2202 2203 private boolean isBackToBackWeeks(TimeLocation t1, TimeLocation t2) { 2204 if (t1.shareWeeks(t2)) return false; 2205 int f1 = t1.getWeekCode().nextSetBit(0); 2206 int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size()); 2207 int f2 = t2.getWeekCode().nextSetBit(0); 2208 int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size()); 2209 if (e1 < f2) { 2210 return (f2 - e1) < 7; 2211 } else if (e2 < f1) { 2212 return (f1 - e2) < 7; 2213 } 2214 return false; 2215 } 2216 2217 private boolean isMaxWeekSpan(TimeLocation t1, TimeLocation t2, int nrWeeks) { 2218 if (t1.shareWeeks(t2)) return false; 2219 if (isBackToBackWeeks(t1, t2)) return true; 2220 2221 int f1 = t1.getWeekCode().nextSetBit(0); 2222 int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size()); 2223 int f2 = t2.getWeekCode().nextSetBit(0); 2224 int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size()); 2225 if (e1 < f2) { 2226 return (3 + e2 - f1) / 7 <= nrWeeks; 2227 } else if (e2 < f1) { 2228 return (3 + e1 - f2) / 7 <= nrWeeks; 2229 } 2230 return false; 2231 } 2232 2233 private boolean isNotBackToBackWeeks(TimeLocation t1, TimeLocation t2) { 2234 if (t1.shareWeeks(t2)) return false; 2235 int f1 = t1.getWeekCode().nextSetBit(0); 2236 int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size()); 2237 int f2 = t2.getWeekCode().nextSetBit(0); 2238 int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size()); 2239 if (e1 < f2) { 2240 return (f2 - e1) >= 7; 2241 } else if (e2 < f1) { 2242 return (f1 - e2) >= 7; 2243 } 2244 return false; 2245 } 2246 2247 private boolean isFollowingWeeksBTB(Placement p1, Placement p2, boolean btb) { 2248 int ord1 = variables().indexOf(p1.variable()); 2249 int ord2 = variables().indexOf(p2.variable()); 2250 TimeLocation t1, t2; 2251 boolean following = false; 2252 if (ord1 < ord2) { 2253 t1 = p1.getTimeLocation(); 2254 t2 = p2.getTimeLocation(); 2255 if (ord1 + 1 == ord2) following = true; 2256 } else { 2257 t2 = p1.getTimeLocation(); 2258 t1 = p2.getTimeLocation(); 2259 if (ord2 + 1 == ord1) following = true; 2260 } 2261 if (t1.shareWeeks(t2)) return false; 2262 int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size()); 2263 int s2 = t2.getWeekCode().nextSetBit(0); 2264 if (e1 >= s2) return false; 2265 if (!btb) // not back-to-back: any two classes must be at least a week apart 2266 return (s2 - e1) >= 7; 2267 else if (following) // back-to-back and following classes: must be within a week 2268 return (s2 - e1) < 7; 2269 else // back-to-back and not following: just the order 2270 return true; 2271 } 2272 2273 private boolean isDifferentDates(TimeLocation t1, TimeLocation t2) { 2274 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return true; 2275 for (Enumeration<Integer> e = t1.getDates(iDayOfWeekOffset); e.hasMoreElements(); ) { 2276 Integer date = e.nextElement(); 2277 if (t2.hasDate(date, iDayOfWeekOffset)) return false; 2278 } 2279 return true; 2280 } 2281 2282 private boolean isSameDates(TimeLocation t1, TimeLocation t2) { 2283 if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false; 2284 // t1 is meets less often 2285 if (t1.countDates(iDayOfWeekOffset) > t2.countDates(iDayOfWeekOffset)) { 2286 TimeLocation t = t1; t1 = t2; t2 = t; 2287 } 2288 for (Enumeration<Integer> e = t1.getDates(iDayOfWeekOffset); e.hasMoreElements(); ) { 2289 Integer date = e.nextElement(); 2290 if (!t2.hasDate(date, iDayOfWeekOffset)) return false; 2291 } 2292 return true; 2293 } 2294}