    001    package ttsolver.constraint;
    002
    003    import ifs.model.*;
    004    import ifs.util.*;
    005    import java.util.*;
    006    import ttsolver.model.*;
    007
    008    /**
    009     * Group constraint.
    010     * <br>
    011     * This constraint expresses relations between several classes, e.g., that two sections of the same lecture can not
    012     * be taught at the same time, or that some classes have to be taught one immediately after another. It can be either
    013     * hard or soft.
    014     * <br><br>
    015     * Following constraints are now supported:
    016     * <table border='1'><tr><th>Constraint</th><thComment</th></tr>
    017     * <tr><td>SAME_TIME</td><td>Same time: given classes have to be taught in the same hours. If the classes are of different length, the smaller one cannot start before the longer one and it cannot end after the longer one.</td></tr>
    018     * <tr><td>SAME_DAYS</td><td>Same days: given classes have to be taught in the same day. If the classes are of different time patterns, the days of one class have to form a subset of the days of the other class.</td></tr>
    019     * <tr><td>BTB</td><td>Back-to-back constraint: given classes have to be taught in the same room and they have to follow one strictly after another.</td></tr>
    020     * <tr><td>BTB_TIME</td><td>Back-to-back constraint: given classes have to follow one strictly after another, but they can be taught in different rooms.</td></tr>
    021     * <tr><td>DIFF_TIME</td><td>Different time: given classes cannot overlap in time.</td></tr>
    022     * <tr><td>NHB(1), NHB(1.5), NHB(2), ... NHB(8)</td><td>Number of hours between: between the given classes, the exact number of hours have to be kept.</td></tr>
    023     * <tr><td>SAME_START</td><td>Same starting hour: given classes have to start in the same hour.</td></tr>
    024     * <tr><td>SAME_ROOM</td><td>Same room: given classes have to be placed in the same room.</td></tr>
    025     * <tr><td>NHB_GTE(1)</td><td>Greater than or equal to 1 hour between: between the given classes, the number of hours have to be one or more.</td></tr>
    026     * <tr><td>NHB_LT(6)</td><td>Less than 6 hours between: between the given classes, the number of hours have to be less than six.</td></tr>
    027     * </table>
    028     *
    029     * @author <a href="mailto:muller@ktiml.mff.cuni.cz">Tomáš Müller</a>
    030     * @version 1.0
    031     */
    032
    033    public class GroupConstraint extends Constraint {
    034        private long iId;
    035        private int iPreference;
    036        private int iType;
    037        private boolean iIsRequired;
    038        private boolean iIsProhibited;
    039        private Counter iGlobalPreference = null;
    040        private int iLastPreference = 0;
    041
    042        /** Same time: given classes have to be taught in the same hours. If the classes are of different length, the smaller one cannot start before the longer one and it cannot end after the longer one.*/
    043        public static int TYPE_SAME_TIME = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("SAME_TIME").getId();
    044        /** Same days: given classes have to be taught in the same day. If the classes are of different time patterns, the days of one class have to form a subset of the days of the other class. */
    045        public static int TYPE_SAME_DAYS  = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("SAME_DAYS").getId();
    046        /** Back-to-back constraint: given classes have to be taught in the same room and they have to follow one strictly after another. */
    047        public static int TYPE_BTB       = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("BTB").getId();
    048        /** Back-to-back constraint: given classes have to follow one strictly after another, but they can be taught in different rooms. */
    049        public static int TYPE_BTB_TIME  = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("BTB_TIME").getId();
    050        /** Different time: given classes cannot overlap in time. */
    051        public static int TYPE_DIFF_TIME = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("DIFF_TIME").getId();
    052        /** One hour between: between the given classes, the exact number of hours have to be kept.*/
    053        public static int TYPE_NHB_1     = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB(1)").getId();
    054        /** Two hours between: between the given classes, the exact number of hours have to be kept.*/
    055        public static int TYPE_NHB_2     = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB(2)").getId();
    056        /** Three hours between: between the given classes, the exact number of hours have to be kept.*/
    057        public static int TYPE_NHB_3     = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB(3)").getId();
    058        /** Four hours between: between the given classes, the exact number of hours have to be kept.*/
    059        public static int TYPE_NHB_4     = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB(4)").getId();
    060        /** Five hours between: between the given classes, the exact number of hours have to be kept.*/
    061        public static int TYPE_NHB_5     = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB(5)").getId();
    062        /** Six hours between: between the given classes, the exact number of hours have to be kept.*/
    063        public static int TYPE_NHB_6     = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB(6)").getId();
    064        /** Seven hours between: between the given classes, the exact number of hours have to be kept.*/
    065        public static int TYPE_NHB_7     = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB(7)").getId();
    066        /** Eight hours between: between the given classes, the exact number of hours have to be kept.*/
    067        public static int TYPE_NHB_8     = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB(8)").getId();
    068        /** Same room: given classes have to placed in the same room.*/
    069        public static int TYPE_SAME_START = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("SAME_START").getId();
    070        /** Same room: given classes have to placed in the same room.*/
    071        public static int TYPE_SAME_ROOM = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("SAME_ROOM").getId();
    072        /** Greater than or equal to 1 hour between: between the given classes, the number of hours have to be one or more.*/
    073        public static int TYPE_NHB_GTE_1 = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB_GTE(1)").getId();
    074        /** Less than 6 hours between: between the given classes, the number of hours have to be less than six. */
    075        public static int TYPE_NHB_LT_6  = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB_LT(6)").getId();
    076        /** One and half hour between: between the given classes, the exact number of hours have to be kept.*/
    077        public static int TYPE_NHB_1_5   = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB(1.5)").getId();
    078        /** Four and half hours between: between the given classes, the exact number of hours have to be kept.*/
    079        public static int TYPE_NHB_4_5   = edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType("NHB(4.5)").getId();
    080
    081        /** Constructor
    082         * @param id constraint id
    083         * @param type constraint type (e.g, {@link GroupConstraint#TYPE_SAME_TIME})
    084         * @param preference time preferent ("R" for required, "P" for prohibited, "-2", "-1", "1", "2" for soft preference)
    085         */
    086        public GroupConstraint(long id, int type, String preference) {
    087            iId=id;
    088            iType=type;
    089            iIsRequired=preference.equals("R");
    090            iIsProhibited=preference.equals("P");
    091            iPreference=(iIsRequired?0:iIsProhibited?0:Integer.parseInt(preference));
    092        }
    093
    094        /** Constructor
    095         * @param id constraint id
    096         * @param type constraint type (e.g, "SAME_TIME")
    097         * @param preference time preferent ("R" for required, "P" for prohibited, "-2", "-1", "1", "2" for soft preference)
    098         */
    099        public GroupConstraint(long id, String type, String preference) {
    100            this(id, edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType(type).getId(),preference);
    101        }
    102
    103        /** Constraint id */
    104        public long getId() { return iId; }
    105        /** Constraint type (e.g, {@link GroupConstraint#TYPE_SAME_TIME} */
    106        public int getType() { return iType; }
    107        /** Constraint type (e.g, "SAME_TIME") */
    108        public String getTypeStr() { return edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType(iType).getType(); }
    109        /** Is constraint required */
    110        public boolean isRequired() { return iIsRequired; }
    111        /** Is constraint prohibited */
    112        public boolean isProhibited() { return iIsProhibited; }
    113        /** Prolog reference: "R" for required, "P" for prohibited", "-2",.."2" for preference */
    114        public String getPrologPreference() { return (iIsRequired?"R":iIsProhibited?"P":String.valueOf(iPreference)); }
    115        /** Global preference counter */
    116        public void setGlobalPreference(Counter globalPreference) { iGlobalPreference = globalPreference; }
    117        /** Global preference counter */
    118        public Counter getGlobalPreference() { return iGlobalPreference;}
    119
    120
    121        public boolean isConsistent(Value value1, Value value2) {
    122            if (!isHard()) return true;
    123            if (!isSatisfiedPair((Lecture)value1.variable(), (Placement)value1, (Lecture)value2.variable(), (Placement)value2))
    124                return false;
    125            if (isBackToBack(getType())) {
    126                Hashtable assignments = new Hashtable();
    127                assignments.put(value1.variable(), value1);
    128                assignments.put(value2.variable(), value2);
    129                if (!isSatisfiedSeq(assignments, false, null))
    130                    return false;
    131            }
    132            return true;
    133        }
    134
    135        public void computeConflicts(Value value, Set conflicts) {
    136            if (!isHard()) return;
    137            for (Enumeration e=variables().elements();e.hasMoreElements();) {
    138                Variable v = (Variable)e.nextElement();
    139                if (v.equals(value.variable())) continue; //ignore this variable
    140                if (v.getAssignment()==null) continue; //there is an unassigned variable -- great, still a chance to get violated
    141                if (!isSatisfiedPair((Lecture)v, (Placement)v.getAssignment(), (Lecture)value.variable(), (Placement)value))
    142                    conflicts.add(v.getAssignment());
    143            }
    144            Hashtable assignments = new Hashtable();
    145            assignments.put(value.variable(), value);
    146            isSatisfiedSeq(assignments, true, conflicts);
    147        }
    148
    149        public boolean inConflict(Value value) {
    150            if (!isHard()) return false;
    151            for (Enumeration e=variables().elements();e.hasMoreElements();) {
    152                Variable v = (Variable)e.nextElement();
    153                if (v.equals(value.variable())) continue; //ignore this variable
    154                if (v.getAssignment()==null) continue; //there is an unassigned variable -- great, still a chance to get violated
    155                if (!isSatisfiedPair((Lecture)v, (Placement)v.getAssignment(), (Lecture)value.variable(), (Placement)value))
    156                    return true;
    157            }
    158            Hashtable assignments = new Hashtable();
    159            assignments.put(value.variable(), value);
    160            return isSatisfiedSeq(assignments, true, null);
    161        }
    162
    163        /** Constraint preference (0 if prohibited or reqired) */
    164        public int getPreference() {
    165            return iPreference;
    166        }
    167
    168        /** Current constraint preference (0 if prohibited or reqired, depends on current satisfaction of the constraint) */
    169        public int getCurrentPreference() {
    170            if (isHard()) return 0; //no preference
    171            if (countAssignedVariables()<2) return 0;
    172            if (iPreference<0) { //preference version (violated -> 0, satisfied -> preference)
    173                for (Enumeration e1=variables().elements();e1.hasMoreElements();) {
    174                    Variable v1 = (Variable)e1.nextElement();
    175                    if (v1.getAssignment()==null) continue;
    176                    for (Enumeration e2=variables().elements();e2.hasMoreElements();) {
    177                        Variable v2 = (Variable)e2.nextElement();
    178                        if (v2.getAssignment()==null) continue;
    179                        if (v1.equals(v2)) continue;
    180                        if (!isSatisfiedPair((Lecture)v1, (Placement)v1.getAssignment(), (Lecture)v2, (Placement)v2.getAssignment()))
    181                            return 0;
    182                    }
    183                }
    184                if (!isSatisfiedSeq(null, true, null))
    185                    return 0;
    186                return iPreference;
    187            } else { //discouraged version (violated -> prefernce, satisfied -> 0)
    188                for (Enumeration e1=variables().elements();e1.hasMoreElements();) {
    189                    Variable v1 = (Variable)e1.nextElement();
    190                    if (v1.getAssignment()==null) continue;
    191                    for (Enumeration e2=variables().elements();e2.hasMoreElements();) {
    192                        Variable v2 = (Variable)e2.nextElement();
    193                        if (v2.getAssignment()==null) continue;
    194                        if (v1.equals(v2)) continue;
    195                        if (!isSatisfiedPair((Lecture)v1, (Placement)v1.getAssignment(), (Lecture)v2, (Placement)v2.getAssignment()))
    196                            return iPreference;
    197                    }
    198                }
    199                if (!isSatisfiedSeq(null, true, null))
    200                    return iPreference;
    201                return 0;
    202            }
    203        }
    204
    205        /** Current constraint preference (if given placement is assigned) */
    206        public int getCurrentPreference(Placement placement) {
    207            if (isHard()) return 0; //no preference
    208            if (iPreference<0) { //preference version
    209                for (Enumeration e1=variables().elements();e1.hasMoreElements();) {
    210                    Variable v1 = (Variable)e1.nextElement();
    211                    if (v1.getAssignment()==null) continue;
    212                    if (v1.equals(placement.variable())) continue;
    213                    if (!isSatisfiedPair((Lecture)v1, (Placement)v1.getAssignment(), (Lecture)placement.variable(), placement))
    214                            return 0;
    215                }
    216                if (isBackToBack(getType())) {
    217                    Hashtable assignment = new Hashtable();
    218                    assignment.put(placement.variable(), placement);
    219                    if (!isSatisfiedSeq(assignment, true, null))
    220                        return 0;
    221                }
    222                return iPreference;
    223            } else { //discouraged version
    224                for (Enumeration e1=variables().elements();e1.hasMoreElements();) {
    225                    Variable v1 = (Variable)e1.nextElement();
    226                    if (v1.getAssignment()==null) continue;
    227                    if (v1.equals(placement.variable())) continue;
    228                    if (!isSatisfiedPair((Lecture)v1, (Placement)v1.getAssignment(), (Lecture)placement.variable(), placement))
    229                            return iPreference;
    230                }
    231                if (isBackToBack(getType())) {
    232                    Hashtable assignment = new Hashtable();
    233                    assignment.put(placement.variable(), placement);
    234                    if (!isSatisfiedSeq(assignment, true, null))
    235                        return iPreference;
    236                }
    237                return 0;
    238            }
    239        }
    240
    241        public void unassigned(long iteration, Value value) {
    242            super.unassigned(iteration, value);
    243            if (iIsRequired || iIsProhibited) return;
    244            iGlobalPreference.dec(iLastPreference);
    245            iLastPreference = getCurrentPreference();
    246            iGlobalPreference.inc(iLastPreference);
    247        }
    248
    249        public void assigned(long iteration, Value value) {
    250            super.assigned(iteration, value);
    251            if (iIsRequired || iIsProhibited) return;
    252            iGlobalPreference.dec(iLastPreference);
    253            iLastPreference = getCurrentPreference();
    254            iGlobalPreference.inc(iLastPreference);
    255        }
    256
    257        public String toString() {
    258            return "GroupConstraint{id="+iId+", type="+edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType(iType).getType()+", preference="+getPrologPreference()+", variables="+variables().size()+", lectures"+ToolBox.col2string(variables(),4)+"\n      }";
    259        }
    260
    261        public boolean isHard() {return iIsRequired || iIsProhibited; }
    262
    263        public String getName() {
    264            StringBuffer varNames = new StringBuffer();
    265            for (Enumeration e=variables().elements();e.hasMoreElements();)
    266                varNames.append(varNames.length()>0?", ":"").append(((Variable)e.nextElement()).getName());
    267            return edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType(iType).getDescription()+" ["+varNames+"]";
    268        }
    269        public String getDescription() { return edu.purdue.smas.timetable.data.Preferences.getPreference(getPrologPreference()).getName().toLowerCase(); }
    270
    271
    272        private static int getGapMin(int type) {
    273            if (type==TYPE_BTB) return 0;
    274            else if (type==TYPE_BTB_TIME) return 0;
    275            else if (type==TYPE_NHB_1) return 2;
    276            else if (type==TYPE_NHB_1_5) return 3;
    277            else if (type==TYPE_NHB_2) return 4;
    278            else if (type==TYPE_NHB_3) return 6;
    279            else if (type==TYPE_NHB_4) return 8;
    280            else if (type==TYPE_NHB_4_5) return 9;
    281            else if (type==TYPE_NHB_5) return 10;
    282            else if (type==TYPE_NHB_6) return 12;
    283            else if (type==TYPE_NHB_7) return 14;
    284            else if (type==TYPE_NHB_8) return 16;
    285            else if (type==TYPE_NHB_GTE_1) return 1;
    286            else if (type==TYPE_NHB_LT_6) return 0;
    287            return -1;
    288        }
    289
    290        private static int getGapMax(int type) {
    291            if (type==TYPE_BTB) return 0;
    292            else if (type==TYPE_BTB_TIME) return 0;
    293            else if (type==TYPE_NHB_1) return 2;
    294            else if (type==TYPE_NHB_1_5) return 3;
    295            else if (type==TYPE_NHB_2) return 4;
    296            else if (type==TYPE_NHB_3) return 6;
    297            else if (type==TYPE_NHB_4) return 8;
    298            else if (type==TYPE_NHB_4_5) return 9;
    299            else if (type==TYPE_NHB_5) return 10;
    300            else if (type==TYPE_NHB_6) return 12;
    301            else if (type==TYPE_NHB_7) return 14;
    302            else if (type==TYPE_NHB_8) return 16;
    303            else if (type==TYPE_NHB_GTE_1) return edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY;
    304            else if (type==TYPE_NHB_LT_6) return 11;
    305            return -1;
    306        }
    307
    308        private static boolean isBackToBack(int type) {
    309            if (type==TYPE_BTB) return true;
    310            if (type==TYPE_BTB_TIME) return true;
    311            if (type==TYPE_NHB_1) return true;
    312            if (type==TYPE_NHB_1_5) return true;
    313            if (type==TYPE_NHB_2) return true;
    314            if (type==TYPE_NHB_3) return true;
    315            if (type==TYPE_NHB_4) return true;
    316            if (type==TYPE_NHB_4_5) return true;
    317            if (type==TYPE_NHB_5) return true;
    318            if (type==TYPE_NHB_6) return true;
    319            if (type==TYPE_NHB_7) return true;
    320            if (type==TYPE_NHB_8) return true;
    321            if (type==TYPE_NHB_GTE_1) return true;
    322            if (type==TYPE_NHB_LT_6) return true;
    323            return false;
    324        }
    325
    326        private static boolean isBackToBackTime(int type) {
    327            if (type==TYPE_BTB_TIME) return true;
    328            if (type==TYPE_NHB_1) return true;
    329            if (type==TYPE_NHB_1_5) return true;
    330            if (type==TYPE_NHB_2) return true;
    331            if (type==TYPE_NHB_3) return true;
    332            if (type==TYPE_NHB_4) return true;
    333            if (type==TYPE_NHB_4_5) return true;
    334            if (type==TYPE_NHB_5) return true;
    335            if (type==TYPE_NHB_6) return true;
    336            if (type==TYPE_NHB_7) return true;
    337            if (type==TYPE_NHB_8) return true;
    338            if (type==TYPE_NHB_GTE_1) return true;
    339            if (type==TYPE_NHB_LT_6) return true;
    340            return false;
    341        }
    342
    343        private static boolean sameRoom(int type) {
    344            if (type==TYPE_SAME_ROOM) return true;
    345            return false;
    346        }
    347
    348        private static boolean sameStartHour(int type) {
    349            return (type==TYPE_SAME_START);
    350        }
    351
    352        private static boolean sameHours(int type) {
    353            return (type==TYPE_SAME_TIME);
    354        }
    355
    356        private static boolean sameDays(int type) {
    357            if (type==TYPE_SAME_DAYS) return true;
    358            return false;
    359        }
    360
    361        private static boolean notOverlap(int type) {
    362            return (type==TYPE_DIFF_TIME);
    363        }
    364
    365        private static boolean sameDays(int[] days1, int[] days2) {
    366            if (days2.length<days1.length) return sameDays(days2,days1);
    367            int i2=0;
    368            for (int i1=0;i1<days1.length;i1++) {
    369                int d1 = days1[i1] / edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY;
    370                while (true) {
    371                    if (i2==days2.length) return false;
    372                    int d2 = days2[i2] / edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY;
    373                    if (d1==d2) break;
    374                    i2++;
    375                    if (i2==days2.length) return false;
    376                }
    377                i2++;
    378            }
    379            return true;
    380        }
    381
    382        private static boolean sameHours(int start1, int len1, int start2, int len2) {
    383            if (len1>len2) return sameHours(start2, len2, start1, len1);
    384            start1 %= edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY;
    385            start2 %= edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY;
    386            return (start1>=start2 && start1+len1<=start2+len2);
    387        }
    388
    389        private static boolean canFill(int totalGap, int gapMin, int gapMax, Vector lengths) {
    390            if (gapMin<=totalGap && totalGap<=gapMax) return true;
    391            if (totalGap<2*gapMin) return false;
    392            for (int i=0;i<lengths.size();i++) {
    393                int length = ((Integer)lengths.elementAt(i)).intValue(); lengths.removeElementAt(i);
    394                for (int gap=gapMin;gap<=gapMax;gap++)
    395                    if (canFill(totalGap-gap-length,gapMin, gapMax, lengths)) return true;
    396                lengths.insertElementAt(new Integer(length), i);
    397            }
    398            return false;
    399        }
    400
    401
    402        private boolean isSatisfiedSeq(Hashtable assignments, boolean considerCurrentAssignments, Set conflicts) {
    403            int gapMin = getGapMin(getType());
    404            int gapMax = getGapMax(getType());
    405            if (gapMin<0 || gapMax<0) return true;
    406
    407            Vector lengths = new FastVector();
    408
    409            Placement [] res = new Placement[edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY];
    410            for (int i=0;i<edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY;i++) res[i]=null;
    411
    412            Vector unAssignedLectures = new Vector();
    413            int nrLectures=0;
    414            String roomId = null;
    415
    416            for (Enumeration e=variables().elements();e.hasMoreElements();) {
    417                Lecture lecture = (Lecture)e.nextElement();
    418                Placement placement = (Placement)(assignments==null?null:assignments.get(lecture));
    419                if (placement==null && considerCurrentAssignments) placement = (Placement)lecture.getAssignment();
    420                if (placement==null) {
    421                    lengths.addElement(new Integer(((Placement)lecture.values().firstElement()).getTimeLocation().getLength()));
    422                } else {
    423                    int pos=placement.getTimeLocation().getSlots()[0] % edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY;
    424                    int length=placement.getTimeLocation().getLength();
    425                    for (int j=pos;j<pos+length;j++) {
    426                        if (res[j]!=null) {
    427                            if (conflicts==null) return false;
    428                            if (!assignments.containsKey(lecture))
    429                                conflicts.add(placement);
    430                            else if (!assignments.containsKey(res[j].variable()))
    431                                conflicts.add(res[j]);
    432                        }
    433                    }
    434                    for (int j=pos;j<pos+length;j++) res[j]=placement;
    435                    nrLectures++;
    436                }
    437            }
    438            if (nrLectures<=1) return true;
    439
    440            if (iIsRequired || (!iIsProhibited && iPreference<0)) {
    441                int i=0;
    442                Placement p=res[i];
    443                while (p==null) p=res[++i];
    444                i+=res[i].getTimeLocation().getLength();
    445                nrLectures--;
    446                while (nrLectures>0) {
    447                    int gap=0;
    448                    while (i<edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY && res[i]==null) { gap++; i++; }
    449                    if (i==edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY) break;
    450                    if (!canFill(gap, gapMin, gapMax, lengths)) {
    451                        if (conflicts==null) return false;
    452                        if (assignments==null || !assignments.containsKey(p.variable()))
    453                            conflicts.add(p);
    454                        else if (!assignments.containsKey(res[i].variable()))
    455                            conflicts.add(res[i]);
    456                    }
    457                    p=res[i];
    458                    i+=res[i].getTimeLocation().getLength();
    459                    nrLectures--;
    460                }
    461            } else if (iIsProhibited || (!iIsRequired && iPreference>0)) {
    462                int i=0;
    463                Placement p=res[i];
    464                while (p==null) p=res[++i];
    465                i+=res[i].getTimeLocation().getLength();
    466                nrLectures--;
    467                while (nrLectures>0) {
    468                    int gap=0;
    469                    while (i<edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY && res[i]==null) { gap++; i++; }
    470                    if (i==edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY) break;
    471                    if ((gapMin==0 || !canFill(gap, 0, gapMin-1, lengths)) &&
    472                            (gapMax>=edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY || !canFill(gap, gapMax+1, edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY, lengths))) {
    473                        if (conflicts==null) return false;
    474                        if (assignments==null || !assignments.containsKey(p.variable()))
    475                            conflicts.add(p);
    476                        else if (!assignments.containsKey(res[i].variable()))
    477                            conflicts.add(res[i]);
    478                    }
    479                    p=res[i];
    480                    i+=res[i].getTimeLocation().getLength();
    481                    nrLectures--;
    482                }
    483            }
    484            return true;
    485        }
    486
    487        private boolean isSatisfiedPair(Lecture lec1, Placement plc1, Lecture lec2, Placement plc2) {
    488            if (iIsRequired || (!iIsProhibited && iPreference<0)) {
    489                if (sameRoom(getType()) || (isBackToBack(getType()) && !isBackToBackTime(getType()))) {
    490                    if (!plc1.getRoomLocation().getId().equals(plc2.getRoomLocation().getId()))
    491                        return false;
    492                }
    493                if (sameStartHour(getType())) {
    494                    if ((plc1.getTimeLocation().getStartSlot()%edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY) !=
    495                            (plc2.getTimeLocation().getStartSlot()%edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY))
    496                        return false;
    497                }
    498                if (sameHours(getType())) {
    499                    if (!sameHours(plc1.getTimeLocation().getStartSlot(), plc1.getTimeLocation().getLength(),
    500                            plc2.getTimeLocation().getStartSlot(), plc2.getTimeLocation().getLength()))
    501                        return false;
    502                }
    503                if (sameDays(getType()) || isBackToBack(getType())) {
    504                    if (!sameDays(plc1.getTimeLocation().getStartSlots(), plc2.getTimeLocation().getStartSlots()))
    505                        return false;
    506                }
    507                if (notOverlap(getType())) {
    508                    if (plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()))
    509                        return false;
    510                }
    511            } else if (iIsProhibited || (!iIsRequired && iPreference>0)) {
    512                if (sameRoom(getType())) {
    513                    if (plc1.getRoomLocation().getId().equals(plc2.getRoomLocation().getId()))
    514                        return false;
    515                }
    516                if (sameHours(getType())) {
    517                    if (plc1.getTimeLocation().shareHours(plc2.getTimeLocation()))
    518                        return false;
    519                }
    520                if (sameStartHour(getType())) {
    521                    if ((plc1.getTimeLocation().getStartSlot()%edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY) ==
    522                            (plc2.getTimeLocation().getStartSlot()%edu.purdue.smas.timetable.util.Constants.SLOTS_PER_DAY))
    523                        return false;
    524                }
    525                if (sameDays(getType())) {
    526                    if (plc1.getTimeLocation().shareDays(plc2.getTimeLocation()))
    527                        return false;
    528                }
    529                if (notOverlap(getType())) {
    530                    if (!plc1.getTimeLocation().hasIntersection(plc2.getTimeLocation()))
    531                        return false;
    532                }
    533                if (isBackToBack(getType())) { //still same time
    534                    if (!sameDays(plc1.getTimeLocation().getStartSlots(), plc2.getTimeLocation().getStartSlots()))
    535                        return false;
    536                    if (!isBackToBackTime(getType())) { //still same room
    537                        if (!plc1.getRoomLocation().getId().equals(plc2.getRoomLocation().getId()))
    538                            return false;
    539                    }
    540                }
    541            }
    542            return true;
    543        }
    544
    545        /*
    546        public void getInfo(Dictionary info) {
    547            StringBuffer varNames = new StringBuffer();
    548            for (Enumeration e=variables().elements();e.hasMoreElements();) {
    549                Variable variable = (Variable)e.nextElement();
    550                varNames.append(varNames.length()>0?", ":"");
    551                varNames.append(variable.getName());
    552                if (variable.getAssignment()!=null)
    553                    varNames.append(" "+variable.getAssignment().getName());
    554            }
    555            info.put("gc"+iId, edu.purdue.smas.timetable.data.GroupConstraintTypes.getGroupConstraintType(iType).getDescription()+" (pref="+getDescription()+" ("+iIsRequired+"/"+iIsProhibited+"/"+iPreference+")"+", current="+getCurrentPreference()+", vars=["+varNames+"])");
    556        }
    557         */
    558
    559    }