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        
970        String iReference, iName;
971        int iFlag = 0;
972        Flag[] iFlags = null;
973        int iMin = 0, iMax = 0;
974        PairCheck iCheck = null;
975        AssignmentPairCheck iAssignmentCheck = null;
976        AssignmentParameterPairCheck<?> iAssignmentPairCheck = null;
977        ConstraintType(String reference, String name, Flag... flags) {
978            iReference = reference;
979            iName = name;
980            iFlags = flags;
981            for (Flag f: flags)
982                iFlag |= f.flag();
983        }
984        ConstraintType(String reference, String name, PairCheck check, Flag... flags) {
985            this(reference, name, flags);
986            iCheck = check;
987        }
988        ConstraintType(String reference, String name, AssignmentPairCheck check, Flag... flags) {
989            this(reference, name, flags);
990            iAssignmentCheck = check;
991        }
992        ConstraintType(String reference, String name, int limit, PairCheck check, Flag... flags) {
993            this(reference, name, check, flags);
994            iMin = iMax = limit;
995        }
996        ConstraintType(String reference, String name, int min, int max, PairCheck check, Flag... flags) {
997            this(reference, name, check, flags);
998            iMin = min;
999            iMax = max;
1000        }
1001        ConstraintType(String reference, String name, AssignmentParameterPairCheck<?> check, Flag... flags) {
1002            this(reference, name, flags);
1003            iAssignmentPairCheck = check;
1004        }
1005        
1006        /**
1007         * Constraint type
1008         * @return constraint type
1009         */
1010        @Override
1011        public ConstraintType type() { return this; }
1012
1013        /** Constraint reference
1014         * @return constraint reference
1015         **/
1016        @Override
1017        public String reference() { return iReference; }
1018        
1019        /** Constraint name
1020         * @return constraint name
1021         **/
1022        @Override
1023        public String getName() { return iName; }
1024        
1025        /** Minimum (gap) parameter
1026         * @return minimum gap (first constraint parameter)
1027         **/
1028        @Override
1029        public int getMin() { return iMin; }
1030        
1031        /** Maximum (gap, hours a day) parameter 
1032         * @return maximum gap (second constraint parameter) 
1033         **/
1034        @Override
1035        public int getMax() { return iMax; }
1036        
1037        /** Flag check (true if contains given flag) 
1038         * @param f a flag to check
1039         * @return true if present
1040         **/
1041        @Override
1042        public boolean is(Flag f) { return (iFlag & f.flag()) != 0; }
1043
1044        /** Constraint type from reference 
1045         * @param reference constraint reference
1046         * @return constraint of the reference
1047         * @deprecated use {@link GroupConstraint#getConstraintType(String)} instead
1048         **/
1049        @Deprecated
1050        public static ConstraintType get(String reference) {
1051            for (ConstraintType t: ConstraintType.values())
1052                if (t.reference().equals(reference)) return t;
1053            return null;
1054        }
1055        
1056        /** True if a required or preferred constraint is satisfied between a pair of placements 
1057         * @param assignment current assignment
1058         * @param gc current constraint
1059         * @param plc1 first placement
1060         * @param plc2 second placement
1061         * @return true if the two placements are consistent with the constraint if preferred or required 
1062         **/ 
1063        @Override
1064        public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) {
1065            if (iCheck != null && !iCheck.isSatisfied(gc, plc1, plc2))
1066                return false;
1067            if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isSatisfied(assignment, gc, plc1, plc2))
1068                return false;
1069            return true;
1070        }
1071        
1072        /** True if a prohibited or discouraged constraint is satisfied between a pair of placements 
1073         * @param assignment current assignment
1074         * @param gc current constraint
1075         * @param plc1 first placement
1076         * @param plc2 second placement
1077         * @return true if the two placements are consistent with the constraint if discouraged or prohibited 
1078         **/ 
1079        @Override
1080        public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) { 
1081            if (iCheck != null && !iCheck.isViolated(gc, plc1, plc2))
1082                return false;
1083            if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isViolated(assignment, gc, plc1, plc2))
1084                return false;
1085            return true;
1086        }
1087        /** Pair check */
1088        private PairCheck check() { return iCheck; }
1089    }
1090    
1091    /** Constraint type from reference 
1092     * @param reference constraint reference
1093     * @return constraint of the reference
1094     **/
1095    public static ConstraintTypeInterface getConstraintType(String reference) {
1096        for (ConstraintType t: ConstraintType.values()) {
1097            if (t.reference().equals(reference)) return t;
1098            if (t.iAssignmentPairCheck != null && reference.matches(t.reference()))
1099                return t.iAssignmentPairCheck.create(reference, t.reference());
1100        }
1101        return null;
1102    }    
1103
1104    public GroupConstraint() {
1105    }
1106    
1107    @Override
1108    public void setModel(Model<Lecture, Placement> model) {
1109        super.setModel(model);
1110        if (model != null) {
1111            DataProperties config = ((TimetableModel)model).getProperties();
1112            iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0);
1113            iPrecedenceConsiderDatePatterns = config.getPropertyBoolean("Precedence.ConsiderDatePatterns", true);
1114            iForwardCheckMaxDepth = config.getPropertyInt("ForwardCheck.MaxDepth", iForwardCheckMaxDepth);
1115            iForwardCheckMaxDomainSize = config.getPropertyInt("ForwardCheck.MaxDomainSize", iForwardCheckMaxDomainSize);
1116            iMaxNHoursADayConsiderDatePatterns = config.getPropertyBoolean("MaxNHoursADay.ConsiderDatePatterns", iMaxNHoursADayConsiderDatePatterns);
1117            iNrWorkDays = (config.getPropertyInt("General.LastWorkDay", 4) - config.getPropertyInt("General.FirstWorkDay", 0) + 1);
1118            if (iNrWorkDays <= 0) iNrWorkDays += 7;
1119            if (iNrWorkDays > 7) iNrWorkDays -= 7;
1120            iFirstWorkDay = config.getPropertyInt("General.FirstWorkDay", 0);
1121        }
1122    }
1123
1124    @Override
1125    public void addVariable(Lecture lecture) {
1126        if (!variables().contains(lecture))
1127            super.addVariable(lecture);
1128        if (getType().is(Flag.CH_NOTOVERLAP)) {
1129            if (lecture.getChildrenSubpartIds() != null) {
1130                for (Long subpartId: lecture.getChildrenSubpartIds()) {
1131                    for (Lecture ch : lecture.getChildren(subpartId)) {
1132                        if (!variables().contains(ch))
1133                            super.addVariable(ch);
1134                    }
1135                }
1136            }
1137        }
1138    }
1139
1140    @Override
1141    public void removeVariable(Lecture lecture) {
1142        if (variables().contains(lecture))
1143            super.removeVariable(lecture);
1144        if (getType().is(Flag.CH_NOTOVERLAP)) {
1145            if (lecture.getChildrenSubpartIds() != null) {
1146                for (Long subpartId: lecture.getChildrenSubpartIds()) {
1147                    for (Lecture ch : lecture.getChildren(subpartId)) {
1148                        if (variables().contains(ch))
1149                            super.removeVariable(ch);
1150                    }
1151                }
1152            }
1153        }
1154    }
1155
1156    /**
1157     * Constructor
1158     * 
1159     * @param id
1160     *            constraint id
1161     * @param type
1162     *            constraString type (e.g, {@link ConstraintType#SAME_TIME})
1163     * @param preference
1164     *            time preference ("R" for required, "P" for prohibited, "-2",
1165     *            "-1", "1", "2" for soft preference)
1166     */
1167    public GroupConstraint(Long id, ConstraintTypeInterface type, String preference) {
1168        iConstraintId = id;
1169        iType = type;
1170        iIsRequired = preference.equals(Constants.sPreferenceRequired);
1171        iIsProhibited = preference.equals(Constants.sPreferenceProhibited);
1172        iPreference = Constants.preference2preferenceLevel(preference);
1173    }
1174
1175    /** Constraint id 
1176     * @return constraint unique id
1177     **/
1178    public Long getConstraintId() {
1179        return iConstraintId;
1180    }
1181
1182    @Override
1183    public long getId() {
1184        return (iConstraintId == null ? -1 : iConstraintId.longValue());
1185    }
1186    
1187    /** Generated unique id 
1188     * @return generated unique id
1189     **/
1190    protected long getGeneratedId() {
1191        return iId;
1192    }
1193
1194    /** Return constraint type (e.g, {@link ConstraintType#SAME_TIME}) 
1195     * @return constraint type
1196     **/
1197    public ConstraintTypeInterface getType() {
1198        return iType;
1199    }
1200
1201    /**
1202     * Set constraint type
1203     * @param type constraint type
1204     */
1205    public void setType(ConstraintType type) {
1206        iType = type;
1207    }
1208
1209    /** Is constraint required 
1210     * @return true if required
1211     **/
1212    public boolean isRequired() {
1213        return iIsRequired;
1214    }
1215
1216    /** Is constraint prohibited 
1217     * @return true if prohibited
1218     **/
1219    public boolean isProhibited() {
1220        return iIsProhibited;
1221    }
1222
1223    /**
1224     * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for
1225     * preference
1226     * @return prolog preference
1227     */
1228    public String getPrologPreference() {
1229        return Constants.preferenceLevel2preference(iPreference);
1230    }
1231
1232    @Override
1233    public boolean isConsistent(Placement value1, Placement value2) {
1234        if (!isHard())
1235            return true;
1236        if (!isSatisfiedPair(null, value1, value2))
1237            return false;
1238        if (getType().is(Flag.BACK_TO_BACK)) {
1239            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1240            assignments.put(value1.variable(), value1);
1241            assignments.put(value2.variable(), value2);
1242            if (!isSatisfiedSeq(null, assignments, null))
1243                return false;
1244        }
1245        if (getType().is(Flag.MAX_HRS_DAY)) {
1246            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1247            assignments.put(value1.variable(), value1);
1248            assignments.put(value2.variable(), value2);
1249            for (int dayCode: Constants.DAY_CODES) {
1250                if (iMaxNHoursADayConsiderDatePatterns) {
1251                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
1252                        if (!value1.getTimeLocation().shareWeeks(week) && !value2.getTimeLocation().shareWeeks(week)) continue;
1253                        if (nrSlotsADay(null, dayCode, week, assignments, null) > getType().getMax()) return false;
1254                    }
1255                } else {
1256                    if (nrSlotsADay(null, dayCode, null, assignments, null) > getType().getMax()) return false;
1257                }
1258            }
1259        }
1260        return true;
1261    }
1262
1263    @Override
1264    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
1265        computeConflicts(assignment, value, conflicts, true);
1266    }
1267    
1268    @Override
1269    public void computeConflictsNoForwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
1270        computeConflicts(assignment, value, conflicts, false);
1271    }
1272    
1273    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, boolean fwdCheck) {
1274        if (!isHard())
1275            return;
1276        for (Lecture v : variables()) {
1277            if (v.equals(value.variable()))
1278                continue; // ignore this variable
1279            Placement p = assignment.getValue(v);
1280            if (p == null)
1281                continue; // there is an unassigned variable -- great, still a chance to get violated
1282            if (!isSatisfiedPair(assignment, p, value))
1283                conflicts.add(p);
1284        }
1285        if (getType().is(Flag.BACK_TO_BACK)) {
1286            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1287            assignments.put(value.variable(), value);
1288            if (!isSatisfiedSeq(assignment, assignments, conflicts))
1289                conflicts.add(value);
1290        }
1291        if (getType().is(Flag.MAX_HRS_DAY)) {
1292            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1293            assignments.put(value.variable(), value);
1294            for (int dayCode: Constants.DAY_CODES) {
1295                if (iMaxNHoursADayConsiderDatePatterns) {
1296                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
1297                        if (!value.getTimeLocation().shareWeeks(week)) continue;
1298                        if (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax()) {
1299                            List<Placement> adepts = new ArrayList<Placement>();
1300                            for (Lecture l: variables()) {
1301                                if (l.equals(value.variable()) || l.isConstant()) continue;
1302                                Placement p = assignment.getValue(l);
1303                                if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue;
1304                                if ((p.getTimeLocation().getDayCode() & dayCode) == 0 || !p.getTimeLocation().shareWeeks(week)) continue;
1305                                adepts.add(p);
1306                            }
1307                            do {
1308                                if (adepts.isEmpty()) { conflicts.add(value); break; }
1309                                Placement conflict = ToolBox.random(adepts);
1310                                adepts.remove(conflict);
1311                                conflicts.add(conflict);
1312                            } while (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax());
1313                        }
1314                    }
1315                } else {
1316                    if (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax()) {
1317                        List<Placement> adepts = new ArrayList<Placement>();
1318                        for (Lecture l: variables()) {
1319                            if (l.equals(value.variable()) || l.isConstant()) continue;
1320                            Placement p = assignment.getValue(l);
1321                            if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue;
1322                            if ((p.getTimeLocation().getDayCode() & dayCode) == 0) continue;
1323                            adepts.add(p);
1324                        }
1325                        do {
1326                            if (adepts.isEmpty()) { conflicts.add(value); break; }
1327                            Placement conflict = ToolBox.random(adepts);
1328                            adepts.remove(conflict);
1329                            conflicts.add(conflict);
1330                        } while (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax());
1331                    }
1332                }
1333            }
1334        }
1335        
1336        // Forward checking
1337        if (fwdCheck) forwardCheck(assignment, value, conflicts, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1);
1338    }
1339    
1340    public void forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, Set<GroupConstraint> ignore, int depth) {
1341        try {
1342            if (depth < 0) return;
1343            ignore.add(this);
1344            
1345            List<Placement> neededSize = null;
1346            
1347            for (Lecture lecture: variables()) {
1348                if (conflicts.contains(value)) break; // already conflicting
1349
1350                if (lecture.equals(value.variable())) continue; // Skip this lecture
1351                Placement current = assignment.getValue(lecture);
1352                if (current != null) { // Has assignment, check whether it is conflicting
1353                    if (isSatisfiedPair(assignment, value, current)) {
1354                        // Increase needed size if the assignment is of the same room and overlapping in time
1355                        if (canShareRoom() && sameRoomAndOverlaps(value, current)) {
1356                            if (neededSize == null) neededSize = new ArrayList<Placement>(); 
1357                            neededSize.add(current);
1358                        }
1359                        continue;
1360                    }
1361                    conflicts.add(current);
1362                }
1363                
1364                // Look for supporting assignments assignment
1365                boolean shareRoomAndOverlaps = canShareRoom();
1366                Placement support = null;
1367                int nrSupports = 0;
1368                if (lecture.nrValues() >= iForwardCheckMaxDomainSize) {
1369                    // ignore variables with large domains
1370                    return;
1371                }
1372                List<Placement> values = lecture.values(assignment);
1373                if (values.isEmpty()) {
1374                    // ignore variables with empty domain
1375                    return;
1376                }
1377                for (Placement other: values) {
1378                    if (nrSupports < 2) {
1379                        if (isSatisfiedPair(assignment, value, other)) {
1380                            if (support == null) support = other;
1381                            nrSupports ++;
1382                            if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other))
1383                                shareRoomAndOverlaps = false;
1384                        }
1385                    } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) {
1386                        shareRoomAndOverlaps = false;
1387                    }
1388                    if (nrSupports > 1 && !shareRoomAndOverlaps)
1389                        break;
1390                }
1391                
1392                // No supporting assignment -> fail
1393                if (nrSupports == 0) {
1394                    conflicts.add(value); // other class cannot be assigned with this value
1395                    return;
1396                }
1397                // Increase needed size if all supporters are of the same room and in overlapping times
1398                if (shareRoomAndOverlaps && support != null) {
1399                    if (neededSize == null) neededSize = new ArrayList<Placement>(); 
1400                    neededSize.add(support);
1401                }
1402
1403                // Only one supporter -> propagate the new assignment over other hard constraints of the lecture
1404                if (nrSupports == 1) {
1405                    for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) {
1406                        if (other instanceof WeakeningConstraint) continue;
1407                        if (other instanceof GroupConstraint) {
1408                            GroupConstraint gc = (GroupConstraint)other;
1409                            if (depth > 0 && !ignore.contains(gc))
1410                                gc.forwardCheck(assignment, support, conflicts, ignore, depth - 1);
1411                        } else {
1412                            other.computeConflicts(assignment, support, conflicts);
1413                        }
1414                    }
1415                    for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) {
1416                        if (other instanceof WeakeningConstraint) continue;
1417                        other.computeConflicts(assignment, support, conflicts);
1418                    }
1419
1420                    if (conflicts.contains(support))
1421                        conflicts.add(value);
1422                }
1423            }
1424            
1425            if (canShareRoom() && neededSize != null) {
1426                if (value.getRoomLocations() != null) {
1427                    for (RoomLocation room: value.getRoomLocations())
1428                        if (room.getRoomConstraint() != null && !room.getRoomConstraint().checkRoomSize(value, neededSize)) {
1429                            // room is too small to fit all meet with classes
1430                            conflicts.add(value);
1431                        }
1432                } else if (value.getRoomLocation() != null) {
1433                    RoomLocation room = value.getRoomLocation();
1434                    if (room.getRoomConstraint() != null && !room.getRoomConstraint().checkRoomSize(value, neededSize)) {
1435                        // room is too small to fit all meet with classes
1436                        conflicts.add(value);
1437                    }
1438                }
1439            }
1440        } finally {
1441            ignore.remove(this);
1442        }
1443    }
1444
1445    @Override
1446    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
1447        if (!isHard())
1448            return false;
1449        for (Lecture v : variables()) {
1450            if (v.equals(value.variable()))
1451                continue; // ignore this variable
1452            Placement p = assignment.getValue(v);
1453            if (p == null)
1454                continue; // there is an unassigned variable -- great, still a chance to get violated
1455            if (!isSatisfiedPair(assignment, p, value))
1456                return true;
1457        }
1458        if (getType().is(Flag.BACK_TO_BACK)) {
1459            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1460            assignments.put(value.variable(), value);
1461            if (!isSatisfiedSeq(assignment, assignments, null))
1462                return true;
1463        }
1464        if (getType().is(Flag.MAX_HRS_DAY)) {
1465            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1466            assignments.put(value.variable(), value);
1467            for (int dayCode: Constants.DAY_CODES) {
1468                if (iMaxNHoursADayConsiderDatePatterns) {
1469                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
1470                        if (!value.getTimeLocation().shareWeeks(week)) continue;
1471                        if (nrSlotsADay(assignment, dayCode, week, assignments, null) > getType().getMax())
1472                            return true;
1473                    }
1474                } else {
1475                    if (nrSlotsADay(assignment, dayCode, null, assignments, null) > getType().getMax()) return true;
1476                }
1477            }
1478        }
1479        
1480        if (!forwardCheck(assignment, value, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1)) return true;
1481        
1482        return false;
1483    }
1484    
1485    public boolean forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<GroupConstraint> ignore, int depth) {
1486        try {
1487            if (depth < 0) return true;
1488            ignore.add(this);
1489            
1490            int neededSize = value.variable().maxRoomUse();
1491            
1492            for (Lecture lecture: variables()) {
1493                if (lecture.equals(value.variable())) continue; // Skip this lecture
1494                Placement current = assignment.getValue(lecture);
1495                if (current != null) { // Has assignment, check whether it is conflicting
1496                    if (isSatisfiedPair(assignment, value, current)) {
1497                        // Increase needed size if the assignment is of the same room and overlapping in time
1498                        if (canShareRoom() && sameRoomAndOverlaps(value, current)) {
1499                            neededSize += lecture.maxRoomUse();
1500                        }
1501                        continue;
1502                    }
1503                    return false;
1504                }
1505                
1506                // Look for supporting assignments assignment
1507                boolean shareRoomAndOverlaps = canShareRoom();
1508                Placement support = null;
1509                int nrSupports = 0;
1510                if (lecture.nrValues() >= iForwardCheckMaxDomainSize) {
1511                    // ignore variables with large domains
1512                    return true;
1513                }
1514                List<Placement> values = lecture.values(assignment);
1515                if (values.isEmpty()) {
1516                    // ignore variables with empty domain
1517                    return true;
1518                }
1519                for (Placement other: lecture.values(assignment)) {
1520                    if (nrSupports < 2) {
1521                        if (isSatisfiedPair(assignment, value, other)) {
1522                            if (support == null) support = other;
1523                            nrSupports ++;
1524                            if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other))
1525                                shareRoomAndOverlaps = false;
1526                        }
1527                    } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) {
1528                        shareRoomAndOverlaps = false;
1529                    }
1530                    if (nrSupports > 1 && !shareRoomAndOverlaps)
1531                        break;
1532                }
1533
1534                // No supporting assignment -> fail
1535                if (nrSupports == 0) {
1536                    return false; // other class cannot be assigned with this value
1537                }
1538                // Increase needed size if all supporters are of the same room and in overlapping times
1539                if (shareRoomAndOverlaps) {
1540                    neededSize += lecture.maxRoomUse();
1541                }
1542
1543                // Only one supporter -> propagate the new assignment over other hard constraints of the lecture
1544                if (nrSupports == 1) {
1545                    for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) {
1546                        if (other instanceof WeakeningConstraint) continue;
1547                        if (other instanceof GroupConstraint) {
1548                            GroupConstraint gc = (GroupConstraint)other;
1549                            if (depth > 0 && !ignore.contains(gc) && !gc.forwardCheck(assignment, support, ignore, depth - 1)) return false;
1550                        } else {
1551                            if (other.inConflict(assignment, support)) return false;
1552                        }
1553                    }
1554                    for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) {
1555                        if (other instanceof WeakeningConstraint) continue;
1556                        if (other.inConflict(assignment, support)) return false;
1557                    }
1558                }
1559            }
1560            
1561            if (canShareRoom() && neededSize > value.getRoomSize()) {
1562                // room is too small to fit all meet with classes
1563                return false;
1564            }
1565         
1566            return true;
1567        } finally {
1568            ignore.remove(this);
1569        }
1570    }
1571
1572    /** Constraint preference (0 if prohibited or required) 
1573     * @return constraint preference (if soft)
1574     **/
1575    public int getPreference() {
1576        return iPreference;
1577    }
1578
1579    /**
1580     * Current constraint preference (0 if prohibited or required, depends on
1581     * current satisfaction of the constraint)
1582     * @param assignment current assignment
1583     * @return current preference
1584     */
1585    public int getCurrentPreference(Assignment<Lecture, Placement> assignment) {
1586        if (isHard()) return 0; // no preference
1587        if (countAssignedVariables(assignment) < 2) return - Math.abs(iPreference); // not enough variable
1588        if (getType().is(Flag.MAX_HRS_DAY)) { // max hours a day
1589            int over = 0;
1590            for (int dayCode: Constants.DAY_CODES) {
1591                if (iMaxNHoursADayConsiderDatePatterns) {
1592                    for (BitSet week: ((TimetableModel)getModel()).getWeeks())
1593                        over += Math.max(0, nrSlotsADay(assignment, dayCode, week, null, null) - getType().getMax());
1594                } else {
1595                    over += Math.max(0, nrSlotsADay(assignment, dayCode, null, null, null) - getType().getMax());
1596                }
1597            }
1598            return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference));
1599        }
1600        int nrViolatedPairs = 0;
1601        for (Lecture v1 : variables()) {
1602            Placement p1 = assignment.getValue(v1);
1603            if (p1 == null) continue;
1604            for (Lecture v2 : variables()) {
1605                Placement p2 = assignment.getValue(v2);
1606                if (p2 == null || v1.getId() >= v2.getId()) continue;
1607                if (!isSatisfiedPair(assignment, p1, p2)) nrViolatedPairs++;
1608            }
1609        }
1610        if (getType().is(Flag.BACK_TO_BACK)) {
1611            Set<Placement> conflicts = new HashSet<Placement>();
1612            if (isSatisfiedSeq(assignment, new HashMap<Lecture, Placement>(), conflicts))
1613                nrViolatedPairs += conflicts.size();
1614            else
1615                nrViolatedPairs = variables().size();
1616        }
1617        return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference));
1618    }
1619
1620    /** Current constraint preference change (if given placement is assigned) 
1621     * @param assignment current assignment
1622     * @param placement placement that is being considered
1623     * @return change in the current preference, if assigned 
1624     **/
1625    public int getCurrentPreference(Assignment<Lecture, Placement> assignment, Placement placement) {
1626        if (isHard()) return 0; // no preference
1627        if (countAssignedVariables(assignment) + (assignment.getValue(placement.variable()) == null ? 1 : 0) < 2) return 0; // not enough variable
1628        if (getType().is(Flag.MAX_HRS_DAY)) {
1629            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1630            assignments.put(placement.variable(), placement);
1631            HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>();
1632            unassignments.put(placement.variable(), null);
1633            int after = 0;
1634            int before = 0;
1635            for (int dayCode: Constants.DAY_CODES) {
1636                if (iMaxNHoursADayConsiderDatePatterns) {
1637                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
1638                        after += Math.max(0, nrSlotsADay(assignment, dayCode, week, assignments, null) - getType().getMax());
1639                        before += Math.max(0, nrSlotsADay(assignment, dayCode, week, unassignments, null) - getType().getMax());
1640                    }
1641                } else {
1642                    after += Math.max(0, nrSlotsADay(assignment, dayCode, null, assignments, null) - getType().getMax());
1643                    before += Math.max(0, nrSlotsADay(assignment, dayCode, null, unassignments, null) - getType().getMax());
1644                }
1645            }
1646            return (after > 0 ? Math.abs(iPreference) * after / 12 : - Math.abs(iPreference)) - (before > 0 ? Math.abs(iPreference) * before / 12 : - Math.abs(iPreference));
1647        }
1648        
1649        int nrViolatedPairsAfter = 0;
1650        int nrViolatedPairsBefore = 0;
1651        for (Lecture v1 : variables()) {
1652            for (Lecture v2 : variables()) {
1653                if (v1.getId() >= v2.getId()) continue;
1654                Placement p1 = (v1.equals(placement.variable()) ? null : assignment.getValue(v1));
1655                Placement p2 = (v2.equals(placement.variable()) ? null : assignment.getValue(v2));
1656                if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2))
1657                    nrViolatedPairsBefore ++;
1658                if (v1.equals(placement.variable())) p1 = placement;
1659                if (v2.equals(placement.variable())) p2 = placement;
1660                if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2))
1661                    nrViolatedPairsAfter ++;
1662            }
1663        }
1664        
1665        if (getType().is(Flag.BACK_TO_BACK)) {
1666            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
1667            assignments.put(placement.variable(), placement);
1668            Set<Placement> conflicts = new HashSet<Placement>();
1669            if (isSatisfiedSeq(assignment, assignments, conflicts))
1670                nrViolatedPairsAfter += conflicts.size();
1671            else
1672                nrViolatedPairsAfter = variables().size();
1673            
1674            HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>();
1675            unassignments.put(placement.variable(), null);
1676            Set<Placement> previous = new HashSet<Placement>();
1677            if (isSatisfiedSeq(assignment, unassignments, previous))
1678                nrViolatedPairsBefore += previous.size();
1679            else
1680                nrViolatedPairsBefore = variables().size();
1681        }
1682        
1683        return (nrViolatedPairsAfter > 0 ? Math.abs(iPreference) * nrViolatedPairsAfter : - Math.abs(iPreference)) -
1684                (nrViolatedPairsBefore > 0 ? Math.abs(iPreference) * nrViolatedPairsBefore : - Math.abs(iPreference));
1685    }
1686
1687    @Override
1688    public String toString() {
1689        StringBuffer sb = new StringBuffer();
1690        sb.append(getName());
1691        sb.append(" between ");
1692        for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) {
1693            Lecture v = e.next();
1694            sb.append(v.getName());
1695            if (e.hasNext())
1696                sb.append(", ");
1697        }
1698        return sb.toString();
1699    }
1700
1701    @Override
1702    public boolean isHard() {
1703        return iIsRequired || iIsProhibited;
1704    }
1705
1706    @Override
1707    public String getName() {
1708        return getType().getName();
1709    }
1710
1711
1712    private boolean isPrecedence(Placement p1, Placement p2, boolean firstGoesFirst, boolean considerDatePatterns) {
1713        int ord1 = variables().indexOf(p1.variable());
1714        int ord2 = variables().indexOf(p2.variable());
1715        TimeLocation t1 = null, t2 = null;
1716        if (ord1 < ord2) {
1717            if (firstGoesFirst) {
1718                t1 = p1.getTimeLocation();
1719                t2 = p2.getTimeLocation();
1720            } else {
1721                t2 = p1.getTimeLocation();
1722                t1 = p2.getTimeLocation();
1723            }
1724        } else {
1725            if (!firstGoesFirst) {
1726                t1 = p1.getTimeLocation();
1727                t2 = p2.getTimeLocation();
1728            } else {
1729                t2 = p1.getTimeLocation();
1730                t1 = p2.getTimeLocation();
1731            }
1732        }
1733        if (considerDatePatterns && iPrecedenceConsiderDatePatterns) {
1734            boolean sameDatePattern = (t1.getDatePatternId() != null ? t1.getDatePatternId().equals(t2.getDatePatternId()) : t1.getWeekCode().equals(t2.getWeekCode()));
1735            if (!sameDatePattern) {
1736                int m1 = t1.getFirstMeeting(iDayOfWeekOffset), m2 = t2.getFirstMeeting(iDayOfWeekOffset);
1737                if (m1 != m2) return m1 < m2;
1738            }
1739        }
1740        if (iFirstWorkDay != 0) {
1741            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
1742                int idx = (i + iFirstWorkDay) % 7;
1743                boolean a = (t1.getDayCode() & Constants.DAY_CODES[idx]) != 0;
1744                boolean b = (t2.getDayCode() & Constants.DAY_CODES[idx]) != 0;
1745                if (b && !a) return false; // second start first
1746                if (a && !b) return true;  // first start first
1747                if (a && b) return t1.getStartSlot() + t1.getLength() <= t2.getStartSlot(); // same day: check times
1748            }
1749        }
1750        return t1.getStartSlots().nextElement() + t1.getLength() <= t2.getStartSlots().nextElement();
1751    }
1752
1753    private boolean isBackToBackDays(TimeLocation t1, TimeLocation t2) {
1754        int f1 = -1, f2 = -1, e1 = -1, e2 = -1;
1755        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
1756            int idx = (i + iFirstWorkDay) % 7;
1757            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1758                if (f1 < 0)
1759                    f1 = i;
1760                e1 = i;
1761            }
1762            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1763                if (f2 < 0)
1764                    f2 = i;
1765                e2 = i;
1766            }
1767        }
1768        return (e1 + 1 == f2) || (e2 + 1 == f1);
1769    }
1770    
1771    private boolean isNrDaysBetweenGreaterThanOne(TimeLocation t1, TimeLocation t2) {
1772        int f1 = -1, f2 = -1, e1 = -1, e2 = -1;
1773        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
1774            int idx = (i + iFirstWorkDay) % 7;
1775            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1776                if (f1 < 0)
1777                    f1 = i;
1778                e1 = i;
1779            }
1780            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1781                if (f2 < 0)
1782                    f2 = i;
1783                e2 = i;
1784            }
1785        }
1786        return (e1 - f2 > 2) || (e2 - f1 > 2);
1787    }
1788
1789    private boolean isFollowingDay(Placement p1, Placement p2, boolean firstGoesFirst) {
1790        int ord1 = variables().indexOf(p1.variable());
1791        int ord2 = variables().indexOf(p2.variable());
1792        TimeLocation t1 = null, t2 = null;
1793        if (ord1 < ord2) {
1794            if (firstGoesFirst) {
1795                t1 = p1.getTimeLocation();
1796                t2 = p2.getTimeLocation();
1797            } else {
1798                t2 = p1.getTimeLocation();
1799                t1 = p2.getTimeLocation();
1800            }
1801        } else {
1802            if (!firstGoesFirst) {
1803                t1 = p1.getTimeLocation();
1804                t2 = p2.getTimeLocation();
1805            } else {
1806                t2 = p1.getTimeLocation();
1807                t1 = p2.getTimeLocation();
1808            }
1809        }
1810        int f1 = -1, f2 = -1, e1 = -1;
1811        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
1812            int idx = (i + iFirstWorkDay) % 7;
1813            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1814                if (f1 < 0)
1815                    f1 = i;
1816                e1 = i;
1817            }
1818            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1819                if (f2 < 0)
1820                    f2 = i;
1821            }
1822        }
1823        return ((e1 + 1) % iNrWorkDays == f2);
1824    }
1825
1826    private boolean isEveryOtherDay(Placement p1, Placement p2, boolean firstGoesFirst) {
1827        int ord1 = variables().indexOf(p1.variable());
1828        int ord2 = variables().indexOf(p2.variable());
1829        TimeLocation t1 = null, t2 = null;
1830        if (ord1 < ord2) {
1831            if (firstGoesFirst) {
1832                t1 = p1.getTimeLocation();
1833                t2 = p2.getTimeLocation();
1834            } else {
1835                t2 = p1.getTimeLocation();
1836                t1 = p2.getTimeLocation();
1837            }
1838        } else {
1839            if (!firstGoesFirst) {
1840                t1 = p1.getTimeLocation();
1841                t2 = p2.getTimeLocation();
1842            } else {
1843                t2 = p1.getTimeLocation();
1844                t1 = p2.getTimeLocation();
1845            }
1846        }
1847        int f1 = -1, f2 = -1, e1 = -1;
1848        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
1849            int idx = (i + iFirstWorkDay) % 7;
1850            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1851                if (f1 < 0)
1852                    f1 = i;
1853                e1 = i;
1854            }
1855            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
1856                if (f2 < 0)
1857                    f2 = i;
1858            }
1859        }
1860        return ((e1 + 2) % iNrWorkDays == f2);
1861    }
1862
1863    private static boolean sameDays(int[] days1, int[] days2) {
1864        if (days2.length < days1.length)
1865            return sameDays(days2, days1);
1866        int i2 = 0;
1867        for (int i1 = 0; i1 < days1.length; i1++) {
1868            int d1 = days1[i1];
1869            while (true) {
1870                if (i2 == days2.length)
1871                    return false;
1872                int d2 = days2[i2];
1873                if (d1 == d2)
1874                    break;
1875                i2++;
1876                if (i2 == days2.length)
1877                    return false;
1878            }
1879            i2++;
1880        }
1881        return true;
1882    }
1883    
1884    private static boolean sameRoomAndOverlaps(Placement p1, Placement p2) {
1885        return p1.shareRooms(p2) && p1.getTimeLocation() != null && p2.getTimeLocation() != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation());
1886    }
1887
1888    private static boolean sameHours(int start1, int len1, int start2, int len2) {
1889        if (len1 > len2)
1890            return sameHours(start2, len2, start1, len1);
1891        start1 %= Constants.SLOTS_PER_DAY;
1892        start2 %= Constants.SLOTS_PER_DAY;
1893        return (start1 >= start2 && start1 + len1 <= start2 + len2);
1894    }
1895    
1896    private static boolean canFill(int totalGap, int gapMin, int gapMax, List<Integer> lengths) {
1897        if (gapMin <= totalGap && totalGap <= gapMax)
1898            return true;
1899        if (totalGap < 2 * gapMin)
1900            return false;
1901        for (int i = 0; i < lengths.size(); i++) {
1902            int length = lengths.get(i);
1903            lengths.remove(i);
1904            for (int gap = gapMin; gap <= gapMax; gap++)
1905                if (canFill(totalGap - gap - length, gapMin, gapMax, lengths))
1906                    return true;
1907            lengths.add(i, length);
1908        }
1909        return false;
1910    }
1911
1912    private boolean isSatisfiedSeq(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
1913        if (conflicts == null)
1914            return isSatisfiedSeqCheck(assignment, assignments, conflicts);
1915        else {
1916            Set<Placement> bestConflicts = isSatisfiedRecursive(assignment, 0, assignments, conflicts,
1917                    new HashSet<Placement>(), null);
1918            if (bestConflicts == null)
1919                return false;
1920            conflicts.addAll(bestConflicts);
1921            return true;
1922        }
1923    }
1924
1925    private Set<Placement> isSatisfiedRecursive(Assignment<Lecture, Placement> assignment, int idx, HashMap<Lecture, Placement> assignments,
1926            Set<Placement> conflicts, Set<Placement> newConflicts, Set<Placement> bestConflicts) {
1927        if (idx == variables().size() && newConflicts.isEmpty())
1928            return bestConflicts;
1929        if (isSatisfiedSeqCheck(assignment, assignments, conflicts)) {
1930            if (bestConflicts == null) {
1931                return new HashSet<Placement>(newConflicts);
1932            } else {
1933                int b = 0, n = 0;
1934                for (Placement value: assignments.values()) {
1935                    if (value != null && bestConflicts.contains(value)) b++;
1936                    if (value != null && newConflicts.contains(value)) n++;
1937                }
1938                if (n < b || (n == b && newConflicts.size() < bestConflicts.size()))
1939                    return new HashSet<Placement>(newConflicts);
1940            }
1941            return bestConflicts;
1942        }
1943        if (idx == variables().size())
1944            return bestConflicts;
1945        bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts,
1946                bestConflicts);
1947        Lecture lecture = variables().get(idx);
1948        //if (assignments != null && assignments.containsKey(lecture))
1949        //    return bestConflicts;
1950        Placement placement = null;
1951        if (assignments != null && assignments.containsKey(lecture))
1952            placement = assignments.get(lecture);
1953        else if (assignment != null)
1954            placement = assignment.getValue(lecture);
1955        if (placement == null)
1956            return bestConflicts;
1957        if (conflicts != null && conflicts.contains(placement))
1958            return bestConflicts;
1959        conflicts.add(placement);
1960        newConflicts.add(placement);
1961        bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts, bestConflicts);
1962        newConflicts.remove(placement);
1963        conflicts.remove(placement);
1964        return bestConflicts;
1965    }
1966
1967    private boolean isSatisfiedSeqCheck(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
1968        if (!getType().is(Flag.BACK_TO_BACK)) return true;
1969        int gapMin = getType().getMin();
1970        int gapMax = getType().getMax();
1971
1972        List<Integer> lengths = new ArrayList<Integer>();
1973
1974        Placement[] res = new Placement[Constants.SLOTS_PER_DAY];
1975        for (int i = 0; i < Constants.SLOTS_PER_DAY; i++)
1976            res[i] = null;
1977
1978        int nrLectures = 0;
1979
1980        for (Lecture lecture : variables()) {
1981            Placement placement = null;
1982            if (assignments != null && assignments.containsKey(lecture))
1983                placement = assignments.get(lecture);
1984            else if (assignment != null)
1985                placement = assignment.getValue(lecture);
1986            if (placement == null) {
1987                if (!lecture.timeLocations().isEmpty())
1988                        lengths.add(lecture.timeLocations().get(0).getLength());
1989            } else if (conflicts != null && conflicts.contains(placement)) {
1990                if (!lecture.timeLocations().isEmpty())
1991                        lengths.add(lecture.timeLocations().get(0).getLength());
1992            } else {
1993                int pos = placement.getTimeLocation().getStartSlot();
1994                int length = placement.getTimeLocation().getLength();
1995                for (int j = pos; j < pos + length; j++) {
1996                    if (res[j] != null) {
1997                        if (conflicts == null)
1998                            return false;
1999                        if (!assignments.containsKey(lecture))
2000                            conflicts.add(placement);
2001                        else if (!assignments.containsKey(res[j].variable()))
2002                            conflicts.add(res[j]);
2003                    }
2004                }
2005                for (int j = pos; j < pos + length; j++)
2006                    res[j] = placement;
2007                nrLectures++;
2008            }
2009        }
2010        if (nrLectures <= 1)
2011            return true;
2012
2013        if (iIsRequired || (!iIsProhibited && iPreference < 0)) {
2014            int i = 0;
2015            Placement p = res[i];
2016            while (p == null)
2017                p = res[++i];
2018            i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
2019            nrLectures--;
2020            while (nrLectures > 0) {
2021                int gap = 0;
2022                while (i < Constants.SLOTS_PER_DAY && res[i] == null) {
2023                    gap++;
2024                    i++;
2025                }
2026                if (i == Constants.SLOTS_PER_DAY)
2027                    break;
2028                if (!canFill(gap, gapMin, gapMax, lengths))
2029                    return false;
2030                p = res[i];
2031                i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
2032                nrLectures--;
2033            }
2034        } else if (iIsProhibited || (!iIsRequired && iPreference > 0)) {
2035            int i = 0;
2036            Placement p = res[i];
2037            while (p == null)
2038                p = res[++i];
2039            i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
2040            nrLectures--;
2041            while (nrLectures > 0) {
2042                int gap = 0;
2043                while (i < Constants.SLOTS_PER_DAY && res[i] == null) {
2044                    gap++;
2045                    i++;
2046                }
2047                if (i == Constants.SLOTS_PER_DAY)
2048                    break;
2049                if ((gapMin == 0 || !canFill(gap, 0, gapMin - 1, lengths))
2050                        && (gapMax >= Constants.SLOTS_PER_DAY || !canFill(gap, gapMax + 1, Constants.SLOTS_PER_DAY,
2051                                lengths))) {
2052                    return false;
2053                }
2054                p = res[i];
2055                i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
2056                nrLectures--;
2057            }
2058        }
2059        return true;
2060    }
2061
2062    public boolean isSatisfied(Assignment<Lecture, Placement> assignment) {
2063        if (isHard()) return true;
2064        if (countAssignedVariables(assignment) < 2) return true;
2065        if (getPreference() == 0) return true;
2066        return isHard() || countAssignedVariables(assignment) < 2 || getPreference() == 0 || getCurrentPreference(assignment) < 0;
2067    }
2068
2069    public boolean isChildrenNotOverlap(Assignment<Lecture, Placement> assignment, Lecture lec1, Placement plc1, Lecture lec2, Placement plc2) {
2070        if (lec1.getSchedulingSubpartId().equals(lec2.getSchedulingSubpartId())) {
2071            // same subpart
2072            boolean overlap = plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation());
2073
2074            if (overlap && lec1.getParent() != null && variables().contains(lec1.getParent())
2075                    && lec2.getParent() != null && variables().contains(lec2.getParent())) {
2076                // children overlaps
2077                Placement p1 = assignment.getValue(lec1.getParent());
2078                Placement p2 = assignment.getValue(lec2.getParent());
2079                // parents not overlap, but children do
2080                if (p1 != null && p2 != null && !p1.getTimeLocation().hasIntersection(p2.getTimeLocation()))
2081                    return false;
2082            }
2083
2084            if (!overlap && lec1.getChildrenSubpartIds() != null && lec2.getChildrenSubpartIds() != null) {
2085                // parents not overlap
2086                for (Long subpartId: lec1.getChildrenSubpartIds()) {
2087                    for (Lecture c1 : lec1.getChildren(subpartId)) {
2088                        Placement p1 = assignment.getValue(c1);
2089                        if (p1 == null) continue;
2090                        for (Lecture c2 : lec2.getChildren(subpartId)) {
2091                            Placement p2 = assignment.getValue(c2);
2092                            if (p2 == null) continue;
2093                            if (!c1.getSchedulingSubpartId().equals(c2.getSchedulingSubpartId())) continue;
2094                            // parents not overlap, but children do
2095                            if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation()))
2096                                return false;
2097                        }
2098                    }
2099                }
2100            }
2101        } else {
2102            // different subpart
2103        }
2104        return true;
2105    }
2106
2107    public boolean isSatisfiedPair(Assignment<Lecture, Placement> assignment, Placement plc1, Placement plc2) {
2108        if (iIsRequired || (!iIsProhibited && iPreference <= 0))
2109            return getType().isSatisfied(assignment, this, plc1, plc2);
2110        else if (iIsProhibited || (!iIsRequired && iPreference > 0))
2111            return getType().isViolated(assignment, this, plc1, plc2);
2112        return true;
2113    }
2114    
2115    public boolean canShareRoom() {
2116        return getType().is(Flag.CAN_SHARE_ROOM);
2117    }
2118    
2119    protected int nrSlotsADay(Assignment<Lecture, Placement> assignment, int dayCode, BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
2120        Set<Integer> slots = new HashSet<Integer>();
2121        for (Lecture lecture: variables()) {
2122            Placement placement = null;
2123            if (assignments != null && assignments.containsKey(lecture))
2124                placement = assignments.get(lecture);
2125            else if (assignment != null)
2126                placement = assignment.getValue(lecture);
2127            if (placement == null || placement.getTimeLocation() == null) continue;
2128            if (conflicts != null && conflicts.contains(placement)) continue;
2129            TimeLocation t = placement.getTimeLocation();
2130            if (t == null || (t.getDayCode() & dayCode) == 0 || (week != null && !t.shareWeeks(week))) continue;
2131            for (int i = 0; i < t.getLength(); i++)
2132                slots.add(i + t.getStartSlot());
2133        }
2134        return slots.size();
2135    }
2136
2137    @Override
2138    public boolean equals(Object o) {
2139        if (o == null || !(o instanceof GroupConstraint)) return false;
2140        return getGeneratedId() == ((GroupConstraint) o).getGeneratedId();
2141    }
2142    
2143    @Override
2144    public GroupConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
2145        return new GroupConstraintContext(assignment);
2146    }
2147
2148    public class GroupConstraintContext implements AssignmentConstraintContext<Lecture, Placement> {
2149        protected int iLastPreference = 0;
2150        
2151        public GroupConstraintContext(Assignment<Lecture, Placement> assignment) {
2152            updateCriterion(assignment);
2153        }
2154
2155        @Override
2156        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
2157            updateCriterion(assignment);
2158        }
2159
2160        @Override
2161        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
2162            updateCriterion(assignment);
2163        }
2164        
2165        protected void updateCriterion(Assignment<Lecture, Placement> assignment) {
2166            if (!isHard()) {
2167                getModel().getCriterion(DistributionPreferences.class).inc(assignment, -iLastPreference);
2168                iLastPreference = getCurrentPreference(assignment) + Math.abs(iPreference);
2169                getModel().getCriterion(DistributionPreferences.class).inc(assignment, iLastPreference);
2170            }
2171        }
2172        
2173        public int getPreference() { return iLastPreference; }
2174    }
2175    
2176    private boolean isBackToBackWeeks(TimeLocation t1, TimeLocation t2) {
2177        if (t1.shareWeeks(t2)) return false;
2178        int f1 = t1.getWeekCode().nextSetBit(0);
2179        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
2180        int f2 = t2.getWeekCode().nextSetBit(0);
2181        int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size());
2182        if (e1 < f2) {
2183            return (f2 - e1) < 7;
2184        } else if (e2 < f1) {
2185            return (f1 - e2) < 7;
2186        }
2187        return false;
2188    }
2189    
2190    private boolean isMaxWeekSpan(TimeLocation t1, TimeLocation t2, int nrWeeks) {
2191        if (t1.shareWeeks(t2)) return false;
2192        if (isBackToBackWeeks(t1, t2)) return true;
2193        
2194        int f1 = t1.getWeekCode().nextSetBit(0);
2195        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
2196        int f2 = t2.getWeekCode().nextSetBit(0);
2197        int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size());
2198        if (e1 < f2) {
2199            return (3 + e2 - f1) / 7 <= nrWeeks;
2200        } else if (e2 < f1) {
2201            return (3 + e1 - f2) / 7 <= nrWeeks;
2202        }
2203        return false;
2204    }
2205    
2206    private boolean isNotBackToBackWeeks(TimeLocation t1, TimeLocation t2) {
2207        if (t1.shareWeeks(t2)) return false;
2208        int f1 = t1.getWeekCode().nextSetBit(0);
2209        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
2210        int f2 = t2.getWeekCode().nextSetBit(0);
2211        int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size());
2212        if (e1 < f2) {
2213            return (f2 - e1) >= 7;
2214        } else if (e2 < f1) {
2215            return (f1 - e2) >= 7;
2216        }
2217        return false;
2218    }
2219    
2220    private boolean isFollowingWeeksBTB(Placement p1, Placement p2, boolean btb) {
2221        int ord1 = variables().indexOf(p1.variable());
2222        int ord2 = variables().indexOf(p2.variable());
2223        TimeLocation t1, t2;
2224        boolean following = false;
2225        if (ord1 < ord2) {
2226            t1 = p1.getTimeLocation();
2227            t2 = p2.getTimeLocation();
2228            if (ord1 + 1 == ord2) following = true;
2229        } else {
2230            t2 = p1.getTimeLocation();
2231            t1 = p2.getTimeLocation();
2232            if (ord2 + 1 == ord1) following = true;
2233        }
2234        if (t1.shareWeeks(t2)) return false;
2235        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
2236        int s2 = t2.getWeekCode().nextSetBit(0);
2237        if (e1 >= s2) return false;
2238        if (!btb) // not back-to-back: any two classes must be at least a week apart
2239            return (s2 - e1) >= 7;
2240        else if (following) // back-to-back and following classes: must be within a week
2241            return (s2 - e1) < 7;
2242        else // back-to-back and not following: just the order
2243            return true;
2244    }
2245    
2246    private boolean isDifferentDates(TimeLocation t1, TimeLocation t2) {
2247        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return true;
2248        for (Enumeration<Integer> e = t1.getDates(iDayOfWeekOffset); e.hasMoreElements(); ) {
2249            Integer date = e.nextElement();
2250            if (t2.hasDate(date, iDayOfWeekOffset)) return false;
2251        }
2252        return true;
2253    }
2254    
2255    private boolean isSameDates(TimeLocation t1, TimeLocation t2) {
2256        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
2257        // t1 is meets less often
2258        if (t1.countDates(iDayOfWeekOffset) > t2.countDates(iDayOfWeekOffset)) {
2259            TimeLocation t = t1; t1 = t2; t2 = t;
2260        }
2261        for (Enumeration<Integer> e = t1.getDates(iDayOfWeekOffset); e.hasMoreElements(); ) {
2262            Integer date = e.nextElement();
2263            if (!t2.hasDate(date, iDayOfWeekOffset)) return false;
2264        }
2265        return true;
2266    }
2267}