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