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