001package org.cpsolver.instructor.constraints;
002
003import java.util.ArrayList;
004import java.util.BitSet;
005import java.util.Collection;
006import java.util.Comparator;
007import java.util.HashSet;
008import java.util.List;
009import java.util.Set;
010import java.util.TreeSet;
011import java.util.regex.Matcher;
012import java.util.regex.Pattern;
013
014import org.cpsolver.coursett.Constants;
015import org.cpsolver.coursett.model.TimeLocation;
016import org.cpsolver.ifs.assignment.Assignment;
017import org.cpsolver.ifs.model.GlobalConstraint;
018import org.cpsolver.ifs.util.ToolBox;
019import org.cpsolver.instructor.model.Instructor;
020import org.cpsolver.instructor.model.Section;
021import org.cpsolver.instructor.model.TeachingAssignment;
022import org.cpsolver.instructor.model.TeachingRequest;
023import org.cpsolver.instructor.model.TeachingRequest.Variable;
024
025/**
026 * Group Constraint. This constraint implements many of the course timetabling group and flexible constraints.
027 * See {@link ConstraintType} for the list, and the appropriate {@link org.cpsolver.coursett.constraint.GroupConstraint.ConstraintType}
028 * or {@link org.cpsolver.coursett.constraint.FlexibleConstraint} constraint for their description.
029 * Because the instructor - class assignments are dynamic, the constraints are implemented by a single group constraint.
030 * 
031 * @author  Tomáš Müller
032 * @version IFS 1.4 (Instructor Sectioning)<br>
033 *          Copyright (C) 2024 Tomáš Müller<br>
034 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
035 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
036 * <br>
037 *          This library is free software; you can redistribute it and/or modify
038 *          it under the terms of the GNU Lesser General Public License as
039 *          published by the Free Software Foundation; either version 3 of the
040 *          License, or (at your option) any later version. <br>
041 * <br>
042 *          This library is distributed in the hope that it will be useful, but
043 *          WITHOUT ANY WARRANTY; without even the implied warranty of
044 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
045 *          Lesser General Public License for more details. <br>
046 * <br>
047 *          You should have received a copy of the GNU Lesser General Public
048 *          License along with this library; if not see
049 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
050 */
051public class GroupConstraint extends GlobalConstraint<TeachingRequest.Variable, TeachingAssignment> {
052    
053    public GroupConstraint() {}
054    
055    @Override
056    public void computeConflicts(Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
057        for (Distribution d: value.getInstructor().getDistributions()) {
058            if (!d.isHard()) continue;
059            d.getType().computeConflicts(d, assignment, value, conflicts);
060        }
061    }
062    
063    @Override
064    public String getName() {
065        return "Distribution";
066    }
067    
068    @Override
069    public String toString() {
070        return getName();
071    }
072    
073    /**
074     * Wrapper class representing one distribution preference set on an instructor.
075     */
076    public static class Distribution {
077        GroupConstraint.ConstraintTypeInterface iType;
078        boolean iRequired = false;
079        boolean iProhibited = false;
080        int iPenalty = 0;
081        
082        public Distribution(GroupConstraint.ConstraintTypeInterface type, String preference) {
083            iType = type;
084            iRequired = Constants.sPreferenceRequired.equals(preference);
085            iProhibited = Constants.sPreferenceProhibited.equals(preference);
086            iPenalty = Constants.preference2preferenceLevel(preference);
087        }
088        
089        public GroupConstraint.ConstraintTypeInterface getType() { return iType; }
090        public int getPenalty() { return iPenalty; }
091        public boolean isRequired() { return iRequired; }
092        public boolean isProhibited() { return iProhibited; }
093        public boolean isHard() { return isRequired() || isProhibited(); }
094        public String getPreference() {
095            if (isRequired()) return Constants.sPreferenceRequired;
096            if (isProhibited()) return Constants.sPreferenceProhibited;
097            return Constants.preferenceLevel2preference(getPenalty());
098        }
099        public boolean isPositive() {
100            if (isRequired()) return true;
101            if (isProhibited()) return false;
102            return getPenalty() <= 0;
103        }
104
105        @SuppressWarnings("unchecked")
106        public <P> P getParameter() {
107            if (iType instanceof ParametrizedConstraintType)
108                return ((ParametrizedConstraintType<P>)iType).getParameter();
109            else
110                return null;
111        }
112    }
113
114    /**
115     * Group constraint check interface
116     */
117    public static interface Check {
118        public void computeConflicts(Distribution distribution, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts);
119        public double getValue(Distribution distribution, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value);
120    }
121    
122    /**
123     * Group constraint check interface for constraints that can be computed on individual class pairs.
124     */
125    public static abstract class PairCheck implements Check {
126        public abstract boolean isSatisfied(Distribution distribution, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, Section s1, Section s2);
127        public abstract boolean isViolated(Distribution distribution, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, Section s1, Section s2);
128        @Override
129        public double getValue(Distribution distribution, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
130            int ret = 0;
131            Set<TeachingAssignment> assignments = instructor.getContext(assignment).getAssignments();
132            if (value == null)
133                for (TeachingAssignment ta1: assignments) {
134                    for (Section s1: ta1.variable().getSections()) {
135                        for (TeachingAssignment ta2: instructor.getContext(assignment).getAssignments()) {
136                            for (Section s2: ta2.variable().getSections()) {
137                                if (s1.equals(s2)) continue;
138                                if (distribution.isPositive()) {
139                                    if (!isSatisfied(distribution, assignment, instructor, s1, s2)) ret ++;
140                                } else {
141                                    if (!isViolated(distribution, assignment, instructor, s1, s2)) ret ++;
142                                }
143                            }
144                        }
145                    }
146                }
147            else
148                for (Section s1: value.variable().getSections()) {
149                    for (TeachingAssignment ta2: assignments) {
150                        for (Section s2: ta2.variable().getSections()) {
151                            if (s1.equals(s2)) continue;
152                            if (distribution.isPositive()) {
153                                if (!isSatisfied(distribution, assignment, instructor, s1, s2)) ret ++;
154                            } else {
155                                if (!isViolated(distribution, assignment, instructor, s1, s2)) ret ++;
156                            }
157                        }
158                    }
159                }
160            if (ret == 0) return 0.0;
161            int n = assignments.size() + (value == null || assignment.getValue(value.variable()) != null ? 0 : 1);
162            return (2.0 * ret) / (n * (n - 1));
163        }
164        @Override
165        public void computeConflicts(Distribution distribution, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
166            for (Section s1: value.variable().getSections()) {
167                for (TeachingAssignment ta2: value.getInstructor().getContext(assignment).getAssignments()) {
168                    for (Section s2: ta2.variable().getSections()) {
169                        if (s1.equals(s2)) continue;
170                        if (distribution.isPositive()) {
171                            if (!isSatisfied(distribution, assignment, value.getInstructor(), s1, s2)) conflicts.add(ta2);
172                        } else {
173                            if (!isViolated(distribution, assignment, value.getInstructor(), s1, s2)) conflicts.add(ta2);
174                        }
175                    }
176                }
177            }
178        }
179    }
180    
181    /**
182     * Simplified group constraint check interface for constraints that can be computed on individual class pairs.
183     */
184    public static abstract class SimpleCheck extends PairCheck {
185        public abstract boolean isSatisfied(Distribution d, Section s1, Section s2);
186        public boolean isViolated(Distribution d,  Section s1, Section s2) { return true; }
187        @Override
188        public boolean isSatisfied(Distribution distribution, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, Section s1, Section s2) {
189            return isSatisfied(distribution, s1, s2);
190        }
191        @Override
192        public boolean isViolated(Distribution distribution, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, Section s1, Section s2) {
193            return isViolated(distribution, s1, s2);
194        }
195    }
196    
197    /**
198     * Simplified group constraint check interface for time-only constraints that can be computed on individual class pairs.
199     */
200    public static abstract class SimpleTimeCheck extends SimpleCheck {
201        public abstract boolean isSatisfied(Distribution d, TimeLocation t1, TimeLocation t2);
202        public boolean isViolated(Distribution d, TimeLocation t1, TimeLocation t2) { return true; }
203        @Override
204        public boolean isSatisfied(Distribution d, Section s1, Section s2) {
205            if (s1.getTime() == null || s2.getTime() == null) return true;
206            return isSatisfied(d, s1.getTime(), s2.getTime());
207        }
208        @Override
209        public boolean isViolated(Distribution d, Section s1, Section s2) {
210            if (s1.getTime() == null || s2.getTime() == null) return true;
211            return isViolated(d, s1.getTime(), s2.getTime());
212        }
213    }
214
215    /**
216     * Factory class for group constraints with parameters
217     */
218    public static interface ConstraintCreator<P> {
219        public ParametrizedConstraintType<P> create(String reference, String referenceRegExp);
220    }
221    
222    /**
223     * Interface for a distribution constraint type, including its implementation
224     */
225    public static interface ConstraintTypeInterface extends Check {
226        public ConstraintType type();
227        public String reference();
228        public String getName();
229    }
230    
231    /**
232     * Distribution constraint with parameters.
233     */
234    public static class ParametrizedConstraintType<P> implements ConstraintTypeInterface {
235        private String iReference;
236        private ConstraintType iType;
237        private P iParameter;
238        private String iName;
239        
240        public ParametrizedConstraintType(ConstraintType type, P parameter, String reference) {
241            iType = type; iParameter = parameter; iReference = reference;
242        }
243        
244        public ParametrizedConstraintType<P> setName(String name) { iName = name; return this; }
245        
246        @Override
247        public double getValue(Distribution distribution, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
248            return iType.check().getValue(distribution, assignment, instructor, value);
249        }
250        
251        @Override
252        public void computeConflicts(Distribution distribution, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
253            iType.check().computeConflicts(distribution, assignment, value, conflicts);
254        }
255
256        public P getParameter() { return iParameter; }
257        @Override
258        public ConstraintType type() { return iType; }
259        @Override
260        public String reference() { return iReference; }
261        @Override
262        public String getName() { return (iName == null ? iType.getName() : iName); }
263    }
264    
265    /**
266     * Distribution types and their implementation
267     */
268    public static enum ConstraintType implements ConstraintTypeInterface {
269        /**
270         * Same Days: Given classes must be taught on the same days. In case of classes of different time patterns, a class
271         * with fewer meetings must meet on a subset of the days used by the class with more meetings. For example, if one
272         * class pattern is 3x50, all others given in the constraint can only be taught on Monday, Wednesday, or Friday.
273         * For a 2x100 class MW, MF, WF is allowed but TTh is prohibited.<BR>
274         * When prohibited or (strongly) discouraged: any pair of classes classes cannot be taught on the same days (cannot
275         *  overlap in days). For instance, if one class is MFW, the second has to be TTh.
276         */
277        SAME_DAYS("SAME_DAYS", "Same Days", new SimpleTimeCheck() {
278            @Override
279            public boolean isSatisfied(Distribution d, TimeLocation t1, TimeLocation t2) {
280                return sameDays(t1.getDaysArray(), t2.getDaysArray());
281            }
282            @Override
283            public boolean isViolated(Distribution d, TimeLocation t1, TimeLocation t2) {
284                return !t1.shareDays(t2);
285            }
286            private boolean sameDays(int[] days1, int[] days2) {
287                if (days2.length < days1.length)
288                    return sameDays(days2, days1);
289                int i2 = 0;
290                for (int i1 = 0; i1 < days1.length; i1++) {
291                    int d1 = days1[i1];
292                    while (true) {
293                        if (i2 == days2.length)
294                            return false;
295                        int d2 = days2[i2];
296                        if (d1 == d2)
297                            break;
298                        i2++;
299                        if (i2 == days2.length)
300                            return false;
301                    }
302                    i2++;
303                }
304                return true;
305            }
306            }),
307        /**
308         * Same Start Time: Given classes must start during the same half-hour period of a day (independent of the actual
309         * day the classes meet). For instance, MW 7:30 is compatible with TTh 7:30 but not with MWF 8:00.<BR>
310         * When prohibited or (strongly) discouraged: any pair of classes in the given constraint cannot start during the
311         * same half-hour period of any day of the week.
312         */
313        SAME_START("SAME_START", "Same Start Time", new SimpleTimeCheck() {
314            @Override
315            public boolean isSatisfied(Distribution d, TimeLocation t1, TimeLocation t2) {
316                return (t1.getStartSlot() % Constants.SLOTS_PER_DAY) ==  (t2.getStartSlot() % Constants.SLOTS_PER_DAY);
317            }
318            @Override
319            public boolean isViolated(Distribution d, TimeLocation t1, TimeLocation t2) {
320                return (t1.getStartSlot() % Constants.SLOTS_PER_DAY) != (t2.getStartSlot() % Constants.SLOTS_PER_DAY);
321            }}),
322        /**
323         * Same Room: Given classes must be taught in the same room.<BR>
324         * When prohibited or (strongly) discouraged: any pair of classes in the constraint cannot be taught in the same room.
325         */
326        SAME_ROOM("SAME_ROOM", "Same Room", new SimpleCheck() {
327            @Override
328            public boolean isSatisfied(Distribution d, Section s1, Section s2) {
329                return s1.isSameRoom(s2);
330            }
331            @Override
332            public boolean isViolated(Distribution d, Section s1, Section s2) {
333                return !s1.isSameRoom(s2);
334            }}),
335        /**
336         * At Most X Hours A Day: Classes are to be placed in a way that there is no more than given number of hours in any day.
337         */
338        MAX_HRS_DAY("MAX_HRS_DAY\\(([0-9\\.]+)\\)", "At Most N Hours A Day", new Check() {
339            protected int nrSlotsADay(Set<TeachingAssignment> assignments, BitSet week, int dayCode, TeachingRequest.Variable variable, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
340                Set<Integer> slots = new HashSet<Integer>();
341                for (TeachingAssignment ta: assignments) {
342                    if (variable != null && variable.equals(ta.variable())) continue;
343                    if (conflicts != null && conflicts.contains(ta)) continue;
344                    for (Section section: ta.variable().getSections()) {
345                        TimeLocation t = section.getTime();
346                        if (t == null || (t.getDayCode() & dayCode) == 0 || (week != null && !t.shareWeeks(week))) continue;
347                        for (int i = 0; i < t.getLength(); i++)
348                            slots.add(i + t.getStartSlot());
349                    }
350                }
351                if (value != null) {
352                    for (Section section: value.variable().getSections()) {
353                        TimeLocation t = section.getTime();
354                        if (t == null || (t.getDayCode() & dayCode) == 0 || (week != null && !t.shareWeeks(week))) continue;
355                        for (int i = 0; i < t.getLength(); i++)
356                            slots.add(i + t.getStartSlot());
357                    }
358                }
359                return slots.size();
360            }
361            @Override
362            public double getValue(Distribution d, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
363                Integer max = d.getParameter();
364                Set<TeachingAssignment> assignments = instructor.getContext(assignment).getAssignments();
365                double over = 0.0;
366                for (int dayCode: Constants.DAY_CODES) {
367                    for (BitSet week: instructor.getModel().getWeeks()) {
368                        if (value == null) {
369                           over += Math.max(0, nrSlotsADay(assignments, week, dayCode, null, null, null) - max);
370                        } else {
371                            int before = Math.max(0, nrSlotsADay(assignments, week, dayCode, value.variable(), null, null) - max);
372                            int after = Math.max(0, nrSlotsADay(assignments, week, dayCode, value.variable(), value, null) - max);
373                            over += after - before;
374                        }
375                    }
376                }
377                return over/ (60.0 * instructor.getModel().getWeeks().size());
378            }
379            @Override
380            public void computeConflicts(Distribution d, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
381                Integer max = d.getParameter();
382                Set<TeachingAssignment> assignments = value.getInstructor().getContext(assignment).getAssignments();
383                for (int dayCode: Constants.DAY_CODES) {
384                    for (BitSet week: value.getInstructor().getModel().getWeeks()) {
385                        if (nrSlotsADay(assignments, week, dayCode, value.variable(), value, conflicts) > max) {
386                            List<TeachingAssignment> adepts = new ArrayList<TeachingAssignment>();
387                            for (TeachingAssignment ta: assignments) {
388                                if (ta.variable().equals(value.variable())) continue;
389                                if (conflicts.contains(ta)) continue;
390                                boolean hasDate = false;
391                                for (Section section: ta.variable().getSections()) {
392                                    TimeLocation t = section.getTime();
393                                    if (t != null && (t.getDayCode() & dayCode) != 0 && t.shareWeeks(week)) {
394                                        hasDate = true;
395                                        break;
396                                    }
397                                }
398                                if (hasDate) adepts.add(ta);
399                            }
400                            do {
401                                if (adepts.isEmpty()) { conflicts.add(value); break; }
402                                TeachingAssignment conflict = ToolBox.random(adepts);
403                                adepts.remove(conflict);
404                                conflicts.add(conflict);
405                            } while (nrSlotsADay(assignments, week, dayCode, value.variable(), value, conflicts) > max);
406                        }
407                    }
408                }
409            }}, new ConstraintCreator<Integer>() {
410            @Override
411            public ParametrizedConstraintType<Integer> create(String reference, String regexp) {
412                Matcher matcher = Pattern.compile(regexp).matcher(reference);
413                if (matcher.find()) {
414                    double hours = Double.parseDouble(matcher.group(1));
415                    int slots = (int)Math.round(12.0 * hours);
416                    return new ParametrizedConstraintType<Integer>(ConstraintType.MAX_HRS_DAY, slots, reference)
417                            .setName("At Most " + matcher.group(1) + " Hours A Day");
418                }
419                return null;
420            }}),
421        /**
422         * Given classes must be taught during the same weeks (i.e., must have the same date pattern).<br>
423         * When prohibited or (strongly) discouraged: any two classes must have non overlapping date patterns.
424         */
425        SAME_WEEKS("SAME_WEEKS", "Same Weeks", new SimpleTimeCheck() {
426            @Override
427            public boolean isSatisfied(Distribution d, TimeLocation t1, TimeLocation t2) {
428                return t1.getWeekCode().equals(t2.getWeekCode());
429            }
430            @Override
431            public boolean isViolated(Distribution d, TimeLocation t1, TimeLocation t2) {
432                return !t1.shareWeeks(t2);
433            }}),
434      /**
435       * Work Day: Classes are to be placed in a way that there is no more than given number of hours between the start of the first class and the end of the class one on any day.
436       */
437        WORKDAY("WORKDAY\\(([0-9\\.]+)\\)", "Work Day", new SimpleTimeCheck() {
438            @Override
439            public boolean isSatisfied(Distribution d, TimeLocation t1, TimeLocation t2) {
440                if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return true;
441                Integer parameter = d.getParameter();
442                return Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot()) <= parameter;
443            }}, new ConstraintCreator<Integer>() {
444                @Override
445                public ParametrizedConstraintType<Integer> create(String reference, String regexp) {
446                    Matcher matcher = Pattern.compile(regexp).matcher(reference);
447                    if (matcher.find()) {
448                        double hours = Double.parseDouble(matcher.group(1));
449                        int slots = (int)Math.round(12.0 * hours);
450                        return new ParametrizedConstraintType<Integer>(ConstraintType.WORKDAY, slots, reference)
451                                .setName(matcher.group(1) + " Hour Work Day");
452                    }
453                    return null;
454                }}),
455        /**
456         * Minimal gap between classes.
457         */
458        MIN_GAP("MIN_GAP\\(([0-9\\.]+)\\)", "Mininal Gap Between Classes", new SimpleTimeCheck() {
459            @Override
460            public boolean isSatisfied(Distribution d, TimeLocation t1, TimeLocation t2) {
461                if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return true;
462                Integer parameter = d.getParameter();
463                return t1.getStartSlot() + t1.getLength() + parameter <= t2.getStartSlot() ||
464                        t2.getStartSlot() + t2.getLength() + parameter <= t1.getStartSlot();
465            }}, new ConstraintCreator<Integer>() {
466            @Override
467            public ParametrizedConstraintType<Integer> create(String reference, String regexp) {
468                Matcher matcher = Pattern.compile(regexp).matcher(reference);
469                if (matcher.find()) {
470                    double hours = Double.parseDouble(matcher.group(1));
471                    int slots = (int)Math.round(12.0 * hours);
472                    return new ParametrizedConstraintType<Integer>(ConstraintType.MIN_GAP, slots, reference)
473                            .setName("At Least " + matcher.group(1) + " Hours Between Classes");
474                }
475                return null;
476            }}),
477        /**
478         * Given classes must be taught in a way there is a break between two blocks of classes. 
479         */
480        MAX_BLOCK("_(MaxBlock):([0-9]+):([0-9]+)_", "Max Block", new Check() {
481            @Override
482            public double getValue(Distribution d, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
483                int [] params = d.getParameter();
484                int maxBlockSlotsBTB = params[0];
485                int maxBreakBetweenBTB = params[1];
486                double penalty = 0;
487                // constraint is checked for every day in week
488                for (int dayCode : Constants.DAY_CODES) {
489                    // constraint is checked for every week in semester (or for the whole semester)
490                    for (BitSet week : instructor.getModel().getWeeks()) {
491                        // each blocks contains placements which are BTB
492                        List<Block> blocks = getBlocks(assignment, instructor, dayCode, null, (value == null ? null : value.variable()), value, week,  maxBreakBetweenBTB);
493                        for (Block block : blocks) {
494                            // ignore single-start/signle-class blocks
495                            if (block.getNbrPlacements() == 1 || block.haveSameStartTime()) continue;
496                            // violated if there is a block containing more than one
497                            // class longer than maxBlockSlotsBTB
498                            if (block.getLengthInSlots() > maxBlockSlotsBTB) {
499                                int blockLengthPenalty = block.getLengthInSlots() / maxBlockSlotsBTB;
500                                penalty += blockLengthPenalty;
501                            }
502                        }
503                    }
504                }
505                return penalty / (5.0 * instructor.getModel().getWeeks().size());
506            }
507            @Override
508            public void computeConflicts(Distribution d, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
509                int [] params = d.getParameter();
510                int maxBlockSlotsBTB = params[0];
511                int maxBreakBetweenBTB = params[1];
512                List<BitSet> weeks = value.getInstructor().getModel().getWeeks();
513                // constraint is checked for every day in week
514                for (int dayCode : Constants.DAY_CODES) {
515                    // constraint is checked for every week in semester (or for the whole semester)
516                    for (BitSet week : weeks) {
517                        boolean isProblem = false;
518                        do {
519                            isProblem = false;
520                            // each blocks contains placements which are BTB 
521                            List<Block> blocks = getBlocks(assignment, value.getInstructor(), dayCode, conflicts, value.variable(), value, week, maxBreakBetweenBTB);
522                            for (Block block : blocks) {
523                                // if the block is not affected by the current placement, continue
524                                if (!block.contains(value)) continue;
525                                Set<TeachingAssignment> adepts = new HashSet<TeachingAssignment>();                        
526                                // if there is only 1 placement in block, the block cannot be shortened
527                                // if placements of a block start at the same time, they intersect
528                                // this solves problem when between 2 classes is required MEET_TOGETHER  
529                                if (block.getNbrPlacements() == 1 || block.haveSameStartTime()) continue;
530                                // if block is longer than maximum size, some of its placements are conflicts
531                                if (block.getLengthInSlots() > maxBlockSlotsBTB) {
532                                    // classes from block are potential conflicts
533                                    for (TeachingAssignmentSection tas: block.getSections())
534                                        adepts.add(tas.getTeachingAssignment());                     
535                                    // do not set currently assigned value as conflict
536                                    adepts.remove(value);
537                                    isProblem = true;
538                                    // pick random placement
539                                    TeachingAssignment conflict = ToolBox.random(adepts);
540                                    if (conflict != null) {
541                                        conflicts.add(conflict);
542                                    }
543                                }
544                            }
545                        } while (isProblem);
546                    }
547                }
548            }}, new ConstraintCreator<int[]>() {
549            @Override
550            public ParametrizedConstraintType<int[]> create(String reference, String regexp) {
551                Matcher matcher = Pattern.compile(regexp).matcher(reference);
552                if (matcher.find()) {
553                    int maxBlockSlotsBTB = Integer.parseInt(matcher.group(2))/Constants.SLOT_LENGTH_MIN;
554                    int maxBreakBetweenBTB = Integer.parseInt(matcher.group(3))/Constants.SLOT_LENGTH_MIN;
555                    return new ParametrizedConstraintType<int[]>(ConstraintType.MAX_BLOCK, new int[] {maxBlockSlotsBTB, maxBreakBetweenBTB}, reference)
556                            .setName("Max " + (maxBlockSlotsBTB / 12.0) + "h Blocks");
557                }
558                return null;
559            }}),
560        /**
561         * Limit number of breaks between adjacent classes on a day.
562         */
563        MAX_BREAKS("_(MaxBreaks):([0-9]+):([0-9]+)_", "Max Breaks", new Check() {
564            @Override
565            public double getValue(Distribution d, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
566                int [] params = d.getParameter();
567                int maxBlocksOnADay = params[0];
568                int maxBreakBetweenBTB = params[1];
569                double penalty = 0;
570                // constraint is checked for every day in week
571                for (int dayCode : Constants.DAY_CODES) {
572                    // constraint is checked for every week in semester (or for the whole semester)
573                    for (BitSet week : instructor.getModel().getWeeks()) {
574                        // each blocks contains placements which are BTB
575                        List<Block> blocks = getBlocks(assignment, instructor, dayCode, null, (value == null ? null : value.variable()), value, week,  maxBreakBetweenBTB);
576                        // too many blocks -> increase penalty
577                        if (blocks.size() > maxBlocksOnADay)
578                            penalty += (blocks.size() - maxBlocksOnADay);
579                    }
580                }
581                return penalty / (5.0 * instructor.getModel().getWeeks().size());
582            }
583            @Override
584            public void computeConflicts(Distribution d, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
585                int [] params = d.getParameter();
586                int maxBlocksOnADay = params[0];
587                int maxBreakBetweenBTB = params[1];
588                List<BitSet> weeks = value.getInstructor().getModel().getWeeks();
589                // constraint is checked for every day in week
590                for (int dayCode : Constants.DAY_CODES) {
591                    // constraint is checked for every week in semester (or for the whole semester)
592                    for (BitSet week : weeks) {
593                     // each blocks contains placements which are BTB 
594                        List<Block> blocks = getBlocks(assignment, value.getInstructor(), dayCode, conflicts, value.variable(), value, week, maxBreakBetweenBTB);
595                        while (blocks.size() > maxBlocksOnADay) {
596                            // too many blocks -> identify adepts for unassignment
597                            List<Block> adepts = new ArrayList<Block>(); int size = 0;
598                            for (Block block: blocks) {
599                                if (block.contains(value)) continue; // skip block containing given value
600                                // select adepts of the smallest size
601                                if (adepts.isEmpty() || size > block.getSections().size()) {
602                                    adepts.clear();
603                                    adepts.add(block);
604                                    size = block.getSections().size();
605                                } else if (size == block.getSections().size()) {
606                                    adepts.add(block);
607                                }
608                            }
609                            // pick one randomly
610                            Block block = ToolBox.random(adepts);
611                            blocks.remove(block);
612                            for (TeachingAssignmentSection tas: block.getSections())
613                                if (tas.getTeachingAssignment().equals(assignment.getValue(tas.getTeachingAssignment().variable())))
614                                    conflicts.add(tas.getTeachingAssignment());
615                        }
616                    }
617                }
618            }}, new ConstraintCreator<int[]>() {
619            @Override
620            public ParametrizedConstraintType<int[]> create(String reference, String regexp) {
621                Matcher matcher = Pattern.compile(regexp).matcher(reference);
622                if (matcher.find()) {
623                    int maxBlocksOnADay = 1 + Integer.parseInt(matcher.group(2));
624                    int maxBreakBetweenBTB = Integer.parseInt(matcher.group(3)) / Constants.SLOT_LENGTH_MIN;
625                    return new ParametrizedConstraintType<int[]>(ConstraintType.MAX_BREAKS, new int[] {maxBlocksOnADay, maxBreakBetweenBTB}, reference)
626                            .setName(maxBlocksOnADay == 1 ? "No Break" : maxBlocksOnADay == 2 ? "Max 1 Break" : "Max " + (maxBlocksOnADay - 1) + " Breaks");
627                }
628                return null;
629            }}),
630        /**
631         * Limit number of days of a week. 
632         */
633        MAX_DAYS("_(MaxDays):([0-9]+)_", "Max Days", new Check() {
634            protected boolean hasDay(BitSet week, int dayOfWeek, Section section) {
635                if (section.getTime() == null || !section.getTime().getWeekCode().intersects(week)) return false;
636                return (section.getTime().getDayCode() & Constants.DAY_CODES[dayOfWeek]) != 0;
637            }
638            protected boolean hasDay(BitSet week, int dayOfWeek, TeachingAssignment ta) {
639                for (Section section: ta.variable().getSections())
640                    if (hasDay(week, dayOfWeek, section)) return true;
641                return false;
642            }
643            @Override
644            public double getValue(Distribution d, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
645                Integer maxDays  = d.getParameter();
646                Set<TeachingAssignment> assignments = instructor.getContext(assignment).getAssignments();
647                double penalty = 0;
648                for (BitSet week: instructor.getModel().getWeeks()) {
649                    Set<Integer> days = new HashSet<Integer>();
650                    for (TeachingAssignment ta: assignments) {
651                        if (value != null && value.variable().equals(ta.variable())) continue;
652                        for (int day = 0; day < Constants.DAY_CODES.length; day++)
653                            if (hasDay(week, day, ta))
654                                days.add(day);
655                    }
656                    if (value != null) {
657                        for (int day = 0; day < Constants.DAY_CODES.length; day++)
658                            if (hasDay(week, day, value) && days.add(day) && days.size() > maxDays)
659                                penalty += 1.0;
660                    } else {
661                        penalty += Math.max(0, days.size() - maxDays);
662                    }
663                }
664                return penalty / (Math.max(1.0, 5.0 - maxDays) * instructor.getModel().getWeeks().size());
665            }
666            @Override
667            public void computeConflicts(Distribution d, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
668                Integer maxDays  = d.getParameter();
669                Set<TeachingAssignment> assignments = value.getInstructor().getContext(assignment).getAssignments();
670                for (BitSet week: value.getInstructor().getModel().getWeeks()) {
671                    Set<Integer> selectedDays = new HashSet<Integer>();
672                    for (int day = 0; day < Constants.DAY_CODES.length; day++)
673                        if (hasDay(week, day, value))
674                            selectedDays.add(day);
675                    // selected value has no days -> next week
676                    if (selectedDays.isEmpty()) continue;
677                    // selected value is over -> it cannot be assigned
678                    if (selectedDays.size() > maxDays) {
679                        conflicts.add(value); continue;
680                    }
681                    // check other days
682                    while (true) {
683                        Set<Integer> otherDays = new HashSet<Integer>();
684                        for (TeachingAssignment ta: assignments) {
685                            if (value != null && value.variable().equals(ta.variable())) continue;
686                            if (conflicts.contains(ta)) continue;
687                            for (int day = 0; day < Constants.DAY_CODES.length; day++)
688                                if (!selectedDays.contains(day) && hasDay(week, day, ta))
689                                    otherDays.add(day);
690                        }
691                        if (otherDays.size() + selectedDays.size() <= maxDays) break;
692                        int day = ToolBox.random(otherDays);
693                        for (TeachingAssignment ta: assignments) {
694                            if (value != null && value.variable().equals(ta.variable())) continue;
695                            if (conflicts.contains(ta)) continue;
696                            if (hasDay(week, day, ta))
697                                conflicts.add(ta);
698                        }
699                    }
700                }
701            }}, new ConstraintCreator<Integer>() {
702            @Override
703            public ParametrizedConstraintType<Integer> create(String reference, String regexp) {
704                Matcher matcher = Pattern.compile(regexp).matcher(reference);
705                if (matcher.find()) {
706                    int maxDays =  Integer.parseInt(matcher.group(2));
707                    return new ParametrizedConstraintType<Integer>(ConstraintType.MAX_DAYS, maxDays, reference)
708                            .setName(maxDays == 1 ? "Max 1 Day" : "Max " + maxDays + " Days");
709                }
710                return null;
711            }}),
712        /**
713         * There must be a break of a given length in a given time interval.
714         */
715        BREAK("_(Break):([0-9]+):([0-9]+):([0-9]+)_", "Break", new Check() {
716            @Override
717            public double getValue(Distribution d, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
718                int [] params = d.getParameter();
719                int breakStart = params[0];
720                int breakEnd = params[1];
721                int breakLength = params[2];
722                double penalty = 0;
723                // constraint is checked for every day in week
724                for (int dayCode : Constants.DAY_CODES) {
725                    // constraint is checked for every week in semester (or for the whole semester)
726                    for (BitSet week : instructor.getModel().getWeeks()) {
727                        // each blocks contains placements which are BTB
728                        List<Block> blocks = getBlocks(assignment, instructor, dayCode, null, (value == null ? null : value.variable()) ,value, week,  breakLength);
729                        // too many blocks -> increase penalty
730                        List<Block> matchingBlocks = new ArrayList<Block>();
731                        for(Block block: blocks) {
732                            // if block intersects with break interval, it will be used in conflict selection
733                            if (block.getStartSlotCurrentBlock() <= breakEnd && block.getEndSlotCurrentBlock() >= breakStart)
734                                matchingBlocks.add(block);          
735                        }
736                        int size = matchingBlocks.size();
737                        if (size == 1) {
738                            Block block = matchingBlocks.get(0);
739                            // the matching block does not contain the given placement -> ignore
740                            if (value != null && !block.contains(value)) continue;
741                            // check whether the block leaves enough space for break
742                            if (block.getStartSlotCurrentBlock() - breakStart >= breakLength || breakEnd - block.getEndSlotCurrentBlock() >= breakLength)
743                                continue;
744                            // if it doesn't
745                            penalty += 1.0;
746                        }   
747                    }
748                }
749                return penalty / (5.0 * instructor.getModel().getWeeks().size());
750            }
751            @Override
752            public void computeConflicts(Distribution d, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
753                int [] params = d.getParameter();
754                int breakStart = params[0];
755                int breakEnd = params[1];
756                int breakLength = params[2];
757                // constraint is checked for every day in week
758                for (int dayCode : Constants.DAY_CODES) {
759                    // constraint is checked for every week in semester (or for the whole semester)
760                    for (BitSet week : value.getInstructor().getModel().getWeeks()) {
761                        while (true) {
762                            // each blocks contains placements which are BTB
763                            List<Block> blocks = getBlocks(assignment, value.getInstructor(), dayCode, conflicts, value.variable(), value, week,  breakLength);
764                            // too many blocks -> increase penalty
765                            List<Block> matchingBlocks = new ArrayList<Block>();
766                            for(Block block: blocks) {
767                                // if block intersects with break interval, it will be used in conflict selection
768                                if (block.getStartSlotCurrentBlock() <= breakEnd && block.getEndSlotCurrentBlock() >= breakStart)
769                                    matchingBlocks.add(block);          
770                            }
771                            int size = matchingBlocks.size();
772                            if (size == 1) {
773                                Block block = matchingBlocks.get(0);
774                                // the matching block does not contain the given placement -> ignore
775                                if (!block.contains(value)) break;
776                                // check whether the block leaves enough space for break
777                                if (block.getStartSlotCurrentBlock() - breakStart >= breakLength || breakEnd - block.getEndSlotCurrentBlock() >= breakLength)
778                                    break;
779                                // if it doesn't
780                                List<TeachingAssignmentSection> adepts = new ArrayList<TeachingAssignmentSection>();
781                                // every placement intersecting with break interval might be potential conflict
782                                for (TeachingAssignmentSection p: block.getSections())
783                                    if (p.getTime().getStartSlot() <= breakEnd && p.getTime().getStartSlot()+ p.getTime().getLength() >= breakStart)
784                                        adepts.add(p);
785                                if (adepts.size() > 0) {
786                                    conflicts.add(ToolBox.random(adepts).getTeachingAssignment());
787                                    continue;
788                                }
789                                break;
790                            }
791                        }   
792                    }
793                }
794            }}, new ConstraintCreator<int[]>() {
795            @Override
796            public ParametrizedConstraintType<int[]> create(String reference, String regexp) {
797                Matcher matcher = Pattern.compile(regexp).matcher(reference);
798                if (matcher.find()) {
799                    int breakStart = Integer.parseInt(matcher.group(2));
800                    int breakEnd = Integer.parseInt(matcher.group(3)); 
801                    int breakLength = Integer.parseInt(matcher.group(4))/Constants.SLOT_LENGTH_MIN;
802                    return new ParametrizedConstraintType<int[]>(ConstraintType.BREAK, new int[] {breakStart, breakEnd, breakLength}, reference)
803                            .setName((breakEnd * 5) + " Min Break");
804                }
805                return null;
806            }}),
807        /**
808         * Limit number of weeks on which an a class can take place.
809         */
810        MAX_WEEKS("_(MaxWeeks):([0-9]+):([0-9]+)_", "Max Weeks", new Check() {
811            @Override
812            public double getValue(Distribution d, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
813                int [] params = d.getParameter();
814                int maxWeeks = params[0];
815                int dayCode = params[1];
816                if (value != null && !isCorectDayOfWeek(value, dayCode)) return 0.0;
817                Set<TeachingAssignment> assignments = instructor.getContext(assignment).getAssignments();
818                double penalty = 0;
819                Set<BitSet> weeks = new HashSet<BitSet>();
820                for (BitSet week: instructor.getModel().getWeeks()) {
821                    for (TeachingAssignment ta: assignments) {
822                        if (value != null && value.variable().equals(ta.variable())) continue;
823                        if (isCorectDayAndWeek(ta, dayCode, week))
824                            weeks.add(week);
825                    }
826                }
827                if (value != null) {
828                    for (BitSet week: instructor.getModel().getWeeks()) {
829                        if (isCorectDayAndWeek(value, dayCode, week) && weeks.add(week) && weeks.size() > maxWeeks)
830                            penalty += 1.0;
831                    }
832                } else {
833                    penalty += Math.max(0.0, weeks.size() - maxWeeks);
834                }
835                return penalty / Math.max(1.0, instructor.getModel().getWeeks().size() - maxWeeks);
836            }
837            @Override
838            public void computeConflicts(Distribution d, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
839                int [] params = d.getParameter();
840                int maxWeeks = params[0];
841                int dayCode = params[1];
842                if (!isCorectDayOfWeek(value, dayCode)) return;
843                
844                Set<BitSet> selectedWeeks = new HashSet<BitSet>();
845                for (BitSet week: value.getInstructor().getModel().getWeeks()) {
846                    if (isCorectDayAndWeek(value, dayCode, week))
847                        selectedWeeks.add(week);
848                }
849                if (selectedWeeks.size() > maxWeeks) {
850                    conflicts.add(value);
851                    return;
852                }
853                Set<TeachingAssignment> assignments = value.getInstructor().getContext(assignment).getAssignments();
854                while (true) {
855                    Set<BitSet> otherWeeks = new HashSet<BitSet>();
856                    for (BitSet week: value.getInstructor().getModel().getWeeks()) {
857                        if (selectedWeeks.contains(week)) continue;
858                        for (TeachingAssignment ta: assignments) {
859                            if (value != null && value.variable().equals(ta.variable())) continue;
860                            if (conflicts.contains(ta)) continue;
861                            if (isCorectDayAndWeek(ta, dayCode, week))
862                                otherWeeks.add(week);
863                        }
864                    }
865                    if (otherWeeks.size() + selectedWeeks.size() <= maxWeeks) break;
866                    BitSet week = ToolBox.random(otherWeeks);
867                    for (TeachingAssignment ta: assignments) {
868                        if (value != null && value.variable().equals(ta.variable())) continue;
869                        if (conflicts.contains(ta)) continue;
870                        if (isCorectDayAndWeek(ta, dayCode, week)) {
871                            conflicts.add(ta);
872                            break;
873                        }
874                    }
875                }
876            }}, new ConstraintCreator<int[]>() {
877            @Override
878            public ParametrizedConstraintType<int[]> create(String reference, String regexp) {
879                Matcher matcher = Pattern.compile(regexp).matcher(reference);
880                if (matcher.find()) {
881                    int maxWeeks = Integer.parseInt(matcher.group(2));
882                    int dayCode = Integer.parseInt(matcher.group(3));
883                    return new ParametrizedConstraintType<int[]>(ConstraintType.MAX_WEEKS, new int[] {maxWeeks, dayCode}, reference)
884                            .setName("Max " + maxWeeks + " Weeks");
885                }
886                return null;
887            }}),
888        /**
889         * Minimize free time of an instructor during a day (between the first and the last class).
890         */
891        MAX_HOLES("_(MaxHoles):([0-9]+)_", "Max Holes", new Check() {
892            int countHoles(Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor,int dayCode, Set<TeachingAssignment> conflicts, TeachingRequest.Variable variable, TeachingAssignment value, BitSet week) {
893                Set<TeachingAssignmentSection> placements = getRelevantPlacements(assignment, instructor, dayCode, conflicts, variable, value, week);
894                int lastSlot = -1;
895                int holes = 0;
896                for (TeachingAssignmentSection placement: placements) {
897                    if (lastSlot >= 0 && placement.getTime().getStartSlot() > lastSlot) {
898                        holes += (placement.getTime().getStartSlot() - lastSlot);
899                    }
900                    lastSlot = Math.max(lastSlot, placement.getTime().getStartSlot() + placement.getTime().getLength());
901                }
902                return holes;
903            }
904            
905            @Override
906            public double getValue(Distribution d, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
907                int [] params = d.getParameter();
908                int maxHolesOnADay = params[0];
909                double penalty = 0;
910                for (int dayCode : Constants.DAY_CODES) {
911                    for (BitSet week: instructor.getModel().getWeeks()) {
912                        if (value != null && !isCorectDayAndWeek(value, dayCode, week)) continue;
913                        if (value == null) {
914                            penalty += Math.max(0, countHoles(assignment, instructor, dayCode, null, null, null, week) - maxHolesOnADay);
915                        } else {
916                            int before = Math.max(0, countHoles(assignment, instructor, dayCode, null, value.variable(), null, week) - maxHolesOnADay);
917                            int after = Math.max(0, countHoles(assignment, instructor, dayCode, null, value.variable(), value, week) - maxHolesOnADay);
918                            penalty += after - before;
919                        }
920                    }
921                }
922                return penalty / (60.0 * instructor.getModel().getWeeks().size());
923            }
924            @Override
925            public void computeConflicts(Distribution d, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
926                int [] params = d.getParameter();
927                int maxHolesOnADay = params[0];
928                for (int dayCode : Constants.DAY_CODES) {
929                    for (BitSet week : value.getInstructor().getModel().getWeeks()) {
930                        if (!isCorectDayAndWeek(value, dayCode, week)) continue;
931                        int penalty = countHoles(assignment, value.getInstructor(), dayCode, conflicts, value.variable(), value, week);
932                        while (penalty > maxHolesOnADay) {
933                            List<TeachingAssignmentSection> adepts = new ArrayList<TeachingAssignmentSection>();
934                            for (TeachingAssignmentSection placement: getRelevantPlacements(assignment, value.getInstructor(), dayCode, conflicts, value.variable(), value, week)) {
935                                if (placement.getTeachingAssignment().equals(value)) continue; // skip given value
936                                // check if removing placement would improve the penalty
937                                Set<TeachingAssignment> test = new HashSet<TeachingAssignment>(conflicts); test.add(placement.getTeachingAssignment());
938                                int newPenalty = countHoles(assignment, value.getInstructor(), dayCode, test, value.variable(), value, week);
939                                if (newPenalty <= penalty)
940                                    adepts.add(placement);
941                            }
942                            
943                            // no adepts -> fail
944                            if (adepts.isEmpty()) {
945                                conflicts.add(value); return;
946                            }
947                            
948                            // pick one randomly
949                            conflicts.add(ToolBox.random(adepts).getTeachingAssignment());
950                            penalty = countHoles(assignment, value.getInstructor(), dayCode, conflicts, value.variable(), value, week);
951                        }
952                    }
953                }
954            }}, new ConstraintCreator<int[]>() {
955            @Override
956            public ParametrizedConstraintType<int[]> create(String reference, String regexp) {
957                Matcher matcher = Pattern.compile(regexp).matcher(reference);
958                if (matcher.find()) {
959                    int maxHolesOnADay = Integer.parseInt(matcher.group(2)) / Constants.SLOT_LENGTH_MIN;
960                    return new ParametrizedConstraintType<int[]>(ConstraintType.MAX_HOLES, new int[] {maxHolesOnADay}, reference)
961                            .setName("Max " + (maxHolesOnADay/12.0) + " Free Hours");
962                }
963                return null;
964            }}),
965        /**
966         * Limit number of half-days of a week. 
967         */
968        MAX_HALF_DAYS("_(MaxHalfDays):([0-9]+)_", "Max Half-Days", new Check() {
969            private Integer iNoonSlot = null; 
970            protected boolean hasHalfDay(BitSet week, int dayOfWeek, Section section, boolean morning) {
971                if (section.getTime() == null || !section.getTime().getWeekCode().intersects(week)) return false;
972                if ((section.getTime().getDayCode() & Constants.DAY_CODES[dayOfWeek]) == 0) return false;
973                if (morning)
974                    return section.getTime().getStartSlot() < iNoonSlot;
975                else
976                    return section.getTime().getStartSlot() >= iNoonSlot;
977            }
978            protected boolean hasHalfDay(BitSet week, int dayOfWeek, TeachingAssignment ta, boolean morning) {
979                for (Section section: ta.variable().getSections())
980                    if (hasHalfDay(week, dayOfWeek, section, morning)) return true;
981                return false;
982            }
983            
984            @Override
985            public double getValue(Distribution d, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
986                if (iNoonSlot == null)
987                    iNoonSlot = instructor.getModel().getProperties().getPropertyInteger("General.HalfDaySlot", 144);
988                int [] params = d.getParameter();
989                int maxHalfDays = params[0];
990                double penalty = 0;
991                Set<TeachingAssignment> assignments = instructor.getContext(assignment).getAssignments();
992                for (BitSet week: instructor.getModel().getWeeks()) {
993                    Set<Integer> mornings = new HashSet<Integer>();
994                    Set<Integer> afternoons = new HashSet<Integer>();
995                    for (TeachingAssignment ta: assignments) {
996                        if (value != null && value.variable().equals(ta.variable())) continue;
997                        for (int day = 0; day < Constants.DAY_CODES.length; day++) {
998                            if (hasHalfDay(week, day, ta, true))
999                                mornings.add(day);
1000                            if (hasHalfDay(week, day, ta, false))
1001                                afternoons.add(day);
1002                        }
1003                    }
1004                    if (value != null) {
1005                        for (int day = 0; day < Constants.DAY_CODES.length; day++) {
1006                            if (hasHalfDay(week, day, value, true) && mornings.add(day) && (mornings.size() + afternoons.size()) > maxHalfDays)
1007                                penalty += 1.0;
1008                            if (hasHalfDay(week, day, value, false) && afternoons.add(day) && (mornings.size() + afternoons.size()) > maxHalfDays)
1009                                penalty += 1.0;
1010                        }
1011                    } else {
1012                        penalty += Math.max(0, mornings.size() + afternoons.size() - maxHalfDays);
1013                    }
1014                }
1015                return penalty / (Math.max(1.0, 10.0 - maxHalfDays) * instructor.getModel().getWeeks().size());
1016            }
1017            @Override
1018            public void computeConflicts(Distribution d, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
1019                if (iNoonSlot == null)
1020                    iNoonSlot = value.getInstructor().getModel().getProperties().getPropertyInteger("General.HalfDaySlot", 144);
1021                int [] params = d.getParameter();
1022                int maxHalfDays = params[0];
1023                Set<TeachingAssignment> assignments = value.getInstructor().getContext(assignment).getAssignments();
1024                for (BitSet week: value.getInstructor().getModel().getWeeks()) {
1025                    Set<Integer> selectedHalfDays = new HashSet<Integer>();
1026                    for (int day = 0; day < Constants.DAY_CODES.length; day++) {
1027                        if (hasHalfDay(week, day, value, true))
1028                            selectedHalfDays.add(2 * day);
1029                        if (hasHalfDay(week, day, value, false))
1030                            selectedHalfDays.add(2 * day + 1);
1031                    }
1032                    // selected value has no days -> next week
1033                    if (selectedHalfDays.size() == 0) continue;
1034                    // selected value is over -> it cannot be assigned
1035                    if (selectedHalfDays.size() > maxHalfDays) {
1036                        conflicts.add(value); continue;
1037                    }
1038                    // check other days
1039                    while (true) {
1040                        Set<Integer> otherHalfDays = new HashSet<Integer>();
1041                        for (TeachingAssignment ta: assignments) {
1042                            if (value != null && value.variable().equals(ta.variable())) continue;
1043                            if (conflicts.contains(ta)) continue;
1044                            for (int day = 0; day < Constants.DAY_CODES.length; day++) {
1045                                if (!selectedHalfDays.contains(2 * day) && hasHalfDay(week, day, ta, true))
1046                                    otherHalfDays.add(2 * day);
1047                                if (!selectedHalfDays.contains(2 * day + 1) && hasHalfDay(week, day, ta, false))
1048                                    otherHalfDays.add(2 * day + 1);
1049                            }
1050                        }
1051                        if (selectedHalfDays.size() + otherHalfDays.size() <= maxHalfDays) break;
1052                        int halfday = ToolBox.random(otherHalfDays);
1053                        int day = halfday / 2;
1054                        boolean morning = ((halfday % 2) == 0);
1055                        for (TeachingAssignment ta: assignments) {
1056                            if (value != null && value.variable().equals(ta.variable())) continue;
1057                            if (conflicts.contains(ta)) continue;
1058                            if (hasHalfDay(week, day, ta, morning))
1059                                conflicts.add(ta);
1060                        }
1061                    }
1062                }
1063            }}, new ConstraintCreator<int[]>() {
1064            @Override
1065            public ParametrizedConstraintType<int[]> create(String reference, String regexp) {
1066                Matcher matcher = Pattern.compile(regexp).matcher(reference);
1067                if (matcher.find()) {
1068                    int maxHalfDays = Integer.parseInt(matcher.group(2));
1069                    return new ParametrizedConstraintType<int[]>(ConstraintType.MAX_HALF_DAYS, new int[] {maxHalfDays}, reference)
1070                            .setName("Max " + maxHalfDays + " Half-Days");
1071                }
1072                return null;
1073            }}),
1074        /**
1075         * Limit number of consecutive days of a week. 
1076         */
1077        MAX_CONSECUTIVE_DAYS("_(MaxConsDays):([0-9]+)_", "Max Consecutive Days", new Check() {
1078            protected boolean hasDay(BitSet week, int dayOfWeek, Section section) {
1079                if (section.getTime() == null || !section.getTime().getWeekCode().intersects(week)) return false;
1080                return (section.getTime().getDayCode() & Constants.DAY_CODES[dayOfWeek]) != 0;
1081            }
1082            protected boolean hasDay(BitSet week, int dayOfWeek, TeachingAssignment ta) {
1083                for (Section section: ta.variable().getSections())
1084                    if (hasDay(week, dayOfWeek, section)) return true;
1085                return false;
1086            }
1087            protected int countDays(TreeSet<Integer> days) {
1088                if (days.isEmpty()) return 0;
1089                return days.last() - days.first() + 1;
1090            }
1091            protected int countDays(TreeSet<Integer> days1, TreeSet<Integer> days2) {
1092                if (days1.isEmpty()) return countDays(days2);
1093                if (days2.isEmpty()) return countDays(days1);
1094                return Math.max(days1.last(), days2.last()) - Math.min(days1.first(), days2.first()) + 1;
1095            }
1096            @Override
1097            public double getValue(Distribution d, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
1098                int [] params = d.getParameter();
1099                int maxDays = params[0];
1100                double penalty = 0;
1101                Set<TeachingAssignment> assignments = instructor.getContext(assignment).getAssignments();
1102                for (BitSet week: instructor.getModel().getWeeks()) {
1103                    TreeSet<Integer> days = new TreeSet<Integer>();
1104                    for (TeachingAssignment ta: assignments) {
1105                        if (value != null && value.variable().equals(ta.variable())) continue;
1106                        for (int day = 0; day < Constants.DAY_CODES.length; day++)
1107                            if (hasDay(week, day, ta))
1108                                days.add(day);
1109                    }
1110                    if (value != null) {
1111                        int before = Math.max(0, countDays(days) - maxDays);
1112                        for (int day = 0; day < Constants.DAY_CODES.length; day++)
1113                            if (hasDay(week, day, value))
1114                                days.add(day);
1115                        int after = Math.max(0, countDays(days) - maxDays);
1116                        penalty += after - before;
1117                    } else {
1118                        penalty += Math.max(0, countDays(days) - maxDays);
1119                    }
1120                }
1121                return penalty / (Math.max(1.0, 5.0 - maxDays) * instructor.getModel().getWeeks().size());
1122            }
1123            @Override
1124            public void computeConflicts(Distribution d, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
1125                int [] params = d.getParameter();
1126                int maxDays = params[0];
1127                Set<TeachingAssignment> assignments = value.getInstructor().getContext(assignment).getAssignments();
1128                for (BitSet week: value.getInstructor().getModel().getWeeks()) {
1129                    TreeSet<Integer> selectedDays = new TreeSet<Integer>();
1130                    for (int day = 0; day < Constants.DAY_CODES.length; day++)
1131                        if (hasDay(week, day, value))
1132                            selectedDays.add(day);
1133                    // selected value has no days -> next week
1134                    if (selectedDays.isEmpty()) continue;
1135                    // selected value is over -> it cannot be assigned
1136                    if (countDays(selectedDays) > maxDays) {
1137                        conflicts.add(value); continue;
1138                    }
1139                    // check other days
1140                    while (true) {
1141                        TreeSet<Integer> otherDays = new TreeSet<Integer>();
1142                        for (TeachingAssignment ta: assignments) {
1143                            if (value != null && value.variable().equals(ta.variable())) continue;
1144                            if (conflicts.contains(ta)) continue;
1145                            for (int day = 0; day < Constants.DAY_CODES.length; day++)
1146                                if (!selectedDays.contains(day) && hasDay(week, day, ta))
1147                                    otherDays.add(day);
1148                        }
1149                        if (countDays(selectedDays, otherDays) <= maxDays) break;
1150                        int day = (ToolBox.random(1) == 0 ? otherDays.first() : otherDays.last());
1151                        for (TeachingAssignment ta: assignments) {
1152                            if (value != null && value.variable().equals(ta.variable())) continue;
1153                            if (conflicts.contains(ta)) continue;
1154                            if (hasDay(week, day, ta))
1155                                conflicts.add(ta);
1156                        }
1157                    }
1158                }
1159            }}, new ConstraintCreator<int[]>() {
1160            @Override
1161            public ParametrizedConstraintType<int[]> create(String reference, String regexp) {
1162                Matcher matcher = Pattern.compile(regexp).matcher(reference);
1163                if (matcher.find()) {
1164                    int maxDays = Integer.parseInt(matcher.group(2));
1165                    return new ParametrizedConstraintType<int[]>(ConstraintType.MAX_CONSECUTIVE_DAYS, new int[] {maxDays}, reference)
1166                            .setName("Max " + maxDays + " Consecutive Days");
1167                }
1168                return null;
1169            }}),
1170        ;
1171        
1172        private String iReference, iName;
1173        private Check iCheck = null;
1174        private ConstraintCreator<?> iCretor = null;
1175        
1176        ConstraintType(String reference, String name, Check check) {
1177            iReference = reference; iName = name; iCheck = check;
1178        }
1179        
1180        ConstraintType(String reference, String name, Check check, ConstraintCreator<?> creator) {
1181            iReference = reference; iName = name; iCheck = check; iCretor = creator;
1182        }
1183        
1184        @Override
1185        public ConstraintType type() { return this; }
1186        
1187        @Override
1188        public String reference() { return iReference; }
1189        
1190        @Override
1191        public String getName() { return iName; }
1192
1193        @Override
1194        public double getValue(Distribution distribution, Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, TeachingAssignment value) {
1195            return iCheck.getValue(distribution, assignment, instructor, value);
1196        }
1197        
1198        @Override
1199        public void computeConflicts(Distribution distribution, Assignment<Variable, TeachingAssignment> assignment, TeachingAssignment value, Set<TeachingAssignment> conflicts) {
1200            iCheck.computeConflicts(distribution, assignment, value, conflicts);
1201        }
1202        
1203        private Check check() { return iCheck; }
1204        private ConstraintCreator<?> creator() { return iCretor; }
1205    }
1206    
1207    /**
1208     * Create a constraint type from the provided reference. Returns null when there is no match.
1209     */
1210    public static ConstraintTypeInterface getConstraintType(String reference, String name) {
1211        for (ConstraintType t: ConstraintType.values()) {
1212            if (t.reference().equals(reference)) {
1213                if (name == null) return t;
1214                return new ParametrizedConstraintType<Integer>(t, null, reference).setName(name);
1215            }
1216            if (t.creator() != null && reference.matches(t.reference())) {
1217                if (name == null) 
1218                    return t.creator().create(reference, t.reference());
1219                else
1220                    return t.creator().create(reference, t.reference()).setName(name);
1221            }
1222        }
1223        return null;
1224    }
1225    
1226    /**
1227     * Teaching assignment and a section (from the assignment) combination.
1228     */
1229    static class TeachingAssignmentSection {
1230        private TeachingAssignment iTeachingAssignment;
1231        private Section iSection;
1232        
1233        TeachingAssignmentSection(TeachingAssignment ta, Section section) {
1234            iTeachingAssignment = ta;
1235            iSection = section;
1236        }
1237        
1238        public TeachingAssignment getTeachingAssignment() { return iTeachingAssignment; }
1239        public Section getSection() { return iSection; }
1240        public TimeLocation getTime() { return getSection().getTime(); }
1241        
1242        @Override
1243        public int hashCode() {
1244            return getTeachingAssignment().hashCode() ^ getSection().hashCode();
1245        }
1246        
1247        @Override
1248        public boolean equals(Object o) {
1249            if (o == null || !(o instanceof TeachingAssignmentSection)) return false;
1250            TeachingAssignmentSection tas = (TeachingAssignmentSection)o;
1251            return tas.getTeachingAssignment().equals(getTeachingAssignment()) && tas.getSection().equals(getSection());
1252        }
1253    }
1254    
1255    /**
1256     * Block of sections that go one after the other without any gap.
1257     */
1258    public static class Block {
1259        // start slot of the block
1260        private int startSlotCurrentBlock = -1;        
1261        // end slot of the block
1262        private int endSlotCurrentBlock = -1;        
1263        // max number of slots between classes to be considered Back-To-Back; 4 slots default      
1264        private int maxSlotsBetweenBackToBack = 4;
1265        // the list of placements of this block
1266        private List<TeachingAssignmentSection> sections = new ArrayList<TeachingAssignmentSection>();
1267        
1268        public Block(int maxSlotsBetweenBTB){
1269            this.maxSlotsBetweenBackToBack = maxSlotsBetweenBTB;            
1270        }              
1271        
1272        public boolean addSection(TeachingAssignmentSection section) {   
1273            if (section == null) return false;
1274            
1275            TimeLocation t = section.getTime();
1276            if (t == null) return false;
1277            
1278            // if placements is empty, the block only contains currently added placement -> set start and end
1279            if (sections.isEmpty()){
1280                sections.add(section);
1281                startSlotCurrentBlock = t.getStartSlot();
1282                endSlotCurrentBlock = t.getStartSlot() + t.getLength();
1283                return true;
1284            }
1285            
1286            // if startSlotCurrentBlock equals placement's start slot, add placement and adjust endSlotCurrentBlock
1287            if (t.getStartSlot() == startSlotCurrentBlock){
1288                sections.add(section);
1289                int tEnd = t.getStartSlot() + t.getLength();
1290                if (tEnd > endSlotCurrentBlock){
1291                    endSlotCurrentBlock = tEnd;
1292                }
1293                return true;
1294            }      
1295            
1296            // if placement starts among endSlotCurrentBlock + modifier and startSlotCurrentBlock, add the placement
1297            if (endSlotCurrentBlock + maxSlotsBetweenBackToBack >= t.getStartSlot() && t.getStartSlot() >= startSlotCurrentBlock ){
1298                sections.add(section);
1299                int tEnd = t.getStartSlot() + t.getLength();
1300                if (tEnd > endSlotCurrentBlock){
1301                    endSlotCurrentBlock = tEnd;
1302                }
1303                return true;
1304            }
1305            
1306            return false;
1307        }
1308
1309        public boolean haveSameStartTime() {
1310            if (!sections.isEmpty()) {
1311                int startSlot = sections.get(0).getTime().getStartSlot();
1312                for (TeachingAssignmentSection p : getSections()) {
1313                    if (p.getTime().getStartSlot() != startSlot)
1314                        return false;
1315                }
1316            }
1317            return true;
1318        }
1319        
1320        public int getStartSlotCurrentBlock() {
1321            return startSlotCurrentBlock;
1322        }
1323        
1324        public int getEndSlotCurrentBlock() {
1325            return endSlotCurrentBlock;
1326        }
1327        
1328        public int getNbrPlacements() {
1329            return sections.size();
1330        }        
1331       
1332        public List<TeachingAssignmentSection> getSections() {
1333            return sections;
1334        }
1335        
1336        public int getLengthInSlots() {
1337            return endSlotCurrentBlock - startSlotCurrentBlock;
1338        }
1339        
1340        public boolean contains(TeachingAssignment ta) {
1341            for (TeachingAssignmentSection tas: getSections())
1342                if (tas.getTeachingAssignment().equals(ta)) return true;
1343            return false;
1344        }
1345        
1346        @Override
1347        public String toString(){
1348            return "[" + startSlotCurrentBlock + ", " + endSlotCurrentBlock + "]" + " PlacementsNbr: "+ getNbrPlacements();
1349        }          
1350    }
1351    
1352    /**
1353     * Returns true if the time overlaps with the provided week date pattern and days of the week.
1354     */
1355    protected static boolean shareWeeksAndDay(TimeLocation t, BitSet week, int dayCode){
1356        boolean matchDay = (t.getDayCode() & dayCode) != 0;
1357        boolean matchWeek = (week == null || t.shareWeeks(week));                
1358        return matchDay && matchWeek;
1359    }
1360    
1361    /**
1362     * Return teaching assignment + section combinations for the given instructor, considering the selected value and the provided conflicts.
1363     * The sections are sorted by time, and must meet during the given week and days of the week.
1364     */
1365    protected static Set<TeachingAssignmentSection> getRelevantPlacements(Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor, int dayCode, Set<TeachingAssignment> conflicts, TeachingRequest.Variable variable, TeachingAssignment value, BitSet week) {
1366        Set<TeachingAssignmentSection> placements = new TreeSet<TeachingAssignmentSection>(new Comparator<TeachingAssignmentSection>() {
1367            @Override
1368            public int compare(TeachingAssignmentSection p1, TeachingAssignmentSection p2) {
1369                TimeLocation t1 = p1.getTime(), t2 = p2.getTime();
1370                // compare by start time (earlier first)
1371                if (t1.getStartSlot() < t2.getStartSlot())
1372                    return -1;
1373                if (t1.getStartSlot() > t2.getStartSlot())
1374                    return 1;
1375                // same start -> compare by length (shorter first)
1376                if (t1.getLength() < t2.getLength())
1377                    return -1;
1378                if (t1.getLength() > t2.getLength())
1379                    return 1;
1380                // fallback
1381                return 0;
1382            }
1383        });
1384        
1385        for (TeachingAssignment ta : instructor.getContext(assignment).getAssignments()) {
1386            // lecture of the value is already assigned
1387            if (variable != null && ta.variable().equals(variable)) continue;
1388            if (conflicts != null && conflicts.contains(ta)) continue;
1389            
1390            for (Section s: ta.variable().getSections()) {
1391                if (s.getTime() != null && shareWeeksAndDay(s.getTime(), week, dayCode))
1392                    placements.add(new TeachingAssignmentSection(ta, s));
1393            }
1394        }
1395        
1396        if (value != null) {
1397            for (Section s: value.variable().getSections()) {
1398                if (s.getTime() != null && shareWeeksAndDay(s.getTime(), week, dayCode))
1399                    placements.add(new TeachingAssignmentSection(value, s));
1400            }
1401        }
1402
1403        return placements;
1404    }
1405    
1406    /**
1407     * Merge sorted teaching assignment + section combinations into block.
1408     */
1409    protected static List<Block> mergeToBlocks(Collection<TeachingAssignmentSection> sorted, int maxBreakBetweenBTB){
1410        List<Block> blocks = new ArrayList<Block>();
1411        // add placements to blocks
1412        for (TeachingAssignmentSection placement: sorted) {
1413            boolean added = false;
1414            // add placement to a suitable block
1415            for (int j = 0; j < blocks.size(); j++) {
1416                if (blocks.get(j).addSection(placement)) {
1417                    added = true;
1418                }
1419            }
1420            // create a new block if a lecture does not fit into any block
1421            if (!added) {
1422                Block block = new Block(maxBreakBetweenBTB);
1423                block.addSection(placement);
1424                blocks.add(block);
1425            }
1426        }   
1427        return blocks;
1428    }
1429    
1430    /**
1431     * Return blocks for an instructor, meeting the provided parameters.
1432     * Combining {@link GroupConstraint#getRelevantPlacements(Assignment, Instructor, int, Set, Variable, TeachingAssignment, BitSet)}
1433     * and {@link GroupConstraint#mergeToBlocks(Collection, int)}. 
1434     */
1435    protected static List<Block> getBlocks(Assignment<TeachingRequest.Variable, TeachingAssignment> assignment, Instructor instructor,int dayCode, Set<TeachingAssignment> conflicts, TeachingRequest.Variable variable, TeachingAssignment value, BitSet week, int maxBreakBetweenBTB) {     
1436        return mergeToBlocks(getRelevantPlacements(assignment, instructor, dayCode, conflicts, variable, value, week), maxBreakBetweenBTB);
1437    }
1438    
1439    /**
1440     * Check if the given assignment has a section on the given days of the week.
1441     */
1442    protected static boolean isCorectDayOfWeek(TeachingAssignment value, int dayCode) {
1443        if (value == null) return true;
1444        for (Section section: value.variable().getSections())
1445            if (section.getTime() != null && (dayCode == 0 || (dayCode & section.getTime().getDayCode()) != 0)) return true;
1446        return false;
1447    }
1448    
1449    /**
1450     * Check if the given assignment has a section on the given days of the week and weeks.
1451     */
1452    protected static boolean isCorectDayAndWeek(TeachingAssignment value, int dayCode, BitSet week) {
1453        if (value == null) return true;
1454        for (Section section: value.variable().getSections())
1455            if (section.getTime() != null && (dayCode == 0 || (dayCode & section.getTime().getDayCode()) != 0)
1456                && section.getTime().getWeekCode().intersects(week)) return true;
1457        return false;
1458    }
1459}