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