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