001package org.cpsolver.coursett.constraint;
002
003import java.util.ArrayList;
004import java.util.BitSet;
005import java.util.Enumeration;
006import java.util.HashSet;
007import java.util.HashMap;
008import java.util.Iterator;
009import java.util.List;
010import java.util.Set;
011import java.util.regex.Matcher;
012import java.util.regex.Pattern;
013
014import org.cpsolver.coursett.Constants;
015import org.cpsolver.coursett.criteria.DistributionPreferences;
016import org.cpsolver.coursett.model.Lecture;
017import org.cpsolver.coursett.model.Placement;
018import org.cpsolver.coursett.model.RoomLocation;
019import org.cpsolver.coursett.model.TimeLocation;
020import org.cpsolver.coursett.model.TimeLocation.IntEnumeration;
021import org.cpsolver.coursett.model.TimetableModel;
022import org.cpsolver.ifs.assignment.Assignment;
023import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
024import org.cpsolver.ifs.assignment.context.ConstraintWithContext;
025import org.cpsolver.ifs.model.Constraint;
026import org.cpsolver.ifs.model.GlobalConstraint;
027import org.cpsolver.ifs.model.Model;
028import org.cpsolver.ifs.model.WeakeningConstraint;
029import org.cpsolver.ifs.util.DataProperties;
030import org.cpsolver.ifs.util.DistanceMetric;
031import org.cpsolver.ifs.util.ToolBox;
032
033
034/**
035 * Group constraint. <br>
036 * This constraint expresses relations between several classes, e.g., that two
037 * sections of the same lecture can not be taught at the same time, or that some
038 * classes have to be taught one immediately after another. It can be either
039 * hard or soft. <br>
040 * <br>
041 * Following constraints are now supported:
042 * <table border='1'><caption>Related Solver Parameters</caption>
043 * <tr>
044 * <th>Constraint</th>
045 * <th>Comment</th>
046 * </tr>
047 * <tr>
048 * <td>SAME_TIME</td>
049 * <td>Same time: given classes have to be taught in the same hours. If the
050 * classes are of different length, the smaller one cannot start before the
051 * longer one and it cannot end after the longer one.</td>
052 * </tr>
053 * <tr>
054 * <td>SAME_DAYS</td>
055 * <td>Same days: given classes have to be taught in the same day. If the
056 * classes are of different time patterns, the days of one class have to form a
057 * subset of the days of the other class.</td>
058 * </tr>
059 * <tr>
060 * <td>BTB</td>
061 * <td>Back-to-back constraint: given classes have to be taught in the same room
062 * and they have to follow one strictly after another.</td>
063 * </tr>
064 * <tr>
065 * <td>BTB_TIME</td>
066 * <td>Back-to-back constraint: given classes have to follow one strictly after
067 * another, but they can be taught in different rooms.</td>
068 * </tr>
069 * <tr>
070 * <td>DIFF_TIME</td>
071 * <td>Different time: given classes cannot overlap in time.</td>
072 * </tr>
073 * <tr>
074 * <td>NHB(1), NHB(1.5), NHB(2), ... NHB(8)</td>
075 * <td>Number of hours between: between the given classes, the exact number of
076 * hours have to be kept.</td>
077 * </tr>
078 * <tr>
079 * <td>SAME_START</td>
080 * <td>Same starting hour: given classes have to start in the same hour.</td>
081 * </tr>
082 * <tr>
083 * <td>SAME_ROOM</td>
084 * <td>Same room: given classes have to be placed in the same room.</td>
085 * </tr>
086 * <tr>
087 * <td>NHB_GTE(1)</td>
088 * <td>Greater than or equal to 1 hour between: between the given classes, the
089 * number of hours have to be one or more.</td>
090 * </tr>
091 * <tr>
092 * <td>NHB_LT(6)</td>
093 * <td>Less than 6 hours between: between the given classes, the number of hours
094 * have to be less than six.</td>
095 * </tr>
096 * </table>
097 * 
098 * @author  Tomas Muller
099 * @version CourseTT 1.3 (University Course Timetabling)<br>
100 *          Copyright (C) 2006 - 2014 Tomas Muller<br>
101 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
102 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
103 * <br>
104 *          This library is free software; you can redistribute it and/or modify
105 *          it under the terms of the GNU Lesser General Public License as
106 *          published by the Free Software Foundation; either version 3 of the
107 *          License, or (at your option) any later version. <br>
108 * <br>
109 *          This library is distributed in the hope that it will be useful, but
110 *          WITHOUT ANY WARRANTY; without even the implied warranty of
111 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
112 *          Lesser General Public License for more details. <br>
113 * <br>
114 *          You should have received a copy of the GNU Lesser General Public
115 *          License along with this library; if not see
116 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
117 */
118public class GroupConstraint extends ConstraintWithContext<Lecture, Placement, GroupConstraint.GroupConstraintContext> {
119    private Long iConstraintId;
120    private int iPreference;
121    private ConstraintTypeInterface iType;
122    private boolean iIsRequired;
123    private boolean iIsProhibited;
124    private int iDayOfWeekOffset = 0;
125    private boolean iPrecedenceConsiderDatePatterns = true;
126    private boolean iPrecedenceSkipSameDatePatternCheck = true;
127    private boolean iMaxNHoursADayConsiderDatePatterns = true;
128    private boolean iMaxNHoursADayPrecideComputation = false;
129    private int iForwardCheckMaxDepth = 2;
130    private int iForwardCheckMaxDomainSize = 1000;
131    private int iNrWorkDays = 5;
132    private int iFirstWorkDay = 0;
133    private String iOnlineRoom = null;
134    
135    /**
136     * Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room),
137     * only need to implement this interface.
138     */
139    public static interface PairCheck {
140        /**
141         * Check whether the constraint is satisfied for the given two assignments (required / preferred 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 isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2);
148        /**
149         * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case)
150         * @param gc Calling group constraint 
151         * @param plc1 First placement
152         * @param plc2 Second placement
153         * @return true if constraint is satisfied
154         */
155        public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2);
156    }
157    
158    /**
159     * Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room),
160     * only need to implement this interface. Unlike {@link PairCheck}, this check is also given current assignment.
161     */
162    public static interface AssignmentPairCheck {
163        /**
164         * Check whether the constraint is satisfied for the given two assignments (required / preferred case)
165         * @param assignment current assignment
166         * @param gc Calling group constraint 
167         * @param plc1 First placement
168         * @param plc2 Second placement
169         * @return true if constraint is satisfied
170         */
171        public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2);
172        /**
173         * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case)
174         * @param assignment current assignment
175         * @param gc Calling group constraint 
176         * @param plc1 First placement
177         * @param plc2 Second placement
178         * @return true if constraint is satisfied
179         */
180        public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2);
181    }
182    
183    /**
184     * Group constraints that can have parameters need to implement this interface instead of {@link AssignmentPairCheck} or {@link PairCheck}.
185     */
186    public static interface AssignmentParameterPairCheck<P> {
187        /**
188         * Check whether the constraint is satisfied for the given two assignments (required / preferred case)
189         * @param assignment current assignment
190         * @param parameter constraint dependent parameter(s)
191         * @param gc Calling group constraint 
192         * @param plc1 First placement
193         * @param plc2 Second placement
194         * @return true if constraint is satisfied
195         */
196        public boolean isSatisfied(Assignment<Lecture, Placement> assignment, P parameter, GroupConstraint gc, Placement plc1, Placement plc2);
197        /**
198         * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case)
199         * @param assignment current assignment
200         * @param parameter constraint dependent parameter(s)
201         * @param gc Calling group constraint 
202         * @param plc1 First placement
203         * @param plc2 Second placement
204         * @return true if constraint is satisfied
205         */
206        public boolean isViolated(Assignment<Lecture, Placement> assignment, P parameter, GroupConstraint gc, Placement plc1, Placement plc2);
207        
208        /**
209         * Create constraint type with the parameters taken from the provided reference
210         * @param reference constraint reference, including parameter(s)
211         * @param referenceRegExp reference regular expression defined on the constraint type
212         * @return constraint type with the parameter
213         */
214        public ParametrizedConstraintType<P> create(String reference, String referenceRegExp);
215    }
216    
217    /**
218     * Group constraint building blocks (individual constraints that need more than {@link PairCheck})
219     */
220    public static enum Flag {
221        /** Back-to-back constraint (sequence check) */
222        BACK_TO_BACK,
223        /** Can share room flag */
224        CAN_SHARE_ROOM,
225        /** Maximum hours a day (number of slots a day check) */
226        MAX_HRS_DAY,
227        /** Children cannot overlap */
228        CH_NOTOVERLAP;
229        /** Bit number (to combine flags) */
230        int flag() { return 1 << ordinal(); }
231    }
232    
233    /**
234     * Constraint type interface
235     */
236    public static interface ConstraintTypeInterface extends AssignmentPairCheck {
237        /** Constraint type
238         * @return constraint type
239         */
240        public ConstraintType type();
241        
242        /** Constraint reference
243         * @return constraint reference
244         **/
245        public String reference();
246        
247        /** Constraint name
248         * @return constraint name
249         **/
250        public String getName();
251        
252        /** Minimum (gap) parameter
253         * @return minimum gap (first constraint parameter)
254         **/
255        public int getMin();
256        
257        /** Maximum (gap, hours a day) parameter 
258         * @return maximum gap (second constraint parameter) 
259         **/
260        public int getMax();
261        
262        /** Flag check (true if contains given flag) 
263         * @param f a flag to check
264         * @return true if present
265         **/
266        public boolean is(Flag f);
267    }
268    
269    /**
270     * Constraint type with a parameter
271     */
272    public static class ParametrizedConstraintType<P> implements ConstraintTypeInterface {
273        private String iReference;
274        private ConstraintType iType;
275        private Integer iMin = null, iMax = null;
276        private String iName = null;
277        private P iParameter;
278        
279        /**
280         * Constructor
281         * @param type constraint type
282         * @param parameter parameter parsed from the reference using {@link AssignmentParameterPairCheck#create(String, String)}
283         * @param reference constraint reference with parameters
284         */
285        public ParametrizedConstraintType(ConstraintType type, P parameter, String reference) {
286            iType = type; iParameter = parameter; iReference = reference;
287        }
288
289        @Override
290        @SuppressWarnings("unchecked")
291        public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) {
292            return ((AssignmentParameterPairCheck<P>)iType.iAssignmentPairCheck).isSatisfied(assignment, iParameter, gc, plc1, plc2);
293        }
294
295        @Override
296        @SuppressWarnings("unchecked")
297        public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) {
298            return ((AssignmentParameterPairCheck<P>)iType.iAssignmentPairCheck).isViolated(assignment, iParameter, gc, plc1, plc2);
299        }
300
301        /**
302         * Return constraint's parameter
303         * @return constraint's parameter
304         */
305        public P getParameter() { return iParameter; }
306        @Override
307        public ConstraintType type() { return iType; }
308        @Override
309        public String reference() { return iReference; }
310        @Override
311        public String getName() { return (iName == null ? iType.getName() : iName); }
312        @Override
313        public int getMin() { return (iMin == null ? iType.getMin() : iMin); }
314        @Override
315        public int getMax() { return (iMax == null ? iType.getMax() : iMax); }
316        @Override
317        public boolean is(Flag f) { return iType.is(f); }
318        public ParametrizedConstraintType<P> setMin(int min) { iMin = min; return this; }
319        public ParametrizedConstraintType<P> setMax(int max) { iMax = max; return this; }
320        public ParametrizedConstraintType<P> setName(String name) { iName = name; return this; }
321    }
322    
323    /**
324     * Group constraint type.
325     */
326    public static enum ConstraintType implements ConstraintTypeInterface {
327        /**
328         * Same Time: Given classes must be taught at the same time of day (independent of the actual day the classes meet).
329         * For the classes of the same length, this is the same constraint as same start. For classes of different length,
330         * the shorter one cannot start before, nor end after, the longer one.<BR>
331         * When prohibited or (strongly) discouraged: one class may not meet on any day at a time of day that overlaps with
332         * that of the other. For example, one class can not meet M 7:30 while the other meets F 7:30. Note the difference
333         * here from the different time constraint that only prohibits the actual class meetings from overlapping.
334         */
335        SAME_TIME("SAME_TIME", "Same Time", new PairCheck() {
336            @Override
337            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
338                return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(),
339                        plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength());
340            }
341            @Override
342            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
343                return !(plc1.getTimeLocation().shareHours(plc2.getTimeLocation()));
344            }}),
345        /**
346         * Same Days: Given classes must be taught on the same days. In case of classes of different time patterns, a class
347         * with fewer meetings must meet on a subset of the days used by the class with more meetings. For example, if one
348         * class pattern is 3x50, all others given in the constraint can only be taught on Monday, Wednesday, or Friday.
349         * For a 2x100 class MW, MF, WF is allowed but TTh is prohibited.<BR>
350         * When prohibited or (strongly) discouraged: any pair of classes classes cannot be taught on the same days (cannot
351         *  overlap in days). For instance, if one class is MFW, the second has to be TTh.
352         */
353        SAME_DAYS("SAME_DAYS", "Same Days", new PairCheck() {
354            @Override
355            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
356                return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
357            }
358            @Override
359            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
360                return !plc1.getTimeLocation().shareDays(plc2.getTimeLocation());
361            }}),
362        /**
363         * Back-To-Back &amp; Same Room: Classes must be offered in adjacent time segments and must be placed in the same room.
364         * Given classes must also be taught on the same days.<BR>
365         * When prohibited or (strongly) discouraged: classes cannot be back-to-back. There must be at least half-hour
366         * between these classes, and they must be taught on the same days and in the same room.
367         */
368        BTB("BTB", "Back-To-Back & Same Room", new PairCheck() {
369            @Override
370            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
371                return
372                    plc1.sameRooms(plc2) &&
373                    sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
374            }
375            @Override
376            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
377                return
378                    plc1.sameRooms(plc2) &&
379                    sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
380            }}, Flag.BACK_TO_BACK),
381        /**
382         * Back-To-Back: Classes must be offered in adjacent time segments but may be placed in different rooms. Given classes
383         * must also be taught on the same days.<BR>
384         * When prohibited or (strongly) discouraged: no pair of classes can be taught back-to-back. They may not overlap in time,
385         * but must be taught on the same days. This means that there must be at least half-hour between these classes. 
386         */
387        BTB_TIME("BTB_TIME", "Back-To-Back", new PairCheck() {
388            @Override
389            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
390                return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
391            }
392            @Override
393            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
394                return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
395            }}, Flag.BACK_TO_BACK),
396        /**
397         * Different Time: Given classes cannot overlap in time. They may be taught at the same time of day if they are on
398         * different days. For instance, MF 7:30 is compatible with TTh 7:30.<BR>
399         * When prohibited or (strongly) discouraged: every pair of classes in the constraint must overlap in time. 
400         */
401        DIFF_TIME("DIFF_TIME", "Different Time", new PairCheck() {
402            @Override
403            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
404                return !plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation());
405            }
406            @Override
407            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
408                return plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation());
409            }}),
410        /**
411         * 1 Hour Between: Given classes must have exactly 1 hour in between the end of one and the beginning of another.
412         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
413         * When prohibited or (strongly) discouraged: classes can not have 1 hour in between. They may not overlap in time
414         * but must be taught on the same days.
415         */
416        NHB_1("NHB(1)", "1 Hour Between", 10, 12, BTB_TIME.check(), Flag.BACK_TO_BACK),
417        /**
418         * 2 Hours Between: Given classes must have exactly 2 hours in between the end of one and the beginning of another.
419         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
420         * When prohibited or (strongly) discouraged: classes can not have 2 hours in between. They may not overlap in time
421         * but must be taught on the same days.
422         */
423        NHB_2("NHB(2)", "2 Hours Between", 20, 24, BTB_TIME.check(), Flag.BACK_TO_BACK),
424        /**
425         * 3 Hours Between: Given classes must have exactly 3 hours in between the end of one and the beginning of another.
426         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
427         * When prohibited or (strongly) discouraged: classes can not have 3 hours in between. They may not overlap in time
428         * but must be taught on the same days.
429         */
430        NHB_3("NHB(3)", "3 Hours Between", 30, 36, BTB_TIME.check(), Flag.BACK_TO_BACK),
431        /**
432         * 4 Hours Between: Given classes must have exactly 4 hours in between the end of one and the beginning of another.
433         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
434         * When prohibited or (strongly) discouraged: classes can not have 4 hours in between. They may not overlap in time
435         * but must be taught on the same days.
436         */
437        NHB_4("NHB(4)", "4 Hours Between", 40, 48, BTB_TIME.check(), Flag.BACK_TO_BACK),
438        /**
439         * 5 Hours Between: Given classes must have exactly 5 hours in between the end of one and the beginning of another.
440         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
441         * When prohibited or (strongly) discouraged: classes can not have 5 hours in between. They may not overlap in time
442         * but must be taught on the same days.
443         */
444        NHB_5("NHB(5)", "5 Hours Between", 50, 60, BTB_TIME.check(), Flag.BACK_TO_BACK),
445        /**
446         * 6 Hours Between: Given classes must have exactly 6 hours in between the end of one and the beginning of another.
447         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
448         * When prohibited or (strongly) discouraged: classes can not have 6 hours in between. They may not overlap in time
449         * but must be taught on the same days.
450         */
451        NHB_6("NHB(6)", "6 Hours Between", 60, 72, BTB_TIME.check(), Flag.BACK_TO_BACK),
452        /**
453         * 7 Hours Between: Given classes must have exactly 7 hours in between the end of one and the beginning of another.
454         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
455         * When prohibited or (strongly) discouraged: classes can not have 7 hours in between. They may not overlap in time
456         * but must be taught on the same days.
457         */
458        NHB_7("NHB(7)", "7 Hours Between", 70, 84, BTB_TIME.check(), Flag.BACK_TO_BACK),
459        /**
460         * 8 Hours Between: Given classes must have exactly 8 hours in between the end of one and the beginning of another.
461         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
462         * When prohibited or (strongly) discouraged: classes can not have 8 hours in between. They may not overlap in time
463         * but must be taught on the same days.
464         */
465        NHB_8("NHB(8)", "8 Hours Between", 80, 96, BTB_TIME.check(), Flag.BACK_TO_BACK),
466        /**
467         * Same Start Time: Given classes must start during the same half-hour period of a day (independent of the actual
468         * day the classes meet). For instance, MW 7:30 is compatible with TTh 7:30 but not with MWF 8:00.<BR>
469         * When prohibited or (strongly) discouraged: any pair of classes in the given constraint cannot start during the
470         * same half-hour period of any day of the week.
471         */
472        SAME_START("SAME_START", "Same Start Time", new PairCheck() {
473            @Override
474            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
475                return
476                    (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) == 
477                    (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY);
478            }
479            @Override
480            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
481                return
482                    (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) != 
483                    (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY);
484            }}),
485        /**
486         * Same Room: Given classes must be taught in the same room.<BR>
487         * When prohibited or (strongly) discouraged: any pair of classes in the constraint cannot be taught in the same room.
488         */
489        SAME_ROOM("SAME_ROOM", "Same Room", new PairCheck() {
490            @Override
491            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
492                return plc1.sameRooms(plc2);
493            }
494            @Override
495            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
496                return !plc1.sameRooms(plc2);
497            }}),
498        /**
499         * At Least 1 Hour Between: Given classes have to have 1 hour or more in between.<BR>
500         * When prohibited or (strongly) discouraged: given classes have to have less than 1 hour in between.
501         */
502        NHB_GTE_1("NHB_GTE(1)", "At Least 1 Hour Between", 6, 288, BTB_TIME.check(), Flag.BACK_TO_BACK),
503        /**
504         * Less Than 6 Hours Between: Given classes must have less than 6 hours from end of first class to the beginning of
505         * the next. Given classes must also be taught on the same days.<BR>
506         * When prohibited or (strongly) discouraged: given classes must have 6 or more hours between. This constraint does
507         * not carry over from classes taught at the end of one day to the beginning of the next.
508         */
509        NHB_LT_6("NHB_LT(6)", "Less Than 6 Hours Between", 0, 72, BTB_TIME.check(), Flag.BACK_TO_BACK),
510        /**
511         * 1.5 Hour Between: Given classes must have exactly 90 minutes in between the end of one and the beginning of another.
512         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
513         * When prohibited or (strongly) discouraged: classes can not have 90 minutes in between. They may not overlap in time
514         * but must be taught on the same days.
515         */
516        NHB_1_5("NHB(1.5)", "1.5 Hour Between", 15, 18, BTB_TIME.check(), Flag.BACK_TO_BACK),
517        /**
518         * 4.5 Hours Between: Given classes must have exactly 4.5 hours in between the end of one and the beginning of another.
519         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
520         * When prohibited or (strongly) discouraged: classes can not have 4.5 hours in between. They may not overlap in time
521         * but must be taught on the same days.
522         */
523        NHB_4_5("NHB(4.5)", "4.5 Hours Between", 45, 54, BTB_TIME.check(), Flag.BACK_TO_BACK),
524        /**
525         * Same Students: Given classes are treated as they are attended by the same students, i.e., they cannot overlap in time
526         * and if they are back-to-back the assigned rooms cannot be too far (student limit is used).
527         */
528        SAME_STUDENTS("SAME_STUDENTS", "Same Students", new PairCheck() {
529            @Override
530            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
531                return !JenrlConstraint.isInConflict(plc1, plc2, ((TimetableModel)gc.getModel()).getDistanceMetric(), ((TimetableModel)gc.getModel()).getStudentWorkDayLimit());
532            }
533            @Override
534            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
535                return true;
536            }}),
537        /**
538         * Same Instructor: Given classes are treated as they are taught by the same instructor, i.e., they cannot overlap in time
539         * and if they are back-to-back the assigned rooms cannot be too far (instructor limit is used).<BR>
540         * If the constraint is required and the classes are back-to-back, discouraged and strongly discouraged distances between
541         * assigned rooms are also considered.
542         */
543        SAME_INSTR("SAME_INSTR", "Same Instructor", new PairCheck() {
544            @Override
545            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
546                TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation();
547                if (t1.shareDays(t2) && t1.shareWeeks(t2)) {
548                    if (t1.shareHours(t2)) return false; // overlap
549                    DistanceMetric m = ((TimetableModel)gc.getModel()).getDistanceMetric();
550                    if ((t1.getStartSlot() + t1.getLength() == t2.getStartSlot() || t2.getStartSlot() + t2.getLength() == t1.getStartSlot())) {
551                        if (Placement.getDistanceInMeters(m, plc1, plc2) > m.getInstructorProhibitedLimit())
552                            return false;
553                    } else if (m.doComputeDistanceConflictsBetweenNonBTBClasses()) {
554                        if (t1.getStartSlot() + t1.getLength() < t2.getStartSlot() && 
555                            Placement.getDistanceInMinutes(m, plc1, plc2) > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t2.getStartSlot() - t1.getStartSlot() - t1.getLength()))
556                            return false;
557                        if (t2.getStartSlot() + t2.getLength() < t1.getStartSlot() &&
558                            Placement.getDistanceInMinutes(m, plc1, plc2) > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t1.getStartSlot() - t2.getStartSlot() - t2.getLength()))
559                            return false;
560                    }
561                }
562                return true;
563            }
564            @Override
565            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
566                return true;
567            }}),
568        /**
569         * Can Share Room: Given classes can share the room (use the room in the same time) if the room is big enough.
570         */
571        CAN_SHARE_ROOM("CAN_SHARE_ROOM", "Can Share Room", Flag.CAN_SHARE_ROOM),
572        /**
573         * Precedence: Given classes have to be taught in the given order (the first meeting of the first class has to end before
574         * the first meeting of the second class etc.)<BR>
575         * When prohibited or (strongly) discouraged: classes have to be taught in the order reverse to the given one.
576         */
577        PRECEDENCE("PRECEDENCE", "Precedence", new PairCheck() {
578            @Override
579            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
580                return gc.isPrecedence(plc1, plc2, true, true);
581            }
582            @Override
583            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
584                return gc.isPrecedence(plc1, plc2, false, true);
585            }}),
586        /**
587         * Back-To-Back Day: Classes must be offered on adjacent days and may be placed in different rooms.<BR>
588         * When prohibited or (strongly) discouraged: classes can not be taught on adjacent days. They also can not be taught
589         * on the same days. This means that there must be at least one day between these classes.
590         */
591        BTB_DAY("BTB_DAY", "Back-To-Back Day", new PairCheck() {
592            @Override
593            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
594                return
595                    !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
596                    gc.isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation());
597            }
598            @Override
599            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
600                return
601                    !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
602                    !gc.isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation());
603            }}),
604        /**
605         * Meet Together: Given classes are meeting together (same as if the given classes require constraints Can Share Room,
606         * Same Room, Same Time and Same Days all together).
607         */
608        MEET_WITH("MEET_WITH", "Meet Together", new PairCheck() {
609            @Override
610            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
611                return
612                        plc1.sameRooms(plc2) &&
613                        sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(),
614                                plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) &&
615                        sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
616                        
617            }
618            @Override
619            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
620                return true;
621            }}, Flag.CAN_SHARE_ROOM),
622        /**
623         * More Than 1 Day Between: Given classes must have two or more days in between.<br>
624         * When prohibited or (strongly) discouraged: given classes must be offered on adjacent days or with at most one day in between.
625         */
626        NDB_GT_1("NDB_GT_1", "More Than 1 Day Between", new PairCheck() {
627            @Override
628            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
629                return
630                    !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
631                    gc.isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation());
632            }
633            @Override
634            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
635                return
636                    !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
637                    !gc.isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation());
638            }}),
639        /**
640         * Children Cannot Overlap: If parent classes do not overlap in time, children classes can not overlap in time as well.<BR>
641         * Note: This constraint only needs to be put on the parent classes. Preferred configurations are Required All Classes
642         * or Pairwise (Strongly) Preferred.
643         */
644        CH_NOTOVERLAP("CH_NOTOVERLAP", "Children Cannot Overlap", new AssignmentPairCheck() {
645            @Override
646            public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) {
647                return gc.isChildrenNotOverlap(assignment, plc1.variable(), plc1, plc2.variable(), plc2);
648            }
649            @Override
650            public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) {
651                return true;
652            }}),
653        /**
654         * Next Day: The second class has to be placed on the following day of the first class (if the first class is on Friday,
655         * second class have to be on Monday).<br>
656         * When prohibited or (strongly) discouraged: The second class has to be placed on the previous day of the first class
657         * (if the first class is on Monday, second class have to be on Friday).<br>
658         * Note: This constraint works only between pairs of classes.
659         */
660        FOLLOWING_DAY("FOLLOWING_DAY", "Next Day", new PairCheck() {
661            @Override
662            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
663                return gc.isFollowingDay(plc1, plc2, true);
664            }
665            @Override
666            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
667                return gc.isFollowingDay(plc1, plc2, false);
668            }}),
669        /**
670         * Two Days After: The second class has to be placed two days after the first class (Monday &rarr; Wednesday, Tuesday &rarr; 
671         * Thurday, Wednesday &rarr; Friday, Thursday &rarr; Monday, Friday &rarr; Tuesday).<br>
672         * When prohibited or (strongly) discouraged: The second class has to be placed two days before the first class (Monday &rarr;
673         * Thursday, Tuesday &rarr; Friday, Wednesday &rarr; Monday, Thursday &rarr; Tuesday, Friday &rarr; Wednesday).<br>
674         * Note: This constraint works only between pairs of classes.
675         */
676        EVERY_OTHER_DAY("EVERY_OTHER_DAY", "Two Days After", new PairCheck() {
677            @Override
678            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
679                return gc.isEveryOtherDay(plc1, plc2, true);
680            }
681            @Override
682            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
683                return gc.isEveryOtherDay(plc1, plc2, false);
684            }}),
685        /**
686         * 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.
687         */
688       MAX_HRS_DAY_3("MAX_HRS_DAY(3)", "At Most 3 Hours A Day", 36, null, Flag.MAX_HRS_DAY),        
689       /**
690        * 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.
691        */
692       MAX_HRS_DAY_4("MAX_HRS_DAY(4)", "At Most 4 Hours A Day", 48, null, Flag.MAX_HRS_DAY),        
693       /**
694         * 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.
695         */
696       MAX_HRS_DAY_5("MAX_HRS_DAY(5)", "At Most 5 Hours A Day", 60, null, Flag.MAX_HRS_DAY),        
697       /**
698        * 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.
699        */
700       MAX_HRS_DAY_6("MAX_HRS_DAY(6)", "At Most 6 Hours A Day", 72, null, Flag.MAX_HRS_DAY),
701       /**
702        * 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.
703        */
704       MAX_HRS_DAY_7("MAX_HRS_DAY(7)", "At Most 7 Hours A Day", 84, null, Flag.MAX_HRS_DAY),
705       /**
706        * 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.
707        */
708       MAX_HRS_DAY_8("MAX_HRS_DAY(8)", "At Most 8 Hours A Day", 96, null, Flag.MAX_HRS_DAY),
709       /**
710        * 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.
711        */
712       MAX_HRS_DAY_9("MAX_HRS_DAY(9)", "At Most 9 Hours A Day", 108, null, Flag.MAX_HRS_DAY),
713       /**
714        * 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.
715        */
716       MAX_HRS_DAY_10("MAX_HRS_DAY(10)", "At Most 10 Hours A Day", 120, null, Flag.MAX_HRS_DAY),
717        /**
718         * At Most X Hours A Day: Classes are to be placed in a way that there is no more than given number of hours in any day.
719         */
720        MAX_HRS_DAY("MAX_HRS_DAY\\(([0-9\\.]+)\\)", "At Most N Hours A Day", new AssignmentParameterPairCheck<Integer>() {
721            @Override
722            public boolean isSatisfied(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) {
723                return true;
724            }
725            @Override
726            public boolean isViolated(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) {
727                return true;
728            }
729            @Override
730            public ParametrizedConstraintType<Integer> create(String reference, String regexp) {
731                Matcher matcher = Pattern.compile(regexp).matcher(reference);
732                if (matcher.find()) {
733                    double hours = Double.parseDouble(matcher.group(1));
734                    int slots = (int)Math.round(12.0 * hours);
735                    return new ParametrizedConstraintType<Integer>(ConstraintType.MAX_HRS_DAY, slots, reference)
736                            .setName("At Most " + matcher.group(1) + " Hours A Day")
737                            .setMin(slots).setMax(slots);
738                }
739                return null;
740            }}, Flag.MAX_HRS_DAY),
741        /**
742         * Given classes must be taught during the same weeks (i.e., must have the same date pattern).<br>
743         * When prohibited or (strongly) discouraged: any two classes must have non overlapping date patterns.
744         */
745        SAME_WEEKS("SAME_WEEKS", "Same Weeks", new PairCheck() {
746            @Override
747            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
748                return plc1.getTimeLocation().getWeekCode().equals(plc2.getTimeLocation().getWeekCode());
749            }
750            @Override
751            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
752                return !plc1.getTimeLocation().shareWeeks(plc2.getTimeLocation());
753            }}),
754        /**
755         * Classes (of different courses) are to be attended by the same students. For instance,
756         * if class A1 (of a course A) and class B1 (of a course B) are linked, a student requesting
757         * both courses must attend A1 if and only if he also attends B1. This is a student sectioning
758         * constraint that is interpreted as Same Students constraint during course timetabling.
759         */
760        LINKED_SECTIONS("LINKED_SECTIONS", "Linked Classes", SAME_STUDENTS.check()),
761        /**
762         * Back-To-Back Precedence: Given classes have to be taught in the given order, on the same days,
763         * and in adjacent time segments.
764         * When prohibited or (strongly) discouraged: Given classes have to be taught in the given order,
765         * on the same days, but cannot be back-to-back.
766         */
767        BTB_PRECEDENCE("BTB_PRECEDENCE", "Back-To-Back Precedence", new PairCheck() {
768            @Override
769            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
770                return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
771            }
772            @Override
773            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
774                return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
775            }}, Flag.BACK_TO_BACK),   
776            
777        /**
778         * Same Days-Time: Given classes must be taught at the same time of day and on the same days.
779         * It is the combination of Same Days and Same Time distribution preferences.     
780         * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days
781         * during the same time.
782         */             
783        SAME_DAYS_TIME("SAME_D_T", "Same Days-Time", new PairCheck() {
784            @Override
785            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
786                return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(),
787                        plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) &&
788                        sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
789            }
790            @Override
791            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
792                return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) ||
793                        !plc1.getTimeLocation().shareDays(plc2.getTimeLocation());
794            }}),
795        /**
796         * Same Days-Room-Time: Given classes must be taught at the same time of day, on the same days and in the same room.
797         * It is the combination of Same Days, Same Time and Same Room distribution preferences.
798         * Note that this constraint is the same as Meet Together constraint, except it does not allow room sharing. In other words,
799         * it is only useful when these classes are taught during non-overlapping date patterns.
800         * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days 
801         * during the same time in the same room.
802         */            
803        SAME_DAYS_ROOM_TIME("SAME_D_R_T", "Same Days-Room-Time", new PairCheck() {
804            @Override
805            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
806                return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(),
807                        plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) &&
808                        sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
809                        plc1.sameRooms(plc2);
810            }
811            @Override
812            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
813                return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) ||
814                        !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()) ||
815                        !plc1.sameRooms(plc2);
816            }}),
817        /**
818         * 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.
819         */
820        WORKDAY_6("WORKDAY(6)", "6 Hour Work Day", 72, new PairCheck() {
821            @Override
822            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
823                TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation();
824                if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return true;
825                return Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()) <= gc.getType().getMax();
826            }
827            @Override
828            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { return true; }
829            }),
830        /**
831         * 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.
832         */
833        WORKDAY_7("WORKDAY(7)", "7 Hour Work Day", 84, WORKDAY_6.check()),
834        /**
835         * 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.
836         */
837        WORKDAY_8("WORKDAY(8)", "8 Hour Work Day", 96, WORKDAY_6.check()),
838        /**
839         * 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.
840         */
841        WORKDAY_9("WORKDAY(9)", "9 Hour Work Day", 108, WORKDAY_6.check()),
842        /**
843         * 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.
844         */
845        WORKDAY_10("WORKDAY(10)", "10 Hour Work Day", 120, WORKDAY_6.check()),
846        /**
847         * 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.
848         */
849        WORKDAY_11("WORKDAY(11)", "11 Hour Work Day", 132, WORKDAY_6.check()),
850        /**
851         * 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.
852         */
853        WORKDAY_12("WORKDAY(12)", "12 Hour Work Day", 144, WORKDAY_6.check()),
854        /**
855         * 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.
856         */
857        WORKDAY_4("WORKDAY(4)", "4 Hour Work Day", 48, WORKDAY_6.check()),
858        /**
859         * 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.
860         */
861        WORKDAY_5("WORKDAY(5)", "5 Hour Work Day", 60, WORKDAY_6.check()),
862          /**
863         * Work Day: Classes are to be placed in a way that there is no more than given number of hours between the start of the first class and the end of the class one on any day.
864         */
865        WORKDAY("WORKDAY\\(([0-9\\.]+)\\)", "Work Day", new AssignmentParameterPairCheck<Integer>() {
866            @Override
867            public boolean isSatisfied(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) {
868                TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation();
869                if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return true;
870                return Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()) <= parameter;
871            }
872            @Override
873            public boolean isViolated(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) {
874                return true;
875            }
876            @Override
877            public ParametrizedConstraintType<Integer> create(String reference, String regexp) {
878                Matcher matcher = Pattern.compile(regexp).matcher(reference);
879                if (matcher.find()) {
880                    double hours = Double.parseDouble(matcher.group(1));
881                    int slots = (int)Math.round(12.0 * hours);
882                    return new ParametrizedConstraintType<Integer>(ConstraintType.WORKDAY, slots, reference)
883                            .setName(matcher.group(1) + " Hour Work Day").setMin(slots).setMax(slots);
884                }
885                return null;
886            }}),
887        /**
888         * Meet Together &amp; Same Weeks: Given classes are meeting together (same as if the given classes require constraints Can Share Room,
889         * Same Room, Same Time, Same Days and Same Weeks all together).
890         */
891        MEET_WITH_WEEKS("MEET_WITH_WEEKS", "Meet Together & Same Weeks", new PairCheck() {
892            @Override
893            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
894                return
895                        plc1.sameRooms(plc2) &&
896                        sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(), plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) &&
897                        sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
898                        plc1.getTimeLocation().getWeekCode().equals(plc2.getTimeLocation().getWeekCode());
899            }
900            @Override
901            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
902                return true;
903            }}, Flag.CAN_SHARE_ROOM),
904        MIN_GAP("MIN_GAP\\(([0-9\\.]+)\\)", "Mininal Gap Between Classes", new AssignmentParameterPairCheck<Integer>() {
905            @Override
906            public boolean isSatisfied(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) {
907                TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation();
908                if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return true;
909                return t1.getStartSlot() + t1.getLength() + parameter <= t2.getStartSlot() ||
910                        t2.getStartSlot() + t2.getLength() + parameter <= t1.getStartSlot();
911            }
912            @Override
913            public boolean isViolated(Assignment<Lecture, Placement> assignment, Integer parameter, GroupConstraint gc, Placement plc1, Placement plc2) { return true; }
914            @Override
915            public ParametrizedConstraintType<Integer> create(String reference, String regexp) {
916                Matcher matcher = Pattern.compile(regexp).matcher(reference);
917                if (matcher.find()) {
918                    double hours = Double.parseDouble(matcher.group(1));
919                    int slots = (int)Math.round(12.0 * hours);
920                    return new ParametrizedConstraintType<Integer>(ConstraintType.MIN_GAP, slots, reference)
921                            .setName("At Least " + matcher.group(1) + " Hours Between Classes")
922                            .setMin(slots).setMax(slots);
923                }
924                return null;
925            }}),
926        /**
927         * Given classes must be taught on weeks that are back-to-back (the gap between the two assigned date patterns is less than a week).<br>
928         * When prohibited or (strongly) discouraged: any two classes must have at least a week gap in between.
929         */
930        BTB_WEEKS("BTB_WEEKS", "Back-To-Back Weeks", new PairCheck() {
931            @Override
932            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
933                if (gc.variables().size() <= 2) {
934                    return gc.isBackToBackWeeks(plc1.getTimeLocation(), plc2.getTimeLocation());
935                } else {
936                    int totalWeeks = 0;
937                    for (Lecture l: gc.variables())
938                        totalWeeks += l.getMinWeeks();
939                    return gc.isMaxWeekSpan(plc1.getTimeLocation(), plc2.getTimeLocation(), totalWeeks);
940                }
941            }
942            @Override
943            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
944                return gc.isNotBackToBackWeeks(plc1.getTimeLocation(), plc2.getTimeLocation());
945            }}),
946        /**
947         * Given classes must be taught on weeks that are back-to-back and in the given order.<br>
948         * When prohibited or (strongly) discouraged: given classes must be taught on weeks in the given order with at least one week between any two following classes.
949         */
950        FOLLOWING_WEEKS("FOLLOWING_WEEKS", "Following Weeks", new PairCheck() {
951            @Override
952            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
953                return gc.isFollowingWeeksBTB(plc1, plc2, true);
954            }
955            @Override
956            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
957                return gc.isFollowingWeeksBTB(plc1, plc2, false);
958            }}),
959        /**
960         * Given classes must be taught on the same dates. If one of the classes meets more often, the class meeting less often can only meet on the dates when the other class is meeting.<br>
961         * When prohibited or (strongly) discouraged: given classes cannot be taught on the same days (there cannot be a date when both classes are meeting).<br>
962         * Note: unlike with the same days/weeks constraint, this constraint consider individual meeting dates of both classes.
963         */
964        SAME_DATES("SAME_DATES", "Same Dates", new PairCheck() {
965            @Override
966            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
967                return gc.isSameDates(plc1.getTimeLocation(), plc2.getTimeLocation());
968            }
969            @Override
970            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
971                return gc.isDifferentDates(plc1.getTimeLocation(), plc2.getTimeLocation());
972            }}),
973        /**
974         * Same Days-Room-Start: Given classes must start at the same time of day, on the same days and in the same room.
975         * It is the combination of Same Days, Same Start and Same Room distribution preferences.
976         * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days 
977         * during the same time in the same room.
978         */
979        SAME_DAYS_ROOM_START("SAME_DAY_ROOM_START", "Same Days-Room-Start", new PairCheck() {
980            @Override
981            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
982                return (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) == 
983                        (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) &&
984                        sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
985                        plc1.sameRooms(plc2);
986            }
987            @Override
988            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
989                return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) ||
990                        !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()) ||
991                        !plc1.sameRooms(plc2);
992            }}),
993        /**
994         * Overnight: The constraint has two parameters: hours and distance in minutes. There is a problem when
995         * an evening class is followed by a morning class the next day and the time in between is less then the
996         * given number of hours, but only when the distance in minutes between them is greater than the
997         * given number of minutes.
998         */
999        DAYBREAK("DAYBREAK\\(([0-9\\.]+),(-?[0-9]+)\\)", "Daybreak", new AssignmentParameterPairCheck<Integer[]>() {
1000            @Override
1001            public boolean isSatisfied(Assignment<Lecture, Placement> assignment, Integer[] param, GroupConstraint gc, Placement plc1, Placement plc2) {
1002                TimeLocation t1 = plc1.getTimeLocation();
1003                TimeLocation t2 = plc2.getTimeLocation();
1004                if (288 + t2.getStartSlot() - t1.getStartSlot() - t1.getLength() < gc.getType().getMin()) { // close to each other
1005                    if (gc.isNextDay(t1, t2)) { // next day
1006                        if (gc.getType().getMax() < 0) { // no distance check
1007                            return false;
1008                        } else {
1009                            DistanceMetric m = ((TimetableModel)gc.getModel()).getDistanceMetric();
1010                            if (Placement.getDistanceInMinutes(m, plc1, plc2) > gc.getType().getMax()) { // distance check
1011                                return false;
1012                            }
1013                        }
1014                    }
1015                } else if (288 + t1.getStartSlot() - t2.getStartSlot() - t2.getLength() < gc.getType().getMin()) { // close to each other, but the other way around
1016                    if (gc.isNextDay(t2, t1)) { // next day
1017                        if (gc.getType().getMax() < 0) { // no distance check
1018                            return false;
1019                        } else {
1020                            DistanceMetric m = ((TimetableModel)gc.getModel()).getDistanceMetric();
1021                            if (Placement.getDistanceInMinutes(m, plc2, plc1) > gc.getType().getMax()) { // distance check
1022                                return false;
1023                            }
1024                        }
1025                    }
1026                }
1027                return true;
1028            }
1029            @Override
1030            public boolean isViolated(Assignment<Lecture, Placement> assignment, Integer[] parameter, GroupConstraint gc, Placement plc1, Placement plc2) {
1031                return true;
1032            }
1033            @Override
1034            public ParametrizedConstraintType<Integer[]> create(String reference, String regexp) {
1035                Matcher matcher = Pattern.compile(regexp).matcher(reference);
1036                if (matcher.find()) {
1037                    double hours = Double.parseDouble(matcher.group(1));
1038                    int distanceSlots = (int)Math.round(12.0 * hours);
1039                    int distanceInMinutes = Integer.parseInt(matcher.group(2));
1040                    return new ParametrizedConstraintType<Integer[]>(ConstraintType.DAYBREAK, 
1041                            new Integer[] {distanceSlots, distanceInMinutes}, reference)
1042                            .setName("Daybreak of " + ( distanceSlots / 12.0) + " hours" + (distanceInMinutes >= 0 ? " when over " + distanceInMinutes + " mins": ""))
1043                            .setMin(distanceSlots).setMax(distanceInMinutes);
1044                }
1045                return null;
1046            }}),
1047            /**
1048             * Online/Offline Room: Given classes, if scheduled on the same day, must be all in the online room or
1049             * none of them can be in the online room. This means there is a conflict when two classes
1050             * are placed on the same day, but one is in online room and the other is not.
1051             */
1052            ONLINE_ROOM("ONLINE_ROOM", "Online/Offline Room", new PairCheck() {
1053                @Override
1054                public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
1055                    TimeLocation t1 = plc1.getTimeLocation();
1056                    TimeLocation t2 = plc2.getTimeLocation();
1057                    if (t1.shareDays(t2) && t1.shareWeeks(t2)) {
1058                        return gc.isOnline(plc1) == gc.isOnline(plc2);
1059                    } else {
1060                        // different days > do not care
1061                        return true;
1062                    }
1063                }
1064                @Override
1065                public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { return true; }
1066            }),
1067            /**
1068             * Same Days-Time-Weeks: Given classes must be taught at the same time of day, on the same days and on the same weeks
1069             * (i.e., must have the same date pattern).
1070             * It is the combination of Same Days, Same Time, and Same Weeks distribution preferences.
1071             * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days
1072             * during the same time and during overlapping date patterns. In other words, the given classes cannot overlap.
1073             */
1074            SAME_DATE_TIME_WEEKS("SAME_DTW", "Same Days-Time-Weeks", new PairCheck() {
1075                @Override
1076                public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
1077                    return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(),
1078                            plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) &&
1079                            sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
1080                            plc1.getTimeLocation().getWeekCode().equals(plc2.getTimeLocation().getWeekCode());
1081                }
1082                @Override
1083                public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
1084                    return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) ||
1085                            !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()) ||
1086                            !plc1.getTimeLocation().shareWeeks(plc2.getTimeLocation());
1087                }}),
1088        ;
1089        
1090        String iReference, iName;
1091        int iFlag = 0;
1092        Flag[] iFlags = null;
1093        int iMin = 0, iMax = 0;
1094        PairCheck iCheck = null;
1095        AssignmentPairCheck iAssignmentCheck = null;
1096        AssignmentParameterPairCheck<?> iAssignmentPairCheck = null;
1097        ConstraintType(String reference, String name, Flag... flags) {
1098            iReference = reference;
1099            iName = name;
1100            iFlags = flags;
1101            for (Flag f: flags)
1102                iFlag |= f.flag();
1103        }
1104        ConstraintType(String reference, String name, PairCheck check, Flag... flags) {
1105            this(reference, name, flags);
1106            iCheck = check;
1107        }
1108        ConstraintType(String reference, String name, AssignmentPairCheck check, Flag... flags) {
1109            this(reference, name, flags);
1110            iAssignmentCheck = check;
1111        }
1112        ConstraintType(String reference, String name, int limit, PairCheck check, Flag... flags) {
1113            this(reference, name, check, flags);
1114            iMin = iMax = limit;
1115        }
1116        ConstraintType(String reference, String name, int min, int max, PairCheck check, Flag... flags) {
1117            this(reference, name, check, flags);
1118            iMin = min;
1119            iMax = max;
1120        }
1121        ConstraintType(String reference, String name, AssignmentParameterPairCheck<?> check, Flag... flags) {
1122            this(reference, name, flags);
1123            iAssignmentPairCheck = check;
1124        }
1125        
1126        /**
1127         * Constraint type
1128         * @return constraint type
1129         */
1130        @Override
1131        public ConstraintType type() { return this; }
1132
1133        /** Constraint reference
1134         * @return constraint reference
1135         **/
1136        @Override
1137        public String reference() { return iReference; }
1138        
1139        /** Constraint name
1140         * @return constraint name
1141         **/
1142        @Override
1143        public String getName() { return iName; }
1144        
1145        /** Minimum (gap) parameter
1146         * @return minimum gap (first constraint parameter)
1147         **/
1148        @Override
1149        public int getMin() { return iMin; }
1150        
1151        /** Maximum (gap, hours a day) parameter 
1152         * @return maximum gap (second constraint parameter) 
1153         **/
1154        @Override
1155        public int getMax() { return iMax; }
1156        
1157        /** Flag check (true if contains given flag) 
1158         * @param f a flag to check
1159         * @return true if present
1160         **/
1161        @Override
1162        public boolean is(Flag f) { return (iFlag & f.flag()) != 0; }
1163
1164        /** Constraint type from reference 
1165         * @param reference constraint reference
1166         * @return constraint of the reference
1167         * @deprecated use {@link GroupConstraint#getConstraintType(String)} instead
1168         **/
1169        @Deprecated
1170        public static ConstraintType get(String reference) {
1171            for (ConstraintType t: ConstraintType.values())
1172                if (t.reference().equals(reference)) return t;
1173            return null;
1174        }
1175        
1176        /** True if a required or preferred constraint is satisfied between a pair of placements 
1177         * @param assignment current assignment
1178         * @param gc current constraint
1179         * @param plc1 first placement
1180         * @param plc2 second placement
1181         * @return true if the two placements are consistent with the constraint if preferred or required 
1182         **/ 
1183        @Override
1184        public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) {
1185            if (iCheck != null && !iCheck.isSatisfied(gc, plc1, plc2))
1186                return false;
1187            if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isSatisfied(assignment, gc, plc1, plc2))
1188                return false;
1189            return true;
1190        }
1191        
1192        /** True if a prohibited or discouraged constraint is satisfied between a pair of placements 
1193         * @param assignment current assignment
1194         * @param gc current constraint
1195         * @param plc1 first placement
1196         * @param plc2 second placement
1197         * @return true if the two placements are consistent with the constraint if discouraged or prohibited 
1198         **/ 
1199        @Override
1200        public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 
1201            if (iCheck != null && !iCheck.isViolated(gc, plc1, plc2))
1202                return false;
1203            if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isViolated(assignment, gc, plc1, plc2))
1204                return false;
1205            return true;
1206        }
1207        /** Pair check */
1208        private PairCheck check() { return iCheck; }
1209    }
1210    
1211    /** Constraint type from reference 
1212     * @param reference constraint reference
1213     * @return constraint of the reference
1214     **/
1215    public static ConstraintTypeInterface getConstraintType(String reference) {
1216        for (ConstraintType t: ConstraintType.values()) {
1217            if (t.reference().equals(reference)) return t;
1218            if (t.iAssignmentPairCheck != null && reference.matches(t.reference()))
1219                return t.iAssignmentPairCheck.create(reference, t.reference());
1220        }
1221        return null;
1222    }    
1223
1224    public GroupConstraint() {
1225    }
1226    
1227    @Override
1228    public void setModel(Model<Lecture, Placement> model) {
1229        super.setModel(model);
1230        if (model != null) {
1231            DataProperties config = ((TimetableModel)model).getProperties();
1232            iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0);
1233            iPrecedenceConsiderDatePatterns = config.getPropertyBoolean("Precedence.ConsiderDatePatterns", true);
1234            iPrecedenceSkipSameDatePatternCheck = config.getPropertyBoolean("Precedence.SkipSameDatePatternCheck", true);
1235            iForwardCheckMaxDepth = config.getPropertyInt("ForwardCheck.MaxDepth", iForwardCheckMaxDepth);
1236            iForwardCheckMaxDomainSize = config.getPropertyInt("ForwardCheck.MaxDomainSize", iForwardCheckMaxDomainSize);
1237            iMaxNHoursADayPrecideComputation = config.getPropertyBoolean("MaxNHoursADay.PreciseComputation", iMaxNHoursADayPrecideComputation);
1238            iMaxNHoursADayConsiderDatePatterns = config.getPropertyBoolean("MaxNHoursADay.ConsiderDatePatterns", iMaxNHoursADayConsiderDatePatterns);
1239            iNrWorkDays = (config.getPropertyInt("General.LastWorkDay", 4) - config.getPropertyInt("General.FirstWorkDay", 0) + 1);
1240            if (iNrWorkDays <= 0) iNrWorkDays += 7;
1241            if (iNrWorkDays > 7) iNrWorkDays -= 7;
1242            iFirstWorkDay = config.getPropertyInt("General.FirstWorkDay", 0);
1243            iOnlineRoom = config.getProperty("General.OnlineRoom", "(?i)ONLINE|");
1244        }
1245    }
1246
1247    @Override
1248    public void addVariable(Lecture lecture) {
1249        if (!variables().contains(lecture))
1250            super.addVariable(lecture);
1251        if (getType().is(Flag.CH_NOTOVERLAP)) {
1252            if (lecture.getChildrenSubpartIds() != null) {
1253                for (Long subpartId: lecture.getChildrenSubpartIds()) {
1254                    for (Lecture ch : lecture.getChildren(subpartId)) {
1255                        if (!variables().contains(ch))
1256                            super.addVariable(ch);
1257                    }
1258                }
1259            }
1260        }
1261    }
1262
1263    @Override
1264    public void removeVariable(Lecture lecture) {
1265        if (variables().contains(lecture))
1266            super.removeVariable(lecture);
1267        if (getType().is(Flag.CH_NOTOVERLAP)) {
1268            if (lecture.getChildrenSubpartIds() != null) {
1269                for (Long subpartId: lecture.getChildrenSubpartIds()) {
1270                    for (Lecture ch : lecture.getChildren(subpartId)) {
1271                        if (variables().contains(ch))
1272                            super.removeVariable(ch);
1273                    }
1274                }
1275            }
1276        }
1277    }
1278
1279    /**
1280     * Constructor
1281     * 
1282     * @param id
1283     *            constraint id
1284     * @param type
1285     *            constraString type (e.g, {@link ConstraintType#SAME_TIME})
1286     * @param preference
1287     *            time preference ("R" for required, "P" for prohibited, "-2",
1288     *            "-1", "1", "2" for soft preference)
1289     */
1290    public GroupConstraint(Long id, ConstraintTypeInterface type, String preference) {
1291        iConstraintId = id;
1292        iType = type;
1293        iIsRequired = preference.equals(Constants.sPreferenceRequired);
1294        iIsProhibited = preference.equals(Constants.sPreferenceProhibited);
1295        iPreference = Constants.preference2preferenceLevel(preference);
1296    }
1297
1298    /** Constraint id 
1299     * @return constraint unique id
1300     **/
1301    public Long getConstraintId() {
1302        return iConstraintId;
1303    }
1304
1305    @Override
1306    public long getId() {
1307        return (iConstraintId == null ? -1 : iConstraintId.longValue());
1308    }
1309    
1310    /** Generated unique id 
1311     * @return generated unique id
1312     **/
1313    protected long getGeneratedId() {
1314        return iId;
1315    }
1316
1317    /** Return constraint type (e.g, {@link ConstraintType#SAME_TIME}) 
1318     * @return constraint type
1319     **/
1320    public ConstraintTypeInterface getType() {
1321        return iType;
1322    }
1323
1324    /**
1325     * Set constraint type
1326     * @param type constraint type
1327     */
1328    public void setType(ConstraintType type) {
1329        iType = type;
1330    }
1331
1332    /** Is constraint required 
1333     * @return true if required
1334     **/
1335    public boolean isRequired() {
1336        return iIsRequired;
1337    }
1338
1339    /** Is constraint prohibited 
1340     * @return true if prohibited
1341     **/
1342    public boolean isProhibited() {
1343        return iIsProhibited;
1344    }
1345
1346    /**
1347     * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for
1348     * preference
1349     * @return prolog preference
1350     */
1351    public String getPrologPreference() {
1352        return Constants.preferenceLevel2preference(iPreference);
1353    }
1354
1355    @Override
1356    public boolean isConsistent(Placement value1, Placement value2) {
1357        if (!isHard())
1358            return true;
1359        if (!isSatisfiedPair(null, value1, value2))
1360            return false;
1361        if (getType().is(Flag.BACK_TO_BACK)) {
1362            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1363            assignments.put(value1.variable(), value1);
1364            assignments.put(value2.variable(), value2);
1365            if (!isSatisfiedSeq(null, assignments, null))
1366                return false;
1367        }
1368        if (getType().is(Flag.MAX_HRS_DAY)) {
1369            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1370            assignments.put(value1.variable(), value1);
1371            assignments.put(value2.variable(), value2);
1372            for (int dayCode: Constants.DAY_CODES) {
1373                if (iMaxNHoursADayPrecideComputation) {
1374                    for (IntEnumeration dates = value1.getTimeLocation().getDates(iDayOfWeekOffset); dates.hasMoreElements(); ) {
1375                        int date = dates.nextElement();
1376                        if (!value2.getTimeLocation().hasDate(date, iDayOfWeekOffset)) continue;
1377                        if (nrSlotsADay(null, date, assignments, null) > getType().getMax()) return false;
1378                    }
1379                } else if (iMaxNHoursADayConsiderDatePatterns) {
1380                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
1381                        if (!value1.getTimeLocation().shareWeeks(week) && !value2.getTimeLocation().shareWeeks(week)) continue;
1382                        if (nrSlotsADay(null, dayCode, week, assignments, null) > getType().getMax()) return false;
1383                    }
1384                } else {
1385                    if (nrSlotsADay(null, dayCode, null, assignments, null) > getType().getMax()) return false;
1386                }
1387            }
1388        }
1389        return true;
1390    }
1391
1392    @Override
1393    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
1394        computeConflicts(assignment, value, conflicts, true);
1395    }
1396    
1397    @Override
1398    public void computeConflictsNoForwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
1399        computeConflicts(assignment, value, conflicts, false);
1400    }
1401    
1402    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, boolean fwdCheck) {
1403        if (!isHard())
1404            return;
1405        for (Lecture v : variables()) {
1406            if (v.equals(value.variable()))
1407                continue; // ignore this variable
1408            Placement p = assignment.getValue(v);
1409            if (p == null)
1410                continue; // there is an unassigned variable -- great, still a chance to get violated
1411            if (!isSatisfiedPair(assignment, p, value))
1412                conflicts.add(p);
1413        }
1414        if (getType().is(Flag.BACK_TO_BACK)) {
1415            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1416            assignments.put(value.variable(), value);
1417            if (!isSatisfiedSeq(assignment, assignments, conflicts))
1418                conflicts.add(value);
1419        }
1420        if (getType().is(Flag.MAX_HRS_DAY)) {
1421            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1422            assignments.put(value.variable(), value);
1423            for (int dayCode: Constants.DAY_CODES) {
1424                if (iMaxNHoursADayPrecideComputation) {
1425                    for (IntEnumeration dates = value.getTimeLocation().getDates(iDayOfWeekOffset); dates.hasMoreElements(); ) {
1426                        int date = dates.nextElement();
1427                        if (nrSlotsADay(assignment, date, assignments, conflicts) > getType().getMax()) {
1428                            List<Placement> adepts = new ArrayList<Placement>();
1429                            for (Lecture l: variables()) {
1430                                if (l.equals(value.variable()) || l.isConstant()) continue;
1431                                Placement p = assignment.getValue(l);
1432                                if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue;
1433                                if (!p.getTimeLocation().hasDate(date, iDayOfWeekOffset)) continue;
1434                                adepts.add(p);
1435                            }
1436                            do {
1437                                if (adepts.isEmpty()) { conflicts.add(value); break; }
1438                                Placement conflict = ToolBox.random(adepts);
1439                                adepts.remove(conflict);
1440                                conflicts.add(conflict);
1441                            } while (nrSlotsADay(assignment, date, assignments, conflicts) > getType().getMax());
1442                        }
1443                    }
1444                } else if (iMaxNHoursADayConsiderDatePatterns) {
1445                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
1446                        if (!value.getTimeLocation().shareWeeks(week)) continue;
1447                        if (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax()) {
1448                            List<Placement> adepts = new ArrayList<Placement>();
1449                            for (Lecture l: variables()) {
1450                                if (l.equals(value.variable()) || l.isConstant()) continue;
1451                                Placement p = assignment.getValue(l);
1452                                if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue;
1453                                if ((p.getTimeLocation().getDayCode() & dayCode) == 0 || !p.getTimeLocation().shareWeeks(week)) continue;
1454                                adepts.add(p);
1455                            }
1456                            do {
1457                                if (adepts.isEmpty()) { conflicts.add(value); break; }
1458                                Placement conflict = ToolBox.random(adepts);
1459                                adepts.remove(conflict);
1460                                conflicts.add(conflict);
1461                            } while (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax());
1462                        }
1463                    }
1464                } else {
1465                    if (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax()) {
1466                        List<Placement> adepts = new ArrayList<Placement>();
1467                        for (Lecture l: variables()) {
1468                            if (l.equals(value.variable()) || l.isConstant()) continue;
1469                            Placement p = assignment.getValue(l);
1470                            if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue;
1471                            if ((p.getTimeLocation().getDayCode() & dayCode) == 0) continue;
1472                            adepts.add(p);
1473                        }
1474                        do {
1475                            if (adepts.isEmpty()) { conflicts.add(value); break; }
1476                            Placement conflict = ToolBox.random(adepts);
1477                            adepts.remove(conflict);
1478                            conflicts.add(conflict);
1479                        } while (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax());
1480                    }
1481                }
1482            }
1483        }
1484        
1485        // Forward checking
1486        if (fwdCheck) forwardCheck(assignment, value, conflicts, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1);
1487    }
1488    
1489    public void forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, Set<GroupConstraint> ignore, int depth) {
1490        try {
1491            if (depth < 0) return;
1492            ignore.add(this);
1493            
1494            List<Placement> neededSize = null;
1495            
1496            for (Lecture lecture: variables()) {
1497                if (conflicts.contains(value)) break; // already conflicting
1498
1499                if (lecture.equals(value.variable())) continue; // Skip this lecture
1500                Placement current = assignment.getValue(lecture);
1501                if (current != null) { // Has assignment, check whether it is conflicting
1502                    if (isSatisfiedPair(assignment, value, current)) {
1503                        // Increase needed size if the assignment is of the same room and overlapping in time
1504                        if (canShareRoom() && sameRoomAndOverlaps(value, current)) {
1505                            if (neededSize == null) neededSize = new ArrayList<Placement>(); 
1506                            neededSize.add(current);
1507                        }
1508                        continue;
1509                    }
1510                    conflicts.add(current);
1511                }
1512                
1513                // Look for supporting assignments assignment
1514                boolean shareRoomAndOverlaps = canShareRoom();
1515                Placement support = null;
1516                int nrSupports = 0;
1517                if (lecture.nrValues() >= iForwardCheckMaxDomainSize) {
1518                    // ignore variables with large domains
1519                    return;
1520                }
1521                List<Placement> values = lecture.values(assignment);
1522                if (values.isEmpty()) {
1523                    // ignore variables with empty domain
1524                    return;
1525                }
1526                for (Placement other: values) {
1527                    if (nrSupports < 2) {
1528                        if (isSatisfiedPair(assignment, value, other)) {
1529                            if (support == null) support = other;
1530                            nrSupports ++;
1531                            if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other))
1532                                shareRoomAndOverlaps = false;
1533                        }
1534                    } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) {
1535                        shareRoomAndOverlaps = false;
1536                    }
1537                    if (nrSupports > 1 && !shareRoomAndOverlaps)
1538                        break;
1539                }
1540                
1541                // No supporting assignment -> fail
1542                if (nrSupports == 0) {
1543                    conflicts.add(value); // other class cannot be assigned with this value
1544                    return;
1545                }
1546                // Increase needed size if all supporters are of the same room and in overlapping times
1547                if (shareRoomAndOverlaps && support != null) {
1548                    if (neededSize == null) neededSize = new ArrayList<Placement>(); 
1549                    neededSize.add(support);
1550                }
1551
1552                // Only one supporter -> propagate the new assignment over other hard constraints of the lecture
1553                if (nrSupports == 1) {
1554                    for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) {
1555                        if (other instanceof WeakeningConstraint) continue;
1556                        if (other instanceof GroupConstraint) {
1557                            GroupConstraint gc = (GroupConstraint)other;
1558                            if (depth > 0 && !ignore.contains(gc))
1559                                gc.forwardCheck(assignment, support, conflicts, ignore, depth - 1);
1560                        } else {
1561                            other.computeConflicts(assignment, support, conflicts);
1562                        }
1563                    }
1564                    for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) {
1565                        if (other instanceof WeakeningConstraint) continue;
1566                        other.computeConflicts(assignment, support, conflicts);
1567                    }
1568
1569                    if (conflicts.contains(support))
1570                        conflicts.add(value);
1571                }
1572            }
1573            
1574            if (canShareRoom() && neededSize != null) {
1575                if (value.getRoomLocations() != null) {
1576                    for (RoomLocation room: value.getRoomLocations())
1577                        if (room.getRoomConstraint() != null && !room.getRoomConstraint().checkRoomSize(value, neededSize)) {
1578                            // room is too small to fit all meet with classes
1579                            conflicts.add(value);
1580                        }
1581                } else if (value.getRoomLocation() != null) {
1582                    RoomLocation room = value.getRoomLocation();
1583                    if (room.getRoomConstraint() != null && !room.getRoomConstraint().checkRoomSize(value, neededSize)) {
1584                        // room is too small to fit all meet with classes
1585                        conflicts.add(value);
1586                    }
1587                }
1588            }
1589        } finally {
1590            ignore.remove(this);
1591        }
1592    }
1593
1594    @Override
1595    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
1596        if (!isHard())
1597            return false;
1598        for (Lecture v : variables()) {
1599            if (v.equals(value.variable()))
1600                continue; // ignore this variable
1601            Placement p = assignment.getValue(v);
1602            if (p == null)
1603                continue; // there is an unassigned variable -- great, still a chance to get violated
1604            if (!isSatisfiedPair(assignment, p, value))
1605                return true;
1606        }
1607        if (getType().is(Flag.BACK_TO_BACK)) {
1608            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1609            assignments.put(value.variable(), value);
1610            if (!isSatisfiedSeq(assignment, assignments, null))
1611                return true;
1612        }
1613        if (getType().is(Flag.MAX_HRS_DAY)) {
1614            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1615            assignments.put(value.variable(), value);
1616            for (int dayCode: Constants.DAY_CODES) {
1617                if (iMaxNHoursADayPrecideComputation) {
1618                    for (IntEnumeration dates = value.getTimeLocation().getDates(iDayOfWeekOffset); dates.hasMoreElements(); ) {
1619                        int date = dates.nextElement();
1620                        if (nrSlotsADay(assignment,date, assignments, null) > getType().getMax())
1621                            return true;
1622                    }
1623                } else if (iMaxNHoursADayConsiderDatePatterns) {
1624                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
1625                        if (!value.getTimeLocation().shareWeeks(week)) continue;
1626                        if (nrSlotsADay(assignment, dayCode, week, assignments, null) > getType().getMax())
1627                            return true;
1628                    }
1629                } else {
1630                    if (nrSlotsADay(assignment, dayCode, null, assignments, null) > getType().getMax()) return true;
1631                }
1632            }
1633        }
1634        
1635        if (!forwardCheck(assignment, value, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1)) return true;
1636        
1637        return false;
1638    }
1639    
1640    public boolean forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<GroupConstraint> ignore, int depth) {
1641        try {
1642            if (depth < 0) return true;
1643            ignore.add(this);
1644            
1645            int neededSize = value.variable().maxRoomUse();
1646            
1647            for (Lecture lecture: variables()) {
1648                if (lecture.equals(value.variable())) continue; // Skip this lecture
1649                Placement current = assignment.getValue(lecture);
1650                if (current != null) { // Has assignment, check whether it is conflicting
1651                    if (isSatisfiedPair(assignment, value, current)) {
1652                        // Increase needed size if the assignment is of the same room and overlapping in time
1653                        if (canShareRoom() && sameRoomAndOverlaps(value, current)) {
1654                            neededSize += lecture.maxRoomUse();
1655                        }
1656                        continue;
1657                    }
1658                    return false;
1659                }
1660                
1661                // Look for supporting assignments assignment
1662                boolean shareRoomAndOverlaps = canShareRoom();
1663                Placement support = null;
1664                int nrSupports = 0;
1665                if (lecture.nrValues() >= iForwardCheckMaxDomainSize) {
1666                    // ignore variables with large domains
1667                    return true;
1668                }
1669                List<Placement> values = lecture.values(assignment);
1670                if (values.isEmpty()) {
1671                    // ignore variables with empty domain
1672                    return true;
1673                }
1674                for (Placement other: lecture.values(assignment)) {
1675                    if (nrSupports < 2) {
1676                        if (isSatisfiedPair(assignment, value, other)) {
1677                            if (support == null) support = other;
1678                            nrSupports ++;
1679                            if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other))
1680                                shareRoomAndOverlaps = false;
1681                        }
1682                    } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) {
1683                        shareRoomAndOverlaps = false;
1684                    }
1685                    if (nrSupports > 1 && !shareRoomAndOverlaps)
1686                        break;
1687                }
1688
1689                // No supporting assignment -> fail
1690                if (nrSupports == 0) {
1691                    return false; // other class cannot be assigned with this value
1692                }
1693                // Increase needed size if all supporters are of the same room and in overlapping times
1694                if (shareRoomAndOverlaps) {
1695                    neededSize += lecture.maxRoomUse();
1696                }
1697
1698                // Only one supporter -> propagate the new assignment over other hard constraints of the lecture
1699                if (nrSupports == 1) {
1700                    for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) {
1701                        if (other instanceof WeakeningConstraint) continue;
1702                        if (other instanceof GroupConstraint) {
1703                            GroupConstraint gc = (GroupConstraint)other;
1704                            if (depth > 0 && !ignore.contains(gc) && !gc.forwardCheck(assignment, support, ignore, depth - 1)) return false;
1705                        } else {
1706                            if (other.inConflict(assignment, support)) return false;
1707                        }
1708                    }
1709                    for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) {
1710                        if (other instanceof WeakeningConstraint) continue;
1711                        if (other.inConflict(assignment, support)) return false;
1712                    }
1713                }
1714            }
1715            
1716            if (canShareRoom() && neededSize > value.getRoomSize()) {
1717                // room is too small to fit all meet with classes
1718                return false;
1719            }
1720         
1721            return true;
1722        } finally {
1723            ignore.remove(this);
1724        }
1725    }
1726
1727    /** Constraint preference (0 if prohibited or required) 
1728     * @return constraint preference (if soft)
1729     **/
1730    public int getPreference() {
1731        return iPreference;
1732    }
1733
1734    /**
1735     * Current constraint preference (0 if prohibited or required, depends on
1736     * current satisfaction of the constraint)
1737     * @param assignment current assignment
1738     * @return current preference
1739     */
1740    public int getCurrentPreference(Assignment<Lecture, Placement> assignment) {
1741        if (isHard()) return 0; // no preference
1742        if (countAssignedVariables(assignment) < 2) return - Math.abs(iPreference); // not enough variable
1743        if (getType().is(Flag.MAX_HRS_DAY)) { // max hours a day
1744            int over = 0;
1745            for (int dayCode: Constants.DAY_CODES) {
1746                if (iMaxNHoursADayPrecideComputation) {
1747                    Set<Integer> allDates = new HashSet<Integer>();
1748                    for (Lecture v1 : variables()) {
1749                        Placement p1 = assignment.getValue(v1);
1750                        if (p1 == null) continue;
1751                        for (IntEnumeration dates = p1.getTimeLocation().getDates(iDayOfWeekOffset); dates.hasMoreElements(); ) {
1752                            int date = dates.nextElement();
1753                            if (allDates.add(date))
1754                                over += Math.max(0, nrSlotsADay(assignment, date, null, null) - getType().getMax());
1755                        }
1756                    }
1757                } else if (iMaxNHoursADayConsiderDatePatterns) {
1758                    for (BitSet week: ((TimetableModel)getModel()).getWeeks())
1759                        over += Math.max(0, nrSlotsADay(assignment, dayCode, week, null, null) - getType().getMax());
1760                } else {
1761                    over += Math.max(0, nrSlotsADay(assignment, dayCode, null, null, null) - getType().getMax());
1762                }
1763            }
1764            return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference));
1765        }
1766        int nrViolatedPairs = 0;
1767        for (Lecture v1 : variables()) {
1768            Placement p1 = assignment.getValue(v1);
1769            if (p1 == null) continue;
1770            for (Lecture v2 : variables()) {
1771                Placement p2 = assignment.getValue(v2);
1772                if (p2 == null || v1.getId() >= v2.getId()) continue;
1773                if (!isSatisfiedPair(assignment, p1, p2)) nrViolatedPairs++;
1774            }
1775        }
1776        if (getType().is(Flag.BACK_TO_BACK)) {
1777            Set<Placement> conflicts = new HashSet<Placement>();
1778            if (isSatisfiedSeq(assignment, new HashMap<Lecture, Placement>(), conflicts))
1779                nrViolatedPairs += conflicts.size();
1780            else
1781                nrViolatedPairs = variables().size();
1782        }
1783        return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference));
1784    }
1785
1786    /** Current constraint preference change (if given placement is assigned) 
1787     * @param assignment current assignment
1788     * @param placement placement that is being considered
1789     * @return change in the current preference, if assigned 
1790     **/
1791    public int getCurrentPreference(Assignment<Lecture, Placement> assignment, Placement placement) {
1792        if (isHard()) return 0; // no preference
1793        if (countAssignedVariables(assignment) + (assignment.getValue(placement.variable()) == null ? 1 : 0) < 2) return 0; // not enough variable
1794        if (getType().is(Flag.MAX_HRS_DAY)) {
1795            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1796            assignments.put(placement.variable(), placement);
1797            HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>();
1798            unassignments.put(placement.variable(), null);
1799            int after = 0;
1800            int before = 0;
1801            for (int dayCode: Constants.DAY_CODES) {
1802                if (iMaxNHoursADayPrecideComputation) {
1803                    for (IntEnumeration dates = placement.getTimeLocation().getDates(iDayOfWeekOffset); dates.hasMoreElements(); ) {
1804                        int date = dates.nextElement();
1805                        after += Math.max(0, nrSlotsADay(assignment, date, assignments, null) - getType().getMax());
1806                        before += Math.max(0, nrSlotsADay(assignment, date, unassignments, null) - getType().getMax());
1807                    }
1808                } else if (iMaxNHoursADayConsiderDatePatterns) {
1809                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
1810                        after += Math.max(0, nrSlotsADay(assignment, dayCode, week, assignments, null) - getType().getMax());
1811                        before += Math.max(0, nrSlotsADay(assignment, dayCode, week, unassignments, null) - getType().getMax());
1812                    }
1813                } else {
1814                    after += Math.max(0, nrSlotsADay(assignment, dayCode, null, assignments, null) - getType().getMax());
1815                    before += Math.max(0, nrSlotsADay(assignment, dayCode, null, unassignments, null) - getType().getMax());
1816                }
1817            }
1818            return (after > 0 ? Math.abs(iPreference) * after / 12 : - Math.abs(iPreference)) - (before > 0 ? Math.abs(iPreference) * before / 12 : - Math.abs(iPreference));
1819        }
1820        
1821        int nrViolatedPairsAfter = 0;
1822        int nrViolatedPairsBefore = 0;
1823        for (Lecture v1 : variables()) {
1824            for (Lecture v2 : variables()) {
1825                if (v1.getId() >= v2.getId()) continue;
1826                Placement p1 = (v1.equals(placement.variable()) ? null : assignment.getValue(v1));
1827                Placement p2 = (v2.equals(placement.variable()) ? null : assignment.getValue(v2));
1828                if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2))
1829                    nrViolatedPairsBefore ++;
1830                if (v1.equals(placement.variable())) p1 = placement;
1831                if (v2.equals(placement.variable())) p2 = placement;
1832                if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2))
1833                    nrViolatedPairsAfter ++;
1834            }
1835        }
1836        
1837        if (getType().is(Flag.BACK_TO_BACK)) {
1838            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1839            assignments.put(placement.variable(), placement);
1840            Set<Placement> conflicts = new HashSet<Placement>();
1841            if (isSatisfiedSeq(assignment, assignments, conflicts))
1842                nrViolatedPairsAfter += conflicts.size();
1843            else
1844                nrViolatedPairsAfter = variables().size();
1845            
1846            HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>();
1847            unassignments.put(placement.variable(), null);
1848            Set<Placement> previous = new HashSet<Placement>();
1849            if (isSatisfiedSeq(assignment, unassignments, previous))
1850                nrViolatedPairsBefore += previous.size();
1851            else
1852                nrViolatedPairsBefore = variables().size();
1853        }
1854        
1855        return (nrViolatedPairsAfter > 0 ? Math.abs(iPreference) * nrViolatedPairsAfter : - Math.abs(iPreference)) -
1856                (nrViolatedPairsBefore > 0 ? Math.abs(iPreference) * nrViolatedPairsBefore : - Math.abs(iPreference));
1857    }
1858
1859    @Override
1860    public String toString() {
1861        StringBuffer sb = new StringBuffer();
1862        sb.append(getName());
1863        sb.append(" between ");
1864        for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) {
1865            Lecture v = e.next();
1866            sb.append(v.getName());
1867            if (e.hasNext())
1868                sb.append(", ");
1869        }
1870        return sb.toString();
1871    }
1872
1873    @Override
1874    public boolean isHard() {
1875        return iIsRequired || iIsProhibited;
1876    }
1877
1878    @Override
1879    public String getName() {
1880        return getType().getName();
1881    }
1882
1883
1884    private boolean isPrecedence(Placement p1, Placement p2, boolean firstGoesFirst, boolean considerDatePatterns) {
1885        int ord1 = variables().indexOf(p1.variable());
1886        int ord2 = variables().indexOf(p2.variable());
1887        TimeLocation t1 = null, t2 = null;
1888        if (ord1 < ord2) {
1889            if (firstGoesFirst) {
1890                t1 = p1.getTimeLocation();
1891                t2 = p2.getTimeLocation();
1892            } else {
1893                t2 = p1.getTimeLocation();
1894                t1 = p2.getTimeLocation();
1895            }
1896        } else {
1897            if (!firstGoesFirst) {
1898                t1 = p1.getTimeLocation();
1899                t2 = p2.getTimeLocation();
1900            } else {
1901                t2 = p1.getTimeLocation();
1902                t1 = p2.getTimeLocation();
1903            }
1904        }
1905        if (considerDatePatterns && iPrecedenceConsiderDatePatterns) {
1906            if (iPrecedenceSkipSameDatePatternCheck) {
1907                int m1 = t1.getFirstMeeting(iDayOfWeekOffset), m2 = t2.getFirstMeeting(iDayOfWeekOffset);
1908                if (m1 != m2) return m1 < m2;
1909            } else {
1910                boolean sameDatePattern = (t1.getDatePatternId() != null ? t1.getDatePatternId().equals(t2.getDatePatternId()) : t1.getWeekCode().equals(t2.getWeekCode()));
1911                if (!sameDatePattern) {
1912                    int m1 = t1.getFirstMeeting(iDayOfWeekOffset), m2 = t2.getFirstMeeting(iDayOfWeekOffset);
1913                    if (m1 != m2) return m1 < m2;
1914                }
1915            }
1916        }
1917        if (iFirstWorkDay != 0) {
1918            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
1919                int idx = (i + iFirstWorkDay) % 7;
1920                boolean a = (t1.getDayCode() & Constants.DAY_CODES[idx]) != 0;
1921                boolean b = (t2.getDayCode() & Constants.DAY_CODES[idx]) != 0;
1922                if (b && !a) return false; // second start first
1923                if (a && !b) return true;  // first start first
1924                if (a && b) return t1.getStartSlot() + t1.getLength() <= t2.getStartSlot(); // same day: check times
1925            }
1926        }
1927        return t1.getStartSlots().nextElement() + t1.getLength() <= t2.getStartSlots().nextElement();
1928    }
1929
1930    private boolean isBackToBackDays(TimeLocation t1, TimeLocation t2) {
1931        int f1 = -1, f2 = -1, e1 = -1, e2 = -1;
1932        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
1933            int idx = (i + iFirstWorkDay) % 7;
1934            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1935                if (f1 < 0)
1936                    f1 = i;
1937                e1 = i;
1938            }
1939            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1940                if (f2 < 0)
1941                    f2 = i;
1942                e2 = i;
1943            }
1944        }
1945        return (e1 + 1 == f2) || (e2 + 1 == f1);
1946    }
1947    
1948    private boolean isNrDaysBetweenGreaterThanOne(TimeLocation t1, TimeLocation t2) {
1949        int f1 = -1, f2 = -1, e1 = -1, e2 = -1;
1950        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
1951            int idx = (i + iFirstWorkDay) % 7;
1952            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1953                if (f1 < 0)
1954                    f1 = i;
1955                e1 = i;
1956            }
1957            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1958                if (f2 < 0)
1959                    f2 = i;
1960                e2 = i;
1961            }
1962        }
1963        return (e1 - f2 > 2) || (e2 - f1 > 2);
1964    }
1965
1966    private boolean isFollowingDay(Placement p1, Placement p2, boolean firstGoesFirst) {
1967        int ord1 = variables().indexOf(p1.variable());
1968        int ord2 = variables().indexOf(p2.variable());
1969        TimeLocation t1 = null, t2 = null;
1970        if (ord1 < ord2) {
1971            if (firstGoesFirst) {
1972                t1 = p1.getTimeLocation();
1973                t2 = p2.getTimeLocation();
1974            } else {
1975                t2 = p1.getTimeLocation();
1976                t1 = p2.getTimeLocation();
1977            }
1978        } else {
1979            if (!firstGoesFirst) {
1980                t1 = p1.getTimeLocation();
1981                t2 = p2.getTimeLocation();
1982            } else {
1983                t2 = p1.getTimeLocation();
1984                t1 = p2.getTimeLocation();
1985            }
1986        }
1987        int f1 = -1, f2 = -1, e1 = -1;
1988        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
1989            int idx = (i + iFirstWorkDay) % 7;
1990            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1991                if (f1 < 0)
1992                    f1 = i;
1993                e1 = i;
1994            }
1995            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1996                if (f2 < 0)
1997                    f2 = i;
1998            }
1999        }
2000        return ((e1 + 1) % iNrWorkDays == f2);
2001    }
2002    
2003    private boolean isNextDay(TimeLocation t1, TimeLocation t2) {
2004        if (iPrecedenceConsiderDatePatterns) {
2005            for (Enumeration<Integer> e = t1.getDates(iDayOfWeekOffset); e.hasMoreElements(); ) {
2006                Integer date = e.nextElement();
2007                if (t2.hasDate(date + 1, iDayOfWeekOffset)) return true;
2008            }
2009            return false;
2010        }
2011        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
2012            int i1 = (i + iFirstWorkDay) % 7;
2013            int i2 = (1 + i1) % 7;
2014            boolean a = (t1.getDayCode() & Constants.DAY_CODES[i1]) != 0;
2015            boolean b = (t2.getDayCode() & Constants.DAY_CODES[i2]) != 0;
2016            if (a && b) return true;
2017        }
2018        return false;
2019    }
2020
2021    private boolean isEveryOtherDay(Placement p1, Placement p2, boolean firstGoesFirst) {
2022        int ord1 = variables().indexOf(p1.variable());
2023        int ord2 = variables().indexOf(p2.variable());
2024        TimeLocation t1 = null, t2 = null;
2025        if (ord1 < ord2) {
2026            if (firstGoesFirst) {
2027                t1 = p1.getTimeLocation();
2028                t2 = p2.getTimeLocation();
2029            } else {
2030                t2 = p1.getTimeLocation();
2031                t1 = p2.getTimeLocation();
2032            }
2033        } else {
2034            if (!firstGoesFirst) {
2035                t1 = p1.getTimeLocation();
2036                t2 = p2.getTimeLocation();
2037            } else {
2038                t2 = p1.getTimeLocation();
2039                t1 = p2.getTimeLocation();
2040            }
2041        }
2042        int f1 = -1, f2 = -1, e1 = -1;
2043        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
2044            int idx = (i + iFirstWorkDay) % 7;
2045            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
2046                if (f1 < 0)
2047                    f1 = i;
2048                e1 = i;
2049            }
2050            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
2051                if (f2 < 0)
2052                    f2 = i;
2053            }
2054        }
2055        return ((e1 + 2) % iNrWorkDays == f2);
2056    }
2057
2058    private static boolean sameDays(int[] days1, int[] days2) {
2059        if (days2.length < days1.length)
2060            return sameDays(days2, days1);
2061        int i2 = 0;
2062        for (int i1 = 0; i1 < days1.length; i1++) {
2063            int d1 = days1[i1];
2064            while (true) {
2065                if (i2 == days2.length)
2066                    return false;
2067                int d2 = days2[i2];
2068                if (d1 == d2)
2069                    break;
2070                i2++;
2071                if (i2 == days2.length)
2072                    return false;
2073            }
2074            i2++;
2075        }
2076        return true;
2077    }
2078    
2079    private static boolean sameRoomAndOverlaps(Placement p1, Placement p2) {
2080        return p1.shareRooms(p2) && p1.getTimeLocation() != null && p2.getTimeLocation() != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation());
2081    }
2082
2083    private static boolean sameHours(int start1, int len1, int start2, int len2) {
2084        if (len1 > len2)
2085            return sameHours(start2, len2, start1, len1);
2086        start1 %= Constants.SLOTS_PER_DAY;
2087        start2 %= Constants.SLOTS_PER_DAY;
2088        return (start1 >= start2 && start1 + len1 <= start2 + len2);
2089    }
2090    
2091    private static boolean canFill(int totalGap, int gapMin, int gapMax, List<Set<Integer>> lengths) {
2092        if (gapMin <= totalGap && totalGap <= gapMax)
2093            return true;
2094        if (totalGap < 2 * gapMin)
2095            return false;
2096        for (int i = 0; i < lengths.size(); i++) {
2097            Set<Integer> length = lengths.get(i);
2098            lengths.remove(i);
2099            for (int gap = gapMin; gap <= gapMax; gap++)
2100                for (Integer l: length)
2101                    if (canFill(totalGap - gap - l, gapMin, gapMax, lengths))
2102                        return true;
2103            lengths.add(i, length);
2104        }
2105        return false;
2106    }
2107
2108    private boolean isSatisfiedSeq(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
2109        if (conflicts == null)
2110            return isSatisfiedSeqCheck(assignment, assignments, conflicts);
2111        else {
2112            Set<Placement> bestConflicts = isSatisfiedRecursive(assignment, 0, assignments, conflicts,
2113                    new HashSet<Placement>(), null);
2114            if (bestConflicts == null)
2115                return false;
2116            conflicts.addAll(bestConflicts);
2117            return true;
2118        }
2119    }
2120
2121    private Set<Placement> isSatisfiedRecursive(Assignment<Lecture, Placement> assignment, int idx, HashMap<Lecture, Placement> assignments,
2122            Set<Placement> conflicts, Set<Placement> newConflicts, Set<Placement> bestConflicts) {
2123        if (idx == variables().size() && newConflicts.isEmpty())
2124            return bestConflicts;
2125        if (isSatisfiedSeqCheck(assignment, assignments, conflicts)) {
2126            if (bestConflicts == null) {
2127                return new HashSet<Placement>(newConflicts);
2128            } else {
2129                int b = 0, n = 0;
2130                for (Placement value: assignments.values()) {
2131                    if (value != null && bestConflicts.contains(value)) b++;
2132                    if (value != null && newConflicts.contains(value)) n++;
2133                }
2134                if (n < b || (n == b && newConflicts.size() < bestConflicts.size()))
2135                    return new HashSet<Placement>(newConflicts);
2136            }
2137            return bestConflicts;
2138        }
2139        if (idx == variables().size())
2140            return bestConflicts;
2141        bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts,
2142                bestConflicts);
2143        Lecture lecture = variables().get(idx);
2144        //if (assignments != null && assignments.containsKey(lecture))
2145        //    return bestConflicts;
2146        Placement placement = null;
2147        if (assignments != null && assignments.containsKey(lecture))
2148            placement = assignments.get(lecture);
2149        else if (assignment != null)
2150            placement = assignment.getValue(lecture);
2151        if (placement == null)
2152            return bestConflicts;
2153        if (conflicts != null && conflicts.contains(placement))
2154            return bestConflicts;
2155        conflicts.add(placement);
2156        newConflicts.add(placement);
2157        bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts, bestConflicts);
2158        newConflicts.remove(placement);
2159        conflicts.remove(placement);
2160        return bestConflicts;
2161    }
2162
2163    private boolean isSatisfiedSeqCheck(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
2164        if (!getType().is(Flag.BACK_TO_BACK)) return true;
2165        int gapMin = getType().getMin();
2166        int gapMax = getType().getMax();
2167
2168        List<Set<Integer>> lengths = new ArrayList<Set<Integer>>();
2169
2170        Placement[] res = new Placement[Constants.SLOTS_PER_DAY];
2171        for (int i = 0; i < Constants.SLOTS_PER_DAY; i++)
2172            res[i] = null;
2173
2174        int nrLectures = 0;
2175
2176        for (Lecture lecture : variables()) {
2177            Placement placement = null;
2178            if (assignments != null && assignments.containsKey(lecture))
2179                placement = assignments.get(lecture);
2180            else if (assignment != null)
2181                placement = assignment.getValue(lecture);
2182            if (placement == null) {
2183                if (!lecture.timeLocations().isEmpty()) {
2184                    Set<Integer> l = new HashSet<Integer>();
2185                    for (TimeLocation time: lecture.timeLocations())
2186                        l.add(time.getLength());
2187                    lengths.add(l);
2188                }
2189            } else if (conflicts != null && conflicts.contains(placement)) {
2190                if (!lecture.timeLocations().isEmpty()) {
2191                    Set<Integer> l = new HashSet<Integer>();
2192                    for (TimeLocation time: lecture.timeLocations())
2193                        l.add(time.getLength());
2194                    lengths.add(l);
2195                }
2196            } else {
2197                int pos = placement.getTimeLocation().getStartSlot();
2198                int length = placement.getTimeLocation().getLength();
2199                for (int j = pos; j < pos + length; j++) {
2200                    if (res[j] != null) {
2201                        if (conflicts == null)
2202                            return false;
2203                        if (!assignments.containsKey(lecture))
2204                            conflicts.add(placement);
2205                        else if (!assignments.containsKey(res[j].variable()))
2206                            conflicts.add(res[j]);
2207                    }
2208                }
2209                for (int j = pos; j < pos + length; j++)
2210                    res[j] = placement;
2211                nrLectures++;
2212            }
2213        }
2214        if (nrLectures <= 1)
2215            return true;
2216
2217        if (iIsRequired || (!iIsProhibited && iPreference < 0)) {
2218            int i = 0;
2219            Placement p = res[i];
2220            while (p == null)
2221                p = res[++i];
2222            i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
2223            nrLectures--;
2224            while (nrLectures > 0) {
2225                int gap = 0;
2226                while (i < Constants.SLOTS_PER_DAY && res[i] == null) {
2227                    gap++;
2228                    i++;
2229                }
2230                if (i == Constants.SLOTS_PER_DAY)
2231                    break;
2232                if (!canFill(gap, gapMin, gapMax, lengths))
2233                    return false;
2234                p = res[i];
2235                i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
2236                nrLectures--;
2237            }
2238        } else if (iIsProhibited || (!iIsRequired && iPreference > 0)) {
2239            int i = 0;
2240            Placement p = res[i];
2241            while (p == null)
2242                p = res[++i];
2243            i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
2244            nrLectures--;
2245            while (nrLectures > 0) {
2246                int gap = 0;
2247                while (i < Constants.SLOTS_PER_DAY && res[i] == null) {
2248                    gap++;
2249                    i++;
2250                }
2251                if (i == Constants.SLOTS_PER_DAY)
2252                    break;
2253                if ((gapMin == 0 || !canFill(gap, 0, gapMin - 1, lengths))
2254                        && (gapMax >= Constants.SLOTS_PER_DAY || !canFill(gap, gapMax + 1, Constants.SLOTS_PER_DAY,
2255                                lengths))) {
2256                    return false;
2257                }
2258                p = res[i];
2259                i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
2260                nrLectures--;
2261            }
2262        }
2263        return true;
2264    }
2265
2266    public boolean isSatisfied(Assignment<Lecture, Placement> assignment) {
2267        if (isHard()) return true;
2268        if (countAssignedVariables(assignment) < 2) return true;
2269        if (getPreference() == 0) return true;
2270        return isHard() || countAssignedVariables(assignment) < 2 || getPreference() == 0 || getCurrentPreference(assignment) < 0;
2271    }
2272
2273    public boolean isChildrenNotOverlap(Assignment<Lecture, Placement> assignment, Lecture lec1, Placement plc1, Lecture lec2, Placement plc2) {
2274        if (lec1.getSchedulingSubpartId().equals(lec2.getSchedulingSubpartId())) {
2275            // same subpart
2276            boolean overlap = plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation());
2277
2278            if (overlap && lec1.getParent() != null && variables().contains(lec1.getParent())
2279                    && lec2.getParent() != null && variables().contains(lec2.getParent())) {
2280                // children overlaps
2281                Placement p1 = assignment.getValue(lec1.getParent());
2282                Placement p2 = assignment.getValue(lec2.getParent());
2283                // parents not overlap, but children do
2284                if (p1 != null && p2 != null && !p1.getTimeLocation().hasIntersection(p2.getTimeLocation()))
2285                    return false;
2286            }
2287
2288            if (!overlap && lec1.getChildrenSubpartIds() != null && lec2.getChildrenSubpartIds() != null) {
2289                // parents not overlap
2290                for (Long subpartId: lec1.getChildrenSubpartIds()) {
2291                    for (Lecture c1 : lec1.getChildren(subpartId)) {
2292                        Placement p1 = assignment.getValue(c1);
2293                        if (p1 == null) continue;
2294                        for (Lecture c2 : lec2.getChildren(subpartId)) {
2295                            Placement p2 = assignment.getValue(c2);
2296                            if (p2 == null) continue;
2297                            if (!c1.getSchedulingSubpartId().equals(c2.getSchedulingSubpartId())) continue;
2298                            // parents not overlap, but children do
2299                            if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation()))
2300                                return false;
2301                        }
2302                    }
2303                }
2304            }
2305        } else {
2306            // different subpart
2307        }
2308        return true;
2309    }
2310
2311    public boolean isSatisfiedPair(Assignment<Lecture, Placement> assignment, Placement plc1, Placement plc2) {
2312        if (iIsRequired || (!iIsProhibited && iPreference <= 0))
2313            return getType().isSatisfied(assignment, this, plc1, plc2);
2314        else if (iIsProhibited || (!iIsRequired && iPreference > 0))
2315            return getType().isViolated(assignment, this, plc1, plc2);
2316        return true;
2317    }
2318    
2319    public boolean canShareRoom() {
2320        return getType().is(Flag.CAN_SHARE_ROOM);
2321    }
2322    
2323    protected int nrSlotsADay(Assignment<Lecture, Placement> assignment, int dayCode, BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
2324        Set<Integer> slots = new HashSet<Integer>();
2325        for (Lecture lecture: variables()) {
2326            Placement placement = null;
2327            if (assignments != null && assignments.containsKey(lecture))
2328                placement = assignments.get(lecture);
2329            else if (assignment != null)
2330                placement = assignment.getValue(lecture);
2331            if (placement == null || placement.getTimeLocation() == null) continue;
2332            if (conflicts != null && conflicts.contains(placement)) continue;
2333            TimeLocation t = placement.getTimeLocation();
2334            if (t == null || (t.getDayCode() & dayCode) == 0 || (week != null && !t.shareWeeks(week))) continue;
2335            for (int i = 0; i < t.getLength(); i++)
2336                slots.add(i + t.getStartSlot());
2337        }
2338        return slots.size();
2339    }
2340    
2341    protected int nrSlotsADay(Assignment<Lecture, Placement> assignment, int date, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
2342        Set<Integer> slots = new HashSet<Integer>();
2343        for (Lecture lecture: variables()) {
2344            Placement placement = null;
2345            if (assignments != null && assignments.containsKey(lecture))
2346                placement = assignments.get(lecture);
2347            else if (assignment != null)
2348                placement = assignment.getValue(lecture);
2349            if (placement == null || placement.getTimeLocation() == null) continue;
2350            if (conflicts != null && conflicts.contains(placement)) continue;
2351            TimeLocation t = placement.getTimeLocation();
2352            if (t == null || !t.hasDate(date, iDayOfWeekOffset)) continue;
2353            for (int i = 0; i < t.getLength(); i++)
2354                slots.add(i + t.getStartSlot());
2355        }
2356        return slots.size();
2357    }
2358
2359    @Override
2360    public boolean equals(Object o) {
2361        if (o == null || !(o instanceof GroupConstraint)) return false;
2362        return getGeneratedId() == ((GroupConstraint) o).getGeneratedId();
2363    }
2364    
2365    @Override
2366    public GroupConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
2367        return new GroupConstraintContext(assignment);
2368    }
2369
2370    public class GroupConstraintContext implements AssignmentConstraintContext<Lecture, Placement> {
2371        protected int iLastPreference = 0;
2372        
2373        public GroupConstraintContext(Assignment<Lecture, Placement> assignment) {
2374            updateCriterion(assignment);
2375        }
2376
2377        @Override
2378        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
2379            updateCriterion(assignment);
2380        }
2381
2382        @Override
2383        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
2384            updateCriterion(assignment);
2385        }
2386        
2387        protected void updateCriterion(Assignment<Lecture, Placement> assignment) {
2388            if (!isHard()) {
2389                getModel().getCriterion(DistributionPreferences.class).inc(assignment, -iLastPreference);
2390                iLastPreference = getCurrentPreference(assignment) + Math.abs(iPreference);
2391                getModel().getCriterion(DistributionPreferences.class).inc(assignment, iLastPreference);
2392            }
2393        }
2394        
2395        public int getPreference() { return iLastPreference; }
2396    }
2397    
2398    private boolean isBackToBackWeeks(TimeLocation t1, TimeLocation t2) {
2399        if (t1.shareWeeks(t2)) return false;
2400        int f1 = t1.getWeekCode().nextSetBit(0);
2401        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
2402        int f2 = t2.getWeekCode().nextSetBit(0);
2403        int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size());
2404        if (e1 < f2) {
2405            return (f2 - e1) < 7;
2406        } else if (e2 < f1) {
2407            return (f1 - e2) < 7;
2408        }
2409        return false;
2410    }
2411    
2412    private boolean isMaxWeekSpan(TimeLocation t1, TimeLocation t2, int nrWeeks) {
2413        if (t1.shareWeeks(t2)) return false;
2414        if (isBackToBackWeeks(t1, t2)) return true;
2415        
2416        int f1 = t1.getWeekCode().nextSetBit(0);
2417        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
2418        int f2 = t2.getWeekCode().nextSetBit(0);
2419        int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size());
2420        if (e1 < f2) {
2421            return (3 + e2 - f1) / 7 <= nrWeeks;
2422        } else if (e2 < f1) {
2423            return (3 + e1 - f2) / 7 <= nrWeeks;
2424        }
2425        return false;
2426    }
2427    
2428    private boolean isNotBackToBackWeeks(TimeLocation t1, TimeLocation t2) {
2429        if (t1.shareWeeks(t2)) return false;
2430        int f1 = t1.getWeekCode().nextSetBit(0);
2431        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
2432        int f2 = t2.getWeekCode().nextSetBit(0);
2433        int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size());
2434        if (e1 < f2) {
2435            return (f2 - e1) >= 7;
2436        } else if (e2 < f1) {
2437            return (f1 - e2) >= 7;
2438        }
2439        return false;
2440    }
2441    
2442    private boolean isFollowingWeeksBTB(Placement p1, Placement p2, boolean btb) {
2443        int ord1 = variables().indexOf(p1.variable());
2444        int ord2 = variables().indexOf(p2.variable());
2445        TimeLocation t1, t2;
2446        boolean following = false;
2447        if (ord1 < ord2) {
2448            t1 = p1.getTimeLocation();
2449            t2 = p2.getTimeLocation();
2450            if (ord1 + 1 == ord2) following = true;
2451        } else {
2452            t2 = p1.getTimeLocation();
2453            t1 = p2.getTimeLocation();
2454            if (ord2 + 1 == ord1) following = true;
2455        }
2456        if (t1.shareWeeks(t2)) return false;
2457        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
2458        int s2 = t2.getWeekCode().nextSetBit(0);
2459        if (e1 >= s2) return false;
2460        if (!btb) // not back-to-back: any two classes must be at least a week apart
2461            return (s2 - e1) >= 7;
2462        else if (following) // back-to-back and following classes: must be within a week
2463            return (s2 - e1) < 7;
2464        else // back-to-back and not following: just the order
2465            return true;
2466    }
2467    
2468    private boolean isDifferentDates(TimeLocation t1, TimeLocation t2) {
2469        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return true;
2470        for (Enumeration<Integer> e = t1.getDates(iDayOfWeekOffset); e.hasMoreElements(); ) {
2471            Integer date = e.nextElement();
2472            if (t2.hasDate(date, iDayOfWeekOffset)) return false;
2473        }
2474        return true;
2475    }
2476    
2477    private boolean isSameDates(TimeLocation t1, TimeLocation t2) {
2478        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
2479        // t1 is meets less often
2480        if (t1.countDates(iDayOfWeekOffset) > t2.countDates(iDayOfWeekOffset)) {
2481            TimeLocation t = t1; t1 = t2; t2 = t;
2482        }
2483        for (Enumeration<Integer> e = t1.getDates(iDayOfWeekOffset); e.hasMoreElements(); ) {
2484            Integer date = e.nextElement();
2485            if (!t2.hasDate(date, iDayOfWeekOffset)) return false;
2486        }
2487        return true;
2488    }
2489    
2490    protected boolean isOnline(Placement p) {
2491        // no room -- StudentConflict.OnlineRoom must allow for a blank string
2492        if (p.getNrRooms() == 0)
2493            return "".matches(iOnlineRoom);
2494        // one room -- room name must match StudentConflict.OnlineRoom
2495        if (p.getNrRooms() == 1)
2496            return (p.getRoomLocation().getName() != null && p.getRoomLocation().getName().matches(iOnlineRoom));
2497        // multiple rooms -- all rooms must match StudentConflict.OnlineRoom
2498        for (RoomLocation r: p.getRoomLocations())
2499            if (r.getName() == null || !r.getName().matches(iOnlineRoom)) return false;
2500        return true;
2501    }
2502}