001 package net.sf.cpsolver.coursett.constraint; 002 003 import java.util.ArrayList; 004 import java.util.HashSet; 005 import java.util.HashMap; 006 import java.util.Iterator; 007 import java.util.List; 008 import java.util.Set; 009 010 import net.sf.cpsolver.coursett.Constants; 011 import net.sf.cpsolver.coursett.criteria.DistributionPreferences; 012 import net.sf.cpsolver.coursett.model.Lecture; 013 import net.sf.cpsolver.coursett.model.Placement; 014 import net.sf.cpsolver.coursett.model.TimeLocation; 015 import net.sf.cpsolver.coursett.model.TimetableModel; 016 import net.sf.cpsolver.ifs.model.Constraint; 017 import net.sf.cpsolver.ifs.model.GlobalConstraint; 018 import net.sf.cpsolver.ifs.model.Model; 019 import net.sf.cpsolver.ifs.util.DataProperties; 020 import net.sf.cpsolver.ifs.util.ToolBox; 021 022 /** 023 * Group constraint. <br> 024 * This constraint expresses relations between several classes, e.g., that two 025 * sections of the same lecture can not be taught at the same time, or that some 026 * classes have to be taught one immediately after another. It can be either 027 * hard or soft. <br> 028 * <br> 029 * Following constraints are now supported: 030 * <table border='1'> 031 * <tr> 032 * <th>Constraint</th> 033 * <th>Comment</th> 034 * </tr> 035 * <tr> 036 * <td>SAME_TIME</td> 037 * <td>Same time: given classes have to be taught in the same hours. If the 038 * classes are of different length, the smaller one cannot start before the 039 * longer one and it cannot end after the longer one.</td> 040 * </tr> 041 * <tr> 042 * <td>SAME_DAYS</td> 043 * <td>Same days: given classes have to be taught in the same day. If the 044 * classes are of different time patterns, the days of one class have to form a 045 * subset of the days of the other class.</td> 046 * </tr> 047 * <tr> 048 * <td>BTB</td> 049 * <td>Back-to-back constraint: given classes have to be taught in the same room 050 * and they have to follow one strictly after another.</td> 051 * </tr> 052 * <tr> 053 * <td>BTB_TIME</td> 054 * <td>Back-to-back constraint: given classes have to follow one strictly after 055 * another, but they can be taught in different rooms.</td> 056 * </tr> 057 * <tr> 058 * <td>DIFF_TIME</td> 059 * <td>Different time: given classes cannot overlap in time.</td> 060 * </tr> 061 * <tr> 062 * <td>NHB(1), NHB(1.5), NHB(2), ... NHB(8)</td> 063 * <td>Number of hours between: between the given classes, the exact number of 064 * hours have to be kept.</td> 065 * </tr> 066 * <tr> 067 * <td>SAME_START</td> 068 * <td>Same starting hour: given classes have to start in the same hour.</td> 069 * </tr> 070 * <tr> 071 * <td>SAME_ROOM</td> 072 * <td>Same room: given classes have to be placed in the same room.</td> 073 * </tr> 074 * <tr> 075 * <td>NHB_GTE(1)</td> 076 * <td>Greater than or equal to 1 hour between: between the given classes, the 077 * number of hours have to be one or more.</td> 078 * </tr> 079 * <tr> 080 * <td>NHB_LT(6)</td> 081 * <td>Less than 6 hours between: between the given classes, the number of hours 082 * have to be less than six.</td> 083 * </tr> 084 * </table> 085 * 086 * @version CourseTT 1.2 (University Course Timetabling)<br> 087 * Copyright (C) 2006 - 2010 Tomas Muller<br> 088 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 089 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 090 * <br> 091 * This library is free software; you can redistribute it and/or modify 092 * it under the terms of the GNU Lesser General Public License as 093 * published by the Free Software Foundation; either version 3 of the 094 * License, or (at your option) any later version. <br> 095 * <br> 096 * This library is distributed in the hope that it will be useful, but 097 * WITHOUT ANY WARRANTY; without even the implied warranty of 098 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 099 * Lesser General Public License for more details. <br> 100 * <br> 101 * You should have received a copy of the GNU Lesser General Public 102 * License along with this library; if not see 103 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 104 */ 105 106 public class GroupConstraint extends Constraint<Lecture, Placement> { 107 private Long iId; 108 private int iPreference; 109 private ConstraintType iType; 110 private boolean iIsRequired; 111 private boolean iIsProhibited; 112 private int iLastPreference = 0; 113 private int iDayOfWeekOffset = 0; 114 private boolean iPrecedenceConsiderDatePatterns = true; 115 116 /** 117 * Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room), 118 * only need to implement this interface. 119 */ 120 public static interface PairCheck { 121 /** 122 * Check whether the constraint is satisfied for the given two assignments (required / preferred case) 123 * @param gc Calling group constraint 124 * @param plc1 First placement 125 * @param plc2 Second placement 126 * @return true if constraint is satisfied 127 */ 128 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2); 129 /** 130 * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case) 131 * @param gc Calling group constraint 132 * @param plc1 First placement 133 * @param plc2 Second placement 134 * @return true if constraint is satisfied 135 */ 136 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2); 137 } 138 139 /** 140 * Group constraint building blocks (individual constraints that need more than {@link PairCheck}) 141 */ 142 public static enum Flag { 143 /** Back-to-back constraint (sequence check) */ 144 BACK_TO_BACK, 145 /** Can share room flag */ 146 CAN_SHARE_ROOM, 147 /** Maximum hours a day (number of slots a day check) */ 148 MAX_HRS_DAY, 149 /** Children cannot overlap */ 150 CH_NOTOVERLAP; 151 /** Bit number (to combine flags) */ 152 int flag() { return 1 << ordinal(); } 153 } 154 155 /** 156 * Group constraint type. 157 */ 158 public static enum ConstraintType { 159 /** 160 * Same Time: Given classes must be taught at the same time of day (independent of the actual day the classes meet). 161 * For the classes of the same length, this is the same constraint as same start. For classes of different length, 162 * the shorter one cannot start before, nor end after, the longer one.<BR> 163 * When prohibited or (strongly) discouraged: one class may not meet on any day at a time of day that overlaps with 164 * that of the other. For example, one class can not meet M 7:30 while the other meets F 7:30. Note the difference 165 * here from the different time constraint that only prohibits the actual class meetings from overlapping. 166 */ 167 SAME_TIME("SAME_TIME", "Same Time", new PairCheck() { 168 @Override 169 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 170 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 171 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()); 172 } 173 @Override 174 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 175 return !(plc1.getTimeLocation().shareHours(plc2.getTimeLocation())); 176 }}), 177 /** 178 * Same Days: Given classes must be taught on the same days. In case of classes of different time patterns, a class 179 * with fewer meetings must meet on a subset of the days used by the class with more meetings. For example, if one 180 * class pattern is 3x50, all others given in the constraint can only be taught on Monday, Wednesday, or Friday. 181 * For a 2x100 class MW, MF, WF is allowed but TTh is prohibited.<BR> 182 * When prohibited or (strongly) discouraged: any pair of classes classes cannot be taught on the same days (cannot 183 * overlap in days). For instance, if one class is MFW, the second has to be TTh. 184 */ 185 SAME_DAYS("SAME_DAYS", "Same Days", new PairCheck() { 186 @Override 187 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 188 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 189 } 190 @Override 191 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 192 return !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()); 193 }}), 194 /** 195 * Back-To-Back & Same Room: Classes must be offered in adjacent time segments and must be placed in the same room. 196 * Given classes must also be taught on the same days.<BR> 197 * When prohibited or (strongly) discouraged: classes cannot be back-to-back. There must be at least half-hour 198 * between these classes, and they must be taught on the same days and in the same room. 199 */ 200 BTB("BTB", "Back-To-Back & Same Room", new PairCheck() { 201 @Override 202 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 203 return 204 plc1.sameRooms(plc2) && 205 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 206 } 207 @Override 208 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 209 return 210 plc1.sameRooms(plc2) && 211 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 212 }}, Flag.BACK_TO_BACK), 213 /** 214 * Back-To-Back: Classes must be offered in adjacent time segments but may be placed in different rooms. Given classes 215 * must also be taught on the same days.<BR> 216 * When prohibited or (strongly) discouraged: no pair of classes can be taught back-to-back. They may not overlap in time, 217 * but must be taught on the same days. This means that there must be at least half-hour between these classes. 218 */ 219 BTB_TIME("BTB_TIME", "Back-To-Back", new PairCheck() { 220 @Override 221 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 222 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 223 } 224 @Override 225 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 226 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 227 }}, Flag.BACK_TO_BACK), 228 /** 229 * Different Time: Given classes cannot overlap in time. They may be taught at the same time of day if they are on 230 * different days. For instance, MF 7:30 is compatible with TTh 7:30.<BR> 231 * When prohibited or (strongly) discouraged: every pair of classes in the constraint must overlap in time. 232 */ 233 DIFF_TIME("DIFF_TIME", "Different Time", new PairCheck() { 234 @Override 235 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 236 return !plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 237 } 238 @Override 239 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 240 return plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 241 }}), 242 /** 243 * 1 Hour Between: Given classes must have exactly 1 hour in between the end of one and the beginning of another. 244 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 245 * When prohibited or (strongly) discouraged: classes can not have 1 hour in between. They may not overlap in time 246 * but must be taught on the same days. 247 */ 248 NHB_1("NHB(1)", "1 Hour Between", 12, BTB_TIME.check(), Flag.BACK_TO_BACK), 249 /** 250 * 2 Hours Between: Given classes must have exactly 2 hours in between the end of one and the beginning of another. 251 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 252 * When prohibited or (strongly) discouraged: classes can not have 2 hours in between. They may not overlap in time 253 * but must be taught on the same days. 254 */ 255 NHB_2("NHB(2)", "2 Hours Between", 24, BTB_TIME.check(), Flag.BACK_TO_BACK), 256 /** 257 * 3 Hours Between: Given classes must have exactly 3 hours in between the end of one and the beginning of another. 258 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 259 * When prohibited or (strongly) discouraged: classes can not have 3 hours in between. They may not overlap in time 260 * but must be taught on the same days. 261 */ 262 NHB_3("NHB(3)", "3 Hours Between", 36, BTB_TIME.check(), Flag.BACK_TO_BACK), 263 /** 264 * 4 Hours Between: Given classes must have exactly 4 hours in between the end of one and the beginning of another. 265 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 266 * When prohibited or (strongly) discouraged: classes can not have 4 hours in between. They may not overlap in time 267 * but must be taught on the same days. 268 */ 269 NHB_4("NHB(4)", "4 Hours Between", 48, BTB_TIME.check(), Flag.BACK_TO_BACK), 270 /** 271 * 5 Hours Between: Given classes must have exactly 5 hours in between the end of one and the beginning of another. 272 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 273 * When prohibited or (strongly) discouraged: classes can not have 5 hours in between. They may not overlap in time 274 * but must be taught on the same days. 275 */ 276 NHB_5("NHB(5)", "5 Hours Between", 60, BTB_TIME.check(), Flag.BACK_TO_BACK), 277 /** 278 * 6 Hours Between: Given classes must have exactly 6 hours in between the end of one and the beginning of another. 279 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 280 * When prohibited or (strongly) discouraged: classes can not have 6 hours in between. They may not overlap in time 281 * but must be taught on the same days. 282 */ 283 NHB_6("NHB(6)", "6 Hours Between", 72, BTB_TIME.check(), Flag.BACK_TO_BACK), 284 /** 285 * 7 Hours Between: Given classes must have exactly 7 hours in between the end of one and the beginning of another. 286 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 287 * When prohibited or (strongly) discouraged: classes can not have 7 hours in between. They may not overlap in time 288 * but must be taught on the same days. 289 */ 290 NHB_7("NHB(7)", "7 Hours Between", 84, BTB_TIME.check(), Flag.BACK_TO_BACK), 291 /** 292 * 8 Hours Between: Given classes must have exactly 8 hours in between the end of one and the beginning of another. 293 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 294 * When prohibited or (strongly) discouraged: classes can not have 8 hours in between. They may not overlap in time 295 * but must be taught on the same days. 296 */ 297 NHB_8("NHB(8)", "8 Hours Between", 96, BTB_TIME.check(), Flag.BACK_TO_BACK), 298 /** 299 * Same Start Time: Given classes must start during the same half-hour period of a day (independent of the actual 300 * day the classes meet). For instance, MW 7:30 is compatible with TTh 7:30 but not with MWF 8:00.<BR> 301 * When prohibited or (strongly) discouraged: any pair of classes in the given constraint cannot start during the 302 * same half-hour period of any day of the week. 303 */ 304 SAME_START("SAME_START", "Same Start Time", new PairCheck() { 305 @Override 306 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 307 return 308 (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) == 309 (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY); 310 } 311 @Override 312 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 313 return 314 (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) != 315 (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY); 316 }}), 317 /** 318 * Same Room: Given classes must be taught in the same room.<BR> 319 * When prohibited or (strongly) discouraged: any pair of classes in the constraint cannot be taught in the same room. 320 */ 321 SAME_ROOM("SAME_ROOM", "Same Room", new PairCheck() { 322 @Override 323 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 324 return plc1.sameRooms(plc2); 325 } 326 @Override 327 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 328 return !plc1.sameRooms(plc2); 329 }}), 330 /** 331 * At Least 1 Hour Between: Given classes have to have 1 hour or more in between.<BR> 332 * When prohibited or (strongly) discouraged: given classes have to have less than 1 hour in between. 333 */ 334 NHB_GTE_1("NHB_GTE(1)", "At Least 1 Hour Between", 6, 288, BTB_TIME.check(), Flag.BACK_TO_BACK), 335 /** 336 * Less Than 6 Hours Between: Given classes must have less than 6 hours from end of first class to the beginning of 337 * the next. Given classes must also be taught on the same days.<BR> 338 * When prohibited or (strongly) discouraged: given classes must have 6 or more hours between. This constraint does 339 * not carry over from classes taught at the end of one day to the beginning of the next. 340 */ 341 NHB_LT_6("NHB_LT(6)", "Less Than 6 Hours Between", 0, 66, BTB_TIME.check(), Flag.BACK_TO_BACK), 342 /** 343 * 1.5 Hour Between: Given classes must have exactly 90 minutes in between the end of one and the beginning of another. 344 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 345 * When prohibited or (strongly) discouraged: classes can not have 90 minutes in between. They may not overlap in time 346 * but must be taught on the same days. 347 */ 348 NHB_1_5("NHB(1.5)", "1.5 Hour Between", 18, BTB_TIME.check(), Flag.BACK_TO_BACK), 349 /** 350 * 4.5 Hours Between: Given classes must have exactly 4.5 hours in between the end of one and the beginning of another. 351 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 352 * When prohibited or (strongly) discouraged: classes can not have 4.5 hours in between. They may not overlap in time 353 * but must be taught on the same days. 354 */ 355 NHB_4_5("NHB(4.5)", "4.5 Hours Between", 54, BTB_TIME.check(), Flag.BACK_TO_BACK), 356 /** 357 * Same Students: Given classes are treated as they are attended by the same students, i.e., they cannot overlap in time 358 * and if they are back-to-back the assigned rooms cannot be too far (student limit is used). 359 */ 360 SAME_STUDENTS("SAME_STUDENTS", "Same Students", new PairCheck() { 361 @Override 362 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 363 return !JenrlConstraint.isInConflict(plc1, plc2, ((TimetableModel)gc.getModel()).getDistanceMetric()); 364 } 365 @Override 366 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 367 return true; 368 }}), 369 /** 370 * Same Instructor: Given classes are treated as they are taught by the same instructor, i.e., they cannot overlap in time 371 * and if they are back-to-back the assigned rooms cannot be too far (instructor limit is used).<BR> 372 * If the constraint is required and the classes are back-to-back, discouraged and strongly discouraged distances between 373 * assigned rooms are also considered. 374 */ 375 SAME_INSTR("SAME_INSTR", "Same Instructor", new PairCheck() { 376 @Override 377 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 378 TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation(); 379 if (t1.shareDays(t2) && t1.shareWeeks(t2)) { 380 if (t1.shareHours(t2)) 381 return false; // overlap 382 int s1 = t1.getStartSlot() % Constants.SLOTS_PER_DAY; 383 int s2 = t2.getStartSlot() % Constants.SLOTS_PER_DAY; 384 if (s1 + t1.getLength() == s2 || s2 + t2.getLength() == s1) { // back-to-back 385 TimetableModel m = (TimetableModel)gc.getModel(); 386 double distance = Placement.getDistanceInMeters(m.getDistanceMetric(), plc1, plc2); 387 if (distance > m.getDistanceMetric().getInstructorProhibitedLimit()) 388 return false; 389 } 390 } 391 return true; 392 } 393 @Override 394 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 395 return true; 396 }}), 397 /** 398 * Can Share Room: Given classes can share the room (use the room in the same time) if the room is big enough. 399 */ 400 CAN_SHARE_ROOM("CAN_SHARE_ROOM", "Can Share Room", null, Flag.CAN_SHARE_ROOM), 401 /** 402 * Precedence: Given classes have to be taught in the given order (the first meeting of the first class has to end before 403 * the first meeting of the second class etc.)<BR> 404 * When prohibited or (strongly) discouraged: classes have to be taught in the order reverse to the given one. 405 */ 406 PRECEDENCE("PRECEDENCE", "Precedence", new PairCheck() { 407 @Override 408 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 409 return gc.isPrecedence(plc1, plc2, true, true); 410 } 411 @Override 412 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 413 return gc.isPrecedence(plc1, plc2, false, true); 414 }}), 415 /** 416 * Back-To-Back Day: Classes must be offered on adjacent days and may be placed in different rooms.<BR> 417 * When prohibited or (strongly) discouraged: classes can not be taught on adjacent days. They also can not be taught 418 * on the same days. This means that there must be at least one day between these classes. 419 */ 420 BTB_DAY("BTB_DAY", "Back-To-Back Day", new PairCheck() { 421 @Override 422 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 423 return 424 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 425 isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation()); 426 } 427 @Override 428 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 429 return 430 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 431 !isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation()); 432 }}), 433 /** 434 * Meet Together: Given classes are meeting together (same as if the given classes require constraints Can Share Room, 435 * Same Room, Same Time and Same Days all together). 436 */ 437 MEET_WITH("MEET_WITH", "Meet Together", new PairCheck() { 438 @Override 439 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 440 return 441 plc1.sameRooms(plc2) && 442 sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 443 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 444 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 445 446 } 447 @Override 448 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 449 return true; 450 }}, Flag.CAN_SHARE_ROOM), 451 /** 452 * More Than 1 Day Between: Given classes must have two or more days in between.<br> 453 * When prohibited or (strongly) discouraged: given classes must be offered on adjacent days or with at most one day in between. 454 */ 455 NDB_GT_1("NDB_GT_1", "More Than 1 Day Between", new PairCheck() { 456 @Override 457 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 458 return 459 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 460 isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation()); 461 } 462 @Override 463 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 464 return 465 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 466 !isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation()); 467 }}), 468 /** 469 * Children Cannot Overlap: If parent classes do not overlap in time, children classes can not overlap in time as well.<BR> 470 * Note: This constraint only needs to be put on the parent classes. Preferred configurations are Required All Classes 471 * or Pairwise (Strongly) Preferred. 472 */ 473 CH_NOTOVERLAP("CH_NOTOVERLAP", "Children Cannot Overlap", new PairCheck() { 474 @Override 475 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 476 return gc.isChildrenNotOverlap(plc1.variable(), plc1, plc2.variable(), plc2); 477 } 478 @Override 479 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 480 return true; 481 }}), 482 /** 483 * Next Day: The second class has to be placed on the following day of the first class (if the first class is on Friday, 484 * second class have to be on Monday).<br> 485 * When prohibited or (strongly) discouraged: The second class has to be placed on the previous day of the first class 486 * (if the first class is on Monday, second class have to be on Friday).<br> 487 * Note: This constraint works only between pairs of classes. 488 */ 489 FOLLOWING_DAY("FOLLOWING_DAY", "Next Day", new PairCheck() { 490 @Override 491 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 492 return gc.isFollowingDay(plc1, plc2, true); 493 } 494 @Override 495 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 496 return gc.isFollowingDay(plc1, plc2, false); 497 }}), 498 /** 499 * Two Days After: The second class has to be placed two days after the first class (Monday → Wednesday, Tuesday → 500 * Thurday, Wednesday → Friday, Thursday → Monday, Friday → Tuesday).<br> 501 * When prohibited or (strongly) discouraged: The second class has to be placed two days before the first class (Monday → 502 * Thursday, Tuesday → Friday, Wednesday → Monday, Thursday → Tuesday, Friday → Wednesday).<br> 503 * Note: This constraint works only between pairs of classes. 504 */ 505 EVERY_OTHER_DAY("EVERY_OTHER_DAY", "Two Days After", new PairCheck() { 506 @Override 507 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 508 return gc.isEveryOtherDay(plc1, plc2, true); 509 } 510 @Override 511 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 512 return gc.isEveryOtherDay(plc1, plc2, false); 513 }}), 514 /** 515 * 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. 516 */ 517 MAX_HRS_DAY_5("MAX_HRS_DAY(5)", "At Most 5 Hours A Day", 60, null, Flag.MAX_HRS_DAY), 518 /** 519 * 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. 520 */ 521 MAX_HRS_DAY_6("MAX_HRS_DAY(6)", "At Most 6 Hours A Day", 72, null, Flag.MAX_HRS_DAY), 522 /** 523 * 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. 524 */ 525 MAX_HRS_DAY_7("MAX_HRS_DAY(7)", "At Most 7 Hours A Day", 84, null, Flag.MAX_HRS_DAY), 526 /** 527 * 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. 528 */ 529 MAX_HRS_DAY_8("MAX_HRS_DAY(8)", "At Most 8 Hours A Day", 96, null, Flag.MAX_HRS_DAY), 530 /** 531 * Given classes must be taught during the same weeks (i.e., must have the same date pattern).<br> 532 * When prohibited or (strongly) discouraged: any two classes must have non overlapping date patterns. 533 */ 534 SAME_WEEKS("SAME_WEEKS", "Same Weeks", new PairCheck() { 535 @Override 536 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 537 return plc1.getTimeLocation().getWeekCode().equals(plc2.getTimeLocation().getWeekCode()); 538 } 539 @Override 540 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 541 return !plc1.getTimeLocation().shareWeeks(plc2.getTimeLocation()); 542 }}), 543 /** 544 * Classes (of different courses) are to be attended by the same students. For instance, 545 * if class A1 (of a course A) and class B1 (of a course B) are linked, a student requesting 546 * both courses must attend A1 if and only if he also attends B1. This is a student sectioning 547 * constraint that is interpreted as Same Students constraint during course timetabling. 548 */ 549 LINKED_SECTIONS("LINKED_SECTIONS", "Linked Classes", SAME_STUDENTS.check()), 550 /** 551 * Back-To-Back Precedence: Given classes have to be taught in the given order, on the same days, 552 * and in adjacent time segments. 553 * When prohibited or (strongly) discouraged: Given classes have to be taught in the given order, 554 * on the same days, but cannot be back-to-back. 555 */ 556 BTB_PRECEDENCE("BTB_PRECEDENCE", "Back-To-Back Precedence", new PairCheck() { 557 @Override 558 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 559 return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 560 } 561 @Override 562 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 563 return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 564 }}, Flag.BACK_TO_BACK), 565 566 /** 567 * Same Days-Time: Given classes must be taught at the same time of day and on the same days. 568 * It is the combination of Same Days and Same Time distribution preferences. 569 * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days 570 * during the same time. 571 */ 572 SAME_DAYS_TIME("SAME_D_T", "Same Days-Time", new PairCheck() { 573 @Override 574 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 575 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 576 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 577 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 578 } 579 @Override 580 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 581 return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) || 582 !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()); 583 }}), 584 /** 585 * Same Days-Room-Time: Given classes must be taught at the same time of day, on the same days and in the same room. 586 * It is the combination of Same Days, Same Time and Same Room distribution preferences. 587 * Note that this constraint is the same as Meet Together constraint, except it does not allow room sharing. In other words, 588 * it is only useful when these classes are taught during non-overlapping date patterns. 589 * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days 590 * during the same time in the same room. 591 */ 592 SAME_DAYS_ROOM_TIME("SAME_D_R_T", "Same Days-Room-Time", new PairCheck() { 593 @Override 594 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 595 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 596 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 597 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 598 plc1.sameRooms(plc2); 599 } 600 @Override 601 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 602 return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) || 603 !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()) || 604 !plc1.sameRooms(plc2); 605 }}), 606 ; 607 608 String iReference, iName; 609 int iFlag = 0; 610 Flag[] iFlags = null; 611 int iMin = 0, iMax = 0; 612 PairCheck iCheck = null; 613 ConstraintType(String reference, String name, PairCheck check, Flag... flags) { 614 iReference = reference; 615 iName = name; 616 iCheck = check; 617 iFlags = flags; 618 for (Flag f: flags) 619 iFlag |= f.flag(); 620 } 621 ConstraintType(String reference, String name, int limit, PairCheck check, Flag... flags) { 622 this(reference, name, check, flags); 623 iMin = iMax = limit; 624 } 625 ConstraintType(String reference, String name, int min, int max, PairCheck check, Flag... flags) { 626 this(reference, name, check, flags); 627 iMin = min; 628 iMax = max; 629 } 630 631 /** Constraint reference */ 632 public String reference() { return iReference; } 633 /** Constraint name */ 634 public String getName() { return iName; } 635 /** Minimum (gap) parameter */ 636 public int getMin() { return iMin; } 637 /** Maximum (gap, hours a day) parameter */ 638 public int getMax() { return iMax; } 639 640 /** Flag check (true if contains given flag) */ 641 public boolean is(Flag f) { return (iFlag & f.flag()) != 0; } 642 643 /** Constraint type from reference */ 644 public static ConstraintType get(String reference) { 645 for (ConstraintType t: ConstraintType.values()) 646 if (t.reference().equals(reference)) return t; 647 return null; 648 } 649 650 /** True if a required or preferred constraint is satisfied between a pair of placements */ 651 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { return (iCheck == null ? true : iCheck.isSatisfied(gc, plc1, plc2)); } 652 /** True if a prohibited or discouraged constraint is satisfied between a pair of placements */ 653 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { return (iCheck == null ? true : iCheck.isViolated(gc, plc1, plc2)); } 654 /** Pair check */ 655 private PairCheck check() { return iCheck; } 656 } 657 658 public GroupConstraint() { 659 } 660 661 @Override 662 public void setModel(Model<Lecture, Placement> model) { 663 super.setModel(model); 664 DataProperties config = ((TimetableModel)model).getProperties(); 665 iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0); 666 iPrecedenceConsiderDatePatterns = config.getPropertyBoolean("Precedence.ConsiderDatePatterns", true); 667 } 668 669 @Override 670 public void addVariable(Lecture lecture) { 671 if (!variables().contains(lecture)) 672 super.addVariable(lecture); 673 if (getType().is(Flag.CH_NOTOVERLAP)) { 674 if (lecture.getChildrenSubpartIds() != null) { 675 for (Long subpartId: lecture.getChildrenSubpartIds()) { 676 for (Lecture ch : lecture.getChildren(subpartId)) { 677 if (!variables().contains(ch)) 678 super.addVariable(ch); 679 } 680 } 681 } 682 } 683 } 684 685 @Override 686 public void removeVariable(Lecture lecture) { 687 if (variables().contains(lecture)) 688 super.removeVariable(lecture); 689 if (getType().is(Flag.CH_NOTOVERLAP)) { 690 if (lecture.getChildrenSubpartIds() != null) { 691 for (Long subpartId: lecture.getChildrenSubpartIds()) { 692 for (Lecture ch : lecture.getChildren(subpartId)) { 693 if (variables().contains(ch)) 694 super.removeVariable(ch); 695 } 696 } 697 } 698 } 699 } 700 701 /** 702 * Constructor 703 * 704 * @param id 705 * constraint id 706 * @param type 707 * constraString type (e.g, {@link ConstraintType#SAME_TIME}) 708 * @param preference 709 * time preference ("R" for required, "P" for prohibited, "-2", 710 * "-1", "1", "2" for soft preference) 711 */ 712 public GroupConstraint(Long id, ConstraintType type, String preference) { 713 iId = id; 714 iType = type; 715 iIsRequired = preference.equals(Constants.sPreferenceRequired); 716 iIsProhibited = preference.equals(Constants.sPreferenceProhibited); 717 iPreference = Constants.preference2preferenceLevel(preference); 718 } 719 720 /** Constraint id */ 721 public Long getConstraintId() { 722 return iId; 723 } 724 725 @Override 726 public long getId() { 727 return (iId == null ? -1 : iId.longValue()); 728 } 729 730 /** ConstraString type (e.g, {@link ConstraintType#SAME_TIME}) */ 731 public ConstraintType getType() { 732 return iType; 733 } 734 735 public void setType(ConstraintType type) { 736 iType = type; 737 } 738 739 /** Is constraint required */ 740 public boolean isRequired() { 741 return iIsRequired; 742 } 743 744 /** Is constraint prohibited */ 745 public boolean isProhibited() { 746 return iIsProhibited; 747 } 748 749 /** 750 * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for 751 * preference 752 */ 753 public String getPrologPreference() { 754 return Constants.preferenceLevel2preference(iPreference); 755 } 756 757 @Override 758 public boolean isConsistent(Placement value1, Placement value2) { 759 if (!isHard()) 760 return true; 761 if (!isSatisfiedPair(value1, value2)) 762 return false; 763 if (getType().is(Flag.BACK_TO_BACK)) { 764 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 765 assignments.put(value1.variable(), value1); 766 assignments.put(value2.variable(), value2); 767 if (!isSatisfiedSeq(assignments, false, null)) 768 return false; 769 } 770 if (getType().is(Flag.MAX_HRS_DAY)) { 771 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 772 assignments.put(value1.variable(), value1); 773 assignments.put(value2.variable(), value2); 774 for (int dayCode: Constants.DAY_CODES) { 775 if (nrSlotsADay(dayCode, assignments, null) > getType().getMax()) 776 return false; 777 } 778 } 779 return true; 780 } 781 782 @Override 783 public void computeConflicts(Placement value, Set<Placement> conflicts) { 784 if (!isHard()) 785 return; 786 for (Lecture v : variables()) { 787 if (v.equals(value.variable())) 788 continue; // ignore this variable 789 if (v.getAssignment() == null) 790 continue; // there is an unassigned variable -- great, still a 791 // chance to get violated 792 if (!isSatisfiedPair(v.getAssignment(), value)) 793 conflicts.add(v.getAssignment()); 794 } 795 if (getType().is(Flag.BACK_TO_BACK)) { 796 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 797 assignments.put(value.variable(), value); 798 if (!isSatisfiedSeq(assignments, true, conflicts)) 799 conflicts.add(value); 800 } 801 if (getType().is(Flag.MAX_HRS_DAY)) { 802 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 803 assignments.put(value.variable(), value); 804 for (int dayCode: Constants.DAY_CODES) { 805 if (nrSlotsADay(dayCode, assignments, conflicts) > getType().getMax()) { 806 List<Placement> adepts = new ArrayList<Placement>(); 807 for (Lecture lecture: assignedVariables()) { 808 if (conflicts.contains(lecture.getAssignment()) || lecture.equals(value.variable())) continue; 809 if (lecture.getAssignment().getTimeLocation() == null) continue; 810 if ((lecture.getAssignment().getTimeLocation().getDayCode() & dayCode) == 0) continue; 811 adepts.add(lecture.getAssignment()); 812 } 813 do { 814 Placement conflict = ToolBox.random(adepts); 815 adepts.remove(conflict); 816 conflicts.add(conflict); 817 } while (!adepts.isEmpty() && nrSlotsADay(dayCode, assignments, conflicts) > getType().getMax()); 818 } 819 } 820 } 821 822 if (iType == ConstraintType.MEET_WITH && !conflicts.contains(value)) { 823 // Check the room size 824 int neededSize = 0; 825 for (Lecture lecture: variables()) 826 neededSize += lecture.maxRoomUse(); 827 if (neededSize > value.getRoomSize()) { 828 conflicts.add(value); // room is too small to fit all meet with classes 829 return; 830 } 831 for (Lecture lecture: variables()) { 832 if (lecture.equals(value.variable())) continue; // Skip this lecture 833 if (lecture.getAssignment() != null) { // Has assignment, check whether it is conflicting 834 Placement other = lecture.getAssignment(); 835 if (other.sameRooms(value) && sameHours(value.getTimeLocation(), other.getTimeLocation()) && 836 sameDays(value.getTimeLocation(), other.getTimeLocation())) 837 continue; 838 conflicts.add(lecture.getAssignment()); 839 } 840 // Look for a matching assignment 841 List<Placement> sameAssignments = new ArrayList<Placement>(); 842 for (Placement other: lecture.values()) { 843 if (other.sameRooms(value) && sameHours(value.getTimeLocation(), other.getTimeLocation()) && 844 sameDays(value.getTimeLocation(), other.getTimeLocation())) { 845 sameAssignments.add(other); 846 } 847 } 848 // No matching assignment -> fail 849 if (sameAssignments.isEmpty()) { 850 conflicts.add(value); // other meet with class cannot be assigned with this value 851 return; 852 } 853 // Propagate the new assignment over other hard constraints of the lecture 854 if (sameAssignments.size() == 1) { 855 Placement sameAssignment = sameAssignments.get(0); 856 for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) { 857 if (other.equals(this)) continue; 858 if (other instanceof GroupConstraint && ((GroupConstraint)other).getType() == ConstraintType.MEET_WITH) continue; 859 other.computeConflicts(sameAssignment, conflicts); 860 if (conflicts.contains(value)) return; 861 if (conflicts.contains(sameAssignment)) { 862 conflicts.add(value); return; 863 } 864 } 865 for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) { 866 other.computeConflicts(sameAssignment, conflicts); 867 if (conflicts.contains(value)) return; 868 if (conflicts.contains(sameAssignment)) { 869 conflicts.add(value); return; 870 } 871 } 872 } 873 } 874 } 875 } 876 877 @Override 878 public boolean inConflict(Placement value) { 879 if (!isHard()) 880 return false; 881 for (Lecture v : variables()) { 882 if (v.equals(value.variable())) 883 continue; // ignore this variable 884 if (v.getAssignment() == null) 885 continue; // there is an unassigned variable -- great, still a 886 // chance to get violated 887 if (!isSatisfiedPair(v.getAssignment(), value)) 888 return true; 889 } 890 if (getType().is(Flag.BACK_TO_BACK)) { 891 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 892 assignments.put(value.variable(), value); 893 if (!isSatisfiedSeq(assignments, true, null)) 894 return true; 895 } 896 if (getType().is(Flag.MAX_HRS_DAY)) { 897 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 898 assignments.put(value.variable(), value); 899 for (int dayCode: Constants.DAY_CODES) { 900 if (nrSlotsADay(dayCode, assignments, null) > getType().getMax()) 901 return true; 902 } 903 } 904 return false; 905 } 906 907 /** Constraint preference (0 if prohibited or reqired) */ 908 public int getPreference() { 909 return iPreference; 910 } 911 912 /** 913 * Current constraint preference (0 if prohibited or reqired, depends on 914 * current satisfaction of the constraint) 915 */ 916 public int getCurrentPreference() { 917 if (isHard()) return 0; // no preference 918 if (countAssignedVariables() < 2) return 0; // not enough variable 919 if (getType().is(Flag.MAX_HRS_DAY)) { // max hours a day 920 int over = 0; 921 for (int dayCode: Constants.DAY_CODES) 922 over += Math.max(0, nrSlotsADay(dayCode, null, null) - getType().getMax()); 923 return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference)); 924 } 925 int nrViolatedPairs = 0; 926 for (Lecture v1 : variables()) { 927 if (v1.getAssignment() == null) continue; 928 for (Lecture v2 : variables()) { 929 if (v2.getAssignment() == null || v1.getId() >= v2.getId()) continue; 930 if (!isSatisfiedPair(v1.getAssignment(), v2.getAssignment())) nrViolatedPairs++; 931 } 932 } 933 if (getType().is(Flag.BACK_TO_BACK)) { 934 Set<Placement> conflicts = new HashSet<Placement>(); 935 if (!isSatisfiedSeq(new HashMap<Lecture, Placement>(), true, conflicts)) 936 nrViolatedPairs += conflicts.size(); 937 } 938 return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference)); 939 } 940 941 /** Current constraint preference (if given placement is assigned) */ 942 public int getCurrentPreference(Placement placement) { 943 if (getType().is(Flag.MAX_HRS_DAY)) { 944 if (placement.getTimeLocation() == null) return 0; 945 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 946 assignments.put(placement.variable(), placement); 947 int over = 0; 948 for (int dayCode: Constants.DAY_CODES) 949 if ((placement.getTimeLocation().getDayCode() & dayCode) != 0) 950 over += Math.min(Math.max(0, nrSlotsADay(dayCode, assignments, null) - getType().getMax()), placement.getTimeLocation().getLength()); 951 return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference)); 952 } 953 int nrViolatedPairs = 0; 954 for (Lecture v1 : variables()) { 955 if (v1.getAssignment() == null || v1.equals(placement.variable())) continue; 956 if (!isSatisfiedPair(v1.getAssignment(), placement)) nrViolatedPairs++; 957 } 958 if (getType().is(Flag.BACK_TO_BACK)) { 959 HashMap<Lecture, Placement> assignment = new HashMap<Lecture, Placement>(); 960 assignment.put(placement.variable(), placement); 961 Set<Placement> conflicts = new HashSet<Placement>(); 962 if (!isSatisfiedSeq(assignment, true, conflicts)) 963 nrViolatedPairs += conflicts.size(); 964 } 965 return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference)); 966 } 967 968 @Override 969 public void unassigned(long iteration, Placement value) { 970 super.unassigned(iteration, value); 971 if (iIsRequired || iIsProhibited) 972 return; 973 getModel().getCriterion(DistributionPreferences.class).inc(-iLastPreference); 974 iLastPreference = Math.min(0, getCurrentPreference()); 975 getModel().getCriterion(DistributionPreferences.class).inc(iLastPreference); 976 } 977 978 @Override 979 public void assigned(long iteration, Placement value) { 980 super.assigned(iteration, value); 981 if (iIsRequired || iIsProhibited) 982 return; 983 getModel().getCriterion(DistributionPreferences.class).inc(-iLastPreference); 984 iLastPreference = Math.min(0, getCurrentPreference()); 985 getModel().getCriterion(DistributionPreferences.class).inc(iLastPreference); 986 } 987 988 @Override 989 public String toString() { 990 StringBuffer sb = new StringBuffer(); 991 sb.append(getName()); 992 sb.append(" between "); 993 for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) { 994 Lecture v = e.next(); 995 sb.append(v.getName()); 996 if (e.hasNext()) 997 sb.append(", "); 998 } 999 return sb.toString(); 1000 } 1001 1002 @Override 1003 public boolean isHard() { 1004 return iIsRequired || iIsProhibited; 1005 } 1006 1007 @Override 1008 public String getName() { 1009 return getType().getName(); 1010 } 1011 1012 1013 private boolean isPrecedence(Placement p1, Placement p2, boolean firstGoesFirst, boolean considerDatePatterns) { 1014 int ord1 = variables().indexOf(p1.variable()); 1015 int ord2 = variables().indexOf(p2.variable()); 1016 TimeLocation t1 = null, t2 = null; 1017 if (ord1 < ord2) { 1018 if (firstGoesFirst) { 1019 t1 = p1.getTimeLocation(); 1020 t2 = p2.getTimeLocation(); 1021 } else { 1022 t2 = p1.getTimeLocation(); 1023 t1 = p2.getTimeLocation(); 1024 } 1025 } else { 1026 if (!firstGoesFirst) { 1027 t1 = p1.getTimeLocation(); 1028 t2 = p2.getTimeLocation(); 1029 } else { 1030 t2 = p1.getTimeLocation(); 1031 t1 = p2.getTimeLocation(); 1032 } 1033 } 1034 if (considerDatePatterns && iPrecedenceConsiderDatePatterns) { 1035 boolean sameDatePattern = (t1.getDatePatternId() != null ? t1.getDatePatternId().equals(t2.getDatePatternId()) : t1.getWeekCode().equals(t2.getWeekCode())); 1036 if (!sameDatePattern) { 1037 int m1 = getFirstMeeting(t1), m2 = getFirstMeeting(t2); 1038 if (m1 != m2) return m1 < m2; 1039 } 1040 } 1041 return t1.getStartSlots().nextElement() + t1.getLength() <= t2.getStartSlots().nextElement(); 1042 } 1043 1044 private int getFirstMeeting(TimeLocation time) { 1045 int idx = -1; 1046 while ((idx = time.getWeekCode().nextSetBit(1 + idx)) >= 0) { 1047 int dow = (idx + iDayOfWeekOffset) % 7; 1048 if ((time.getDayCode() & Constants.DAY_CODES[dow]) != 0) break; 1049 } 1050 return idx; 1051 } 1052 1053 private static boolean isBackToBackDays(TimeLocation t1, TimeLocation t2) { 1054 int f1 = -1, f2 = -1, e1 = -1, e2 = -1; 1055 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1056 if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1057 if (f1 < 0) 1058 f1 = i; 1059 e1 = i; 1060 } 1061 if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1062 if (f2 < 0) 1063 f2 = i; 1064 e2 = i; 1065 } 1066 } 1067 return (e1 + 1 == f2) || (e2 + 1 == f1); 1068 } 1069 1070 private static boolean isNrDaysBetweenGreaterThanOne(TimeLocation t1, TimeLocation t2) { 1071 int f1 = -1, f2 = -1, e1 = -1, e2 = -1; 1072 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1073 if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1074 if (f1 < 0) 1075 f1 = i; 1076 e1 = i; 1077 } 1078 if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1079 if (f2 < 0) 1080 f2 = i; 1081 e2 = i; 1082 } 1083 } 1084 return (e1 - f2 > 2) || (e2 - f1 > 2); 1085 } 1086 1087 private boolean isFollowingDay(Placement p1, Placement p2, boolean firstGoesFirst) { 1088 int ord1 = variables().indexOf(p1.variable()); 1089 int ord2 = variables().indexOf(p2.variable()); 1090 TimeLocation t1 = null, t2 = null; 1091 if (ord1 < ord2) { 1092 if (firstGoesFirst) { 1093 t1 = p1.getTimeLocation(); 1094 t2 = p2.getTimeLocation(); 1095 } else { 1096 t2 = p1.getTimeLocation(); 1097 t1 = p2.getTimeLocation(); 1098 } 1099 } else { 1100 if (!firstGoesFirst) { 1101 t1 = p1.getTimeLocation(); 1102 t2 = p2.getTimeLocation(); 1103 } else { 1104 t2 = p1.getTimeLocation(); 1105 t1 = p2.getTimeLocation(); 1106 } 1107 } 1108 int f1 = -1, f2 = -1, e1 = -1; 1109 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1110 if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1111 if (f1 < 0) 1112 f1 = i; 1113 e1 = i; 1114 } 1115 if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1116 if (f2 < 0) 1117 f2 = i; 1118 } 1119 } 1120 return ((e1 + 1) % Constants.NR_DAYS_WEEK == f2); 1121 } 1122 1123 private boolean isEveryOtherDay(Placement p1, Placement p2, boolean firstGoesFirst) { 1124 int ord1 = variables().indexOf(p1.variable()); 1125 int ord2 = variables().indexOf(p2.variable()); 1126 TimeLocation t1 = null, t2 = null; 1127 if (ord1 < ord2) { 1128 if (firstGoesFirst) { 1129 t1 = p1.getTimeLocation(); 1130 t2 = p2.getTimeLocation(); 1131 } else { 1132 t2 = p1.getTimeLocation(); 1133 t1 = p2.getTimeLocation(); 1134 } 1135 } else { 1136 if (!firstGoesFirst) { 1137 t1 = p1.getTimeLocation(); 1138 t2 = p2.getTimeLocation(); 1139 } else { 1140 t2 = p1.getTimeLocation(); 1141 t1 = p2.getTimeLocation(); 1142 } 1143 } 1144 int f1 = -1, f2 = -1, e1 = -1; 1145 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1146 if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1147 if (f1 < 0) 1148 f1 = i; 1149 e1 = i; 1150 } 1151 if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) { 1152 if (f2 < 0) 1153 f2 = i; 1154 } 1155 } 1156 return ((e1 + 2) % Constants.NR_DAYS_WEEK == f2); 1157 } 1158 1159 private static boolean sameDays(int[] days1, int[] days2) { 1160 if (days2.length < days1.length) 1161 return sameDays(days2, days1); 1162 int i2 = 0; 1163 for (int i1 = 0; i1 < days1.length; i1++) { 1164 int d1 = days1[i1]; 1165 while (true) { 1166 if (i2 == days2.length) 1167 return false; 1168 int d2 = days2[i2]; 1169 if (d1 == d2) 1170 break; 1171 i2++; 1172 if (i2 == days2.length) 1173 return false; 1174 } 1175 i2++; 1176 } 1177 return true; 1178 } 1179 1180 private static boolean sameDays(TimeLocation t1, TimeLocation t2) { 1181 if (t1 == null || t2 == null) return false; 1182 return sameDays(t1.getDaysArray(), t2.getDaysArray()); 1183 } 1184 1185 private static boolean sameHours(int start1, int len1, int start2, int len2) { 1186 if (len1 > len2) 1187 return sameHours(start2, len2, start1, len1); 1188 start1 %= Constants.SLOTS_PER_DAY; 1189 start2 %= Constants.SLOTS_PER_DAY; 1190 return (start1 >= start2 && start1 + len1 <= start2 + len2); 1191 } 1192 1193 private static boolean sameHours(TimeLocation t1, TimeLocation t2) { 1194 if (t1 == null || t2 == null) return false; 1195 return sameHours(t1.getStartSlot(), t1.getLength(), t2.getStartSlot(), t2.getLength()); 1196 } 1197 1198 private static boolean canFill(int totalGap, int gapMin, int gapMax, List<Integer> lengths) { 1199 if (gapMin <= totalGap && totalGap <= gapMax) 1200 return true; 1201 if (totalGap < 2 * gapMin) 1202 return false; 1203 for (int i = 0; i < lengths.size(); i++) { 1204 int length = lengths.get(i); 1205 lengths.remove(i); 1206 for (int gap = gapMin; gap <= gapMax; gap++) 1207 if (canFill(totalGap - gap - length, gapMin, gapMax, lengths)) 1208 return true; 1209 lengths.add(i, length); 1210 } 1211 return false; 1212 } 1213 1214 private boolean isSatisfiedSeq(HashMap<Lecture, Placement> assignments, boolean considerCurrentAssignments, 1215 Set<Placement> conflicts) { 1216 if (conflicts == null) 1217 return isSatisfiedSeqCheck(assignments, considerCurrentAssignments, conflicts); 1218 else { 1219 Set<Placement> bestConflicts = isSatisfiedRecursive(0, assignments, considerCurrentAssignments, conflicts, 1220 new HashSet<Placement>(), null); 1221 if (bestConflicts == null) 1222 return false; 1223 conflicts.addAll(bestConflicts); 1224 return true; 1225 } 1226 } 1227 1228 private Set<Placement> isSatisfiedRecursive(int idx, HashMap<Lecture, Placement> assignments, 1229 boolean considerCurrentAssignments, Set<Placement> conflicts, Set<Placement> newConflicts, 1230 Set<Placement> bestConflicts) { 1231 if (idx == variables().size() && newConflicts.isEmpty()) 1232 return bestConflicts; 1233 if (isSatisfiedSeqCheck(assignments, considerCurrentAssignments, conflicts)) { 1234 if (bestConflicts == null || bestConflicts.size() > newConflicts.size()) 1235 return new HashSet<Placement>(newConflicts); 1236 return bestConflicts; 1237 } 1238 if (idx == variables().size()) 1239 return bestConflicts; 1240 bestConflicts = isSatisfiedRecursive(idx + 1, assignments, considerCurrentAssignments, conflicts, newConflicts, 1241 bestConflicts); 1242 Lecture lecture = variables().get(idx); 1243 if (assignments != null && assignments.containsKey(lecture)) 1244 return bestConflicts; 1245 Placement placement = (assignments == null ? null : assignments.get(lecture)); 1246 if (placement == null && considerCurrentAssignments) 1247 placement = lecture.getAssignment(); 1248 if (placement == null) 1249 return bestConflicts; 1250 if (conflicts != null && conflicts.contains(placement)) 1251 return bestConflicts; 1252 conflicts.add(placement); 1253 newConflicts.add(placement); 1254 bestConflicts = isSatisfiedRecursive(idx + 1, assignments, considerCurrentAssignments, conflicts, newConflicts, 1255 bestConflicts); 1256 newConflicts.remove(placement); 1257 conflicts.remove(placement); 1258 return bestConflicts; 1259 } 1260 1261 private boolean isSatisfiedSeqCheck(HashMap<Lecture, Placement> assignments, boolean considerCurrentAssignments, 1262 Set<Placement> conflicts) { 1263 if (!getType().is(Flag.BACK_TO_BACK)) return true; 1264 int gapMin = getType().getMin(); 1265 int gapMax = getType().getMax(); 1266 1267 List<Integer> lengths = new ArrayList<Integer>(); 1268 1269 Placement[] res = new Placement[Constants.SLOTS_PER_DAY]; 1270 for (int i = 0; i < Constants.SLOTS_PER_DAY; i++) 1271 res[i] = null; 1272 1273 int nrLectures = 0; 1274 1275 for (Lecture lecture : variables()) { 1276 Placement placement = (assignments == null ? null : assignments.get(lecture)); 1277 if (placement == null && considerCurrentAssignments) 1278 placement = lecture.getAssignment(); 1279 if (placement == null) { 1280 lengths.add(lecture.timeLocations().get(0).getLength()); 1281 } else if (conflicts != null && conflicts.contains(placement)) { 1282 lengths.add(lecture.timeLocations().get(0).getLength()); 1283 } else { 1284 int pos = placement.getTimeLocation().getStartSlot(); 1285 int length = placement.getTimeLocation().getLength(); 1286 for (int j = pos; j < pos + length; j++) { 1287 if (res[j] != null) { 1288 if (conflicts == null) 1289 return false; 1290 if (!assignments.containsKey(lecture)) 1291 conflicts.add(placement); 1292 else if (!assignments.containsKey(res[j].variable())) 1293 conflicts.add(res[j]); 1294 } 1295 } 1296 for (int j = pos; j < pos + length; j++) 1297 res[j] = placement; 1298 nrLectures++; 1299 } 1300 } 1301 if (nrLectures <= 1) 1302 return true; 1303 1304 if (iIsRequired || (!iIsProhibited && iPreference < 0)) { 1305 int i = 0; 1306 Placement p = res[i]; 1307 while (p == null) 1308 p = res[++i]; 1309 i += res[i].getTimeLocation().getLength(); 1310 nrLectures--; 1311 while (nrLectures > 0) { 1312 int gap = 0; 1313 while (i < Constants.SLOTS_PER_DAY && res[i] == null) { 1314 gap++; 1315 i++; 1316 } 1317 if (i == Constants.SLOTS_PER_DAY) 1318 break; 1319 if (!canFill(gap, gapMin, gapMax, lengths)) 1320 return false; 1321 p = res[i]; 1322 i += res[i].getTimeLocation().getLength(); 1323 nrLectures--; 1324 } 1325 } else if (iIsProhibited || (!iIsRequired && iPreference > 0)) { 1326 int i = 0; 1327 Placement p = res[i]; 1328 while (p == null) 1329 p = res[++i]; 1330 i += res[i].getTimeLocation().getLength(); 1331 nrLectures--; 1332 while (nrLectures > 0) { 1333 int gap = 0; 1334 while (i < Constants.SLOTS_PER_DAY && res[i] == null) { 1335 gap++; 1336 i++; 1337 } 1338 if (i == Constants.SLOTS_PER_DAY) 1339 break; 1340 if ((gapMin == 0 || !canFill(gap, 0, gapMin - 1, lengths)) 1341 && (gapMax >= Constants.SLOTS_PER_DAY || !canFill(gap, gapMax + 1, Constants.SLOTS_PER_DAY, 1342 lengths))) { 1343 return false; 1344 } 1345 p = res[i]; 1346 i += res[i].getTimeLocation().getLength(); 1347 nrLectures--; 1348 } 1349 } 1350 return true; 1351 } 1352 1353 public boolean isSatisfied() { 1354 if (isHard()) return true; 1355 if (countAssignedVariables() < 2) return true; 1356 if (getPreference() == 0) return true; 1357 return isHard() || countAssignedVariables() < 2 || getPreference() == 0 || getCurrentPreference() < 0; 1358 } 1359 1360 public boolean isChildrenNotOverlap(Lecture lec1, Placement plc1, Lecture lec2, Placement plc2) { 1361 if (lec1.getSchedulingSubpartId().equals(lec2.getSchedulingSubpartId())) { 1362 // same subpart 1363 boolean overlap = plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 1364 1365 if (overlap && lec1.getParent() != null && variables().contains(lec1.getParent()) 1366 && lec2.getParent() != null && variables().contains(lec2.getParent())) { 1367 // children overlaps 1368 Placement p1 = lec1.getParent().getAssignment(); 1369 Placement p2 = lec2.getParent().getAssignment(); 1370 // parents not overlap, but children do 1371 if (p1 != null && p2 != null && !p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) 1372 return false; 1373 } 1374 1375 if (!overlap && lec1.getChildrenSubpartIds() != null && lec2.getChildrenSubpartIds() != null) { 1376 // parents not overlap 1377 for (Long subpartId: lec1.getChildrenSubpartIds()) { 1378 for (Lecture c1 : lec1.getChildren(subpartId)) { 1379 if (c1.getAssignment() == null) 1380 continue; 1381 for (Lecture c2 : lec2.getChildren(subpartId)) { 1382 if (c2.getAssignment() == null) 1383 continue; 1384 if (!c1.getSchedulingSubpartId().equals(c2.getSchedulingSubpartId())) 1385 continue; 1386 Placement p1 = c1.getAssignment(); 1387 Placement p2 = c2.getAssignment(); 1388 // parents not overlap, but children do 1389 if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) 1390 return false; 1391 } 1392 } 1393 } 1394 } 1395 } else { 1396 // different subpart 1397 } 1398 return true; 1399 } 1400 1401 public boolean isSatisfiedPair(Placement plc1, Placement plc2) { 1402 if (iIsRequired || (!iIsProhibited && iPreference <= 0)) 1403 return getType().isSatisfied(this, plc1, plc2); 1404 else if (iIsProhibited || (!iIsRequired && iPreference > 0)) 1405 return getType().isViolated(this, plc1, plc2); 1406 return true; 1407 } 1408 1409 public boolean canShareRoom() { 1410 return getType().is(Flag.CAN_SHARE_ROOM); 1411 } 1412 1413 private int nrSlotsADay(int dayCode, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 1414 Set<Integer> slots = new HashSet<Integer>(); 1415 for (Lecture lecture: variables()) { 1416 Placement placement = (assignments == null ? null : assignments.get(lecture)); 1417 if (placement == null) { 1418 placement = lecture.getAssignment(); 1419 if (conflicts != null && conflicts.contains(placement)) continue; 1420 } 1421 if (placement == null || placement.getTimeLocation() == null) continue; 1422 TimeLocation t = placement.getTimeLocation(); 1423 if (t == null || (t.getDayCode() & dayCode) == 0) continue; 1424 for (int i = 0; i < t.getLength(); i++) 1425 slots.add(i + t.getStartSlot()); 1426 } 1427 return slots.size(); 1428 } 1429 1430 1431 }