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