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