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