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