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