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