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