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