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