001package org.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.BitSet; 005import java.util.HashSet; 006import java.util.HashMap; 007import java.util.Iterator; 008import java.util.List; 009import java.util.Set; 010 011import org.cpsolver.coursett.Constants; 012import org.cpsolver.coursett.criteria.DistributionPreferences; 013import org.cpsolver.coursett.model.Lecture; 014import org.cpsolver.coursett.model.Placement; 015import org.cpsolver.coursett.model.TimeLocation; 016import org.cpsolver.coursett.model.TimetableModel; 017import org.cpsolver.ifs.assignment.Assignment; 018import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 019import org.cpsolver.ifs.assignment.context.ConstraintWithContext; 020import org.cpsolver.ifs.model.Constraint; 021import org.cpsolver.ifs.model.GlobalConstraint; 022import org.cpsolver.ifs.model.Model; 023import org.cpsolver.ifs.model.WeakeningConstraint; 024import org.cpsolver.ifs.util.DataProperties; 025import org.cpsolver.ifs.util.DistanceMetric; 026import org.cpsolver.ifs.util.ToolBox; 027 028 029/** 030 * Group constraint. <br> 031 * This constraint expresses relations between several classes, e.g., that two 032 * sections of the same lecture can not be taught at the same time, or that some 033 * classes have to be taught one immediately after another. It can be either 034 * hard or soft. <br> 035 * <br> 036 * Following constraints are now supported: 037 * <table border='1' summary='Related Solver Parameters'> 038 * <tr> 039 * <th>Constraint</th> 040 * <th>Comment</th> 041 * </tr> 042 * <tr> 043 * <td>SAME_TIME</td> 044 * <td>Same time: given classes have to be taught in the same hours. If the 045 * classes are of different length, the smaller one cannot start before the 046 * longer one and it cannot end after the longer one.</td> 047 * </tr> 048 * <tr> 049 * <td>SAME_DAYS</td> 050 * <td>Same days: given classes have to be taught in the same day. If the 051 * classes are of different time patterns, the days of one class have to form a 052 * subset of the days of the other class.</td> 053 * </tr> 054 * <tr> 055 * <td>BTB</td> 056 * <td>Back-to-back constraint: given classes have to be taught in the same room 057 * and they have to follow one strictly after another.</td> 058 * </tr> 059 * <tr> 060 * <td>BTB_TIME</td> 061 * <td>Back-to-back constraint: given classes have to follow one strictly after 062 * another, but they can be taught in different rooms.</td> 063 * </tr> 064 * <tr> 065 * <td>DIFF_TIME</td> 066 * <td>Different time: given classes cannot overlap in time.</td> 067 * </tr> 068 * <tr> 069 * <td>NHB(1), NHB(1.5), NHB(2), ... NHB(8)</td> 070 * <td>Number of hours between: between the given classes, the exact number of 071 * hours have to be kept.</td> 072 * </tr> 073 * <tr> 074 * <td>SAME_START</td> 075 * <td>Same starting hour: given classes have to start in the same hour.</td> 076 * </tr> 077 * <tr> 078 * <td>SAME_ROOM</td> 079 * <td>Same room: given classes have to be placed in the same room.</td> 080 * </tr> 081 * <tr> 082 * <td>NHB_GTE(1)</td> 083 * <td>Greater than or equal to 1 hour between: between the given classes, the 084 * number of hours have to be one or more.</td> 085 * </tr> 086 * <tr> 087 * <td>NHB_LT(6)</td> 088 * <td>Less than 6 hours between: between the given classes, the number of hours 089 * have to be less than six.</td> 090 * </tr> 091 * </table> 092 * 093 * @version CourseTT 1.3 (University Course Timetabling)<br> 094 * Copyright (C) 2006 - 2014 Tomas Muller<br> 095 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 096 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 097 * <br> 098 * This library is free software; you can redistribute it and/or modify 099 * it under the terms of the GNU Lesser General Public License as 100 * published by the Free Software Foundation; either version 3 of the 101 * License, or (at your option) any later version. <br> 102 * <br> 103 * This library is distributed in the hope that it will be useful, but 104 * WITHOUT ANY WARRANTY; without even the implied warranty of 105 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 106 * Lesser General Public License for more details. <br> 107 * <br> 108 * You should have received a copy of the GNU Lesser General Public 109 * License along with this library; if not see 110 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 111 */ 112 113public class GroupConstraint extends ConstraintWithContext<Lecture, Placement, GroupConstraint.GroupConstraintContext> { 114 private Long iConstraintId; 115 private int iPreference; 116 private ConstraintType iType; 117 private boolean iIsRequired; 118 private boolean iIsProhibited; 119 private int iDayOfWeekOffset = 0; 120 private boolean iPrecedenceConsiderDatePatterns = true; 121 private boolean iMaxNHoursADayConsiderDatePatterns = true; 122 private int iForwardCheckMaxDepth = 2; 123 private int iForwardCheckMaxDomainSize = 1000; 124 private int iNrWorkDays = 5; 125 private int iFirstWorkDay = 0; 126 127 /** 128 * Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room), 129 * only need to implement this interface. 130 */ 131 public static interface PairCheck { 132 /** 133 * Check whether the constraint is satisfied for the given two assignments (required / preferred case) 134 * @param gc Calling group constraint 135 * @param plc1 First placement 136 * @param plc2 Second placement 137 * @return true if constraint is satisfied 138 */ 139 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2); 140 /** 141 * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case) 142 * @param gc Calling group constraint 143 * @param plc1 First placement 144 * @param plc2 Second placement 145 * @return true if constraint is satisfied 146 */ 147 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2); 148 } 149 150 /** 151 * Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room), 152 * only need to implement this interface. Unlike {@link PairCheck}, this check is also given current assignment. 153 */ 154 public static interface AssignmentPairCheck { 155 /** 156 * Check whether the constraint is satisfied for the given two assignments (required / preferred case) 157 * @param assignment current assignment 158 * @param gc Calling group constraint 159 * @param plc1 First placement 160 * @param plc2 Second placement 161 * @return true if constraint is satisfied 162 */ 163 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2); 164 /** 165 * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case) 166 * @param assignment current assignment 167 * @param gc Calling group constraint 168 * @param plc1 First placement 169 * @param plc2 Second placement 170 * @return true if constraint is satisfied 171 */ 172 public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2); 173 } 174 175 /** 176 * Group constraint building blocks (individual constraints that need more than {@link PairCheck}) 177 */ 178 public static enum Flag { 179 /** Back-to-back constraint (sequence check) */ 180 BACK_TO_BACK, 181 /** Can share room flag */ 182 CAN_SHARE_ROOM, 183 /** Maximum hours a day (number of slots a day check) */ 184 MAX_HRS_DAY, 185 /** Children cannot overlap */ 186 CH_NOTOVERLAP; 187 /** Bit number (to combine flags) */ 188 int flag() { return 1 << ordinal(); } 189 } 190 191 /** 192 * Group constraint type. 193 */ 194 public static enum ConstraintType { 195 /** 196 * Same Time: Given classes must be taught at the same time of day (independent of the actual day the classes meet). 197 * For the classes of the same length, this is the same constraint as same start. For classes of different length, 198 * the shorter one cannot start before, nor end after, the longer one.<BR> 199 * When prohibited or (strongly) discouraged: one class may not meet on any day at a time of day that overlaps with 200 * that of the other. For example, one class can not meet M 7:30 while the other meets F 7:30. Note the difference 201 * here from the different time constraint that only prohibits the actual class meetings from overlapping. 202 */ 203 SAME_TIME("SAME_TIME", "Same Time", new PairCheck() { 204 @Override 205 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 206 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 207 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()); 208 } 209 @Override 210 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 211 return !(plc1.getTimeLocation().shareHours(plc2.getTimeLocation())); 212 }}), 213 /** 214 * Same Days: Given classes must be taught on the same days. In case of classes of different time patterns, a class 215 * with fewer meetings must meet on a subset of the days used by the class with more meetings. For example, if one 216 * class pattern is 3x50, all others given in the constraint can only be taught on Monday, Wednesday, or Friday. 217 * For a 2x100 class MW, MF, WF is allowed but TTh is prohibited.<BR> 218 * When prohibited or (strongly) discouraged: any pair of classes classes cannot be taught on the same days (cannot 219 * overlap in days). For instance, if one class is MFW, the second has to be TTh. 220 */ 221 SAME_DAYS("SAME_DAYS", "Same Days", new PairCheck() { 222 @Override 223 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 224 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 225 } 226 @Override 227 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 228 return !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()); 229 }}), 230 /** 231 * Back-To-Back & Same Room: Classes must be offered in adjacent time segments and must be placed in the same room. 232 * Given classes must also be taught on the same days.<BR> 233 * When prohibited or (strongly) discouraged: classes cannot be back-to-back. There must be at least half-hour 234 * between these classes, and they must be taught on the same days and in the same room. 235 */ 236 BTB("BTB", "Back-To-Back & Same Room", new PairCheck() { 237 @Override 238 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 239 return 240 plc1.sameRooms(plc2) && 241 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 242 } 243 @Override 244 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 245 return 246 plc1.sameRooms(plc2) && 247 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 248 }}, Flag.BACK_TO_BACK), 249 /** 250 * Back-To-Back: Classes must be offered in adjacent time segments but may be placed in different rooms. Given classes 251 * must also be taught on the same days.<BR> 252 * When prohibited or (strongly) discouraged: no pair of classes can be taught back-to-back. They may not overlap in time, 253 * but must be taught on the same days. This means that there must be at least half-hour between these classes. 254 */ 255 BTB_TIME("BTB_TIME", "Back-To-Back", new PairCheck() { 256 @Override 257 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 258 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 259 } 260 @Override 261 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 262 return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 263 }}, Flag.BACK_TO_BACK), 264 /** 265 * Different Time: Given classes cannot overlap in time. They may be taught at the same time of day if they are on 266 * different days. For instance, MF 7:30 is compatible with TTh 7:30.<BR> 267 * When prohibited or (strongly) discouraged: every pair of classes in the constraint must overlap in time. 268 */ 269 DIFF_TIME("DIFF_TIME", "Different Time", new PairCheck() { 270 @Override 271 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 272 return !plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 273 } 274 @Override 275 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 276 return plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 277 }}), 278 /** 279 * 1 Hour Between: Given classes must have exactly 1 hour 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 1 hour in between. They may not overlap in time 282 * but must be taught on the same days. 283 */ 284 NHB_1("NHB(1)", "1 Hour Between", 10, 12, BTB_TIME.check(), Flag.BACK_TO_BACK), 285 /** 286 * 2 Hours Between: Given classes must have exactly 2 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 2 hours in between. They may not overlap in time 289 * but must be taught on the same days. 290 */ 291 NHB_2("NHB(2)", "2 Hours Between", 20, 24, BTB_TIME.check(), Flag.BACK_TO_BACK), 292 /** 293 * 3 Hours Between: Given classes must have exactly 3 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 3 hours in between. They may not overlap in time 296 * but must be taught on the same days. 297 */ 298 NHB_3("NHB(3)", "3 Hours Between", 30, 36, BTB_TIME.check(), Flag.BACK_TO_BACK), 299 /** 300 * 4 Hours Between: Given classes must have exactly 4 hours in between the end of one and the beginning of another. 301 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 302 * When prohibited or (strongly) discouraged: classes can not have 4 hours in between. They may not overlap in time 303 * but must be taught on the same days. 304 */ 305 NHB_4("NHB(4)", "4 Hours Between", 40, 48, BTB_TIME.check(), Flag.BACK_TO_BACK), 306 /** 307 * 5 Hours Between: Given classes must have exactly 5 hours in between the end of one and the beginning of another. 308 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 309 * When prohibited or (strongly) discouraged: classes can not have 5 hours in between. They may not overlap in time 310 * but must be taught on the same days. 311 */ 312 NHB_5("NHB(5)", "5 Hours Between", 50, 60, BTB_TIME.check(), Flag.BACK_TO_BACK), 313 /** 314 * 6 Hours Between: Given classes must have exactly 6 hours in between the end of one and the beginning of another. 315 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 316 * When prohibited or (strongly) discouraged: classes can not have 6 hours in between. They may not overlap in time 317 * but must be taught on the same days. 318 */ 319 NHB_6("NHB(6)", "6 Hours Between", 60, 72, BTB_TIME.check(), Flag.BACK_TO_BACK), 320 /** 321 * 7 Hours Between: Given classes must have exactly 7 hours in between the end of one and the beginning of another. 322 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 323 * When prohibited or (strongly) discouraged: classes can not have 7 hours in between. They may not overlap in time 324 * but must be taught on the same days. 325 */ 326 NHB_7("NHB(7)", "7 Hours Between", 70, 84, BTB_TIME.check(), Flag.BACK_TO_BACK), 327 /** 328 * 8 Hours Between: Given classes must have exactly 8 hours in between the end of one and the beginning of another. 329 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 330 * When prohibited or (strongly) discouraged: classes can not have 8 hours in between. They may not overlap in time 331 * but must be taught on the same days. 332 */ 333 NHB_8("NHB(8)", "8 Hours Between", 80, 96, BTB_TIME.check(), Flag.BACK_TO_BACK), 334 /** 335 * Same Start Time: Given classes must start during the same half-hour period of a day (independent of the actual 336 * day the classes meet). For instance, MW 7:30 is compatible with TTh 7:30 but not with MWF 8:00.<BR> 337 * When prohibited or (strongly) discouraged: any pair of classes in the given constraint cannot start during the 338 * same half-hour period of any day of the week. 339 */ 340 SAME_START("SAME_START", "Same Start Time", new PairCheck() { 341 @Override 342 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 343 return 344 (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) == 345 (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY); 346 } 347 @Override 348 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 349 return 350 (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) != 351 (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY); 352 }}), 353 /** 354 * Same Room: Given classes must be taught in the same room.<BR> 355 * When prohibited or (strongly) discouraged: any pair of classes in the constraint cannot be taught in the same room. 356 */ 357 SAME_ROOM("SAME_ROOM", "Same Room", new PairCheck() { 358 @Override 359 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 360 return plc1.sameRooms(plc2); 361 } 362 @Override 363 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 364 return !plc1.sameRooms(plc2); 365 }}), 366 /** 367 * At Least 1 Hour Between: Given classes have to have 1 hour or more in between.<BR> 368 * When prohibited or (strongly) discouraged: given classes have to have less than 1 hour in between. 369 */ 370 NHB_GTE_1("NHB_GTE(1)", "At Least 1 Hour Between", 6, 288, BTB_TIME.check(), Flag.BACK_TO_BACK), 371 /** 372 * Less Than 6 Hours Between: Given classes must have less than 6 hours from end of first class to the beginning of 373 * the next. Given classes must also be taught on the same days.<BR> 374 * When prohibited or (strongly) discouraged: given classes must have 6 or more hours between. This constraint does 375 * not carry over from classes taught at the end of one day to the beginning of the next. 376 */ 377 NHB_LT_6("NHB_LT(6)", "Less Than 6 Hours Between", 0, 72, BTB_TIME.check(), Flag.BACK_TO_BACK), 378 /** 379 * 1.5 Hour Between: Given classes must have exactly 90 minutes in between the end of one and the beginning of another. 380 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 381 * When prohibited or (strongly) discouraged: classes can not have 90 minutes in between. They may not overlap in time 382 * but must be taught on the same days. 383 */ 384 NHB_1_5("NHB(1.5)", "1.5 Hour Between", 15, 18, BTB_TIME.check(), Flag.BACK_TO_BACK), 385 /** 386 * 4.5 Hours Between: Given classes must have exactly 4.5 hours in between the end of one and the beginning of another. 387 * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR> 388 * When prohibited or (strongly) discouraged: classes can not have 4.5 hours in between. They may not overlap in time 389 * but must be taught on the same days. 390 */ 391 NHB_4_5("NHB(4.5)", "4.5 Hours Between", 45, 54, BTB_TIME.check(), Flag.BACK_TO_BACK), 392 /** 393 * Same Students: Given classes are treated as they are attended by the same students, i.e., they cannot overlap in time 394 * and if they are back-to-back the assigned rooms cannot be too far (student limit is used). 395 */ 396 SAME_STUDENTS("SAME_STUDENTS", "Same Students", new PairCheck() { 397 @Override 398 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 399 return !JenrlConstraint.isInConflict(plc1, plc2, ((TimetableModel)gc.getModel()).getDistanceMetric(), ((TimetableModel)gc.getModel()).getStudentWorkDayLimit()); 400 } 401 @Override 402 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 403 return true; 404 }}), 405 /** 406 * Same Instructor: Given classes are treated as they are taught by the same instructor, i.e., they cannot overlap in time 407 * and if they are back-to-back the assigned rooms cannot be too far (instructor limit is used).<BR> 408 * If the constraint is required and the classes are back-to-back, discouraged and strongly discouraged distances between 409 * assigned rooms are also considered. 410 */ 411 SAME_INSTR("SAME_INSTR", "Same Instructor", new PairCheck() { 412 @Override 413 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 414 TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation(); 415 if (t1.shareDays(t2) && t1.shareWeeks(t2)) { 416 if (t1.shareHours(t2)) return false; // overlap 417 DistanceMetric m = ((TimetableModel)gc.getModel()).getDistanceMetric(); 418 if ((t1.getStartSlot() + t1.getLength() == t2.getStartSlot() || t2.getStartSlot() + t2.getLength() == t1.getStartSlot())) { 419 if (Placement.getDistanceInMeters(m, plc1, plc2) > m.getInstructorProhibitedLimit()) 420 return false; 421 } else if (m.doComputeDistanceConflictsBetweenNonBTBClasses()) { 422 if (t1.getStartSlot() + t1.getLength() < t2.getStartSlot() && 423 Placement.getDistanceInMinutes(m, plc1, plc2) > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t2.getStartSlot() - t1.getStartSlot() - t1.getLength())) 424 return false; 425 if (t2.getStartSlot() + t2.getLength() < t1.getStartSlot() && 426 Placement.getDistanceInMinutes(m, plc1, plc2) > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t1.getStartSlot() - t2.getStartSlot() - t2.getLength())) 427 return false; 428 } 429 } 430 return true; 431 } 432 @Override 433 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 434 return true; 435 }}), 436 /** 437 * Can Share Room: Given classes can share the room (use the room in the same time) if the room is big enough. 438 */ 439 CAN_SHARE_ROOM("CAN_SHARE_ROOM", "Can Share Room", Flag.CAN_SHARE_ROOM), 440 /** 441 * Precedence: Given classes have to be taught in the given order (the first meeting of the first class has to end before 442 * the first meeting of the second class etc.)<BR> 443 * When prohibited or (strongly) discouraged: classes have to be taught in the order reverse to the given one. 444 */ 445 PRECEDENCE("PRECEDENCE", "Precedence", new PairCheck() { 446 @Override 447 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 448 return gc.isPrecedence(plc1, plc2, true, true); 449 } 450 @Override 451 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 452 return gc.isPrecedence(plc1, plc2, false, true); 453 }}), 454 /** 455 * Back-To-Back Day: Classes must be offered on adjacent days and may be placed in different rooms.<BR> 456 * When prohibited or (strongly) discouraged: classes can not be taught on adjacent days. They also can not be taught 457 * on the same days. This means that there must be at least one day between these classes. 458 */ 459 BTB_DAY("BTB_DAY", "Back-To-Back Day", 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 gc.isBackToBackDays(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 !gc.isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation()); 471 }}), 472 /** 473 * Meet Together: Given classes are meeting together (same as if the given classes require constraints Can Share Room, 474 * Same Room, Same Time and Same Days all together). 475 */ 476 MEET_WITH("MEET_WITH", "Meet Together", new PairCheck() { 477 @Override 478 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 479 return 480 plc1.sameRooms(plc2) && 481 sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 482 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 483 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 484 485 } 486 @Override 487 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 488 return true; 489 }}, Flag.CAN_SHARE_ROOM), 490 /** 491 * More Than 1 Day Between: Given classes must have two or more days in between.<br> 492 * When prohibited or (strongly) discouraged: given classes must be offered on adjacent days or with at most one day in between. 493 */ 494 NDB_GT_1("NDB_GT_1", "More Than 1 Day Between", new PairCheck() { 495 @Override 496 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 497 return 498 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 499 gc.isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation()); 500 } 501 @Override 502 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 503 return 504 !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 505 !gc.isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation()); 506 }}), 507 /** 508 * Children Cannot Overlap: If parent classes do not overlap in time, children classes can not overlap in time as well.<BR> 509 * Note: This constraint only needs to be put on the parent classes. Preferred configurations are Required All Classes 510 * or Pairwise (Strongly) Preferred. 511 */ 512 CH_NOTOVERLAP("CH_NOTOVERLAP", "Children Cannot Overlap", new AssignmentPairCheck() { 513 @Override 514 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 515 return gc.isChildrenNotOverlap(assignment, plc1.variable(), plc1, plc2.variable(), plc2); 516 } 517 @Override 518 public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 519 return true; 520 }}), 521 /** 522 * Next Day: The second class has to be placed on the following day of the first class (if the first class is on Friday, 523 * second class have to be on Monday).<br> 524 * When prohibited or (strongly) discouraged: The second class has to be placed on the previous day of the first class 525 * (if the first class is on Monday, second class have to be on Friday).<br> 526 * Note: This constraint works only between pairs of classes. 527 */ 528 FOLLOWING_DAY("FOLLOWING_DAY", "Next Day", new PairCheck() { 529 @Override 530 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 531 return gc.isFollowingDay(plc1, plc2, true); 532 } 533 @Override 534 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 535 return gc.isFollowingDay(plc1, plc2, false); 536 }}), 537 /** 538 * Two Days After: The second class has to be placed two days after the first class (Monday → Wednesday, Tuesday → 539 * Thurday, Wednesday → Friday, Thursday → Monday, Friday → Tuesday).<br> 540 * When prohibited or (strongly) discouraged: The second class has to be placed two days before the first class (Monday → 541 * Thursday, Tuesday → Friday, Wednesday → Monday, Thursday → Tuesday, Friday → Wednesday).<br> 542 * Note: This constraint works only between pairs of classes. 543 */ 544 EVERY_OTHER_DAY("EVERY_OTHER_DAY", "Two Days After", new PairCheck() { 545 @Override 546 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 547 return gc.isEveryOtherDay(plc1, plc2, true); 548 } 549 @Override 550 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 551 return gc.isEveryOtherDay(plc1, plc2, false); 552 }}), 553 /** 554 * At Most 3 Hours A Day: Classes are to be placed in a way that there is no more than three hours in any day. 555 */ 556 MAX_HRS_DAY_3("MAX_HRS_DAY(3)", "At Most 3 Hours A Day", 36, null, Flag.MAX_HRS_DAY), 557 /** 558 * At Most 4 Hours A Day: Classes are to be placed in a way that there is no more than four hours in any day. 559 */ 560 MAX_HRS_DAY_4("MAX_HRS_DAY(4)", "At Most 4 Hours A Day", 48, null, Flag.MAX_HRS_DAY), 561 /** 562 * 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. 563 */ 564 MAX_HRS_DAY_5("MAX_HRS_DAY(5)", "At Most 5 Hours A Day", 60, null, Flag.MAX_HRS_DAY), 565 /** 566 * 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. 567 */ 568 MAX_HRS_DAY_6("MAX_HRS_DAY(6)", "At Most 6 Hours A Day", 72, null, Flag.MAX_HRS_DAY), 569 /** 570 * 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. 571 */ 572 MAX_HRS_DAY_7("MAX_HRS_DAY(7)", "At Most 7 Hours A Day", 84, null, Flag.MAX_HRS_DAY), 573 /** 574 * 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. 575 */ 576 MAX_HRS_DAY_8("MAX_HRS_DAY(8)", "At Most 8 Hours A Day", 96, null, Flag.MAX_HRS_DAY), 577 /** 578 * At Most 9 Hours A Day: Classes are to be placed in a way that there is no more than nine hours in any day. 579 */ 580 MAX_HRS_DAY_9("MAX_HRS_DAY(9)", "At Most 9 Hours A Day", 108, null, Flag.MAX_HRS_DAY), 581 /** 582 * At Most 10 Hours A Day: Classes are to be placed in a way that there is no more than ten hours in any day. 583 */ 584 MAX_HRS_DAY_10("MAX_HRS_DAY(10)", "At Most 10 Hours A Day", 120, null, Flag.MAX_HRS_DAY), 585 /** 586 * Given classes must be taught during the same weeks (i.e., must have the same date pattern).<br> 587 * When prohibited or (strongly) discouraged: any two classes must have non overlapping date patterns. 588 */ 589 SAME_WEEKS("SAME_WEEKS", "Same Weeks", new PairCheck() { 590 @Override 591 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 592 return plc1.getTimeLocation().getWeekCode().equals(plc2.getTimeLocation().getWeekCode()); 593 } 594 @Override 595 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 596 return !plc1.getTimeLocation().shareWeeks(plc2.getTimeLocation()); 597 }}), 598 /** 599 * Classes (of different courses) are to be attended by the same students. For instance, 600 * if class A1 (of a course A) and class B1 (of a course B) are linked, a student requesting 601 * both courses must attend A1 if and only if he also attends B1. This is a student sectioning 602 * constraint that is interpreted as Same Students constraint during course timetabling. 603 */ 604 LINKED_SECTIONS("LINKED_SECTIONS", "Linked Classes", SAME_STUDENTS.check()), 605 /** 606 * Back-To-Back Precedence: Given classes have to be taught in the given order, on the same days, 607 * and in adjacent time segments. 608 * When prohibited or (strongly) discouraged: Given classes have to be taught in the given order, 609 * on the same days, but cannot be back-to-back. 610 */ 611 BTB_PRECEDENCE("BTB_PRECEDENCE", "Back-To-Back Precedence", new PairCheck() { 612 @Override 613 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 614 return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 615 } 616 @Override 617 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 618 return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 619 }}, Flag.BACK_TO_BACK), 620 621 /** 622 * Same Days-Time: Given classes must be taught at the same time of day and on the same days. 623 * It is the combination of Same Days and Same Time distribution preferences. 624 * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days 625 * during the same time. 626 */ 627 SAME_DAYS_TIME("SAME_D_T", "Same Days-Time", new PairCheck() { 628 @Override 629 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 630 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 631 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 632 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()); 633 } 634 @Override 635 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 636 return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) || 637 !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()); 638 }}), 639 /** 640 * Same Days-Room-Time: Given classes must be taught at the same time of day, on the same days and in the same room. 641 * It is the combination of Same Days, Same Time and Same Room distribution preferences. 642 * Note that this constraint is the same as Meet Together constraint, except it does not allow room sharing. In other words, 643 * it is only useful when these classes are taught during non-overlapping date patterns. 644 * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days 645 * during the same time in the same room. 646 */ 647 SAME_DAYS_ROOM_TIME("SAME_D_R_T", "Same Days-Room-Time", new PairCheck() { 648 @Override 649 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 650 return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), 651 plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 652 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 653 plc1.sameRooms(plc2); 654 } 655 @Override 656 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 657 return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) || 658 !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()) || 659 !plc1.sameRooms(plc2); 660 }}), 661 /** 662 * 6 Hour Work Day: Classes are to be placed in a way that there is no more than six hours between the start of the first class and the end of the class one on any day. 663 */ 664 WORKDAY_6("WORKDAY(6)", "6 Hour Work Day", 72, new PairCheck() { 665 @Override 666 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 667 TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation(); 668 if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return true; 669 return Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()) <= gc.getType().getMax(); 670 } 671 @Override 672 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { return true; } 673 }), 674 /** 675 * 7 Hour Work Day: Classes are to be placed in a way that there is no more than seven hours between the start of the first class and the end of the class one on any day. 676 */ 677 WORKDAY_7("WORKDAY(7)", "7 Hour Work Day", 84, WORKDAY_6.check()), 678 /** 679 * 8 Hour Work Day: Classes are to be placed in a way that there is no more than eight hours between the start of the first class and the end of the class one on any day. 680 */ 681 WORKDAY_8("WORKDAY(8)", "8 Hour Work Day", 96, WORKDAY_6.check()), 682 /** 683 * 9 Hour Work Day: Classes are to be placed in a way that there is no more than nine hours between the start of the first class and the end of the class one on any day. 684 */ 685 WORKDAY_9("WORKDAY(9)", "9 Hour Work Day", 108, WORKDAY_6.check()), 686 /** 687 * 10 Hour Work Day: Classes are to be placed in a way that there is no more than ten hours between the start of the first class and the end of the class one on any day. 688 */ 689 WORKDAY_10("WORKDAY(10)", "10 Hour Work Day", 120, WORKDAY_6.check()), 690 /** 691 * 11 Hour Work Day: Classes are to be placed in a way that there is no more than eleven hours between the start of the first class and the end of the class one on any day. 692 */ 693 WORKDAY_11("WORKDAY(11)", "11 Hour Work Day", 132, WORKDAY_6.check()), 694 /** 695 * 12 Hour Work Day: Classes are to be placed in a way that there is no more than twelve hours between the start of the first class and the end of the class one on any day. 696 */ 697 WORKDAY_12("WORKDAY(12)", "12 Hour Work Day", 144, WORKDAY_6.check()), 698 /** 699 * 4 Hour Work Day: Classes are to be placed in a way that there is no more than four hours between the start of the first class and the end of the class one on any day. 700 */ 701 WORKDAY_4("WORKDAY(4)", "4 Hour Work Day", 48, WORKDAY_6.check()), 702 /** 703 * 5 Hour Work Day: Classes are to be placed in a way that there is no more than five hours between the start of the first class and the end of the class one on any day. 704 */ 705 WORKDAY_5("WORKDAY(5)", "5 Hour Work Day", 60, WORKDAY_6.check()), 706 /** 707 * Meet Together & Same Weeks: Given classes are meeting together (same as if the given classes require constraints Can Share Room, 708 * Same Room, Same Time, Same Days and Same Weeks all together). 709 */ 710 MEET_WITH_WEEKS("MEET_WITH_WEEKS", "Meet Together & Same Weeks", new PairCheck() { 711 @Override 712 public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { 713 return 714 plc1.sameRooms(plc2) && 715 sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) && 716 sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) && 717 plc1.getTimeLocation().getWeekCode().equals(plc2.getTimeLocation().getWeekCode()); 718 } 719 @Override 720 public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { 721 return true; 722 }}, Flag.CAN_SHARE_ROOM), 723 ; 724 725 String iReference, iName; 726 int iFlag = 0; 727 Flag[] iFlags = null; 728 int iMin = 0, iMax = 0; 729 PairCheck iCheck = null; 730 AssignmentPairCheck iAssignmentCheck = null; 731 ConstraintType(String reference, String name, Flag... flags) { 732 iReference = reference; 733 iName = name; 734 iFlags = flags; 735 for (Flag f: flags) 736 iFlag |= f.flag(); 737 } 738 ConstraintType(String reference, String name, PairCheck check, Flag... flags) { 739 this(reference, name, flags); 740 iCheck = check; 741 } 742 ConstraintType(String reference, String name, AssignmentPairCheck check, Flag... flags) { 743 this(reference, name, flags); 744 iAssignmentCheck = check; 745 } 746 ConstraintType(String reference, String name, int limit, PairCheck check, Flag... flags) { 747 this(reference, name, check, flags); 748 iMin = iMax = limit; 749 } 750 ConstraintType(String reference, String name, int min, int max, PairCheck check, Flag... flags) { 751 this(reference, name, check, flags); 752 iMin = min; 753 iMax = max; 754 } 755 756 /** Constraint reference 757 * @return constraint reference 758 **/ 759 public String reference() { return iReference; } 760 /** Constraint name 761 * @return constraint name 762 **/ 763 public String getName() { return iName; } 764 /** Minimum (gap) parameter 765 * @return minimum gap (first constraint parameter) 766 **/ 767 public int getMin() { return iMin; } 768 /** Maximum (gap, hours a day) parameter 769 * @return maximum gap (second constraint parameter) 770 **/ 771 public int getMax() { return iMax; } 772 773 /** Flag check (true if contains given flag) 774 * @param f a flag to check 775 * @return true if present 776 **/ 777 public boolean is(Flag f) { return (iFlag & f.flag()) != 0; } 778 779 /** Constraint type from reference 780 * @param reference constraint reference 781 * @return constraint of the reference 782 **/ 783 public static ConstraintType get(String reference) { 784 for (ConstraintType t: ConstraintType.values()) 785 if (t.reference().equals(reference)) return t; 786 return null; 787 } 788 789 /** True if a required or preferred constraint is satisfied between a pair of placements 790 * @param assignment current assignment 791 * @param gc current constraint 792 * @param plc1 first placement 793 * @param plc2 second placement 794 * @return true if the two placements are consistent with the constraint if preferred or required 795 **/ 796 public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 797 if (iCheck != null && !iCheck.isSatisfied(gc, plc1, plc2)) 798 return false; 799 if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isSatisfied(assignment, gc, plc1, plc2)) 800 return false; 801 return true; 802 } 803 /** True if a prohibited or discouraged constraint is satisfied between a pair of placements 804 * @param assignment current assignment 805 * @param gc current constraint 806 * @param plc1 first placement 807 * @param plc2 second placement 808 * @return true if the two placements are consistent with the constraint if discouraged or prohibited 809 **/ 810 public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 811 if (iCheck != null && !iCheck.isViolated(gc, plc1, plc2)) 812 return false; 813 if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isViolated(assignment, gc, plc1, plc2)) 814 return false; 815 return true; 816 } 817 /** Pair check */ 818 private PairCheck check() { return iCheck; } 819 } 820 821 public GroupConstraint() { 822 } 823 824 @Override 825 public void setModel(Model<Lecture, Placement> model) { 826 super.setModel(model); 827 if (model != null) { 828 DataProperties config = ((TimetableModel)model).getProperties(); 829 iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0); 830 iPrecedenceConsiderDatePatterns = config.getPropertyBoolean("Precedence.ConsiderDatePatterns", true); 831 iForwardCheckMaxDepth = config.getPropertyInt("ForwardCheck.MaxDepth", iForwardCheckMaxDepth); 832 iForwardCheckMaxDomainSize = config.getPropertyInt("ForwardCheck.MaxDomainSize", iForwardCheckMaxDomainSize); 833 iMaxNHoursADayConsiderDatePatterns = config.getPropertyBoolean("MaxNHoursADay.ConsiderDatePatterns", iMaxNHoursADayConsiderDatePatterns); 834 iNrWorkDays = (config.getPropertyInt("General.LastWorkDay", 4) - config.getPropertyInt("General.FirstWorkDay", 0) + 1); 835 if (iNrWorkDays <= 0) iNrWorkDays += 7; 836 if (iNrWorkDays > 7) iNrWorkDays -= 7; 837 iFirstWorkDay = config.getPropertyInt("General.FirstWorkDay", 0); 838 } 839 } 840 841 @Override 842 public void addVariable(Lecture lecture) { 843 if (!variables().contains(lecture)) 844 super.addVariable(lecture); 845 if (getType().is(Flag.CH_NOTOVERLAP)) { 846 if (lecture.getChildrenSubpartIds() != null) { 847 for (Long subpartId: lecture.getChildrenSubpartIds()) { 848 for (Lecture ch : lecture.getChildren(subpartId)) { 849 if (!variables().contains(ch)) 850 super.addVariable(ch); 851 } 852 } 853 } 854 } 855 } 856 857 @Override 858 public void removeVariable(Lecture lecture) { 859 if (variables().contains(lecture)) 860 super.removeVariable(lecture); 861 if (getType().is(Flag.CH_NOTOVERLAP)) { 862 if (lecture.getChildrenSubpartIds() != null) { 863 for (Long subpartId: lecture.getChildrenSubpartIds()) { 864 for (Lecture ch : lecture.getChildren(subpartId)) { 865 if (variables().contains(ch)) 866 super.removeVariable(ch); 867 } 868 } 869 } 870 } 871 } 872 873 /** 874 * Constructor 875 * 876 * @param id 877 * constraint id 878 * @param type 879 * constraString type (e.g, {@link ConstraintType#SAME_TIME}) 880 * @param preference 881 * time preference ("R" for required, "P" for prohibited, "-2", 882 * "-1", "1", "2" for soft preference) 883 */ 884 public GroupConstraint(Long id, ConstraintType type, String preference) { 885 iConstraintId = id; 886 iType = type; 887 iIsRequired = preference.equals(Constants.sPreferenceRequired); 888 iIsProhibited = preference.equals(Constants.sPreferenceProhibited); 889 iPreference = Constants.preference2preferenceLevel(preference); 890 } 891 892 /** Constraint id 893 * @return constraint unique id 894 **/ 895 public Long getConstraintId() { 896 return iConstraintId; 897 } 898 899 @Override 900 public long getId() { 901 return (iConstraintId == null ? -1 : iConstraintId.longValue()); 902 } 903 904 /** Generated unique id 905 * @return generated unique id 906 **/ 907 protected long getGeneratedId() { 908 return iId; 909 } 910 911 /** Return constraint type (e.g, {@link ConstraintType#SAME_TIME}) 912 * @return constraint type 913 **/ 914 public ConstraintType getType() { 915 return iType; 916 } 917 918 /** 919 * Set constraint type 920 * @param type constraint type 921 */ 922 public void setType(ConstraintType type) { 923 iType = type; 924 } 925 926 /** Is constraint required 927 * @return true if required 928 **/ 929 public boolean isRequired() { 930 return iIsRequired; 931 } 932 933 /** Is constraint prohibited 934 * @return true if prohibited 935 **/ 936 public boolean isProhibited() { 937 return iIsProhibited; 938 } 939 940 /** 941 * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for 942 * preference 943 * @return prolog preference 944 */ 945 public String getPrologPreference() { 946 return Constants.preferenceLevel2preference(iPreference); 947 } 948 949 @Override 950 public boolean isConsistent(Placement value1, Placement value2) { 951 if (!isHard()) 952 return true; 953 if (!isSatisfiedPair(null, value1, value2)) 954 return false; 955 if (getType().is(Flag.BACK_TO_BACK)) { 956 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 957 assignments.put(value1.variable(), value1); 958 assignments.put(value2.variable(), value2); 959 if (!isSatisfiedSeq(null, assignments, null)) 960 return false; 961 } 962 if (getType().is(Flag.MAX_HRS_DAY)) { 963 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 964 assignments.put(value1.variable(), value1); 965 assignments.put(value2.variable(), value2); 966 for (int dayCode: Constants.DAY_CODES) { 967 if (iMaxNHoursADayConsiderDatePatterns) { 968 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 969 if (!value1.getTimeLocation().shareWeeks(week) && !value2.getTimeLocation().shareWeeks(week)) continue; 970 if (nrSlotsADay(null, dayCode, week, assignments, null) > getType().getMax()) return false; 971 } 972 } else { 973 if (nrSlotsADay(null, dayCode, null, assignments, null) > getType().getMax()) return false; 974 } 975 } 976 } 977 return true; 978 } 979 980 @Override 981 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 982 computeConflicts(assignment, value, conflicts, true); 983 } 984 985 @Override 986 public void computeConflictsNoForwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 987 computeConflicts(assignment, value, conflicts, false); 988 } 989 990 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, boolean fwdCheck) { 991 if (!isHard()) 992 return; 993 for (Lecture v : variables()) { 994 if (v.equals(value.variable())) 995 continue; // ignore this variable 996 Placement p = assignment.getValue(v); 997 if (p == null) 998 continue; // there is an unassigned variable -- great, still a chance to get violated 999 if (!isSatisfiedPair(assignment, p, value)) 1000 conflicts.add(p); 1001 } 1002 if (getType().is(Flag.BACK_TO_BACK)) { 1003 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1004 assignments.put(value.variable(), value); 1005 if (!isSatisfiedSeq(assignment, assignments, conflicts)) 1006 conflicts.add(value); 1007 } 1008 if (getType().is(Flag.MAX_HRS_DAY)) { 1009 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1010 assignments.put(value.variable(), value); 1011 for (int dayCode: Constants.DAY_CODES) { 1012 if (iMaxNHoursADayConsiderDatePatterns) { 1013 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1014 if (!value.getTimeLocation().shareWeeks(week)) continue; 1015 if (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax()) { 1016 List<Placement> adepts = new ArrayList<Placement>(); 1017 for (Lecture l: variables()) { 1018 if (l.equals(value.variable()) || l.isConstant()) continue; 1019 Placement p = assignment.getValue(l); 1020 if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue; 1021 if ((p.getTimeLocation().getDayCode() & dayCode) == 0 || !p.getTimeLocation().shareWeeks(week)) continue; 1022 adepts.add(p); 1023 } 1024 do { 1025 if (adepts.isEmpty()) { conflicts.add(value); break; } 1026 Placement conflict = ToolBox.random(adepts); 1027 adepts.remove(conflict); 1028 conflicts.add(conflict); 1029 } while (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax()); 1030 } 1031 } 1032 } else { 1033 if (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax()) { 1034 List<Placement> adepts = new ArrayList<Placement>(); 1035 for (Lecture l: variables()) { 1036 if (l.equals(value.variable()) || l.isConstant()) continue; 1037 Placement p = assignment.getValue(l); 1038 if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue; 1039 if ((p.getTimeLocation().getDayCode() & dayCode) == 0) continue; 1040 adepts.add(p); 1041 } 1042 do { 1043 if (adepts.isEmpty()) { conflicts.add(value); break; } 1044 Placement conflict = ToolBox.random(adepts); 1045 adepts.remove(conflict); 1046 conflicts.add(conflict); 1047 } while (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax()); 1048 } 1049 } 1050 } 1051 } 1052 1053 // Forward checking 1054 if (fwdCheck) forwardCheck(assignment, value, conflicts, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1); 1055 } 1056 1057 public void forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, Set<GroupConstraint> ignore, int depth) { 1058 try { 1059 if (depth < 0) return; 1060 ignore.add(this); 1061 1062 int neededSize = value.variable().maxRoomUse(); 1063 1064 for (Lecture lecture: variables()) { 1065 if (conflicts.contains(value)) break; // already conflicting 1066 1067 if (lecture.equals(value.variable())) continue; // Skip this lecture 1068 Placement current = assignment.getValue(lecture); 1069 if (current != null) { // Has assignment, check whether it is conflicting 1070 if (isSatisfiedPair(assignment, value, current)) { 1071 // Increase needed size if the assignment is of the same room and overlapping in time 1072 if (canShareRoom() && sameRoomAndOverlaps(value, current)) { 1073 neededSize += lecture.maxRoomUse(); 1074 } 1075 continue; 1076 } 1077 conflicts.add(current); 1078 } 1079 1080 // Look for supporting assignments assignment 1081 boolean shareRoomAndOverlaps = canShareRoom(); 1082 Placement support = null; 1083 int nrSupports = 0; 1084 if (lecture.nrValues() >= iForwardCheckMaxDomainSize) { 1085 // ignore variables with large domains 1086 return; 1087 } 1088 List<Placement> values = lecture.values(assignment); 1089 if (values.isEmpty()) { 1090 // ignore variables with empty domain 1091 return; 1092 } 1093 for (Placement other: values) { 1094 if (nrSupports < 2) { 1095 if (isSatisfiedPair(assignment, value, other)) { 1096 if (support == null) support = other; 1097 nrSupports ++; 1098 if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other)) 1099 shareRoomAndOverlaps = false; 1100 } 1101 } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) { 1102 shareRoomAndOverlaps = false; 1103 } 1104 if (nrSupports > 1 && !shareRoomAndOverlaps) 1105 break; 1106 } 1107 1108 // No supporting assignment -> fail 1109 if (nrSupports == 0) { 1110 conflicts.add(value); // other class cannot be assigned with this value 1111 return; 1112 } 1113 // Increase needed size if all supporters are of the same room and in overlapping times 1114 if (shareRoomAndOverlaps) { 1115 neededSize += lecture.maxRoomUse(); 1116 } 1117 1118 // Only one supporter -> propagate the new assignment over other hard constraints of the lecture 1119 if (nrSupports == 1) { 1120 for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) { 1121 if (other instanceof WeakeningConstraint) continue; 1122 if (other instanceof GroupConstraint) { 1123 GroupConstraint gc = (GroupConstraint)other; 1124 if (depth > 0 && !ignore.contains(gc)) 1125 gc.forwardCheck(assignment, support, conflicts, ignore, depth - 1); 1126 } else { 1127 other.computeConflicts(assignment, support, conflicts); 1128 } 1129 } 1130 for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) { 1131 if (other instanceof WeakeningConstraint) continue; 1132 other.computeConflicts(assignment, support, conflicts); 1133 } 1134 1135 if (conflicts.contains(support)) 1136 conflicts.add(value); 1137 } 1138 } 1139 1140 if (canShareRoom() && neededSize > value.getRoomSize()) { 1141 // room is too small to fit all meet with classes 1142 conflicts.add(value); 1143 } 1144 1145 } finally { 1146 ignore.remove(this); 1147 } 1148 } 1149 1150 @Override 1151 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) { 1152 if (!isHard()) 1153 return false; 1154 for (Lecture v : variables()) { 1155 if (v.equals(value.variable())) 1156 continue; // ignore this variable 1157 Placement p = assignment.getValue(v); 1158 if (p == null) 1159 continue; // there is an unassigned variable -- great, still a chance to get violated 1160 if (!isSatisfiedPair(assignment, p, value)) 1161 return true; 1162 } 1163 if (getType().is(Flag.BACK_TO_BACK)) { 1164 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1165 assignments.put(value.variable(), value); 1166 if (!isSatisfiedSeq(assignment, assignments, null)) 1167 return true; 1168 } 1169 if (getType().is(Flag.MAX_HRS_DAY)) { 1170 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1171 assignments.put(value.variable(), value); 1172 for (int dayCode: Constants.DAY_CODES) { 1173 if (iMaxNHoursADayConsiderDatePatterns) { 1174 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1175 if (!value.getTimeLocation().shareWeeks(week)) continue; 1176 if (nrSlotsADay(assignment, dayCode, week, assignments, null) > getType().getMax()) 1177 return true; 1178 } 1179 } else { 1180 if (nrSlotsADay(assignment, dayCode, null, assignments, null) > getType().getMax()) return true; 1181 } 1182 } 1183 } 1184 1185 if (!forwardCheck(assignment, value, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1)) return true; 1186 1187 return false; 1188 } 1189 1190 public boolean forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<GroupConstraint> ignore, int depth) { 1191 try { 1192 if (depth < 0) return true; 1193 ignore.add(this); 1194 1195 int neededSize = value.variable().maxRoomUse(); 1196 1197 for (Lecture lecture: variables()) { 1198 if (lecture.equals(value.variable())) continue; // Skip this lecture 1199 Placement current = assignment.getValue(lecture); 1200 if (current != null) { // Has assignment, check whether it is conflicting 1201 if (isSatisfiedPair(assignment, value, current)) { 1202 // Increase needed size if the assignment is of the same room and overlapping in time 1203 if (canShareRoom() && sameRoomAndOverlaps(value, current)) { 1204 neededSize += lecture.maxRoomUse(); 1205 } 1206 continue; 1207 } 1208 return false; 1209 } 1210 1211 // Look for supporting assignments assignment 1212 boolean shareRoomAndOverlaps = canShareRoom(); 1213 Placement support = null; 1214 int nrSupports = 0; 1215 if (lecture.nrValues() >= iForwardCheckMaxDomainSize) { 1216 // ignore variables with large domains 1217 return true; 1218 } 1219 List<Placement> values = lecture.values(assignment); 1220 if (values.isEmpty()) { 1221 // ignore variables with empty domain 1222 return true; 1223 } 1224 for (Placement other: lecture.values(assignment)) { 1225 if (nrSupports < 2) { 1226 if (isSatisfiedPair(assignment, value, other)) { 1227 if (support == null) support = other; 1228 nrSupports ++; 1229 if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other)) 1230 shareRoomAndOverlaps = false; 1231 } 1232 } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) { 1233 shareRoomAndOverlaps = false; 1234 } 1235 if (nrSupports > 1 && !shareRoomAndOverlaps) 1236 break; 1237 } 1238 1239 // No supporting assignment -> fail 1240 if (nrSupports == 0) { 1241 return false; // other class cannot be assigned with this value 1242 } 1243 // Increase needed size if all supporters are of the same room and in overlapping times 1244 if (shareRoomAndOverlaps) { 1245 neededSize += lecture.maxRoomUse(); 1246 } 1247 1248 // Only one supporter -> propagate the new assignment over other hard constraints of the lecture 1249 if (nrSupports == 1) { 1250 for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) { 1251 if (other instanceof WeakeningConstraint) continue; 1252 if (other instanceof GroupConstraint) { 1253 GroupConstraint gc = (GroupConstraint)other; 1254 if (depth > 0 && !ignore.contains(gc) && !gc.forwardCheck(assignment, support, ignore, depth - 1)) return false; 1255 } else { 1256 if (other.inConflict(assignment, support)) return false; 1257 } 1258 } 1259 for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) { 1260 if (other instanceof WeakeningConstraint) continue; 1261 if (other.inConflict(assignment, support)) return false; 1262 } 1263 } 1264 } 1265 1266 if (canShareRoom() && neededSize > value.getRoomSize()) { 1267 // room is too small to fit all meet with classes 1268 return false; 1269 } 1270 1271 return true; 1272 } finally { 1273 ignore.remove(this); 1274 } 1275 } 1276 1277 /** Constraint preference (0 if prohibited or required) 1278 * @return constraint preference (if soft) 1279 **/ 1280 public int getPreference() { 1281 return iPreference; 1282 } 1283 1284 /** 1285 * Current constraint preference (0 if prohibited or required, depends on 1286 * current satisfaction of the constraint) 1287 * @param assignment current assignment 1288 * @return current preference 1289 */ 1290 public int getCurrentPreference(Assignment<Lecture, Placement> assignment) { 1291 if (isHard()) return 0; // no preference 1292 if (countAssignedVariables(assignment) < 2) return - Math.abs(iPreference); // not enough variable 1293 if (getType().is(Flag.MAX_HRS_DAY)) { // max hours a day 1294 int over = 0; 1295 for (int dayCode: Constants.DAY_CODES) { 1296 if (iMaxNHoursADayConsiderDatePatterns) { 1297 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) 1298 over += Math.max(0, nrSlotsADay(assignment, dayCode, week, null, null) - getType().getMax()); 1299 } else { 1300 over += Math.max(0, nrSlotsADay(assignment, dayCode, null, null, null) - getType().getMax()); 1301 } 1302 } 1303 return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference)); 1304 } 1305 int nrViolatedPairs = 0; 1306 for (Lecture v1 : variables()) { 1307 Placement p1 = assignment.getValue(v1); 1308 if (p1 == null) continue; 1309 for (Lecture v2 : variables()) { 1310 Placement p2 = assignment.getValue(v2); 1311 if (p2 == null || v1.getId() >= v2.getId()) continue; 1312 if (!isSatisfiedPair(assignment, p1, p2)) nrViolatedPairs++; 1313 } 1314 } 1315 if (getType().is(Flag.BACK_TO_BACK)) { 1316 Set<Placement> conflicts = new HashSet<Placement>(); 1317 if (isSatisfiedSeq(assignment, new HashMap<Lecture, Placement>(), conflicts)) 1318 nrViolatedPairs += conflicts.size(); 1319 else 1320 nrViolatedPairs = variables().size(); 1321 } 1322 return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference)); 1323 } 1324 1325 /** Current constraint preference change (if given placement is assigned) 1326 * @param assignment current assignment 1327 * @param placement placement that is being considered 1328 * @return change in the current preference, if assigned 1329 **/ 1330 public int getCurrentPreference(Assignment<Lecture, Placement> assignment, Placement placement) { 1331 if (isHard()) return 0; // no preference 1332 if (countAssignedVariables(assignment) + (assignment.getValue(placement.variable()) == null ? 1 : 0) < 2) return 0; // not enough variable 1333 if (getType().is(Flag.MAX_HRS_DAY)) { 1334 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1335 assignments.put(placement.variable(), placement); 1336 HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>(); 1337 unassignments.put(placement.variable(), null); 1338 int after = 0; 1339 int before = 0; 1340 for (int dayCode: Constants.DAY_CODES) { 1341 if (iMaxNHoursADayConsiderDatePatterns) { 1342 for (BitSet week: ((TimetableModel)getModel()).getWeeks()) { 1343 after += Math.max(0, nrSlotsADay(assignment, dayCode, week, assignments, null) - getType().getMax()); 1344 before += Math.max(0, nrSlotsADay(assignment, dayCode, week, unassignments, null) - getType().getMax()); 1345 } 1346 } else { 1347 after += Math.max(0, nrSlotsADay(assignment, dayCode, null, assignments, null) - getType().getMax()); 1348 before += Math.max(0, nrSlotsADay(assignment, dayCode, null, unassignments, null) - getType().getMax()); 1349 } 1350 } 1351 return (after > 0 ? Math.abs(iPreference) * after / 12 : - Math.abs(iPreference)) - (before > 0 ? Math.abs(iPreference) * before / 12 : - Math.abs(iPreference)); 1352 } 1353 1354 int nrViolatedPairsAfter = 0; 1355 int nrViolatedPairsBefore = 0; 1356 for (Lecture v1 : variables()) { 1357 for (Lecture v2 : variables()) { 1358 if (v1.getId() >= v2.getId()) continue; 1359 Placement p1 = (v1.equals(placement.variable()) ? null : assignment.getValue(v1)); 1360 Placement p2 = (v2.equals(placement.variable()) ? null : assignment.getValue(v2)); 1361 if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2)) 1362 nrViolatedPairsBefore ++; 1363 if (v1.equals(placement.variable())) p1 = placement; 1364 if (v2.equals(placement.variable())) p2 = placement; 1365 if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2)) 1366 nrViolatedPairsAfter ++; 1367 } 1368 } 1369 1370 if (getType().is(Flag.BACK_TO_BACK)) { 1371 HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); 1372 assignments.put(placement.variable(), placement); 1373 Set<Placement> conflicts = new HashSet<Placement>(); 1374 if (isSatisfiedSeq(assignment, assignments, conflicts)) 1375 nrViolatedPairsAfter += conflicts.size(); 1376 else 1377 nrViolatedPairsAfter = variables().size(); 1378 1379 HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>(); 1380 unassignments.put(placement.variable(), null); 1381 Set<Placement> previous = new HashSet<Placement>(); 1382 if (isSatisfiedSeq(assignment, unassignments, previous)) 1383 nrViolatedPairsBefore += previous.size(); 1384 else 1385 nrViolatedPairsBefore = variables().size(); 1386 } 1387 1388 return (nrViolatedPairsAfter > 0 ? Math.abs(iPreference) * nrViolatedPairsAfter : - Math.abs(iPreference)) - 1389 (nrViolatedPairsBefore > 0 ? Math.abs(iPreference) * nrViolatedPairsBefore : - Math.abs(iPreference)); 1390 } 1391 1392 @Override 1393 public String toString() { 1394 StringBuffer sb = new StringBuffer(); 1395 sb.append(getName()); 1396 sb.append(" between "); 1397 for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) { 1398 Lecture v = e.next(); 1399 sb.append(v.getName()); 1400 if (e.hasNext()) 1401 sb.append(", "); 1402 } 1403 return sb.toString(); 1404 } 1405 1406 @Override 1407 public boolean isHard() { 1408 return iIsRequired || iIsProhibited; 1409 } 1410 1411 @Override 1412 public String getName() { 1413 return getType().getName(); 1414 } 1415 1416 1417 private boolean isPrecedence(Placement p1, Placement p2, boolean firstGoesFirst, boolean considerDatePatterns) { 1418 int ord1 = variables().indexOf(p1.variable()); 1419 int ord2 = variables().indexOf(p2.variable()); 1420 TimeLocation t1 = null, t2 = null; 1421 if (ord1 < ord2) { 1422 if (firstGoesFirst) { 1423 t1 = p1.getTimeLocation(); 1424 t2 = p2.getTimeLocation(); 1425 } else { 1426 t2 = p1.getTimeLocation(); 1427 t1 = p2.getTimeLocation(); 1428 } 1429 } else { 1430 if (!firstGoesFirst) { 1431 t1 = p1.getTimeLocation(); 1432 t2 = p2.getTimeLocation(); 1433 } else { 1434 t2 = p1.getTimeLocation(); 1435 t1 = p2.getTimeLocation(); 1436 } 1437 } 1438 if (considerDatePatterns && iPrecedenceConsiderDatePatterns) { 1439 boolean sameDatePattern = (t1.getDatePatternId() != null ? t1.getDatePatternId().equals(t2.getDatePatternId()) : t1.getWeekCode().equals(t2.getWeekCode())); 1440 if (!sameDatePattern) { 1441 int m1 = t1.getFirstMeeting(iDayOfWeekOffset), m2 = t2.getFirstMeeting(iDayOfWeekOffset); 1442 if (m1 != m2) return m1 < m2; 1443 } 1444 } 1445 if (iFirstWorkDay != 0) { 1446 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1447 int idx = (i + iFirstWorkDay) % 7; 1448 boolean a = (t1.getDayCode() & Constants.DAY_CODES[idx]) != 0; 1449 boolean b = (t2.getDayCode() & Constants.DAY_CODES[idx]) != 0; 1450 if (b && !a) return false; // second start first 1451 if (a && !b) return true; // first start first 1452 if (a && b) return t1.getStartSlot() + t1.getLength() <= t2.getStartSlot(); // same day: check times 1453 } 1454 } 1455 return t1.getStartSlots().nextElement() + t1.getLength() <= t2.getStartSlots().nextElement(); 1456 } 1457 1458 private boolean isBackToBackDays(TimeLocation t1, TimeLocation t2) { 1459 int f1 = -1, f2 = -1, e1 = -1, e2 = -1; 1460 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1461 int idx = (i + iFirstWorkDay) % 7; 1462 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1463 if (f1 < 0) 1464 f1 = i; 1465 e1 = i; 1466 } 1467 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1468 if (f2 < 0) 1469 f2 = i; 1470 e2 = i; 1471 } 1472 } 1473 return (e1 + 1 == f2) || (e2 + 1 == f1); 1474 } 1475 1476 private boolean isNrDaysBetweenGreaterThanOne(TimeLocation t1, TimeLocation t2) { 1477 int f1 = -1, f2 = -1, e1 = -1, e2 = -1; 1478 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1479 int idx = (i + iFirstWorkDay) % 7; 1480 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1481 if (f1 < 0) 1482 f1 = i; 1483 e1 = i; 1484 } 1485 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1486 if (f2 < 0) 1487 f2 = i; 1488 e2 = i; 1489 } 1490 } 1491 return (e1 - f2 > 2) || (e2 - f1 > 2); 1492 } 1493 1494 private boolean isFollowingDay(Placement p1, Placement p2, boolean firstGoesFirst) { 1495 int ord1 = variables().indexOf(p1.variable()); 1496 int ord2 = variables().indexOf(p2.variable()); 1497 TimeLocation t1 = null, t2 = null; 1498 if (ord1 < ord2) { 1499 if (firstGoesFirst) { 1500 t1 = p1.getTimeLocation(); 1501 t2 = p2.getTimeLocation(); 1502 } else { 1503 t2 = p1.getTimeLocation(); 1504 t1 = p2.getTimeLocation(); 1505 } 1506 } else { 1507 if (!firstGoesFirst) { 1508 t1 = p1.getTimeLocation(); 1509 t2 = p2.getTimeLocation(); 1510 } else { 1511 t2 = p1.getTimeLocation(); 1512 t1 = p2.getTimeLocation(); 1513 } 1514 } 1515 int f1 = -1, f2 = -1, e1 = -1; 1516 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1517 int idx = (i + iFirstWorkDay) % 7; 1518 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1519 if (f1 < 0) 1520 f1 = i; 1521 e1 = i; 1522 } 1523 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1524 if (f2 < 0) 1525 f2 = i; 1526 } 1527 } 1528 return ((e1 + 1) % iNrWorkDays == f2); 1529 } 1530 1531 private boolean isEveryOtherDay(Placement p1, Placement p2, boolean firstGoesFirst) { 1532 int ord1 = variables().indexOf(p1.variable()); 1533 int ord2 = variables().indexOf(p2.variable()); 1534 TimeLocation t1 = null, t2 = null; 1535 if (ord1 < ord2) { 1536 if (firstGoesFirst) { 1537 t1 = p1.getTimeLocation(); 1538 t2 = p2.getTimeLocation(); 1539 } else { 1540 t2 = p1.getTimeLocation(); 1541 t1 = p2.getTimeLocation(); 1542 } 1543 } else { 1544 if (!firstGoesFirst) { 1545 t1 = p1.getTimeLocation(); 1546 t2 = p2.getTimeLocation(); 1547 } else { 1548 t2 = p1.getTimeLocation(); 1549 t1 = p2.getTimeLocation(); 1550 } 1551 } 1552 int f1 = -1, f2 = -1, e1 = -1; 1553 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 1554 int idx = (i + iFirstWorkDay) % 7; 1555 if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1556 if (f1 < 0) 1557 f1 = i; 1558 e1 = i; 1559 } 1560 if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) { 1561 if (f2 < 0) 1562 f2 = i; 1563 } 1564 } 1565 return ((e1 + 2) % iNrWorkDays == f2); 1566 } 1567 1568 private static boolean sameDays(int[] days1, int[] days2) { 1569 if (days2.length < days1.length) 1570 return sameDays(days2, days1); 1571 int i2 = 0; 1572 for (int i1 = 0; i1 < days1.length; i1++) { 1573 int d1 = days1[i1]; 1574 while (true) { 1575 if (i2 == days2.length) 1576 return false; 1577 int d2 = days2[i2]; 1578 if (d1 == d2) 1579 break; 1580 i2++; 1581 if (i2 == days2.length) 1582 return false; 1583 } 1584 i2++; 1585 } 1586 return true; 1587 } 1588 1589 private static boolean sameRoomAndOverlaps(Placement p1, Placement p2) { 1590 return p1.shareRooms(p2) && p1.getTimeLocation() != null && p2.getTimeLocation() != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation()); 1591 } 1592 1593 private static boolean sameHours(int start1, int len1, int start2, int len2) { 1594 if (len1 > len2) 1595 return sameHours(start2, len2, start1, len1); 1596 start1 %= Constants.SLOTS_PER_DAY; 1597 start2 %= Constants.SLOTS_PER_DAY; 1598 return (start1 >= start2 && start1 + len1 <= start2 + len2); 1599 } 1600 1601 private static boolean canFill(int totalGap, int gapMin, int gapMax, List<Integer> lengths) { 1602 if (gapMin <= totalGap && totalGap <= gapMax) 1603 return true; 1604 if (totalGap < 2 * gapMin) 1605 return false; 1606 for (int i = 0; i < lengths.size(); i++) { 1607 int length = lengths.get(i); 1608 lengths.remove(i); 1609 for (int gap = gapMin; gap <= gapMax; gap++) 1610 if (canFill(totalGap - gap - length, gapMin, gapMax, lengths)) 1611 return true; 1612 lengths.add(i, length); 1613 } 1614 return false; 1615 } 1616 1617 private boolean isSatisfiedSeq(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 1618 if (conflicts == null) 1619 return isSatisfiedSeqCheck(assignment, assignments, conflicts); 1620 else { 1621 Set<Placement> bestConflicts = isSatisfiedRecursive(assignment, 0, assignments, conflicts, 1622 new HashSet<Placement>(), null); 1623 if (bestConflicts == null) 1624 return false; 1625 conflicts.addAll(bestConflicts); 1626 return true; 1627 } 1628 } 1629 1630 private Set<Placement> isSatisfiedRecursive(Assignment<Lecture, Placement> assignment, int idx, HashMap<Lecture, Placement> assignments, 1631 Set<Placement> conflicts, Set<Placement> newConflicts, Set<Placement> bestConflicts) { 1632 if (idx == variables().size() && newConflicts.isEmpty()) 1633 return bestConflicts; 1634 if (isSatisfiedSeqCheck(assignment, assignments, conflicts)) { 1635 if (bestConflicts == null) { 1636 return new HashSet<Placement>(newConflicts); 1637 } else { 1638 int b = 0, n = 0; 1639 for (Placement value: assignments.values()) { 1640 if (value != null && bestConflicts.contains(value)) b++; 1641 if (value != null && newConflicts.contains(value)) n++; 1642 } 1643 if (n < b || (n == b && newConflicts.size() < bestConflicts.size())) 1644 return new HashSet<Placement>(newConflicts); 1645 } 1646 return bestConflicts; 1647 } 1648 if (idx == variables().size()) 1649 return bestConflicts; 1650 bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts, 1651 bestConflicts); 1652 Lecture lecture = variables().get(idx); 1653 //if (assignments != null && assignments.containsKey(lecture)) 1654 // return bestConflicts; 1655 Placement placement = null; 1656 if (assignments != null && assignments.containsKey(lecture)) 1657 placement = assignments.get(lecture); 1658 else if (assignment != null) 1659 placement = assignment.getValue(lecture); 1660 if (placement == null) 1661 return bestConflicts; 1662 if (conflicts != null && conflicts.contains(placement)) 1663 return bestConflicts; 1664 conflicts.add(placement); 1665 newConflicts.add(placement); 1666 bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts, bestConflicts); 1667 newConflicts.remove(placement); 1668 conflicts.remove(placement); 1669 return bestConflicts; 1670 } 1671 1672 private boolean isSatisfiedSeqCheck(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 1673 if (!getType().is(Flag.BACK_TO_BACK)) return true; 1674 int gapMin = getType().getMin(); 1675 int gapMax = getType().getMax(); 1676 1677 List<Integer> lengths = new ArrayList<Integer>(); 1678 1679 Placement[] res = new Placement[Constants.SLOTS_PER_DAY]; 1680 for (int i = 0; i < Constants.SLOTS_PER_DAY; i++) 1681 res[i] = null; 1682 1683 int nrLectures = 0; 1684 1685 for (Lecture lecture : variables()) { 1686 Placement placement = null; 1687 if (assignments != null && assignments.containsKey(lecture)) 1688 placement = assignments.get(lecture); 1689 else if (assignment != null) 1690 placement = assignment.getValue(lecture); 1691 if (placement == null) { 1692 if (!lecture.timeLocations().isEmpty()) 1693 lengths.add(lecture.timeLocations().get(0).getLength()); 1694 } else if (conflicts != null && conflicts.contains(placement)) { 1695 if (!lecture.timeLocations().isEmpty()) 1696 lengths.add(lecture.timeLocations().get(0).getLength()); 1697 } else { 1698 int pos = placement.getTimeLocation().getStartSlot(); 1699 int length = placement.getTimeLocation().getLength(); 1700 for (int j = pos; j < pos + length; j++) { 1701 if (res[j] != null) { 1702 if (conflicts == null) 1703 return false; 1704 if (!assignments.containsKey(lecture)) 1705 conflicts.add(placement); 1706 else if (!assignments.containsKey(res[j].variable())) 1707 conflicts.add(res[j]); 1708 } 1709 } 1710 for (int j = pos; j < pos + length; j++) 1711 res[j] = placement; 1712 nrLectures++; 1713 } 1714 } 1715 if (nrLectures <= 1) 1716 return true; 1717 1718 if (iIsRequired || (!iIsProhibited && iPreference < 0)) { 1719 int i = 0; 1720 Placement p = res[i]; 1721 while (p == null) 1722 p = res[++i]; 1723 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 1724 nrLectures--; 1725 while (nrLectures > 0) { 1726 int gap = 0; 1727 while (i < Constants.SLOTS_PER_DAY && res[i] == null) { 1728 gap++; 1729 i++; 1730 } 1731 if (i == Constants.SLOTS_PER_DAY) 1732 break; 1733 if (!canFill(gap, gapMin, gapMax, lengths)) 1734 return false; 1735 p = res[i]; 1736 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 1737 nrLectures--; 1738 } 1739 } else if (iIsProhibited || (!iIsRequired && iPreference > 0)) { 1740 int i = 0; 1741 Placement p = res[i]; 1742 while (p == null) 1743 p = res[++i]; 1744 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 1745 nrLectures--; 1746 while (nrLectures > 0) { 1747 int gap = 0; 1748 while (i < Constants.SLOTS_PER_DAY && res[i] == null) { 1749 gap++; 1750 i++; 1751 } 1752 if (i == Constants.SLOTS_PER_DAY) 1753 break; 1754 if ((gapMin == 0 || !canFill(gap, 0, gapMin - 1, lengths)) 1755 && (gapMax >= Constants.SLOTS_PER_DAY || !canFill(gap, gapMax + 1, Constants.SLOTS_PER_DAY, 1756 lengths))) { 1757 return false; 1758 } 1759 p = res[i]; 1760 i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength(); 1761 nrLectures--; 1762 } 1763 } 1764 return true; 1765 } 1766 1767 public boolean isSatisfied(Assignment<Lecture, Placement> assignment) { 1768 if (isHard()) return true; 1769 if (countAssignedVariables(assignment) < 2) return true; 1770 if (getPreference() == 0) return true; 1771 return isHard() || countAssignedVariables(assignment) < 2 || getPreference() == 0 || getCurrentPreference(assignment) < 0; 1772 } 1773 1774 public boolean isChildrenNotOverlap(Assignment<Lecture, Placement> assignment, Lecture lec1, Placement plc1, Lecture lec2, Placement plc2) { 1775 if (lec1.getSchedulingSubpartId().equals(lec2.getSchedulingSubpartId())) { 1776 // same subpart 1777 boolean overlap = plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()); 1778 1779 if (overlap && lec1.getParent() != null && variables().contains(lec1.getParent()) 1780 && lec2.getParent() != null && variables().contains(lec2.getParent())) { 1781 // children overlaps 1782 Placement p1 = assignment.getValue(lec1.getParent()); 1783 Placement p2 = assignment.getValue(lec2.getParent()); 1784 // parents not overlap, but children do 1785 if (p1 != null && p2 != null && !p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) 1786 return false; 1787 } 1788 1789 if (!overlap && lec1.getChildrenSubpartIds() != null && lec2.getChildrenSubpartIds() != null) { 1790 // parents not overlap 1791 for (Long subpartId: lec1.getChildrenSubpartIds()) { 1792 for (Lecture c1 : lec1.getChildren(subpartId)) { 1793 Placement p1 = assignment.getValue(c1); 1794 if (p1 == null) continue; 1795 for (Lecture c2 : lec2.getChildren(subpartId)) { 1796 Placement p2 = assignment.getValue(c2); 1797 if (p2 == null) continue; 1798 if (!c1.getSchedulingSubpartId().equals(c2.getSchedulingSubpartId())) continue; 1799 // parents not overlap, but children do 1800 if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) 1801 return false; 1802 } 1803 } 1804 } 1805 } 1806 } else { 1807 // different subpart 1808 } 1809 return true; 1810 } 1811 1812 public boolean isSatisfiedPair(Assignment<Lecture, Placement> assignment, Placement plc1, Placement plc2) { 1813 if (iIsRequired || (!iIsProhibited && iPreference <= 0)) 1814 return getType().isSatisfied(assignment, this, plc1, plc2); 1815 else if (iIsProhibited || (!iIsRequired && iPreference > 0)) 1816 return getType().isViolated(assignment, this, plc1, plc2); 1817 return true; 1818 } 1819 1820 public boolean canShareRoom() { 1821 return getType().is(Flag.CAN_SHARE_ROOM); 1822 } 1823 1824 private int nrSlotsADay(Assignment<Lecture, Placement> assignment, int dayCode, BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 1825 Set<Integer> slots = new HashSet<Integer>(); 1826 for (Lecture lecture: variables()) { 1827 Placement placement = null; 1828 if (assignments != null && assignments.containsKey(lecture)) 1829 placement = assignments.get(lecture); 1830 else if (assignment != null) 1831 placement = assignment.getValue(lecture); 1832 if (placement == null || placement.getTimeLocation() == null) continue; 1833 if (conflicts != null && conflicts.contains(placement)) continue; 1834 TimeLocation t = placement.getTimeLocation(); 1835 if (t == null || (t.getDayCode() & dayCode) == 0 || (week != null && !t.shareWeeks(week))) continue; 1836 for (int i = 0; i < t.getLength(); i++) 1837 slots.add(i + t.getStartSlot()); 1838 } 1839 return slots.size(); 1840 } 1841 1842 @Override 1843 public boolean equals(Object o) { 1844 if (o == null || !(o instanceof GroupConstraint)) return false; 1845 return getGeneratedId() == ((GroupConstraint) o).getGeneratedId(); 1846 } 1847 1848 @Override 1849 public GroupConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 1850 return new GroupConstraintContext(assignment); 1851 } 1852 1853 public class GroupConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 1854 private int iLastPreference = 0; 1855 1856 public GroupConstraintContext(Assignment<Lecture, Placement> assignment) { 1857 updateCriterion(assignment); 1858 } 1859 1860 @Override 1861 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 1862 updateCriterion(assignment); 1863 } 1864 1865 @Override 1866 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 1867 updateCriterion(assignment); 1868 } 1869 1870 private void updateCriterion(Assignment<Lecture, Placement> assignment) { 1871 if (!isHard()) { 1872 getModel().getCriterion(DistributionPreferences.class).inc(assignment, -iLastPreference); 1873 iLastPreference = getCurrentPreference(assignment) + Math.abs(iPreference); 1874 getModel().getCriterion(DistributionPreferences.class).inc(assignment, iLastPreference); 1875 } 1876 } 1877 1878 public int getPreference() { return iLastPreference; } 1879 } 1880}