    001package net.sf.cpsolver.coursett.constraint;
    002
    003import java.util.ArrayList;
    004import java.util.HashSet;
    005import java.util.HashMap;
    006import java.util.Iterator;
    007import java.util.List;
    008import java.util.Set;
    009
    010import net.sf.cpsolver.coursett.Constants;
    011import net.sf.cpsolver.coursett.criteria.DistributionPreferences;
    012import net.sf.cpsolver.coursett.model.Lecture;
    013import net.sf.cpsolver.coursett.model.Placement;
    014import net.sf.cpsolver.coursett.model.TimeLocation;
    015import net.sf.cpsolver.coursett.model.TimetableModel;
    016import net.sf.cpsolver.ifs.model.Constraint;
    017import net.sf.cpsolver.ifs.model.GlobalConstraint;
    018import net.sf.cpsolver.ifs.model.Model;
    019import net.sf.cpsolver.ifs.model.WeakeningConstraint;
    020import net.sf.cpsolver.ifs.util.DataProperties;
    021import net.sf.cpsolver.ifs.util.DistanceMetric;
    022import net.sf.cpsolver.ifs.util.ToolBox;
    023
    024/**
    025 * Group constraint. <br>
    026 * This constraint expresses relations between several classes, e.g., that two
    027 * sections of the same lecture can not be taught at the same time, or that some
    028 * classes have to be taught one immediately after another. It can be either
    029 * hard or soft. <br>
    030 * <br>
    031 * Following constraints are now supported:
    032 * <table border='1'>
    033 * <tr>
    034 * <th>Constraint</th>
    035 * <th>Comment</th>
    036 * </tr>
    037 * <tr>
    038 * <td>SAME_TIME</td>
    039 * <td>Same time: given classes have to be taught in the same hours. If the
    040 * classes are of different length, the smaller one cannot start before the
    041 * longer one and it cannot end after the longer one.</td>
    042 * </tr>
    043 * <tr>
    044 * <td>SAME_DAYS</td>
    045 * <td>Same days: given classes have to be taught in the same day. If the
    046 * classes are of different time patterns, the days of one class have to form a
    047 * subset of the days of the other class.</td>
    048 * </tr>
    049 * <tr>
    050 * <td>BTB</td>
    051 * <td>Back-to-back constraint: given classes have to be taught in the same room
    052 * and they have to follow one strictly after another.</td>
    053 * </tr>
    054 * <tr>
    055 * <td>BTB_TIME</td>
    056 * <td>Back-to-back constraint: given classes have to follow one strictly after
    057 * another, but they can be taught in different rooms.</td>
    058 * </tr>
    059 * <tr>
    060 * <td>DIFF_TIME</td>
    061 * <td>Different time: given classes cannot overlap in time.</td>
    062 * </tr>
    063 * <tr>
    064 * <td>NHB(1), NHB(1.5), NHB(2), ... NHB(8)</td>
    065 * <td>Number of hours between: between the given classes, the exact number of
    066 * hours have to be kept.</td>
    067 * </tr>
    068 * <tr>
    069 * <td>SAME_START</td>
    070 * <td>Same starting hour: given classes have to start in the same hour.</td>
    071 * </tr>
    072 * <tr>
    073 * <td>SAME_ROOM</td>
    074 * <td>Same room: given classes have to be placed in the same room.</td>
    075 * </tr>
    076 * <tr>
    077 * <td>NHB_GTE(1)</td>
    078 * <td>Greater than or equal to 1 hour between: between the given classes, the
    079 * number of hours have to be one or more.</td>
    080 * </tr>
    081 * <tr>
    082 * <td>NHB_LT(6)</td>
    083 * <td>Less than 6 hours between: between the given classes, the number of hours
    084 * have to be less than six.</td>
    085 * </tr>
    086 * </table>
    087 *
    088 * @version CourseTT 1.2 (University Course Timetabling)<br>
    089 *          Copyright (C) 2006 - 2010 Tomáš Müller<br>
    090 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    091 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    092 * <br>
    093 *          This library is free software; you can redistribute it and/or modify
    094 *          it under the terms of the GNU Lesser General Public License as
    095 *          published by the Free Software Foundation; either version 3 of the
    096 *          License, or (at your option) any later version. <br>
    097 * <br>
    098 *          This library is distributed in the hope that it will be useful, but
    099 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    100 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    101 *          Lesser General Public License for more details. <br>
    102 * <br>
    103 *          You should have received a copy of the GNU Lesser General Public
    104 *          License along with this library; if not see
    105 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    106 */
    107
    108public class GroupConstraint extends Constraint<Lecture, Placement> {
    109    private Long iConstraintId;
    110    private int iPreference;
    111    private ConstraintType iType;
    112    private boolean iIsRequired;
    113    private boolean iIsProhibited;
    114    private int iLastPreference = 0;
    115    private int iDayOfWeekOffset = 0;
    116    private boolean iPrecedenceConsiderDatePatterns = true;
    117    private int iForwardCheckMaxDepth = 2;
    118    private int iForwardCheckMaxDomainSize = 1000;
    119
    120    /**
    121     * Group constraints that can be checked on pairs of classes (e.g., same room means any two classes are in the same room),
    122     * only need to implement this interface.
    123     */
    124    public static interface PairCheck {
    125        /**
    126         * Check whether the constraint is satisfied for the given two assignments (required / preferred case)
    127         * @param gc Calling group constraint
    128         * @param plc1 First placement
    129         * @param plc2 Second placement
    130         * @return true if constraint is satisfied
    131         */
    132        public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2);
    133        /**
    134         * Check whether the constraint is satisfied for the given two assignments (prohibited / discouraged case)
    135         * @param gc Calling group constraint
    136         * @param plc1 First placement
    137         * @param plc2 Second placement
    138         * @return true if constraint is satisfied
    139         */
    140        public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2);
    141    }
    142
    143    /**
    144     * Group constraint building blocks (individual constraints that need more than {@link PairCheck})
    145     */
    146    public static enum Flag {
    147        /** Back-to-back constraint (sequence check) */
    148        BACK_TO_BACK,
    149        /** Can share room flag */
    150        CAN_SHARE_ROOM,
    151        /** Maximum hours a day (number of slots a day check) */
    152        MAX_HRS_DAY,
    153        /** Children cannot overlap */
    154        CH_NOTOVERLAP;
    155        /** Bit number (to combine flags) */
    156        int flag() { return 1 << ordinal(); }
    157    }
    158
    159    /**
    160     * Group constraint type.
    161     */
    162    public static enum ConstraintType {
    163        /**
    164         * Same Time: Given classes must be taught at the same time of day (independent of the actual day the classes meet).
    165         * For the classes of the same length, this is the same constraint as same start. For classes of different length,
    166         * the shorter one cannot start before, nor end after, the longer one.<BR>
    167         * When prohibited or (strongly) discouraged: one class may not meet on any day at a time of day that overlaps with
    168         * that of the other. For example, one class can not meet M 7:30 while the other meets F 7:30. Note the difference
    169         * here from the different time constraint that only prohibits the actual class meetings from overlapping.
    170         */
    171        SAME_TIME("SAME_TIME", "Same Time", new PairCheck() {
    172            @Override
    173            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    174                return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(),
    175                        plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength());
    176            }
    177            @Override
    178            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    179                return !(plc1.getTimeLocation().shareHours(plc2.getTimeLocation()));
    180            }}),
    181        /**
    182         * Same Days: Given classes must be taught on the same days. In case of classes of different time patterns, a class
    183         * with fewer meetings must meet on a subset of the days used by the class with more meetings. For example, if one
    184         * class pattern is 3x50, all others given in the constraint can only be taught on Monday, Wednesday, or Friday.
    185         * For a 2x100 class MW, MF, WF is allowed but TTh is prohibited.<BR>
    186         * When prohibited or (strongly) discouraged: any pair of classes classes cannot be taught on the same days (cannot
    187         *  overlap in days). For instance, if one class is MFW, the second has to be TTh.
    188         */
    189        SAME_DAYS("SAME_DAYS", "Same Days", new PairCheck() {
    190            @Override
    191            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    192                return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
    193            }
    194            @Override
    195            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    196                return !plc1.getTimeLocation().shareDays(plc2.getTimeLocation());
    197            }}),
    198        /**
    199         * Back-To-Back &amp; Same Room: Classes must be offered in adjacent time segments and must be placed in the same room.
    200         * Given classes must also be taught on the same days.<BR>
    201         * When prohibited or (strongly) discouraged: classes cannot be back-to-back. There must be at least half-hour
    202         * between these classes, and they must be taught on the same days and in the same room.
    203         */
    204        BTB("BTB", "Back-To-Back & Same Room", new PairCheck() {
    205            @Override
    206            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    207                return
    208                    plc1.sameRooms(plc2) &&
    209                    sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
    210            }
    211            @Override
    212            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    213                return
    214                    plc1.sameRooms(plc2) &&
    215                    sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
    216            }}, Flag.BACK_TO_BACK),
    217        /**
    218         * Back-To-Back: Classes must be offered in adjacent time segments but may be placed in different rooms. Given classes
    219         * must also be taught on the same days.<BR>
    220         * When prohibited or (strongly) discouraged: no pair of classes can be taught back-to-back. They may not overlap in time,
    221         * but must be taught on the same days. This means that there must be at least half-hour between these classes.
    222         */
    223        BTB_TIME("BTB_TIME", "Back-To-Back", new PairCheck() {
    224            @Override
    225            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    226                return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
    227            }
    228            @Override
    229            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    230                return sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
    231            }}, Flag.BACK_TO_BACK),
    232        /**
    233         * Different Time: Given classes cannot overlap in time. They may be taught at the same time of day if they are on
    234         * different days. For instance, MF 7:30 is compatible with TTh 7:30.<BR>
    235         * When prohibited or (strongly) discouraged: every pair of classes in the constraint must overlap in time.
    236         */
    237        DIFF_TIME("DIFF_TIME", "Different Time", new PairCheck() {
    238            @Override
    239            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    240                return !plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation());
    241            }
    242            @Override
    243            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    244                return plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation());
    245            }}),
    246        /**
    247         * 1 Hour Between: Given classes must have exactly 1 hour in between the end of one and the beginning of another.
    248         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
    249         * When prohibited or (strongly) discouraged: classes can not have 1 hour in between. They may not overlap in time
    250         * but must be taught on the same days.
    251         */
    252        NHB_1("NHB(1)", "1 Hour Between", 10, 12, BTB_TIME.check(), Flag.BACK_TO_BACK),
    253        /**
    254         * 2 Hours Between: Given classes must have exactly 2 hours in between the end of one and the beginning of another.
    255         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
    256         * When prohibited or (strongly) discouraged: classes can not have 2 hours in between. They may not overlap in time
    257         * but must be taught on the same days.
    258         */
    259        NHB_2("NHB(2)", "2 Hours Between", 20, 24, BTB_TIME.check(), Flag.BACK_TO_BACK),
    260        /**
    261         * 3 Hours Between: Given classes must have exactly 3 hours in between the end of one and the beginning of another.
    262         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
    263         * When prohibited or (strongly) discouraged: classes can not have 3 hours in between. They may not overlap in time
    264         * but must be taught on the same days.
    265         */
    266        NHB_3("NHB(3)", "3 Hours Between", 30, 36, BTB_TIME.check(), Flag.BACK_TO_BACK),
    267        /**
    268         * 4 Hours Between: Given classes must have exactly 4 hours in between the end of one and the beginning of another.
    269         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
    270         * When prohibited or (strongly) discouraged: classes can not have 4 hours in between. They may not overlap in time
    271         * but must be taught on the same days.
    272         */
    273        NHB_4("NHB(4)", "4 Hours Between", 40, 48, BTB_TIME.check(), Flag.BACK_TO_BACK),
    274        /**
    275         * 5 Hours Between: Given classes must have exactly 5 hours in between the end of one and the beginning of another.
    276         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
    277         * When prohibited or (strongly) discouraged: classes can not have 5 hours in between. They may not overlap in time
    278         * but must be taught on the same days.
    279         */
    280        NHB_5("NHB(5)", "5 Hours Between", 50, 60, BTB_TIME.check(), Flag.BACK_TO_BACK),
    281        /**
    282         * 6 Hours Between: Given classes must have exactly 6 hours in between the end of one and the beginning of another.
    283         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
    284         * When prohibited or (strongly) discouraged: classes can not have 6 hours in between. They may not overlap in time
    285         * but must be taught on the same days.
    286         */
    287        NHB_6("NHB(6)", "6 Hours Between", 60, 72, BTB_TIME.check(), Flag.BACK_TO_BACK),
    288        /**
    289         * 7 Hours Between: Given classes must have exactly 7 hours in between the end of one and the beginning of another.
    290         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
    291         * When prohibited or (strongly) discouraged: classes can not have 7 hours in between. They may not overlap in time
    292         * but must be taught on the same days.
    293         */
    294        NHB_7("NHB(7)", "7 Hours Between", 70, 84, BTB_TIME.check(), Flag.BACK_TO_BACK),
    295        /**
    296         * 8 Hours Between: Given classes must have exactly 8 hours in between the end of one and the beginning of another.
    297         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
    298         * When prohibited or (strongly) discouraged: classes can not have 8 hours in between. They may not overlap in time
    299         * but must be taught on the same days.
    300         */
    301        NHB_8("NHB(8)", "8 Hours Between", 80, 96, BTB_TIME.check(), Flag.BACK_TO_BACK),
    302        /**
    303         * Same Start Time: Given classes must start during the same half-hour period of a day (independent of the actual
    304         * day the classes meet). For instance, MW 7:30 is compatible with TTh 7:30 but not with MWF 8:00.<BR>
    305         * When prohibited or (strongly) discouraged: any pair of classes in the given constraint cannot start during the
    306         * same half-hour period of any day of the week.
    307         */
    308        SAME_START("SAME_START", "Same Start Time", new PairCheck() {
    309            @Override
    310            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    311                return
    312                    (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) ==
    313                    (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY);
    314            }
    315            @Override
    316            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    317                return
    318                    (plc1.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY) !=
    319                    (plc2.getTimeLocation().getStartSlot() % Constants.SLOTS_PER_DAY);
    320            }}),
    321        /**
    322         * Same Room: Given classes must be taught in the same room.<BR>
    323         * When prohibited or (strongly) discouraged: any pair of classes in the constraint cannot be taught in the same room.
    324         */
    325        SAME_ROOM("SAME_ROOM", "Same Room", new PairCheck() {
    326            @Override
    327            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    328                return plc1.sameRooms(plc2);
    329            }
    330            @Override
    331            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    332                return !plc1.sameRooms(plc2);
    333            }}),
    334        /**
    335         * At Least 1 Hour Between: Given classes have to have 1 hour or more in between.<BR>
    336         * When prohibited or (strongly) discouraged: given classes have to have less than 1 hour in between.
    337         */
    338        NHB_GTE_1("NHB_GTE(1)", "At Least 1 Hour Between", 6, 288, BTB_TIME.check(), Flag.BACK_TO_BACK),
    339        /**
    340         * Less Than 6 Hours Between: Given classes must have less than 6 hours from end of first class to the beginning of
    341         * the next. Given classes must also be taught on the same days.<BR>
    342         * When prohibited or (strongly) discouraged: given classes must have 6 or more hours between. This constraint does
    343         * not carry over from classes taught at the end of one day to the beginning of the next.
    344         */
    345        NHB_LT_6("NHB_LT(6)", "Less Than 6 Hours Between", 0, 72, BTB_TIME.check(), Flag.BACK_TO_BACK),
    346        /**
    347         * 1.5 Hour Between: Given classes must have exactly 90 minutes in between the end of one and the beginning of another.
    348         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
    349         * When prohibited or (strongly) discouraged: classes can not have 90 minutes in between. They may not overlap in time
    350         * but must be taught on the same days.
    351         */
    352        NHB_1_5("NHB(1.5)", "1.5 Hour Between", 15, 18, BTB_TIME.check(), Flag.BACK_TO_BACK),
    353        /**
    354         * 4.5 Hours Between: Given classes must have exactly 4.5 hours in between the end of one and the beginning of another.
    355         * As with the <i>back-to-back time</i> constraint, given classes must be taught on the same days.<BR>
    356         * When prohibited or (strongly) discouraged: classes can not have 4.5 hours in between. They may not overlap in time
    357         * but must be taught on the same days.
    358         */
    359        NHB_4_5("NHB(4.5)", "4.5 Hours Between", 45, 54, BTB_TIME.check(), Flag.BACK_TO_BACK),
    360        /**
    361         * Same Students: Given classes are treated as they are attended by the same students, i.e., they cannot overlap in time
    362         * and if they are back-to-back the assigned rooms cannot be too far (student limit is used).
    363         */
    364        SAME_STUDENTS("SAME_STUDENTS", "Same Students", new PairCheck() {
    365            @Override
    366            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    367                return !JenrlConstraint.isInConflict(plc1, plc2, ((TimetableModel)gc.getModel()).getDistanceMetric());
    368            }
    369            @Override
    370            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    371                return true;
    372            }}),
    373        /**
    374         * Same Instructor: Given classes are treated as they are taught by the same instructor, i.e., they cannot overlap in time
    375         * and if they are back-to-back the assigned rooms cannot be too far (instructor limit is used).<BR>
    376         * If the constraint is required and the classes are back-to-back, discouraged and strongly discouraged distances between
    377         * assigned rooms are also considered.
    378         */
    379        SAME_INSTR("SAME_INSTR", "Same Instructor", new PairCheck() {
    380            @Override
    381            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    382                TimeLocation t1 = plc1.getTimeLocation(), t2 = plc2.getTimeLocation();
    383                if (t1.shareDays(t2) && t1.shareWeeks(t2)) {
    384                    if (t1.shareHours(t2)) return false; // overlap
    385                    DistanceMetric m = ((TimetableModel)gc.getModel()).getDistanceMetric();
    386                    if ((t1.getStartSlot() + t1.getLength() == t2.getStartSlot() || t2.getStartSlot() + t2.getLength() == t1.getStartSlot())) {
    387                        if (Placement.getDistanceInMeters(m, plc1, plc2) > m.getInstructorProhibitedLimit())
    388                            return false;
    389                    } else if (m.doComputeDistanceConflictsBetweenNonBTBClasses()) {
    390                        if (t1.getStartSlot() + t1.getLength() < t2.getStartSlot() &&
    391                            Placement.getDistanceInMinutes(m, plc1, plc2) > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t2.getStartSlot() - t1.getStartSlot() - t1.getLength()))
    392                            return false;
    393                        if (t2.getStartSlot() + t2.getLength() < t1.getStartSlot() &&
    394                            Placement.getDistanceInMinutes(m, plc1, plc2) > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t1.getStartSlot() - t2.getStartSlot() - t2.getLength()))
    395                            return false;
    396                    }
    397                }
    398                return true;
    399            }
    400            @Override
    401            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    402                return true;
    403            }}),
    404        /**
    405         * Can Share Room: Given classes can share the room (use the room in the same time) if the room is big enough.
    406         */
    407        CAN_SHARE_ROOM("CAN_SHARE_ROOM", "Can Share Room", null, Flag.CAN_SHARE_ROOM),
    408        /**
    409         * Precedence: Given classes have to be taught in the given order (the first meeting of the first class has to end before
    410         * the first meeting of the second class etc.)<BR>
    411         * When prohibited or (strongly) discouraged: classes have to be taught in the order reverse to the given one.
    412         */
    413        PRECEDENCE("PRECEDENCE", "Precedence", new PairCheck() {
    414            @Override
    415            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    416                return gc.isPrecedence(plc1, plc2, true, true);
    417            }
    418            @Override
    419            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    420                return gc.isPrecedence(plc1, plc2, false, true);
    421            }}),
    422        /**
    423         * Back-To-Back Day: Classes must be offered on adjacent days and may be placed in different rooms.<BR>
    424         * When prohibited or (strongly) discouraged: classes can not be taught on adjacent days. They also can not be taught
    425         * on the same days. This means that there must be at least one day between these classes.
    426         */
    427        BTB_DAY("BTB_DAY", "Back-To-Back Day", new PairCheck() {
    428            @Override
    429            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    430                return
    431                    !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
    432                    isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation());
    433            }
    434            @Override
    435            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    436                return
    437                    !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
    438                    !isBackToBackDays(plc1.getTimeLocation(), plc2.getTimeLocation());
    439            }}),
    440        /**
    441         * Meet Together: Given classes are meeting together (same as if the given classes require constraints Can Share Room,
    442         * Same Room, Same Time and Same Days all together).
    443         */
    444        MEET_WITH("MEET_WITH", "Meet Together", new PairCheck() {
    445            @Override
    446            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    447                return
    448                        plc1.sameRooms(plc2) &&
    449                        sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(),
    450                                plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) &&
    451                        sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
    452
    453            }
    454            @Override
    455            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    456                return true;
    457            }}, Flag.CAN_SHARE_ROOM),
    458        /**
    459         * More Than 1 Day Between: Given classes must have two or more days in between.<br>
    460         * When prohibited or (strongly) discouraged: given classes must be offered on adjacent days or with at most one day in between.
    461         */
    462        NDB_GT_1("NDB_GT_1", "More Than 1 Day Between", new PairCheck() {
    463            @Override
    464            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    465                return
    466                    !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
    467                    isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation());
    468            }
    469            @Override
    470            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    471                return
    472                    !sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
    473                    !isNrDaysBetweenGreaterThanOne(plc1.getTimeLocation(), plc2.getTimeLocation());
    474            }}),
    475        /**
    476         * Children Cannot Overlap: If parent classes do not overlap in time, children classes can not overlap in time as well.<BR>
    477         * Note: This constraint only needs to be put on the parent classes. Preferred configurations are Required All Classes
    478         * or Pairwise (Strongly) Preferred.
    479         */
    480        CH_NOTOVERLAP("CH_NOTOVERLAP", "Children Cannot Overlap", new PairCheck() {
    481            @Override
    482            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    483                return gc.isChildrenNotOverlap(plc1.variable(), plc1, plc2.variable(), plc2);
    484            }
    485            @Override
    486            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    487                return true;
    488            }}),
    489        /**
    490         * Next Day: The second class has to be placed on the following day of the first class (if the first class is on Friday,
    491         * second class have to be on Monday).<br>
    492         * When prohibited or (strongly) discouraged: The second class has to be placed on the previous day of the first class
    493         * (if the first class is on Monday, second class have to be on Friday).<br>
    494         * Note: This constraint works only between pairs of classes.
    495         */
    496        FOLLOWING_DAY("FOLLOWING_DAY", "Next Day", new PairCheck() {
    497            @Override
    498            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    499                return gc.isFollowingDay(plc1, plc2, true);
    500            }
    501            @Override
    502            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    503                return gc.isFollowingDay(plc1, plc2, false);
    504            }}),
    505        /**
    506         * Two Days After: The second class has to be placed two days after the first class (Monday &rarr; Wednesday, Tuesday &rarr;
    507         * Thurday, Wednesday &rarr; Friday, Thursday &rarr; Monday, Friday &rarr; Tuesday).<br>
    508         * When prohibited or (strongly) discouraged: The second class has to be placed two days before the first class (Monday &rarr;
    509         * Thursday, Tuesday &rarr; Friday, Wednesday &rarr; Monday, Thursday &rarr; Tuesday, Friday &rarr; Wednesday).<br>
    510         * Note: This constraint works only between pairs of classes.
    511         */
    512        EVERY_OTHER_DAY("EVERY_OTHER_DAY", "Two Days After", new PairCheck() {
    513            @Override
    514            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    515                return gc.isEveryOtherDay(plc1, plc2, true);
    516            }
    517            @Override
    518            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    519                return gc.isEveryOtherDay(plc1, plc2, false);
    520            }}),
    521        /**
    522          * 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.
    523          */
    524        MAX_HRS_DAY_5("MAX_HRS_DAY(5)", "At Most 5 Hours A Day", 60, null, Flag.MAX_HRS_DAY),
    525        /**
    526         * 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.
    527         */
    528        MAX_HRS_DAY_6("MAX_HRS_DAY(6)", "At Most 6 Hours A Day", 72, null, Flag.MAX_HRS_DAY),
    529        /**
    530         * 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.
    531         */
    532        MAX_HRS_DAY_7("MAX_HRS_DAY(7)", "At Most 7 Hours A Day", 84, null, Flag.MAX_HRS_DAY),
    533        /**
    534         * 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.
    535         */
    536        MAX_HRS_DAY_8("MAX_HRS_DAY(8)", "At Most 8 Hours A Day", 96, null, Flag.MAX_HRS_DAY),
    537        /**
    538         * Given classes must be taught during the same weeks (i.e., must have the same date pattern).<br>
    539         * When prohibited or (strongly) discouraged: any two classes must have non overlapping date patterns.
    540         */
    541        SAME_WEEKS("SAME_WEEKS", "Same Weeks", new PairCheck() {
    542            @Override
    543            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    544                return plc1.getTimeLocation().getWeekCode().equals(plc2.getTimeLocation().getWeekCode());
    545            }
    546            @Override
    547            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    548                return !plc1.getTimeLocation().shareWeeks(plc2.getTimeLocation());
    549            }}),
    550        /**
    551         * Classes (of different courses) are to be attended by the same students. For instance,
    552         * if class A1 (of a course A) and class B1 (of a course B) are linked, a student requesting
    553         * both courses must attend A1 if and only if he also attends B1. This is a student sectioning
    554         * constraint that is interpreted as Same Students constraint during course timetabling.
    555         */
    556        LINKED_SECTIONS("LINKED_SECTIONS", "Linked Classes", SAME_STUDENTS.check()),
    557        /**
    558         * Back-To-Back Precedence: Given classes have to be taught in the given order, on the same days,
    559         * and in adjacent time segments.
    560         * When prohibited or (strongly) discouraged: Given classes have to be taught in the given order,
    561         * on the same days, but cannot be back-to-back.
    562         */
    563        BTB_PRECEDENCE("BTB_PRECEDENCE", "Back-To-Back Precedence", new PairCheck() {
    564            @Override
    565            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    566                return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
    567            }
    568            @Override
    569            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    570                return gc.isPrecedence(plc1, plc2, true, false) && sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
    571            }}, Flag.BACK_TO_BACK),
    572
    573        /**
    574         * Same Days-Time: Given classes must be taught at the same time of day and on the same days.
    575         * It is the combination of Same Days and Same Time distribution preferences.
    576         * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days
    577         * during the same time.
    578         */
    579        SAME_DAYS_TIME("SAME_D_T", "Same Days-Time", new PairCheck() {
    580            @Override
    581            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    582                return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(),
    583                        plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) &&
    584                        sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray());
    585            }
    586            @Override
    587            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    588                return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) ||
    589                        !plc1.getTimeLocation().shareDays(plc2.getTimeLocation());
    590            }}),
    591        /**
    592         * Same Days-Room-Time: Given classes must be taught at the same time of day, on the same days and in the same room.
    593         * It is the combination of Same Days, Same Time and Same Room distribution preferences.
    594         * Note that this constraint is the same as Meet Together constraint, except it does not allow room sharing. In other words,
    595         * it is only useful when these classes are taught during non-overlapping date patterns.
    596         * When prohibited or (strongly) discouraged: Any pair of classes classes cannot be taught on the same days
    597         * during the same time in the same room.
    598         */
    599        SAME_DAYS_ROOM_TIME("SAME_D_R_T", "Same Days-Room-Time", new PairCheck() {
    600            @Override
    601            public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) {
    602                return sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(),
    603                        plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()) &&
    604                        sameDays(plc1.getTimeLocation().getDaysArray(), plc2.getTimeLocation().getDaysArray()) &&
    605                        plc1.sameRooms(plc2);
    606            }
    607            @Override
    608            public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) {
    609                return !plc1.getTimeLocation().shareHours(plc2.getTimeLocation()) ||
    610                        !plc1.getTimeLocation().shareDays(plc2.getTimeLocation()) ||
    611                        !plc1.sameRooms(plc2);
    612            }}),
    613        ;
    614
    615        String iReference, iName;
    616        int iFlag = 0;
    617        Flag[] iFlags = null;
    618        int iMin = 0, iMax = 0;
    619        PairCheck iCheck = null;
    620        ConstraintType(String reference, String name, PairCheck check, Flag... flags) {
    621            iReference = reference;
    622            iName = name;
    623            iCheck = check;
    624            iFlags = flags;
    625            for (Flag f: flags)
    626                iFlag |= f.flag();
    627        }
    628        ConstraintType(String reference, String name, int limit, PairCheck check, Flag... flags) {
    629            this(reference, name, check, flags);
    630            iMin = iMax = limit;
    631        }
    632        ConstraintType(String reference, String name, int min, int max, PairCheck check, Flag... flags) {
    633            this(reference, name, check, flags);
    634            iMin = min;
    635            iMax = max;
    636        }
    637
    638        /** Constraint reference */
    639        public String reference() { return iReference; }
    640        /** Constraint name */
    641        public String getName() { return iName; }
    642        /** Minimum (gap) parameter */
    643        public int getMin() { return iMin; }
    644        /** Maximum (gap, hours a day) parameter */
    645        public int getMax() { return iMax; }
    646
    647        /** Flag check (true if contains given flag) */
    648        public boolean is(Flag f) { return (iFlag & f.flag()) != 0; }
    649
    650        /** Constraint type from reference */
    651        public static ConstraintType get(String reference) {
    652            for (ConstraintType t: ConstraintType.values())
    653                if (t.reference().equals(reference)) return t;
    654            return null;
    655        }
    656
    657        /** True if a required or preferred constraint is satisfied between a pair of placements */
    658        public boolean isSatisfied(GroupConstraint gc, Placement plc1, Placement plc2) { return (iCheck == null ? true : iCheck.isSatisfied(gc, plc1, plc2)); }
    659        /** True if a prohibited or discouraged constraint is satisfied between a pair of placements */
    660        public boolean isViolated(GroupConstraint gc, Placement plc1, Placement plc2) { return (iCheck == null ? true : iCheck.isViolated(gc, plc1, plc2)); }
    661        /** Pair check */
    662        private PairCheck check() { return iCheck; }
    663    }
    664
    665    public GroupConstraint() {
    666    }
    667
    668    @Override
    669    public void setModel(Model<Lecture, Placement> model) {
    670        super.setModel(model);
    671        if (model != null) {
    672            DataProperties config = ((TimetableModel)model).getProperties();
    673            iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0);
    674            iPrecedenceConsiderDatePatterns = config.getPropertyBoolean("Precedence.ConsiderDatePatterns", true);
    675            iForwardCheckMaxDepth = config.getPropertyInt("ForwardCheck.MaxDepth", iForwardCheckMaxDepth);
    676            iForwardCheckMaxDomainSize = config.getPropertyInt("ForwardCheck.MaxDomainSize", iForwardCheckMaxDomainSize);
    677        }
    678        if (!isHard()) {
    679            iLastPreference = getCurrentPreference();
    680            if (model != null)
    681                model.getCriterion(DistributionPreferences.class).inc(iLastPreference);
    682        }
    683    }
    684
    685    @Override
    686    public void addVariable(Lecture lecture) {
    687        if (!variables().contains(lecture))
    688            super.addVariable(lecture);
    689        if (getType().is(Flag.CH_NOTOVERLAP)) {
    690            if (lecture.getChildrenSubpartIds() != null) {
    691                for (Long subpartId: lecture.getChildrenSubpartIds()) {
    692                    for (Lecture ch : lecture.getChildren(subpartId)) {
    693                        if (!variables().contains(ch))
    694                            super.addVariable(ch);
    695                    }
    696                }
    697            }
    698        }
    699    }
    700
    701    @Override
    702    public void removeVariable(Lecture lecture) {
    703        if (variables().contains(lecture))
    704            super.removeVariable(lecture);
    705        if (getType().is(Flag.CH_NOTOVERLAP)) {
    706            if (lecture.getChildrenSubpartIds() != null) {
    707                for (Long subpartId: lecture.getChildrenSubpartIds()) {
    708                    for (Lecture ch : lecture.getChildren(subpartId)) {
    709                        if (variables().contains(ch))
    710                            super.removeVariable(ch);
    711                    }
    712                }
    713            }
    714        }
    715    }
    716
    717    /**
    718     * Constructor
    719     *
    720     * @param id
    721     *            constraint id
    722     * @param type
    723     *            constraString type (e.g, {@link ConstraintType#SAME_TIME})
    724     * @param preference
    725     *            time preference ("R" for required, "P" for prohibited, "-2",
    726     *            "-1", "1", "2" for soft preference)
    727     */
    728    public GroupConstraint(Long id, ConstraintType type, String preference) {
    729        iConstraintId = id;
    730        iType = type;
    731        iIsRequired = preference.equals(Constants.sPreferenceRequired);
    732        iIsProhibited = preference.equals(Constants.sPreferenceProhibited);
    733        iPreference = Constants.preference2preferenceLevel(preference);
    734    }
    735
    736    /** Constraint id */
    737    public Long getConstraintId() {
    738        return iConstraintId;
    739    }
    740
    741    @Override
    742    public long getId() {
    743        return (iConstraintId == null ? -1 : iConstraintId.longValue());
    744    }
    745
    746    /** Generated unique id */
    747    protected long getGeneratedId() {
    748        return iId;
    749    }
    750
    751    /** ConstraString type (e.g, {@link ConstraintType#SAME_TIME}) */
    752    public ConstraintType getType() {
    753        return iType;
    754    }
    755
    756    public void setType(ConstraintType type) {
    757        iType = type;
    758    }
    759
    760    /** Is constraint required */
    761    public boolean isRequired() {
    762        return iIsRequired;
    763    }
    764
    765    /** Is constraint prohibited */
    766    public boolean isProhibited() {
    767        return iIsProhibited;
    768    }
    769
    770    /**
    771     * Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for
    772     * preference
    773     */
    774    public String getPrologPreference() {
    775        return Constants.preferenceLevel2preference(iPreference);
    776    }
    777
    778    @Override
    779    public boolean isConsistent(Placement value1, Placement value2) {
    780        if (!isHard())
    781            return true;
    782        if (!isSatisfiedPair(value1, value2))
    783            return false;
    784        if (getType().is(Flag.BACK_TO_BACK)) {
    785            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    786            assignments.put(value1.variable(), value1);
    787            assignments.put(value2.variable(), value2);
    788            if (!isSatisfiedSeq(assignments, false, null))
    789                return false;
    790        }
    791        if (getType().is(Flag.MAX_HRS_DAY)) {
    792            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    793            assignments.put(value1.variable(), value1);
    794            assignments.put(value2.variable(), value2);
    795            for (int dayCode: Constants.DAY_CODES) {
    796                if (nrSlotsADay(dayCode, assignments, null) > getType().getMax())
    797                    return false;
    798            }
    799        }
    800        return true;
    801    }
    802
    803    @Override
    804    public void computeConflicts(Placement value, Set<Placement> conflicts) {
    805        if (!isHard())
    806            return;
    807        for (Lecture v : variables()) {
    808            if (v.equals(value.variable()))
    809                continue; // ignore this variable
    810            if (v.getAssignment() == null)
    811                continue; // there is an unassigned variable -- great, still a
    812                          // chance to get violated
    813            if (!isSatisfiedPair(v.getAssignment(), value))
    814                conflicts.add(v.getAssignment());
    815        }
    816        if (getType().is(Flag.BACK_TO_BACK)) {
    817            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    818            assignments.put(value.variable(), value);
    819            if (!isSatisfiedSeq(assignments, true, conflicts))
    820                conflicts.add(value);
    821        }
    822        if (getType().is(Flag.MAX_HRS_DAY)) {
    823            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    824            assignments.put(value.variable(), value);
    825            for (int dayCode: Constants.DAY_CODES) {
    826                if (nrSlotsADay(dayCode, assignments, conflicts) > getType().getMax()) {
    827                    List<Placement> adepts = new ArrayList<Placement>();
    828                    for (Lecture lecture: assignedVariables()) {
    829                        if (conflicts.contains(lecture.getAssignment()) || lecture.equals(value.variable())) continue;
    830                        if (lecture.getAssignment().getTimeLocation() == null) continue;
    831                        if ((lecture.getAssignment().getTimeLocation().getDayCode() & dayCode) == 0) continue;
    832                        adepts.add(lecture.getAssignment());
    833                    }
    834                    do {
    835                        Placement conflict = ToolBox.random(adepts);
    836                        adepts.remove(conflict);
    837                        conflicts.add(conflict);
    838                    } while (!adepts.isEmpty() && nrSlotsADay(dayCode, assignments, conflicts) > getType().getMax());
    839                }
    840            }
    841        }
    842
    843        // Forward checking
    844        forwardCheck(value, conflicts, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1);
    845    }
    846
    847    public void forwardCheck(Placement value, Set<Placement> conflicts, Set<GroupConstraint> ignore, int depth) {
    848        try {
    849            if (depth < 0) return;
    850            ignore.add(this);
    851
    852            int neededSize = value.variable().maxRoomUse();
    853
    854            for (Lecture lecture: variables()) {
    855                if (conflicts.contains(value)) break; // already conflicting
    856
    857                if (lecture.equals(value.variable())) continue; // Skip this lecture
    858                if (lecture.getAssignment() != null) { // Has assignment, check whether it is conflicting
    859                    if (isSatisfiedPair(value, lecture.getAssignment())) {
    860                        // Increase needed size if the assignment is of the same room and overlapping in time
    861                        if (canShareRoom() && sameRoomAndOverlaps(value, lecture.getAssignment())) {
    862                            neededSize += lecture.maxRoomUse();
    863                        }
    864                        continue;
    865                    }
    866                    conflicts.add(lecture.getAssignment());
    867                }
    868
    869                // Look for supporting assignments assignment
    870                boolean shareRoomAndOverlaps = canShareRoom();
    871                Placement support = null;
    872                int nrSupports = 0;
    873                if (lecture.nrValues() >= iForwardCheckMaxDomainSize) {
    874                    // ignore variables with large domains
    875                    return;
    876                }
    877                if (lecture.values().isEmpty()) {
    878                    // ignore variables with empty domain
    879                    return;
    880                }
    881                for (Placement other: lecture.values()) {
    882                    if (nrSupports < 2) {
    883                        if (isSatisfiedPair(value, other)) {
    884                            if (support == null) support = other;
    885                            nrSupports ++;
    886                            if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other))
    887                                shareRoomAndOverlaps = false;
    888                        }
    889                    } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(value, other)) {
    890                        shareRoomAndOverlaps = false;
    891                    }
    892                    if (nrSupports > 1 && !shareRoomAndOverlaps)
    893                        break;
    894                }
    895
    896                // No supporting assignment -> fail
    897                if (nrSupports == 0) {
    898                    conflicts.add(value); // other class cannot be assigned with this value
    899                    return;
    900                }
    901                // Increase needed size if all supporters are of the same room and in overlapping times
    902                if (shareRoomAndOverlaps) {
    903                    neededSize += lecture.maxRoomUse();
    904                }
    905
    906                // Only one supporter -> propagate the new assignment over other hard constraints of the lecture
    907                if (nrSupports == 1) {
    908                    for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) {
    909                        if (other instanceof WeakeningConstraint) continue;
    910                        if (other instanceof GroupConstraint) {
    911                            GroupConstraint gc = (GroupConstraint)other;
    912                            if (depth > 0 && !ignore.contains(gc))
    913                                gc.forwardCheck(support, conflicts, ignore, depth - 1);
    914                        } else {
    915                            other.computeConflicts(support, conflicts);
    916                        }
    917                    }
    918                    for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) {
    919                        if (other instanceof WeakeningConstraint) continue;
    920                        other.computeConflicts(support, conflicts);
    921                    }
    922
    923                    if (conflicts.contains(support))
    924                        conflicts.add(value);
    925                }
    926            }
    927
    928            if (canShareRoom() && neededSize > value.getRoomSize()) {
    929                // room is too small to fit all meet with classes
    930                conflicts.add(value);
    931            }
    932
    933        } finally {
    934            ignore.remove(this);
    935        }
    936    }
    937
    938    @Override
    939    public boolean inConflict(Placement value) {
    940        if (!isHard())
    941            return false;
    942        for (Lecture v : variables()) {
    943            if (v.equals(value.variable()))
    944                continue; // ignore this variable
    945            if (v.getAssignment() == null)
    946                continue; // there is an unassigned variable -- great, still a
    947                          // chance to get violated
    948            if (!isSatisfiedPair(v.getAssignment(), value))
    949                return true;
    950        }
    951        if (getType().is(Flag.BACK_TO_BACK)) {
    952            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    953            assignments.put(value.variable(), value);
    954            if (!isSatisfiedSeq(assignments, true, null))
    955                return true;
    956        }
    957        if (getType().is(Flag.MAX_HRS_DAY)) {
    958            HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>();
    959            assignments.put(value.variable(), value);
    960            for (int dayCode: Constants.DAY_CODES) {
    961                if (nrSlotsADay(dayCode, assignments, null) > getType().getMax())
    962                    return true;
    963            }
    964        }
    965
    966        if (!forwardCheck(value, new HashSet<GroupConstraint>(), iForwardCheckMaxDepth - 1)) return true;
    967
    968        return false;
    969    }
    970
    971    public boolean forwardCheck(Placement value, Set<GroupConstraint> ignore, int depth) {
    972        try {
    973            if (depth < 0) return true;
    974            ignore.add(this);
    975
    976            int neededSize = value.variable().maxRoomUse();
    977
    978            for (Lecture lecture: variables()) {
    979                if (lecture.equals(value.variable())) continue; // Skip this lecture
    980                if (lecture.getAssignment() != null) { // Has assignment, check whether it is conflicting
    981                    if (isSatisfiedPair(value, lecture.getAssignment())) {
    982                        // Increase needed size if the assignment is of the same room and overlapping in time
    983                        if (canShareRoom() && sameRoomAndOverlaps(value, lecture.getAssignment())) {
    984                            neededSize += lecture.maxRoomUse();
    985                        }
    986                        continue;
    987                    }
    988                    return false;
    989                }
    990
    991                // Look for supporting assignments assignment
    992                boolean shareRoomAndOverlaps = canShareRoom();
    993                Placement support = null;
    994                int nrSupports = 0;
    995                if (lecture.nrValues() >= iForwardCheckMaxDomainSize) {
    996                    // ignore variables with large domains
    997                    return true;
    998                }
    999                if (lecture.values().isEmpty()) {
    1000                    // ignore variables with empty domain
    1001                    return true;
    1002                }
    1003                for (Placement other: lecture.values()) {
    1004                    if (nrSupports < 2) {
    1005                        if (isSatisfiedPair(value, other)) {
    1006                            if (support == null) support = other;
    1007                            nrSupports ++;
    1008                            if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other))
    1009                                shareRoomAndOverlaps = false;
    1010                        }
    1011                    } else if (shareRoomAndOverlaps && !sameRoomAndOverlaps(value, other) && isSatisfiedPair(value, other)) {
    1012                        shareRoomAndOverlaps = false;
    1013                    }
    1014                    if (nrSupports > 1 && !shareRoomAndOverlaps)
    1015                        break;
    1016                }
    1017
    1018                // No supporting assignment -> fail
    1019                if (nrSupports == 0) {
    1020                    return false; // other class cannot be assigned with this value
    1021                }
    1022                // Increase needed size if all supporters are of the same room and in overlapping times
    1023                if (shareRoomAndOverlaps) {
    1024                    neededSize += lecture.maxRoomUse();
    1025                }
    1026
    1027                // Only one supporter -> propagate the new assignment over other hard constraints of the lecture
    1028                if (nrSupports == 1) {
    1029                    for (Constraint<Lecture, Placement> other: lecture.hardConstraints()) {
    1030                        if (other instanceof WeakeningConstraint) continue;
    1031                        if (other instanceof GroupConstraint) {
    1032                            GroupConstraint gc = (GroupConstraint)other;
    1033                            if (depth > 0 && !ignore.contains(gc) && !gc.forwardCheck(support, ignore, depth - 1)) return false;
    1034                        } else {
    1035                            if (other.inConflict(support)) return false;
    1036                        }
    1037                    }
    1038                    for (GlobalConstraint<Lecture, Placement> other: getModel().globalConstraints()) {
    1039                        if (other instanceof WeakeningConstraint) continue;
    1040                        if (other.inConflict(support)) return false;
    1041                    }
    1042                }
    1043            }
    1044
    1045            if (canShareRoom() && neededSize > value.getRoomSize()) {
    1046                // room is too small to fit all meet with classes
    1047                return false;
    1048            }
    1049
    1050            return true;
    1051        } finally {
    1052            ignore.remove(this);
    1053        }
    1054    }
    1055
    1056    /** Constraint preference (0 if prohibited or reqired) */
    1057    public int getPreference() {
    1058        return iPreference;
    1059    }
    1060
    1061    /**
    1062     * Current constraint preference (0 if prohibited or reqired, depends on
    1063     * current satisfaction of the constraint)
    1064     */
    1065    public int getCurrentPreference() {
    1066        if (isHard()) return 0; // no preference
    1067        if (countAssignedVariables() < 2) return - Math.abs(iPreference); // not enough variable
    1068        if (getType().is(Flag.MAX_HRS_DAY)) { // max hours a day
    1069            int over = 0;
    1070            for (int dayCode: Constants.DAY_CODES)
    1071                over += Math.max(0, nrSlotsADay(dayCode, null, null) - getType().getMax());
    1072            return (over > 0 ? Math.abs(iPreference) * over / 12 : - Math.abs(iPreference));
    1073        }
    1074        int nrViolatedPairs = 0;
    1075        for (Lecture v1 : variables()) {
    1076            if (v1.getAssignment() == null) continue;
    1077            for (Lecture v2 : variables()) {
    1078                if (v2.getAssignment() == null || v1.getId() >= v2.getId()) continue;
    1079                if (!isSatisfiedPair(v1.getAssignment(), v2.getAssignment())) nrViolatedPairs++;
    1080            }
    1081        }
    1082        if (getType().is(Flag.BACK_TO_BACK)) {
    1083            Set<Placement> conflicts = new HashSet<Placement>();
    1084            if (isSatisfiedSeq(new HashMap<Lecture, Placement>(), true, conflicts))
    1085                nrViolatedPairs += conflicts.size();
    1086            else
    1087                nrViolatedPairs = variables().size();
    1088        }
    1089        return (nrViolatedPairs > 0 ? Math.abs(iPreference) * nrViolatedPairs : - Math.abs(iPreference));
    1090    }
    1091
    1092    /** Current constraint preference change (if given placement is assigned) */
    1093    public int getCurrentPreference(Placement placement) {
    1094        if (isHard()) return 0; // no preference
    1095        if (countAssignedVariables() + (placement.variable().getAssignment() == null ? 1 : 0) < 2) return 0; // not enough variable
    1096        if (getType().is(Flag.MAX_HRS_DAY)) {
    1097            HashMap<Lecture, Placement> assignment = new HashMap<Lecture, Placement>();
    1098            assignment.put(placement.variable(), placement);
    1099            HashMap<Lecture, Placement> unassignment = new HashMap<Lecture, Placement>();
    1100            unassignment.put(placement.variable(), null);
    1101            int after = 0;
    1102            int before = 0;
    1103            for (int dayCode: Constants.DAY_CODES) {
    1104                after += Math.max(0, nrSlotsADay(dayCode, assignment, null) - getType().getMax());
    1105                before += Math.max(0, nrSlotsADay(dayCode, unassignment, null) - getType().getMax());
    1106            }
    1107            return (after > 0 ? Math.abs(iPreference) * after / 12 : - Math.abs(iPreference)) - (before > 0 ? Math.abs(iPreference) * before / 12 : - Math.abs(iPreference));
    1108        }
    1109
    1110        int nrViolatedPairsAfter = 0;
    1111        int nrViolatedPairsBefore = 0;
    1112        for (Lecture v1 : variables()) {
    1113            for (Lecture v2 : variables()) {
    1114                if (v1.getId() >= v2.getId()) continue;
    1115                Placement p1 = (v1.equals(placement.variable()) ? null : v1.getAssignment());
    1116                Placement p2 = (v2.equals(placement.variable()) ? null : v2.getAssignment());
    1117                if (p1 != null && p2 != null && !isSatisfiedPair(p1, p2))
    1118                    nrViolatedPairsBefore ++;
    1119                if (v1.equals(placement.variable())) p1 = placement;
    1120                if (v2.equals(placement.variable())) p2 = placement;
    1121                if (p1 != null && p2 != null && !isSatisfiedPair(p1, p2))
    1122                    nrViolatedPairsAfter ++;
    1123            }
    1124        }
    1125
    1126        if (getType().is(Flag.BACK_TO_BACK)) {
    1127            HashMap<Lecture, Placement> assignment = new HashMap<Lecture, Placement>();
    1128            assignment.put(placement.variable(), placement);
    1129            Set<Placement> conflicts = new HashSet<Placement>();
    1130            if (isSatisfiedSeq(assignment, true, conflicts))
    1131                nrViolatedPairsAfter += conflicts.size();
    1132            else
    1133                nrViolatedPairsAfter = variables().size();
    1134
    1135            HashMap<Lecture, Placement> unassignment = new HashMap<Lecture, Placement>();
    1136            unassignment.put(placement.variable(), null);
    1137            Set<Placement> previous = new HashSet<Placement>();
    1138            if (isSatisfiedSeq(unassignment, true, previous))
    1139                nrViolatedPairsBefore += previous.size();
    1140            else
    1141                nrViolatedPairsBefore = variables().size();
    1142        }
    1143
    1144        return (nrViolatedPairsAfter > 0 ? Math.abs(iPreference) * nrViolatedPairsAfter : - Math.abs(iPreference)) -
    1145                (nrViolatedPairsBefore > 0 ? Math.abs(iPreference) * nrViolatedPairsBefore : - Math.abs(iPreference));
    1146    }
    1147
    1148    @Override
    1149    public void unassigned(long iteration, Placement value) {
    1150        super.unassigned(iteration, value);
    1151        if (iIsRequired || iIsProhibited)
    1152            return;
    1153        getModel().getCriterion(DistributionPreferences.class).inc(-iLastPreference);
    1154        iLastPreference = getCurrentPreference();
    1155        getModel().getCriterion(DistributionPreferences.class).inc(iLastPreference);
    1156    }
    1157
    1158    @Override
    1159    public void assigned(long iteration, Placement value) {
    1160        super.assigned(iteration, value);
    1161        if (iIsRequired || iIsProhibited)
    1162            return;
    1163        getModel().getCriterion(DistributionPreferences.class).inc(-iLastPreference);
    1164        iLastPreference = getCurrentPreference();
    1165        getModel().getCriterion(DistributionPreferences.class).inc(iLastPreference);
    1166    }
    1167
    1168    @Override
    1169    public String toString() {
    1170        StringBuffer sb = new StringBuffer();
    1171        sb.append(getName());
    1172        sb.append(" between ");
    1173        for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) {
    1174            Lecture v = e.next();
    1175            sb.append(v.getName() + " " + (v.getAssignment() == null ? "" : v.getAssignment().getName()));
    1176            if (e.hasNext())
    1177                sb.append(", ");
    1178        }
    1179        return sb.toString();
    1180    }
    1181
    1182    @Override
    1183    public boolean isHard() {
    1184        return iIsRequired || iIsProhibited;
    1185    }
    1186
    1187    @Override
    1188    public String getName() {
    1189        return getType().getName();
    1190    }
    1191
    1192
    1193    private boolean isPrecedence(Placement p1, Placement p2, boolean firstGoesFirst, boolean considerDatePatterns) {
    1194        int ord1 = variables().indexOf(p1.variable());
    1195        int ord2 = variables().indexOf(p2.variable());
    1196        TimeLocation t1 = null, t2 = null;
    1197        if (ord1 < ord2) {
    1198            if (firstGoesFirst) {
    1199                t1 = p1.getTimeLocation();
    1200                t2 = p2.getTimeLocation();
    1201            } else {
    1202                t2 = p1.getTimeLocation();
    1203                t1 = p2.getTimeLocation();
    1204            }
    1205        } else {
    1206            if (!firstGoesFirst) {
    1207                t1 = p1.getTimeLocation();
    1208                t2 = p2.getTimeLocation();
    1209            } else {
    1210                t2 = p1.getTimeLocation();
    1211                t1 = p2.getTimeLocation();
    1212            }
    1213        }
    1214        if (considerDatePatterns && iPrecedenceConsiderDatePatterns) {
    1215            boolean sameDatePattern = (t1.getDatePatternId() != null ? t1.getDatePatternId().equals(t2.getDatePatternId()) : t1.getWeekCode().equals(t2.getWeekCode()));
    1216            if (!sameDatePattern) {
    1217                int m1 = t1.getFirstMeeting(iDayOfWeekOffset), m2 = t2.getFirstMeeting(iDayOfWeekOffset);
    1218                if (m1 != m2) return m1 < m2;
    1219            }
    1220        }
    1221        return t1.getStartSlots().nextElement() + t1.getLength() <= t2.getStartSlots().nextElement();
    1222    }
    1223
    1224    private static boolean isBackToBackDays(TimeLocation t1, TimeLocation t2) {
    1225        int f1 = -1, f2 = -1, e1 = -1, e2 = -1;
    1226        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    1227            if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) {
    1228                if (f1 < 0)
    1229                    f1 = i;
    1230                e1 = i;
    1231            }
    1232            if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) {
    1233                if (f2 < 0)
    1234                    f2 = i;
    1235                e2 = i;
    1236            }
    1237        }
    1238        return (e1 + 1 == f2) || (e2 + 1 == f1);
    1239    }
    1240
    1241    private static boolean isNrDaysBetweenGreaterThanOne(TimeLocation t1, TimeLocation t2) {
    1242        int f1 = -1, f2 = -1, e1 = -1, e2 = -1;
    1243        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    1244            if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) {
    1245                if (f1 < 0)
    1246                    f1 = i;
    1247                e1 = i;
    1248            }
    1249            if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) {
    1250                if (f2 < 0)
    1251                    f2 = i;
    1252                e2 = i;
    1253            }
    1254        }
    1255        return (e1 - f2 > 2) || (e2 - f1 > 2);
    1256    }
    1257
    1258    private boolean isFollowingDay(Placement p1, Placement p2, boolean firstGoesFirst) {
    1259        int ord1 = variables().indexOf(p1.variable());
    1260        int ord2 = variables().indexOf(p2.variable());
    1261        TimeLocation t1 = null, t2 = null;
    1262        if (ord1 < ord2) {
    1263            if (firstGoesFirst) {
    1264                t1 = p1.getTimeLocation();
    1265                t2 = p2.getTimeLocation();
    1266            } else {
    1267                t2 = p1.getTimeLocation();
    1268                t1 = p2.getTimeLocation();
    1269            }
    1270        } else {
    1271            if (!firstGoesFirst) {
    1272                t1 = p1.getTimeLocation();
    1273                t2 = p2.getTimeLocation();
    1274            } else {
    1275                t2 = p1.getTimeLocation();
    1276                t1 = p2.getTimeLocation();
    1277            }
    1278        }
    1279        int f1 = -1, f2 = -1, e1 = -1;
    1280        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    1281            if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) {
    1282                if (f1 < 0)
    1283                    f1 = i;
    1284                e1 = i;
    1285            }
    1286            if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) {
    1287                if (f2 < 0)
    1288                    f2 = i;
    1289            }
    1290        }
    1291        return ((e1 + 1) % Constants.NR_DAYS_WEEK == f2);
    1292    }
    1293
    1294    private boolean isEveryOtherDay(Placement p1, Placement p2, boolean firstGoesFirst) {
    1295        int ord1 = variables().indexOf(p1.variable());
    1296        int ord2 = variables().indexOf(p2.variable());
    1297        TimeLocation t1 = null, t2 = null;
    1298        if (ord1 < ord2) {
    1299            if (firstGoesFirst) {
    1300                t1 = p1.getTimeLocation();
    1301                t2 = p2.getTimeLocation();
    1302            } else {
    1303                t2 = p1.getTimeLocation();
    1304                t1 = p2.getTimeLocation();
    1305            }
    1306        } else {
    1307            if (!firstGoesFirst) {
    1308                t1 = p1.getTimeLocation();
    1309                t2 = p2.getTimeLocation();
    1310            } else {
    1311                t2 = p1.getTimeLocation();
    1312                t1 = p2.getTimeLocation();
    1313            }
    1314        }
    1315        int f1 = -1, f2 = -1, e1 = -1;
    1316        for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    1317            if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) {
    1318                if (f1 < 0)
    1319                    f1 = i;
    1320                e1 = i;
    1321            }
    1322            if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) {
    1323                if (f2 < 0)
    1324                    f2 = i;
    1325            }
    1326        }
    1327        return ((e1 + 2) % Constants.NR_DAYS_WEEK == f2);
    1328    }
    1329
    1330    private static boolean sameDays(int[] days1, int[] days2) {
    1331        if (days2.length < days1.length)
    1332            return sameDays(days2, days1);
    1333        int i2 = 0;
    1334        for (int i1 = 0; i1 < days1.length; i1++) {
    1335            int d1 = days1[i1];
    1336            while (true) {
    1337                if (i2 == days2.length)
    1338                    return false;
    1339                int d2 = days2[i2];
    1340                if (d1 == d2)
    1341                    break;
    1342                i2++;
    1343                if (i2 == days2.length)
    1344                    return false;
    1345            }
    1346            i2++;
    1347        }
    1348        return true;
    1349    }
    1350
    1351    private static boolean sameRoomAndOverlaps(Placement p1, Placement p2) {
    1352        return p1.shareRooms(p2) && p1.getTimeLocation() != null && p2.getTimeLocation() != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation());
    1353    }
    1354
    1355    private static boolean sameHours(int start1, int len1, int start2, int len2) {
    1356        if (len1 > len2)
    1357            return sameHours(start2, len2, start1, len1);
    1358        start1 %= Constants.SLOTS_PER_DAY;
    1359        start2 %= Constants.SLOTS_PER_DAY;
    1360        return (start1 >= start2 && start1 + len1 <= start2 + len2);
    1361    }
    1362
    1363    private static boolean canFill(int totalGap, int gapMin, int gapMax, List<Integer> lengths) {
    1364        if (gapMin <= totalGap && totalGap <= gapMax)
    1365            return true;
    1366        if (totalGap < 2 * gapMin)
    1367            return false;
    1368        for (int i = 0; i < lengths.size(); i++) {
    1369            int length = lengths.get(i);
    1370            lengths.remove(i);
    1371            for (int gap = gapMin; gap <= gapMax; gap++)
    1372                if (canFill(totalGap - gap - length, gapMin, gapMax, lengths))
    1373                    return true;
    1374            lengths.add(i, length);
    1375        }
    1376        return false;
    1377    }
    1378
    1379    private boolean isSatisfiedSeq(HashMap<Lecture, Placement> assignments, boolean considerCurrentAssignments,
    1380            Set<Placement> conflicts) {
    1381        if (conflicts == null)
    1382            return isSatisfiedSeqCheck(assignments, considerCurrentAssignments, conflicts);
    1383        else {
    1384            Set<Placement> bestConflicts = isSatisfiedRecursive(0, assignments, considerCurrentAssignments, conflicts,
    1385                    new HashSet<Placement>(), null);
    1386            if (bestConflicts == null)
    1387                return false;
    1388            conflicts.addAll(bestConflicts);
    1389            return true;
    1390        }
    1391    }
    1392
    1393    private Set<Placement> isSatisfiedRecursive(int idx, HashMap<Lecture, Placement> assignments,
    1394            boolean considerCurrentAssignments, Set<Placement> conflicts, Set<Placement> newConflicts,
    1395            Set<Placement> bestConflicts) {
    1396        if (idx == variables().size() && newConflicts.isEmpty())
    1397            return bestConflicts;
    1398        if (isSatisfiedSeqCheck(assignments, considerCurrentAssignments, conflicts)) {
    1399            if (bestConflicts == null) {
    1400                return new HashSet<Placement>(newConflicts);
    1401            } else {
    1402                int b = 0, n = 0;
    1403                for (Placement value: assignments.values()) {
    1404                    if (value != null && bestConflicts.contains(value)) b++;
    1405                    if (value != null && newConflicts.contains(value)) n++;
    1406                }
    1407                if (n < b || (n == b && newConflicts.size() < bestConflicts.size()))
    1408                    return new HashSet<Placement>(newConflicts);
    1409            }
    1410            return bestConflicts;
    1411        }
    1412        if (idx == variables().size())
    1413            return bestConflicts;
    1414        bestConflicts = isSatisfiedRecursive(idx + 1, assignments, considerCurrentAssignments, conflicts, newConflicts,
    1415                bestConflicts);
    1416        Lecture lecture = variables().get(idx);
    1417        //if (assignments != null && assignments.containsKey(lecture))
    1418        //    return bestConflicts;
    1419        Placement placement = null;
    1420        if (assignments != null && assignments.containsKey(lecture))
    1421            placement = assignments.get(lecture);
    1422        else if (considerCurrentAssignments)
    1423            placement = lecture.getAssignment();
    1424        if (placement == null)
    1425            return bestConflicts;
    1426        if (conflicts != null && conflicts.contains(placement))
    1427            return bestConflicts;
    1428        conflicts.add(placement);
    1429        newConflicts.add(placement);
    1430        bestConflicts = isSatisfiedRecursive(idx + 1, assignments, considerCurrentAssignments, conflicts, newConflicts,
    1431                bestConflicts);
    1432        newConflicts.remove(placement);
    1433        conflicts.remove(placement);
    1434        return bestConflicts;
    1435    }
    1436
    1437    private boolean isSatisfiedSeqCheck(HashMap<Lecture, Placement> assignments, boolean considerCurrentAssignments,
    1438            Set<Placement> conflicts) {
    1439        if (!getType().is(Flag.BACK_TO_BACK)) return true;
    1440        int gapMin = getType().getMin();
    1441        int gapMax = getType().getMax();
    1442
    1443        List<Integer> lengths = new ArrayList<Integer>();
    1444
    1445        Placement[] res = new Placement[Constants.SLOTS_PER_DAY];
    1446        for (int i = 0; i < Constants.SLOTS_PER_DAY; i++)
    1447            res[i] = null;
    1448
    1449        int nrLectures = 0;
    1450
    1451        for (Lecture lecture : variables()) {
    1452            Placement placement = null;
    1453            if (assignments != null && assignments.containsKey(lecture))
    1454                placement = assignments.get(lecture);
    1455            else if (considerCurrentAssignments)
    1456                placement = lecture.getAssignment();
    1457            if (placement == null) {
    1458                lengths.add(lecture.timeLocations().get(0).getLength());
    1459            } else if (conflicts != null && conflicts.contains(placement)) {
    1460                lengths.add(lecture.timeLocations().get(0).getLength());
    1461            } else {
    1462                int pos = placement.getTimeLocation().getStartSlot();
    1463                int length = placement.getTimeLocation().getLength();
    1464                for (int j = pos; j < pos + length; j++) {
    1465                    if (res[j] != null) {
    1466                        if (conflicts == null)
    1467                            return false;
    1468                        if (!assignments.containsKey(lecture))
    1469                            conflicts.add(placement);
    1470                        else if (!assignments.containsKey(res[j].variable()))
    1471                            conflicts.add(res[j]);
    1472                    }
    1473                }
    1474                for (int j = pos; j < pos + length; j++)
    1475                    res[j] = placement;
    1476                nrLectures++;
    1477            }
    1478        }
    1479        if (nrLectures <= 1)
    1480            return true;
    1481
    1482        if (iIsRequired || (!iIsProhibited && iPreference < 0)) {
    1483            int i = 0;
    1484            Placement p = res[i];
    1485            while (p == null)
    1486                p = res[++i];
    1487            i += res[i].getTimeLocation().getLength();
    1488            nrLectures--;
    1489            while (nrLectures > 0) {
    1490                int gap = 0;
    1491                while (i < Constants.SLOTS_PER_DAY && res[i] == null) {
    1492                    gap++;
    1493                    i++;
    1494                }
    1495                if (i == Constants.SLOTS_PER_DAY)
    1496                    break;
    1497                if (!canFill(gap, gapMin, gapMax, lengths))
    1498                    return false;
    1499                p = res[i];
    1500                i += res[i].getTimeLocation().getLength();
    1501                nrLectures--;
    1502            }
    1503        } else if (iIsProhibited || (!iIsRequired && iPreference > 0)) {
    1504            int i = 0;
    1505            Placement p = res[i];
    1506            while (p == null)
    1507                p = res[++i];
    1508            i += res[i].getTimeLocation().getLength();
    1509            nrLectures--;
    1510            while (nrLectures > 0) {
    1511                int gap = 0;
    1512                while (i < Constants.SLOTS_PER_DAY && res[i] == null) {
    1513                    gap++;
    1514                    i++;
    1515                }
    1516                if (i == Constants.SLOTS_PER_DAY)
    1517                    break;
    1518                if ((gapMin == 0 || !canFill(gap, 0, gapMin - 1, lengths))
    1519                        && (gapMax >= Constants.SLOTS_PER_DAY || !canFill(gap, gapMax + 1, Constants.SLOTS_PER_DAY,
    1520                                lengths))) {
    1521                    return false;
    1522                }
    1523                p = res[i];
    1524                i += res[i].getTimeLocation().getLength();
    1525                nrLectures--;
    1526            }
    1527        }
    1528        return true;
    1529    }
    1530
    1531    public boolean isSatisfied() {
    1532        if (isHard()) return true;
    1533        if (countAssignedVariables() < 2) return true;
    1534        if (getPreference() == 0) return true;
    1535        return isHard() || countAssignedVariables() < 2 || getPreference() == 0 || getCurrentPreference() < 0;
    1536    }
    1537
    1538    public boolean isChildrenNotOverlap(Lecture lec1, Placement plc1, Lecture lec2, Placement plc2) {
    1539        if (lec1.getSchedulingSubpartId().equals(lec2.getSchedulingSubpartId())) {
    1540            // same subpart
    1541            boolean overlap = plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation());
    1542
    1543            if (overlap && lec1.getParent() != null && variables().contains(lec1.getParent())
    1544                    && lec2.getParent() != null && variables().contains(lec2.getParent())) {
    1545                // children overlaps
    1546                Placement p1 = lec1.getParent().getAssignment();
    1547                Placement p2 = lec2.getParent().getAssignment();
    1548                // parents not overlap, but children do
    1549                if (p1 != null && p2 != null && !p1.getTimeLocation().hasIntersection(p2.getTimeLocation()))
    1550                    return false;
    1551            }
    1552
    1553            if (!overlap && lec1.getChildrenSubpartIds() != null && lec2.getChildrenSubpartIds() != null) {
    1554                // parents not overlap
    1555                for (Long subpartId: lec1.getChildrenSubpartIds()) {
    1556                    for (Lecture c1 : lec1.getChildren(subpartId)) {
    1557                        if (c1.getAssignment() == null)
    1558                            continue;
    1559                        for (Lecture c2 : lec2.getChildren(subpartId)) {
    1560                            if (c2.getAssignment() == null)
    1561                                continue;
    1562                            if (!c1.getSchedulingSubpartId().equals(c2.getSchedulingSubpartId()))
    1563                                continue;
    1564                            Placement p1 = c1.getAssignment();
    1565                            Placement p2 = c2.getAssignment();
    1566                            // parents not overlap, but children do
    1567                            if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation()))
    1568                                return false;
    1569                        }
    1570                    }
    1571                }
    1572            }
    1573        } else {
    1574            // different subpart
    1575        }
    1576        return true;
    1577    }
    1578
    1579    public boolean isSatisfiedPair(Placement plc1, Placement plc2) {
    1580        if (iIsRequired || (!iIsProhibited && iPreference <= 0))
    1581            return getType().isSatisfied(this, plc1, plc2);
    1582        else if (iIsProhibited || (!iIsRequired && iPreference > 0))
    1583            return getType().isViolated(this, plc1, plc2);
    1584        return true;
    1585    }
    1586
    1587    public boolean canShareRoom() {
    1588        return getType().is(Flag.CAN_SHARE_ROOM);
    1589    }
    1590
    1591    private int nrSlotsADay(int dayCode, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
    1592        Set<Integer> slots = new HashSet<Integer>();
    1593        for (Lecture lecture: variables()) {
    1594            Placement placement = null;
    1595            if (assignments != null && assignments.containsKey(lecture))
    1596                placement = assignments.get(lecture);
    1597            else
    1598                placement = lecture.getAssignment();
    1599            if (placement == null || placement.getTimeLocation() == null) continue;
    1600            if (conflicts != null && conflicts.contains(placement)) continue;
    1601            TimeLocation t = placement.getTimeLocation();
    1602            if (t == null || (t.getDayCode() & dayCode) == 0) continue;
    1603            for (int i = 0; i < t.getLength(); i++)
    1604                slots.add(i + t.getStartSlot());
    1605        }
    1606        return slots.size();
    1607    }
    1608
    1609    @Override
    1610    public boolean equals(Object o) {
    1611        if (o == null || !(o instanceof GroupConstraint)) return false;
    1612        return getGeneratedId() == ((GroupConstraint) o).getGeneratedId();
    1613    }
    1614}