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