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