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