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