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