    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
    1209        String iReference, iName;
    1210        int iFlag = 0;
    1211        Flag[] iFlags = null;
    1212        int iMin = 0, iMax = 0;
    1213        PairCheck iCheck = null;
    1214        AssignmentPairCheck iAssignmentCheck = null;
    1215        AssignmentParameterPairCheck<?> iAssignmentPairCheck = null;
    1216        ConstraintType(String reference, String name, Flag... flags) {
    1217            iReference = reference;
    1218            iName = name;
    1219            iFlags = flags;
    1220            for (Flag f: flags)
    1221                iFlag |= f.flag();
    1222        }
    1223        ConstraintType(String reference, String name, PairCheck check, Flag... flags) {
    1224            this(reference, name, flags);
    1225            iCheck = check;
    1226        }
    1227        ConstraintType(String reference, String name, AssignmentPairCheck check, Flag... flags) {
    1228            this(reference, name, flags);
    1229            iAssignmentCheck = check;
    1230        }
    1231        ConstraintType(String reference, String name, int limit, PairCheck check, Flag... flags) {
    1232            this(reference, name, check, flags);
    1233            iMin = iMax = limit;
    1234        }
    1235        ConstraintType(String reference, String name, int min, int max, PairCheck check, Flag... flags) {
    1236            this(reference, name, check, flags);
    1237            iMin = min;
    1238            iMax = max;
    1239        }
    1240        ConstraintType(String reference, String name, AssignmentParameterPairCheck<?> check, Flag... flags) {
    1241            this(reference, name, flags);
    1242            iAssignmentPairCheck = check;
    1243        }
    1244
    1245        /**
    1246         * Constraint type
    1247         * @return constraint type
    1248         */
    1249        @Override
    1250        public ConstraintType type() { return this; }
    1251
    1252        /** Constraint reference
    1253         * @return constraint reference
    1254         **/
    1255        @Override
    1256        public String reference() { return iReference; }
    1257
    1258        /** Constraint name
    1259         * @return constraint name
    1260         **/
    1261        @Override
    1262        public String getName() { return iName; }
    1263
    1264        /** Minimum (gap) parameter
    1265         * @return minimum gap (first constraint parameter)
    1266         **/
    1267        @Override
    1268        public int getMin() { return iMin; }
    1269
    1270        /** Maximum (gap, hours a day) parameter
    1271         * @return maximum gap (second constraint parameter)
    1272         **/
    1273        @Override
    1274        public int getMax() { return iMax; }
    1275
    1276        /** Flag check (true if contains given flag)
    1277         * @param f a flag to check
    1278         * @return true if present
    1279         **/
    1280        @Override
    1281        public boolean is(Flag f) { return (iFlag & f.flag()) != 0; }
    1282
    1283        /** Constraint type from reference
    1284         * @param reference constraint reference
    1285         * @return constraint of the reference
    1286         * @deprecated use {@link GroupConstraint#getConstraintType(String)} instead
    1287         **/
    1288        @Deprecated
    1289        public static ConstraintType get(String reference) {
    1290            for (ConstraintType t: ConstraintType.values())
    1291                if (t.reference().equals(reference)) return t;
    1292            return null;
    1293        }
    1294
    1295        /** True if a required or preferred constraint is satisfied between a pair of placements
    1296         * @param assignment current assignment
    1297         * @param gc current constraint
    1298         * @param plc1 first placement
    1299         * @param plc2 second placement
    1300         * @return true if the two placements are consistent with the constraint if preferred or required
    1301         **/
    1302        @Override
    1303        public boolean isSatisfied(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) {
    1304            if (iCheck != null && !iCheck.isSatisfied(gc, plc1, plc2))
    1305                return false;
    1306            if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isSatisfied(assignment, gc, plc1, plc2))
    1307                return false;
    1308            return true;
    1309        }
    1310
    1311        /** True if a prohibited or discouraged constraint is satisfied between a pair of placements
    1312         * @param assignment current assignment
    1313         * @param gc current constraint
    1314         * @param plc1 first placement
    1315         * @param plc2 second placement
    1316         * @return true if the two placements are consistent with the constraint if discouraged or prohibited
    1317         **/
    1318        @Override
    1319        public boolean isViolated(Assignment<Lecture, Placement> assignment, GroupConstraint gc, Placement plc1, Placement plc2) {
    1320            if (iCheck != null && !iCheck.isViolated(gc, plc1, plc2))
    1321                return false;
    1322            if (iAssignmentCheck != null && assignment != null && !iAssignmentCheck.isViolated(assignment, gc, plc1, plc2))
    1323                return false;
    1324            return true;
    1325        }
    1326        /** Pair check */
    1327        private PairCheck check() { return iCheck; }
    1328    }
    1329
    1330    /** Constraint type from reference
    1331     * @param reference constraint reference
    1332     * @return constraint of the reference
    1333     **/
    1334    public static ConstraintTypeInterface getConstraintType(String reference) {
    1335        for (ConstraintType t: ConstraintType.values()) {
    1336            if (t.reference().equals(reference)) return t;
    1337            if (t.iAssignmentPairCheck != null && reference.matches(t.reference()))
    1338                return t.iAssignmentPairCheck.create(reference, t.reference());
    1339        }
    1340        return null;
    1341    }
    1342
    1343    public GroupConstraint() {
    1344    }
    1345
    1346    @Override
    1347    public void setModel(Model<Lecture, Placement> model) {
    1348        super.setModel(model);
    1349        if (model != null) {
    1350            DataProperties config = ((TimetableModel)model).getProperties();
    1351            iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0);
    1352            iPrecedenceConsiderDatePatterns = config.getPropertyBoolean("Precedence.ConsiderDatePatterns", true);
    1353            iPrecedenceSkipSameDatePatternCheck = config.getPropertyBoolean("Precedence.SkipSameDatePatternCheck", true);
    1354            iForwardCheckMaxDepth = config.getPropertyInt("ForwardCheck.MaxDepth", iForwardCheckMaxDepth);
    1355            iForwardCheckMaxDomainSize = config.getPropertyInt("ForwardCheck.MaxDomainSize", iForwardCheckMaxDomainSize);
    1356            iMaxNHoursADayPrecideComputation = config.getPropertyBoolean("MaxNHoursADay.PreciseComputation", iMaxNHoursADayPrecideComputation);
    1357            iMaxNHoursADayConsiderDatePatterns = config.getPropertyBoolean("MaxNHoursADay.ConsiderDatePatterns", iMaxNHoursADayConsiderDatePatterns);
    1358            iNrWorkDays = (config.getPropertyInt("General.LastWorkDay", 4) - config.getPropertyInt("General.FirstWorkDay", 0) + 1);
    1359            if (iNrWorkDays <= 0) iNrWorkDays += 7;
    1360            if (iNrWorkDays > 7) iNrWorkDays -= 7;
    1361            iFirstWorkDay = config.getPropertyInt("General.FirstWorkDay", 0);
    1362            iOnlineRoom = config.getProperty("General.OnlineRoom", "(?i)ONLINE|");
    1363        }
    1364    }
    1365
    1366    @Override
    1367    public void addVariable(Lecture lecture) {
    1368        if (!variables().contains(lecture))
    1369            super.addVariable(lecture);
    1370        if (getType().is(Flag.CH_NOTOVERLAP)) {
    1371            if (lecture.getChildrenSubpartIds() != null) {
    1372                for (Long subpartId: lecture.getChildrenSubpartIds()) {
    1373                    for (Lecture ch : lecture.getChildren(subpartId)) {
    1374                        if (!variables().contains(ch))
    1375                            super.addVariable(ch);
    1376                    }
    1377                }
    1378            }
    1379        }
    1380    }
    1381
    1382    @Override
    1383    public void removeVariable(Lecture lecture) {
    1384        if (variables().contains(lecture))
    1385            super.removeVariable(lecture);
    1386        if (getType().is(Flag.CH_NOTOVERLAP)) {
    1387            if (lecture.getChildrenSubpartIds() != null) {
    1388                for (Long subpartId: lecture.getChildrenSubpartIds()) {
    1389                    for (Lecture ch : lecture.getChildren(subpartId)) {
    1390                        if (variables().contains(ch))
    1391                            super.removeVariable(ch);
    1392                    }
    1393                }
    1394            }
    1395        }
    1396    }
    1397
    1398    /**
    1399     * Constructor
    1400     *
    1401     * @param id
    1402     *            constraint id
    1403     * @param type
    1404     *            constraString type (e.g, {@link ConstraintType#SAME_TIME})
    1405     * @param preference
    1406     *            time preference ("R" for required, "P" for prohibited, "-2",
    1407     *            "-1", "1", "2" for soft preference)
    1408     */
    1409    public GroupConstraint(Long id, ConstraintTypeInterface type, String preference) {
    1410        iConstraintId = id;
    1411        iType = type;
    1412        iIsRequired = preference.equals(Constants.sPreferenceRequired);
    1413        iIsProhibited = preference.equals(Constants.sPreferenceProhibited);
    1414        iPreference = Constants.preference2preferenceLevel(preference);
    1415    }
    1416
    1417    /** Constraint id
    1418     * @return constraint unique id
    1419     **/
    1420    public Long getConstraintId() {
    1421        return iConstraintId;
    1422    }
    1423
    1424    @Override
    1425    public long getId() {
    1426        return (iConstraintId == null ? -1 : iConstraintId.longValue());
    1427    }
    1428
    1429    /** Generated unique id
    1430     * @return generated unique id
    1431     **/
    1432    protected long getGeneratedId() {
    1433        return iId;
    1434    }
    1435
    1436    /** Return constraint type (e.g, {@link ConstraintType#SAME_TIME})
    1437     * @return constraint type
    1438     **/
    1439    public ConstraintTypeInterface getType() {
    1440        return iType;
    1441    }
    1442
    1443    /**
    1444     * Set constraint type
    1445     * @param type constraint type
    1446     */
    1447    public void setType(ConstraintType type) {
    1448        iType = type;
    1449    }
    1450
    1451    /** Is constraint required
    1452     * @return true if required
    1453     **/
    1454    public boolean isRequired() {
    1455        return iIsRequired;
    1456    }
    1457
    1458    /** Is constraint prohibited
    1459     * @return true if prohibited
    1460     **/
    1461    public boolean isProhibited() {
    1462        return iIsProhibited;
    1463    }
    1464
    1465    /**
    1466     * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for
    1467     * preference
    1468     * @return prolog preference
    1469     */
    1470    public String getPrologPreference() {
    1471        return Constants.preferenceLevel2preference(iPreference);
    1472    }
    1473
    1474    @Override
    1475    public boolean isConsistent(Placement value1, Placement value2) {
    1476        if (!isHard())
    1477            return true;
    1478        if (!isSatisfiedPair(null, value1, value2))
    1479            return false;
    1480        if (getType().is(Flag.BACK_TO_BACK)) {
    1481            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    1482            assignments.put(value1.variable(), value1);
    1483            assignments.put(value2.variable(), value2);
    1484            if (!isSatisfiedSeq(null, assignments, null))
    1485                return false;
    1486        }
    1487        if (getType().is(Flag.MAX_HRS_DAY)) {
    1488            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    1489            assignments.put(value1.variable(), value1);
    1490            assignments.put(value2.variable(), value2);
    1491            for (int dayCode: Constants.DAY_CODES) {
    1492                if (iMaxNHoursADayPrecideComputation) {
    1493                    for (IntEnumeration dates = value1.getTimeLocation().getDates(iDayOfWeekOffset); dates.hasMoreElements(); ) {
    1494                        int date = dates.nextElement();
    1495                        if (!value2.getTimeLocation().hasDate(date, iDayOfWeekOffset)) continue;
    1496                        if (nrSlotsADay(null, date, assignments, null) > getType().getMax()) return false;
    1497                    }
    1498                } else if (iMaxNHoursADayConsiderDatePatterns) {
    1499                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
    1500                        if (!value1.getTimeLocation().shareWeeks(week) && !value2.getTimeLocation().shareWeeks(week)) continue;
    1501                        if (nrSlotsADay(null, dayCode, week, assignments, null) > getType().getMax()) return false;
    1502                    }
    1503                } else {
    1504                    if (nrSlotsADay(null, dayCode, null, assignments, null) > getType().getMax()) return false;
    1505                }
    1506            }
    1507        }
    1508        return true;
    1509    }
    1510
    1511    @Override
    1512    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    1513        computeConflicts(assignment, value, conflicts, true);
    1514    }
    1515
    1516    @Override
    1517    public void computeConflictsNoForwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    1518        computeConflicts(assignment, value, conflicts, false);
    1519    }
    1520
    1521    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, boolean fwdCheck) {
    1522        if (!isHard())
    1523            return;
    1524        for (Lecture v : variables()) {
    1525            if (v.equals(value.variable()))
    1526                continue; // ignore this variable
    1527            Placement p = assignment.getValue(v);
    1528            if (p == null)
    1529                continue; // there is an unassigned variable -- great, still a chance to get violated
    1530            if (!isSatisfiedPair(assignment, p, value))
    1531                conflicts.add(p);
    1532        }
    1533        if (getType().is(Flag.BACK_TO_BACK)) {
    1534            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    1535            assignments.put(value.variable(), value);
    1536            if (!isSatisfiedSeq(assignment, assignments, conflicts))
    1537                conflicts.add(value);
    1538        }
    1539        if (getType().is(Flag.MAX_HRS_DAY)) {
    1540            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    1541            assignments.put(value.variable(), value);
    1542            for (int dayCode: Constants.DAY_CODES) {
    1543                if (iMaxNHoursADayPrecideComputation) {
    1544                    for (IntEnumeration dates = value.getTimeLocation().getDates(iDayOfWeekOffset); dates.hasMoreElements(); ) {
    1545                        int date = dates.nextElement();
    1546                        if (nrSlotsADay(assignment, date, assignments, conflicts) > getType().getMax()) {
    1547                            List<Placement> adepts = new ArrayList<Placement>();
    1548                            for (Lecture l: variables()) {
    1549                                if (l.equals(value.variable()) || l.isConstant()) continue;
    1550                                Placement p = assignment.getValue(l);
    1551                                if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue;
    1552                                if (!p.getTimeLocation().hasDate(date, iDayOfWeekOffset)) continue;
    1553                                adepts.add(p);
    1554                            }
    1555                            do {
    1556                                if (adepts.isEmpty()) { conflicts.add(value); break; }
    1557                                Placement conflict = ToolBox.random(adepts);
    1558                                adepts.remove(conflict);
    1559                                conflicts.add(conflict);
    1560                            } while (nrSlotsADay(assignment, date, assignments, conflicts) > getType().getMax());
    1561                        }
    1562                    }
    1563                } else if (iMaxNHoursADayConsiderDatePatterns) {
    1564                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
    1565                        if (!value.getTimeLocation().shareWeeks(week)) continue;
    1566                        if (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax()) {
    1567                            List<Placement> adepts = new ArrayList<Placement>();
    1568                            for (Lecture l: variables()) {
    1569                                if (l.equals(value.variable()) || l.isConstant()) continue;
    1570                                Placement p = assignment.getValue(l);
    1571                                if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue;
    1572                                if ((p.getTimeLocation().getDayCode() & dayCode) == 0 || !p.getTimeLocation().shareWeeks(week)) continue;
    1573                                adepts.add(p);
    1574                            }
    1575                            do {
    1576                                if (adepts.isEmpty()) { conflicts.add(value); break; }
    1577                                Placement conflict = ToolBox.random(adepts);
    1578                                adepts.remove(conflict);
    1579                                conflicts.add(conflict);
    1580                            } while (nrSlotsADay(assignment, dayCode, week, assignments, conflicts) > getType().getMax());
    1581                        }
    1582                    }
    1583                } else {
    1584                    if (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax()) {
    1585                        List<Placement> adepts = new ArrayList<Placement>();
    1586                        for (Lecture l: variables()) {
    1587                            if (l.equals(value.variable()) || l.isConstant()) continue;
    1588                            Placement p = assignment.getValue(l);
    1589                            if (p == null || conflicts.contains(p) || p.getTimeLocation() == null) continue;
    1590                            if ((p.getTimeLocation().getDayCode() & dayCode) == 0) continue;
    1591                            adepts.add(p);
    1592                        }
    1593                        do {
    1594                            if (adepts.isEmpty()) { conflicts.add(value); break; }
    1595                            Placement conflict = ToolBox.random(adepts);
    1596                            adepts.remove(conflict);
    1597                            conflicts.add(conflict);
    1598                        } while (nrSlotsADay(assignment, dayCode, null, assignments, conflicts) > getType().getMax());
    1599                    }
    1600                }
    1601            }
    1602        }
    1603
    1604        // Forward checking
    1605        if (fwdCheck) forwardCheck(assignment, value, conflicts, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1);
    1606    }
    1607
    1608    public void forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts, Set<GroupConstraint> ignore, int depth) {
    1609        try {
    1610            if (depth < 0) return;
    1611            ignore.add(this);
    1612
    1613            List<Placement> neededSize = null;
    1614
    1615            for (Lecture lecture: variables()) {
    1616                if (conflicts.contains(value)) break; // already conflicting
    1617
    1618                if (lecture.equals(value.variable())) continue; // Skip this lecture
    1619                Placement current = assignment.getValue(lecture);
    1620                if (current != null) { // Has assignment, check whether it is conflicting
    1621                    if (isSatisfiedPair(assignment, value, current)) {
    1622                        // Increase needed size if the assignment is of the same room and overlapping in time
    1623                        if (canShareRoom() && sameRoomAndOverlaps(value, current)) {
    1624                            if (neededSize == null) neededSize = new ArrayList<Placement>();
    1625                            neededSize.add(current);
    1626                        }
    1627                        continue;
    1628                    }
    1629                    conflicts.add(current);
    1630                }
    1631
    1632                // Look for supporting assignments assignment
    1633                boolean shareRoomAndOverlaps = canShareRoom();
    1634                Placement support = null;
    1635                int nrSupports = 0;
    1636                if (lecture.nrValues() >= iForwardCheckMaxDomainSize) {
    1637                    // ignore variables with large domains
    1638                    return;
    1639                }
    1640                List<Placement> values = lecture.values(assignment);
    1641                if (values.isEmpty()) {
    1642                    // ignore variables with empty domain
    1643                    return;
    1644                }
    1645                for (Placement other: values) {
    1646                    if (nrSupports < 2) {
    1647                        if (isSatisfiedPair(assignment, value, other)) {
    1648                            if (support == null) support = other;
    1649                            nrSupports ++;
    1650                            if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other))
    1651                                shareRoomAndOverlaps = false;
    1652                        }
    1653                    } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) {
    1654                        shareRoomAndOverlaps = false;
    1655                    }
    1656                    if (nrSupports > 1 && !shareRoomAndOverlaps)
    1657                        break;
    1658                }
    1659
    1660                // No supporting assignment -> fail
    1661                if (nrSupports == 0) {
    1662                    conflicts.add(value); // other class cannot be assigned with this value
    1663                    return;
    1664                }
    1665                // Increase needed size if all supporters are of the same room and in overlapping times
    1666                if (shareRoomAndOverlaps && support != null) {
    1667                    if (neededSize == null) neededSize = new ArrayList<Placement>();
    1668                    neededSize.add(support);
    1669                }
    1670
    1671                // Only one supporter -> propagate the new assignment over other hard constraints of the lecture
    1672                if (nrSupports == 1) {
    1673                    for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) {
    1674                        if (other instanceof WeakeningConstraint) continue;
    1675                        if (other instanceof GroupConstraint) {
    1676                            GroupConstraint gc = (GroupConstraint)other;
    1677                            if (depth > 0 && !ignore.contains(gc))
    1678                                gc.forwardCheck(assignment, support, conflicts, ignore, depth - 1);
    1679                        } else {
    1680                            other.computeConflicts(assignment, support, conflicts);
    1681                        }
    1682                    }
    1683                    for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) {
    1684                        if (other instanceof WeakeningConstraint) continue;
    1685                        other.computeConflicts(assignment, support, conflicts);
    1686                    }
    1687
    1688                    if (conflicts.contains(support))
    1689                        conflicts.add(value);
    1690                }
    1691            }
    1692
    1693            if (canShareRoom() && neededSize != null) {
    1694                if (value.getRoomLocations() != null) {
    1695                    for (RoomLocation room: value.getRoomLocations())
    1696                        if (room.getRoomConstraint() != null && !room.getRoomConstraint().checkRoomSize(value, neededSize)) {
    1697                            // room is too small to fit all meet with classes
    1698                            conflicts.add(value);
    1699                        }
    1700                } else if (value.getRoomLocation() != null) {
    1701                    RoomLocation room = value.getRoomLocation();
    1702                    if (room.getRoomConstraint() != null && !room.getRoomConstraint().checkRoomSize(value, neededSize)) {
    1703                        // room is too small to fit all meet with classes
    1704                        conflicts.add(value);
    1705                    }
    1706                }
    1707            }
    1708        } finally {
    1709            ignore.remove(this);
    1710        }
    1711    }
    1712
    1713    @Override
    1714    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
    1715        if (!isHard())
    1716            return false;
    1717        for (Lecture v : variables()) {
    1718            if (v.equals(value.variable()))
    1719                continue; // ignore this variable
    1720            Placement p = assignment.getValue(v);
    1721            if (p == null)
    1722                continue; // there is an unassigned variable -- great, still a chance to get violated
    1723            if (!isSatisfiedPair(assignment, p, value))
    1724                return true;
    1725        }
    1726        if (getType().is(Flag.BACK_TO_BACK)) {
    1727            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    1728            assignments.put(value.variable(), value);
    1729            if (!isSatisfiedSeq(assignment, assignments, null))
    1730                return true;
    1731        }
    1732        if (getType().is(Flag.MAX_HRS_DAY)) {
    1733            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    1734            assignments.put(value.variable(), value);
    1735            for (int dayCode: Constants.DAY_CODES) {
    1736                if (iMaxNHoursADayPrecideComputation) {
    1737                    for (IntEnumeration dates = value.getTimeLocation().getDates(iDayOfWeekOffset); dates.hasMoreElements(); ) {
    1738                        int date = dates.nextElement();
    1739                        if (nrSlotsADay(assignment,date, assignments, null) > getType().getMax())
    1740                            return true;
    1741                    }
    1742                } else if (iMaxNHoursADayConsiderDatePatterns) {
    1743                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
    1744                        if (!value.getTimeLocation().shareWeeks(week)) continue;
    1745                        if (nrSlotsADay(assignment, dayCode, week, assignments, null) > getType().getMax())
    1746                            return true;
    1747                    }
    1748                } else {
    1749                    if (nrSlotsADay(assignment, dayCode, null, assignments, null) > getType().getMax()) return true;
    1750                }
    1751            }
    1752        }
    1753
    1754        if (!forwardCheck(assignment, value, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1)) return true;
    1755
    1756        return false;
    1757    }
    1758
    1759    public boolean forwardCheck(Assignment<Lecture, Placement> assignment, Placement value, Set<GroupConstraint> ignore, int depth) {
    1760        try {
    1761            if (depth < 0) return true;
    1762            ignore.add(this);
    1763
    1764            int neededSize = value.variable().maxRoomUse();
    1765
    1766            for (Lecture lecture: variables()) {
    1767                if (lecture.equals(value.variable())) continue; // Skip this lecture
    1768                Placement current = assignment.getValue(lecture);
    1769                if (current != null) { // Has assignment, check whether it is conflicting
    1770                    if (isSatisfiedPair(assignment, value, current)) {
    1771                        // Increase needed size if the assignment is of the same room and overlapping in time
    1772                        if (canShareRoom() && sameRoomAndOverlaps(value, current)) {
    1773                            neededSize += lecture.maxRoomUse();
    1774                        }
    1775                        continue;
    1776                    }
    1777                    return false;
    1778                }
    1779
    1780                // Look for supporting assignments assignment
    1781                boolean shareRoomAndOverlaps = canShareRoom();
    1782                Placement support = null;
    1783                int nrSupports = 0;
    1784                if (lecture.nrValues() >= iForwardCheckMaxDomainSize) {
    1785                    // ignore variables with large domains
    1786                    return true;
    1787                }
    1788                List<Placement> values = lecture.values(assignment);
    1789                if (values.isEmpty()) {
    1790                    // ignore variables with empty domain
    1791                    return true;
    1792                }
    1793                for (Placement other: lecture.values(assignment)) {
    1794                    if (nrSupports < 2) {
    1795                        if (isSatisfiedPair(assignment, value, other)) {
    1796                            if (support == null) support = other;
    1797                            nrSupports ++;
    1798                            if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other))
    1799                                shareRoomAndOverlaps = false;
    1800                        }
    1801                    } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(assignment, value, other)) {
    1802                        shareRoomAndOverlaps = false;
    1803                    }
    1804                    if (nrSupports > 1 && !shareRoomAndOverlaps)
    1805                        break;
    1806                }
    1807
    1808                // No supporting assignment -> fail
    1809                if (nrSupports == 0) {
    1810                    return false; // other class cannot be assigned with this value
    1811                }
    1812                // Increase needed size if all supporters are of the same room and in overlapping times
    1813                if (shareRoomAndOverlaps) {
    1814                    neededSize += lecture.maxRoomUse();
    1815                }
    1816
    1817                // Only one supporter -> propagate the new assignment over other hard constraints of the lecture
    1818                if (nrSupports == 1) {
    1819                    for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) {
    1820                        if (other instanceof WeakeningConstraint) continue;
    1821                        if (other instanceof GroupConstraint) {
    1822                            GroupConstraint gc = (GroupConstraint)other;
    1823                            if (depth > 0 && !ignore.contains(gc) && !gc.forwardCheck(assignment, support, ignore, depth - 1)) return false;
    1824                        } else {
    1825                            if (other.inConflict(assignment, support)) return false;
    1826                        }
    1827                    }
    1828                    for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) {
    1829                        if (other instanceof WeakeningConstraint) continue;
    1830                        if (other.inConflict(assignment, support)) return false;
    1831                    }
    1832                }
    1833            }
    1834
    1835            if (canShareRoom() && neededSize > value.getRoomSize()) {
    1836                // room is too small to fit all meet with classes
    1837                return false;
    1838            }
    1839
    1840            return true;
    1841        } finally {
    1842            ignore.remove(this);
    1843        }
    1844    }
    1845
    1846    /** Constraint preference (0 if prohibited or required)
    1847     * @return constraint preference (if soft)
    1848     **/
    1849    public int getPreference() {
    1850        return iPreference;
    1851    }
    1852
    1853    /**
    1854     * Current constraint preference (0 if prohibited or required, depends on
    1855     * current satisfaction of the constraint)
    1856     * @param assignment current assignment
    1857     * @return current preference
    1858     */
    1859    public int getCurrentPreference(Assignment<Lecture, Placement> assignment) {
    1860        if (isHard()) return 0; // no preference
    1861        if (countAssignedVariables(assignment) < 2) return - Math.abs(iPreference); // not enough variable
    1862        if (getType().is(Flag.MAX_HRS_DAY)) { // max hours a day
    1863            int over = 0;
    1864            for (int dayCode: Constants.DAY_CODES) {
    1865                if (iMaxNHoursADayPrecideComputation) {
    1866                    Set<Integer> allDates = new HashSet<Integer>();
    1867                    for (Lecture v1 : variables()) {
    1868                        Placement p1 = assignment.getValue(v1);
    1869                        if (p1 == null) continue;
    1870                        for (IntEnumeration dates = p1.getTimeLocation().getDates(iDayOfWeekOffset); dates.hasMoreElements(); ) {
    1871                            int date = dates.nextElement();
    1872                            if (allDates.add(date))
    1873                                over += Math.max(0, nrSlotsADay(assignment, date, null, null) - getType().getMax());
    1874                        }
    1875                    }
    1876                } else if (iMaxNHoursADayConsiderDatePatterns) {
    1877                    for (BitSet week: ((TimetableModel)getModel()).getWeeks())
    1878                        over += Math.max(0, nrSlotsADay(assignment, dayCode, week, null, null) - getType().getMax());
    1879                } else {
    1880                    over += Math.max(0, nrSlotsADay(assignment, dayCode, null, null, null) - getType().getMax());
    1881                }
    1882            }
    1883            return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference));
    1884        }
    1885        int nrViolatedPairs = 0;
    1886        for (Lecture v1 : variables()) {
    1887            Placement p1 = assignment.getValue(v1);
    1888            if (p1 == null) continue;
    1889            for (Lecture v2 : variables()) {
    1890                Placement p2 = assignment.getValue(v2);
    1891                if (p2 == null || v1.getId() >= v2.getId()) continue;
    1892                if (!isSatisfiedPair(assignment, p1, p2)) nrViolatedPairs++;
    1893            }
    1894        }
    1895        if (getType().is(Flag.BACK_TO_BACK)) {
    1896            Set<Placement> conflicts = new HashSet<Placement>();
    1897            if (isSatisfiedSeq(assignment, new HashMap<Lecture, Placement>(), conflicts))
    1898                nrViolatedPairs += conflicts.size();
    1899            else
    1900                nrViolatedPairs = variables().size();
    1901        }
    1902        return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference));
    1903    }
    1904
    1905    /** Current constraint preference change (if given placement is assigned)
    1906     * @param assignment current assignment
    1907     * @param placement placement that is being considered
    1908     * @return change in the current preference, if assigned
    1909     **/
    1910    public int getCurrentPreference(Assignment<Lecture, Placement> assignment, Placement placement) {
    1911        if (isHard()) return 0; // no preference
    1912        if (countAssignedVariables(assignment) + (assignment.getValue(placement.variable()) == null ? 1 : 0) < 2) return 0; // not enough variable
    1913        if (getType().is(Flag.MAX_HRS_DAY)) {
    1914            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    1915            assignments.put(placement.variable(), placement);
    1916            HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>();
    1917            unassignments.put(placement.variable(), null);
    1918            int after = 0;
    1919            int before = 0;
    1920            for (int dayCode: Constants.DAY_CODES) {
    1921                if (iMaxNHoursADayPrecideComputation) {
    1922                    for (IntEnumeration dates = placement.getTimeLocation().getDates(iDayOfWeekOffset); dates.hasMoreElements(); ) {
    1923                        int date = dates.nextElement();
    1924                        after += Math.max(0, nrSlotsADay(assignment, date, assignments, null) - getType().getMax());
    1925                        before += Math.max(0, nrSlotsADay(assignment, date, unassignments, null) - getType().getMax());
    1926                    }
    1927                } else if (iMaxNHoursADayConsiderDatePatterns) {
    1928                    for (BitSet week: ((TimetableModel)getModel()).getWeeks()) {
    1929                        after += Math.max(0, nrSlotsADay(assignment, dayCode, week, assignments, null) - getType().getMax());
    1930                        before += Math.max(0, nrSlotsADay(assignment, dayCode, week, unassignments, null) - getType().getMax());
    1931                    }
    1932                } else {
    1933                    after += Math.max(0, nrSlotsADay(assignment, dayCode, null, assignments, null) - getType().getMax());
    1934                    before += Math.max(0, nrSlotsADay(assignment, dayCode, null, unassignments, null) - getType().getMax());
    1935                }
    1936            }
    1937            return (after > 0 ? Math.abs(iPreference) * after / 12 : - Math.abs(iPreference)) - (before > 0 ? Math.abs(iPreference) * before / 12 : - Math.abs(iPreference));
    1938        }
    1939
    1940        int nrViolatedPairsAfter = 0;
    1941        int nrViolatedPairsBefore = 0;
    1942        for (Lecture v1 : variables()) {
    1943            for (Lecture v2 : variables()) {
    1944                if (v1.getId() >= v2.getId()) continue;
    1945                Placement p1 = (v1.equals(placement.variable()) ? null : assignment.getValue(v1));
    1946                Placement p2 = (v2.equals(placement.variable()) ? null : assignment.getValue(v2));
    1947                if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2))
    1948                    nrViolatedPairsBefore ++;
    1949                if (v1.equals(placement.variable())) p1 = placement;
    1950                if (v2.equals(placement.variable())) p2 = placement;
    1951                if (p1 != null && p2 != null && !isSatisfiedPair(assignment, p1, p2))
    1952                    nrViolatedPairsAfter ++;
    1953            }
    1954        }
    1955
    1956        if (getType().is(Flag.BACK_TO_BACK)) {
    1957            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    1958            assignments.put(placement.variable(), placement);
    1959            Set<Placement> conflicts = new HashSet<Placement>();
    1960            if (isSatisfiedSeq(assignment, assignments, conflicts))
    1961                nrViolatedPairsAfter += conflicts.size();
    1962            else
    1963                nrViolatedPairsAfter = variables().size();
    1964
    1965            HashMap<Lecture, Placement> unassignments = new HashMap<Lecture, Placement>();
    1966            unassignments.put(placement.variable(), null);
    1967            Set<Placement> previous = new HashSet<Placement>();
    1968            if (isSatisfiedSeq(assignment, unassignments, previous))
    1969                nrViolatedPairsBefore += previous.size();
    1970            else
    1971                nrViolatedPairsBefore = variables().size();
    1972        }
    1973
    1974        return (nrViolatedPairsAfter > 0 ? Math.abs(iPreference) * nrViolatedPairsAfter : - Math.abs(iPreference)) -
    1975                (nrViolatedPairsBefore > 0 ? Math.abs(iPreference) * nrViolatedPairsBefore : - Math.abs(iPreference));
    1976    }
    1977
    1978    @Override
    1979    public String toString() {
    1980        StringBuffer sb = new StringBuffer();
    1981        sb.append(getName());
    1982        sb.append(" between ");
    1983        for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) {
    1984            Lecture v = e.next();
    1985            sb.append(v.getName());
    1986            if (e.hasNext())
    1987                sb.append(", ");
    1988        }
    1989        return sb.toString();
    1990    }
    1991
    1992    @Override
    1993    public boolean isHard() {
    1994        return iIsRequired || iIsProhibited;
    1995    }
    1996
    1997    @Override
    1998    public String getName() {
    1999        return getType().getName();
    2000    }
    2001
    2002
    2003    private boolean isPrecedence(Placement p1, Placement p2, boolean firstGoesFirst, boolean considerDatePatterns) {
    2004        int ord1 = variables().indexOf(p1.variable());
    2005        int ord2 = variables().indexOf(p2.variable());
    2006        TimeLocation t1 = null, t2 = null;
    2007        if (ord1 < ord2) {
    2008            if (firstGoesFirst) {
    2009                t1 = p1.getTimeLocation();
    2010                t2 = p2.getTimeLocation();
    2011            } else {
    2012                t2 = p1.getTimeLocation();
    2013                t1 = p2.getTimeLocation();
    2014            }
    2015        } else {
    2016            if (!firstGoesFirst) {
    2017                t1 = p1.getTimeLocation();
    2018                t2 = p2.getTimeLocation();
    2019            } else {
    2020                t2 = p1.getTimeLocation();
    2021                t1 = p2.getTimeLocation();
    2022            }
    2023        }
    2024        if (considerDatePatterns && iPrecedenceConsiderDatePatterns) {
    2025            if (iPrecedenceSkipSameDatePatternCheck) {
    2026                int m1 = t1.getFirstMeeting(iDayOfWeekOffset), m2 = t2.getFirstMeeting(iDayOfWeekOffset);
    2027                if (m1 != m2) return m1 < m2;
    2028            } else {
    2029                boolean sameDatePattern = (t1.getDatePatternId() != null ? t1.getDatePatternId().equals(t2.getDatePatternId()) : t1.getWeekCode().equals(t2.getWeekCode()));
    2030                if (!sameDatePattern) {
    2031                    int m1 = t1.getFirstMeeting(iDayOfWeekOffset), m2 = t2.getFirstMeeting(iDayOfWeekOffset);
    2032                    if (m1 != m2) return m1 < m2;
    2033                }
    2034            }
    2035        }
    2036        if (iFirstWorkDay != 0) {
    2037            for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    2038                int idx = (i + iFirstWorkDay) % 7;
    2039                boolean a = (t1.getDayCode() & Constants.DAY_CODES[idx]) != 0;
    2040                boolean b = (t2.getDayCode() & Constants.DAY_CODES[idx]) != 0;
    2041                if (b && !a) return false; // second start first
    2042                if (a && !b) return true;  // first start first
    2043                if (a && b) return t1.getStartSlot() + t1.getLength() <= t2.getStartSlot(); // same day: check times
    2044            }
    2045        }
    2046        return t1.getStartSlots().nextElement() + t1.getLength() <= t2.getStartSlots().nextElement();
    2047    }
    2048
    2049    private boolean isBackToBackDays(TimeLocation t1, TimeLocation t2) {
    2050        int f1 = -1, f2 = -1, e1 = -1, e2 = -1;
    2051        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    2052            int idx = (i + iFirstWorkDay) % 7;
    2053            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
    2054                if (f1 < 0)
    2055                    f1 = i;
    2056                e1 = i;
    2057            }
    2058            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
    2059                if (f2 < 0)
    2060                    f2 = i;
    2061                e2 = i;
    2062            }
    2063        }
    2064        return (e1 + 1 == f2) || (e2 + 1 == f1);
    2065    }
    2066
    2067    private boolean isNrDaysBetweenGreaterThanOne(TimeLocation t1, TimeLocation t2) {
    2068        int f1 = -1, f2 = -1, e1 = -1, e2 = -1;
    2069        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    2070            int idx = (i + iFirstWorkDay) % 7;
    2071            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
    2072                if (f1 < 0)
    2073                    f1 = i;
    2074                e1 = i;
    2075            }
    2076            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
    2077                if (f2 < 0)
    2078                    f2 = i;
    2079                e2 = i;
    2080            }
    2081        }
    2082        return (e1 - f2 > 2) || (e2 - f1 > 2);
    2083    }
    2084
    2085    private boolean isFollowingDay(Placement p1, Placement p2, boolean firstGoesFirst) {
    2086        int ord1 = variables().indexOf(p1.variable());
    2087        int ord2 = variables().indexOf(p2.variable());
    2088        TimeLocation t1 = null, t2 = null;
    2089        if (ord1 < ord2) {
    2090            if (firstGoesFirst) {
    2091                t1 = p1.getTimeLocation();
    2092                t2 = p2.getTimeLocation();
    2093            } else {
    2094                t2 = p1.getTimeLocation();
    2095                t1 = p2.getTimeLocation();
    2096            }
    2097        } else {
    2098            if (!firstGoesFirst) {
    2099                t1 = p1.getTimeLocation();
    2100                t2 = p2.getTimeLocation();
    2101            } else {
    2102                t2 = p1.getTimeLocation();
    2103                t1 = p2.getTimeLocation();
    2104            }
    2105        }
    2106        int f1 = -1, f2 = -1, e1 = -1;
    2107        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    2108            int idx = (i + iFirstWorkDay) % 7;
    2109            if ((t1.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
    2110                if (f1 < 0)
    2111                    f1 = i;
    2112                e1 = i;
    2113            }
    2114            if ((t2.getDayCode() & Constants.DAY_CODES[idx]) != 0) {
    2115                if (f2 < 0)
    2116                    f2 = i;
    2117            }
    2118        }
    2119        return ((e1 + 1) % iNrWorkDays == f2);
    2120    }
    2121
    2122    private boolean isNextDay(TimeLocation t1, TimeLocation t2) {
    2123        if (iPrecedenceConsiderDatePatterns) {
    2124            for (Enumeration<Integer> e = t1.getDates(iDayOfWeekOffset); e.hasMoreElements(); ) {
    2125                Integer date = e.nextElement();
    2126                if (t2.hasDate(date + 1, iDayOfWeekOffset)) return true;
    2127            }
    2128            return false;
    2129        }
    2130        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    2131            int i1 = (i + iFirstWorkDay) % 7;
    2132            int i2 = (1 + i1) % 7;
    2133            boolean a = (t1.getDayCode() & Constants.DAY_CODES[i1]) != 0;
    2134            boolean b = (t2.getDayCode() & Constants.DAY_CODES[i2]) != 0;
    2135            if (a && b) return true;
    2136        }
    2137        return false;
    2138    }
    2139
    2140    private boolean isEveryOtherDay(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 + 2) % iNrWorkDays == f2);
    2175    }
    2176
    2177    private static boolean sameDays(int[] days1, int[] days2) {
    2178        if (days2.length < days1.length)
    2179            return sameDays(days2, days1);
    2180        int i2 = 0;
    2181        for (int i1 = 0; i1 < days1.length; i1++) {
    2182            int d1 = days1[i1];
    2183            while (true) {
    2184                if (i2 == days2.length)
    2185                    return false;
    2186                int d2 = days2[i2];
    2187                if (d1 == d2)
    2188                    break;
    2189                i2++;
    2190                if (i2 == days2.length)
    2191                    return false;
    2192            }
    2193            i2++;
    2194        }
    2195        return true;
    2196    }
    2197
    2198    private static boolean sameRoomAndOverlaps(Placement p1, Placement p2) {
    2199        return p1.shareRooms(p2) && p1.getTimeLocation() != null && p2.getTimeLocation() != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation());
    2200    }
    2201
    2202    private static boolean sameHours(int start1, int len1, int start2, int len2) {
    2203        if (len1 > len2)
    2204            return sameHours(start2, len2, start1, len1);
    2205        start1 %= Constants.SLOTS_PER_DAY;
    2206        start2 %= Constants.SLOTS_PER_DAY;
    2207        return (start1 >= start2 && start1 + len1 <= start2 + len2);
    2208    }
    2209
    2210    private static boolean canFill(int totalGap, int gapMin, int gapMax, List<Set<Integer>> lengths) {
    2211        if (gapMin <= totalGap && totalGap <= gapMax)
    2212            return true;
    2213        if (totalGap < 2 * gapMin)
    2214            return false;
    2215        for (int i = 0; i < lengths.size(); i++) {
    2216            Set<Integer> length = lengths.get(i);
    2217            lengths.remove(i);
    2218            for (int gap = gapMin; gap <= gapMax; gap++)
    2219                for (Integer l: length)
    2220                    if (canFill(totalGap - gap - l, gapMin, gapMax, lengths))
    2221                        return true;
    2222            lengths.add(i, length);
    2223        }
    2224        return false;
    2225    }
    2226
    2227    private boolean isSatisfiedSeq(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
    2228        if (conflicts == null)
    2229            return isSatisfiedSeqCheck(assignment, assignments, conflicts);
    2230        else {
    2231            Set<Placement> bestConflicts = isSatisfiedRecursive(assignment, 0, assignments, conflicts,
    2232                    new HashSet<Placement>(), null);
    2233            if (bestConflicts == null)
    2234                return false;
    2235            conflicts.addAll(bestConflicts);
    2236            return true;
    2237        }
    2238    }
    2239
    2240    private Set<Placement> isSatisfiedRecursive(Assignment<Lecture, Placement> assignment, int idx, HashMap<Lecture, Placement> assignments,
    2241            Set<Placement> conflicts, Set<Placement> newConflicts, Set<Placement> bestConflicts) {
    2242        if (idx == variables().size() && newConflicts.isEmpty())
    2243            return bestConflicts;
    2244        if (isSatisfiedSeqCheck(assignment, assignments, conflicts)) {
    2245            if (bestConflicts == null) {
    2246                return new HashSet<Placement>(newConflicts);
    2247            } else {
    2248                int b = 0, n = 0;
    2249                for (Placement value: assignments.values()) {
    2250                    if (value != null && bestConflicts.contains(value)) b++;
    2251                    if (value != null && newConflicts.contains(value)) n++;
    2252                }
    2253                if (n < b || (n == b && newConflicts.size() < bestConflicts.size()))
    2254                    return new HashSet<Placement>(newConflicts);
    2255            }
    2256            return bestConflicts;
    2257        }
    2258        if (idx == variables().size())
    2259            return bestConflicts;
    2260        bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts,
    2261                bestConflicts);
    2262        Lecture lecture = variables().get(idx);
    2263        //if (assignments != null && assignments.containsKey(lecture))
    2264        //    return bestConflicts;
    2265        Placement placement = null;
    2266        if (assignments != null && assignments.containsKey(lecture))
    2267            placement = assignments.get(lecture);
    2268        else if (assignment != null)
    2269            placement = assignment.getValue(lecture);
    2270        if (placement == null)
    2271            return bestConflicts;
    2272        if (conflicts != null && conflicts.contains(placement))
    2273            return bestConflicts;
    2274        conflicts.add(placement);
    2275        newConflicts.add(placement);
    2276        bestConflicts = isSatisfiedRecursive(assignment, idx + 1, assignments, conflicts, newConflicts, bestConflicts);
    2277        newConflicts.remove(placement);
    2278        conflicts.remove(placement);
    2279        return bestConflicts;
    2280    }
    2281
    2282    private boolean isSatisfiedSeqCheck(Assignment<Lecture, Placement> assignment, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
    2283        if (!getType().is(Flag.BACK_TO_BACK)) return true;
    2284        int gapMin = getType().getMin();
    2285        int gapMax = getType().getMax();
    2286
    2287        List<Set<Integer>> lengths = new ArrayList<Set<Integer>>();
    2288
    2289        Placement[] res = new Placement[Constants.SLOTS_PER_DAY];
    2290        for (int i = 0; i < Constants.SLOTS_PER_DAY; i++)
    2291            res[i] = null;
    2292
    2293        int nrLectures = 0;
    2294
    2295        for (Lecture lecture : variables()) {
    2296            Placement placement = null;
    2297            if (assignments != null && assignments.containsKey(lecture))
    2298                placement = assignments.get(lecture);
    2299            else if (assignment != null)
    2300                placement = assignment.getValue(lecture);
    2301            if (placement == null) {
    2302                if (!lecture.timeLocations().isEmpty()) {
    2303                    Set<Integer> l = new HashSet<Integer>();
    2304                    for (TimeLocation time: lecture.timeLocations())
    2305                        l.add(time.getLength());
    2306                    lengths.add(l);
    2307                }
    2308            } else if (conflicts != null && conflicts.contains(placement)) {
    2309                if (!lecture.timeLocations().isEmpty()) {
    2310                    Set<Integer> l = new HashSet<Integer>();
    2311                    for (TimeLocation time: lecture.timeLocations())
    2312                        l.add(time.getLength());
    2313                    lengths.add(l);
    2314                }
    2315            } else {
    2316                int pos = placement.getTimeLocation().getStartSlot();
    2317                int length = placement.getTimeLocation().getLength();
    2318                for (int j = pos; j < pos + length; j++) {
    2319                    if (res[j] != null) {
    2320                        if (conflicts == null)
    2321                            return false;
    2322                        if (!assignments.containsKey(lecture))
    2323                            conflicts.add(placement);
    2324                        else if (!assignments.containsKey(res[j].variable()))
    2325                            conflicts.add(res[j]);
    2326                    }
    2327                }
    2328                for (int j = pos; j < pos + length; j++)
    2329                    res[j] = placement;
    2330                nrLectures++;
    2331            }
    2332        }
    2333        if (nrLectures <= 1)
    2334            return true;
    2335
    2336        if (iIsRequired || (!iIsProhibited && iPreference < 0)) {
    2337            int i = 0;
    2338            Placement p = res[i];
    2339            while (p == null)
    2340                p = res[++i];
    2341            i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
    2342            nrLectures--;
    2343            while (nrLectures > 0) {
    2344                int gap = 0;
    2345                while (i < Constants.SLOTS_PER_DAY && res[i] == null) {
    2346                    gap++;
    2347                    i++;
    2348                }
    2349                if (i == Constants.SLOTS_PER_DAY)
    2350                    break;
    2351                if (!canFill(gap, gapMin, gapMax, lengths))
    2352                    return false;
    2353                p = res[i];
    2354                i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
    2355                nrLectures--;
    2356            }
    2357        } else if (iIsProhibited || (!iIsRequired && iPreference > 0)) {
    2358            int i = 0;
    2359            Placement p = res[i];
    2360            while (p == null)
    2361                p = res[++i];
    2362            i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
    2363            nrLectures--;
    2364            while (nrLectures > 0) {
    2365                int gap = 0;
    2366                while (i < Constants.SLOTS_PER_DAY && res[i] == null) {
    2367                    gap++;
    2368                    i++;
    2369                }
    2370                if (i == Constants.SLOTS_PER_DAY)
    2371                    break;
    2372                if ((gapMin == 0 || !canFill(gap, 0, gapMin - 1, lengths))
    2373                        && (gapMax >= Constants.SLOTS_PER_DAY || !canFill(gap, gapMax + 1, Constants.SLOTS_PER_DAY,
    2374                                lengths))) {
    2375                    return false;
    2376                }
    2377                p = res[i];
    2378                i = res[i].getTimeLocation().getStartSlot() + res[i].getTimeLocation().getLength();
    2379                nrLectures--;
    2380            }
    2381        }
    2382        return true;
    2383    }
    2384
    2385    public boolean isSatisfied(Assignment<Lecture, Placement> assignment) {
    2386        if (isHard()) return true;
    2387        if (countAssignedVariables(assignment) < 2) return true;
    2388        if (getPreference() == 0) return true;
    2389        return isHard() || countAssignedVariables(assignment) < 2 || getPreference() == 0 || getCurrentPreference(assignment) < 0;
    2390    }
    2391
    2392    public boolean isChildrenNotOverlap(Assignment<Lecture, Placement> assignment, Lecture lec1, Placement plc1, Lecture lec2, Placement plc2) {
    2393        if (lec1.getSchedulingSubpartId().equals(lec2.getSchedulingSubpartId())) {
    2394            // same subpart
    2395            boolean overlap = plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation());
    2396
    2397            if (overlap && lec1.getParent() != null && variables().contains(lec1.getParent())
    2398                    && lec2.getParent() != null && variables().contains(lec2.getParent())) {
    2399                // children overlaps
    2400                Placement p1 = assignment.getValue(lec1.getParent());
    2401                Placement p2 = assignment.getValue(lec2.getParent());
    2402                // parents not overlap, but children do
    2403                if (p1 != null && p2 != null && !p1.getTimeLocation().hasIntersection(p2.getTimeLocation()))
    2404                    return false;
    2405            }
    2406
    2407            if (!overlap && lec1.getChildrenSubpartIds() != null && lec2.getChildrenSubpartIds() != null) {
    2408                // parents not overlap
    2409                for (Long subpartId: lec1.getChildrenSubpartIds()) {
    2410                    for (Lecture c1 : lec1.getChildren(subpartId)) {
    2411                        Placement p1 = assignment.getValue(c1);
    2412                        if (p1 == null) continue;
    2413                        for (Lecture c2 : lec2.getChildren(subpartId)) {
    2414                            Placement p2 = assignment.getValue(c2);
    2415                            if (p2 == null) continue;
    2416                            if (!c1.getSchedulingSubpartId().equals(c2.getSchedulingSubpartId())) continue;
    2417                            // parents not overlap, but children do
    2418                            if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation()))
    2419                                return false;
    2420                        }
    2421                    }
    2422                }
    2423            }
    2424        } else {
    2425            // different subpart
    2426        }
    2427        return true;
    2428    }
    2429
    2430    public boolean isSatisfiedPair(Assignment<Lecture, Placement> assignment, Placement plc1, Placement plc2) {
    2431        if (iIsRequired || (!iIsProhibited && iPreference <= 0))
    2432            return getType().isSatisfied(assignment, this, plc1, plc2);
    2433        else if (iIsProhibited || (!iIsRequired && iPreference > 0))
    2434            return getType().isViolated(assignment, this, plc1, plc2);
    2435        return true;
    2436    }
    2437
    2438    public boolean canShareRoom() {
    2439        return getType().is(Flag.CAN_SHARE_ROOM);
    2440    }
    2441
    2442    protected int nrSlotsADay(Assignment<Lecture, Placement> assignment, int dayCode, BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
    2443        Set<Integer> slots = new HashSet<Integer>();
    2444        for (Lecture lecture: variables()) {
    2445            Placement placement = null;
    2446            if (assignments != null && assignments.containsKey(lecture))
    2447                placement = assignments.get(lecture);
    2448            else if (assignment != null)
    2449                placement = assignment.getValue(lecture);
    2450            if (placement == null || placement.getTimeLocation() == null) continue;
    2451            if (conflicts != null && conflicts.contains(placement)) continue;
    2452            TimeLocation t = placement.getTimeLocation();
    2453            if (t == null || (t.getDayCode() & dayCode) == 0 || (week != null && !t.shareWeeks(week))) continue;
    2454            for (int i = 0; i < t.getLength(); i++)
    2455                slots.add(i + t.getStartSlot());
    2456        }
    2457        return slots.size();
    2458    }
    2459
    2460    protected int nrSlotsADay(Assignment<Lecture, Placement> assignment, int date, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
    2461        Set<Integer> slots = new HashSet<Integer>();
    2462        for (Lecture lecture: variables()) {
    2463            Placement placement = null;
    2464            if (assignments != null && assignments.containsKey(lecture))
    2465                placement = assignments.get(lecture);
    2466            else if (assignment != null)
    2467                placement = assignment.getValue(lecture);
    2468            if (placement == null || placement.getTimeLocation() == null) continue;
    2469            if (conflicts != null && conflicts.contains(placement)) continue;
    2470            TimeLocation t = placement.getTimeLocation();
    2471            if (t == null || !t.hasDate(date, iDayOfWeekOffset)) continue;
    2472            for (int i = 0; i < t.getLength(); i++)
    2473                slots.add(i + t.getStartSlot());
    2474        }
    2475        return slots.size();
    2476    }
    2477
    2478    @Override
    2479    public boolean equals(Object o) {
    2480        if (o == null || !(o instanceof GroupConstraint)) return false;
    2481        return getGeneratedId() == ((GroupConstraint) o).getGeneratedId();
    2482    }
    2483
    2484    @Override
    2485    public GroupConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    2486        return new GroupConstraintContext(assignment);
    2487    }
    2488
    2489    public class GroupConstraintContext implements AssignmentConstraintContext<Lecture, Placement> {
    2490        protected int iLastPreference = 0;
    2491
    2492        public GroupConstraintContext(Assignment<Lecture, Placement> assignment) {
    2493            updateCriterion(assignment);
    2494        }
    2495
    2496        @Override
    2497        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
    2498            updateCriterion(assignment);
    2499        }
    2500
    2501        @Override
    2502        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
    2503            updateCriterion(assignment);
    2504        }
    2505
    2506        protected void updateCriterion(Assignment<Lecture, Placement> assignment) {
    2507            if (!isHard()) {
    2508                getModel().getCriterion(DistributionPreferences.class).inc(assignment, -iLastPreference);
    2509                iLastPreference = getCurrentPreference(assignment) + Math.abs(iPreference);
    2510                getModel().getCriterion(DistributionPreferences.class).inc(assignment, iLastPreference);
    2511            }
    2512        }
    2513
    2514        public int getPreference() { return iLastPreference; }
    2515    }
    2516
    2517    private boolean isBackToBackWeeks(TimeLocation t1, TimeLocation t2) {
    2518        if (t1.shareWeeks(t2)) return false;
    2519        int f1 = t1.getWeekCode().nextSetBit(0);
    2520        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
    2521        int f2 = t2.getWeekCode().nextSetBit(0);
    2522        int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size());
    2523        if (e1 < f2) {
    2524            return (f2 - e1) < 7;
    2525        } else if (e2 < f1) {
    2526            return (f1 - e2) < 7;
    2527        }
    2528        return false;
    2529    }
    2530
    2531    private boolean isMaxWeekSpan(TimeLocation t1, TimeLocation t2, int nrWeeks) {
    2532        if (t1.shareWeeks(t2)) return false;
    2533        if (isBackToBackWeeks(t1, t2)) return true;
    2534
    2535        int f1 = t1.getWeekCode().nextSetBit(0);
    2536        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
    2537        int f2 = t2.getWeekCode().nextSetBit(0);
    2538        int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size());
    2539        if (e1 < f2) {
    2540            return (3 + e2 - f1) / 7 <= nrWeeks;
    2541        } else if (e2 < f1) {
    2542            return (3 + e1 - f2) / 7 <= nrWeeks;
    2543        }
    2544        return false;
    2545    }
    2546
    2547    private boolean isNotBackToBackWeeks(TimeLocation t1, TimeLocation t2) {
    2548        if (t1.shareWeeks(t2)) return false;
    2549        int f1 = t1.getWeekCode().nextSetBit(0);
    2550        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
    2551        int f2 = t2.getWeekCode().nextSetBit(0);
    2552        int e2 = t2.getWeekCode().previousSetBit(t2.getWeekCode().size());
    2553        if (e1 < f2) {
    2554            return (f2 - e1) >= 7;
    2555        } else if (e2 < f1) {
    2556            return (f1 - e2) >= 7;
    2557        }
    2558        return false;
    2559    }
    2560
    2561    private boolean isFollowingWeeksBTB(Placement p1, Placement p2, boolean btb) {
    2562        int ord1 = variables().indexOf(p1.variable());
    2563        int ord2 = variables().indexOf(p2.variable());
    2564        TimeLocation t1, t2;
    2565        boolean following = false;
    2566        if (ord1 < ord2) {
    2567            t1 = p1.getTimeLocation();
    2568            t2 = p2.getTimeLocation();
    2569            if (ord1 + 1 == ord2) following = true;
    2570        } else {
    2571            t2 = p1.getTimeLocation();
    2572            t1 = p2.getTimeLocation();
    2573            if (ord2 + 1 == ord1) following = true;
    2574        }
    2575        if (t1.shareWeeks(t2)) return false;
    2576        int e1 = t1.getWeekCode().previousSetBit(t1.getWeekCode().size());
    2577        int s2 = t2.getWeekCode().nextSetBit(0);
    2578        if (e1 >= s2) return false;
    2579        if (!btb) // not back-to-back: any two classes must be at least a week apart
    2580            return (s2 - e1) >= 7;
    2581        else if (following) // back-to-back and following classes: must be within a week
    2582            return (s2 - e1) < 7;
    2583        else // back-to-back and not following: just the order
    2584            return true;
    2585    }
    2586
    2587    private boolean isDifferentDates(TimeLocation t1, TimeLocation t2) {
    2588        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return true;
    2589        for (Enumeration<Integer> e = t1.getDates(iDayOfWeekOffset); e.hasMoreElements(); ) {
    2590            Integer date = e.nextElement();
    2591            if (t2.hasDate(date, iDayOfWeekOffset)) return false;
    2592        }
    2593        return true;
    2594    }
    2595
    2596    private boolean isSameDates(TimeLocation t1, TimeLocation t2) {
    2597        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
    2598        // t1 is meets less often
    2599        if (t1.countDates(iDayOfWeekOffset) > t2.countDates(iDayOfWeekOffset)) {
    2600            TimeLocation t = t1; t1 = t2; t2 = t;
    2601        }
    2602        for (Enumeration<Integer> e = t1.getDates(iDayOfWeekOffset); e.hasMoreElements(); ) {
    2603            Integer date = e.nextElement();
    2604            if (!t2.hasDate(date, iDayOfWeekOffset)) return false;
    2605        }
    2606        return true;
    2607    }
    2608
    2609    private int nextDate(BitSet weekCode, int dayCode, int nextDate) {
    2610        while (true) {
    2611            nextDate = weekCode.nextSetBit(1 + nextDate);
    2612            if (nextDate < 0) return -1;
    2613            int dow = (nextDate + iDayOfWeekOffset) % 7;
    2614            if ((dayCode & Constants.DAY_CODES[dow]) != 0) return nextDate;
    2615        }
    2616    }
    2617
    2618    private boolean isFollowingDates(Placement p1, Placement p2, boolean btb) {
    2619        int ord1 = variables().indexOf(p1.variable());
    2620        int ord2 = variables().indexOf(p2.variable());
    2621        TimeLocation t1, t2;
    2622        boolean following = false;
    2623        if (ord1 < ord2) {
    2624            t1 = p1.getTimeLocation();
    2625            t2 = p2.getTimeLocation();
    2626            if (ord1 + 1 == ord2) following = true;
    2627        } else {
    2628            t2 = p1.getTimeLocation();
    2629            t1 = p2.getTimeLocation();
    2630            if (ord2 + 1 == ord1) following = true;
    2631        }
    2632        int d1 = nextDate(t1.getWeekCode(), t1.getDayCode(), -1);
    2633        int d2 = nextDate(t2.getWeekCode(), t2.getDayCode(), -1);
    2634        while (d1 >= 0) {
    2635            int d1next = nextDate(t1.getWeekCode(), t1.getDayCode(), d1);
    2636            int d2next = nextDate(t2.getWeekCode(), t2.getDayCode(), d2);
    2637            if (d1 >= d2) return false; // next date of p2 is before or on d1 (or there is no next date)
    2638            // d1 < d2 (d1 before d2)
    2639            if (d1next >= 0 && d2 >= d1next) return false; // p1 has a next date, but p2 date is not before that date
    2640            // d1next < 0 || d2 < d1next (no next d1, or d2 before next d2
    2641            if (!btb && d1 + 1 == d2) return false; // p2 is on a following day of p1
    2642            // btb || d1 + 1 < d2 (back-to-back or at least one day gap in between)
    2643            if (btb && following && d1 + 1 != d2) return false; // d2 is not on the next date from d1
    2644            // !following || d1 + 1 == d2 (not following or on the next day)
    2645            d1 = d1next; d2 = d2next;
    2646        }
    2647        // d1 < 0 (no next d1), check that there is also no d2
    2648        return (d2 < 0); // both patterns have ended
    2649    }
    2650
    2651    protected boolean isOnline(Placement p) {
    2652        // no room -- StudentConflict.OnlineRoom must allow for a blank string
    2653        if (p.getNrRooms() == 0)
    2654            return "".matches(iOnlineRoom);
    2655        // one room -- room name must match StudentConflict.OnlineRoom
    2656        if (p.getNrRooms() == 1)
    2657            return (p.getRoomLocation().getName() != null && p.getRoomLocation().getName().matches(iOnlineRoom));
    2658        // multiple rooms -- all rooms must match StudentConflict.OnlineRoom
    2659        for (RoomLocation r: p.getRoomLocations())
    2660            if (r.getName() == null || !r.getName().matches(iOnlineRoom)) return false;
    2661        return true;
    2662    }
    2663}