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