001package org.cpsolver.coursett.constraint;
002
003import java.util.Enumeration;
004import java.util.HashSet;
005import java.util.Iterator;
006import java.util.List;
007import java.util.Set;
008
009import org.cpsolver.coursett.Constants;
010import org.cpsolver.coursett.criteria.SameSubpartBalancingPenalty;
011import org.cpsolver.coursett.model.Lecture;
012import org.cpsolver.coursett.model.Placement;
013import org.cpsolver.ifs.assignment.Assignment;
014import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
015import org.cpsolver.ifs.assignment.context.ConstraintWithContext;
016import org.cpsolver.ifs.criteria.Criterion;
017import org.cpsolver.ifs.model.WeakeningConstraint;
018import org.cpsolver.ifs.util.DataProperties;
019import org.cpsolver.ifs.util.ToolBox;
020
021
022/**
023 * Spread given set of classes in time as much as possible. See
024 * {@link DepartmentSpreadConstraint} for more details.
025 * 
026 * @version CourseTT 1.3 (University Course Timetabling)<br>
027 *          Copyright (C) 2006 - 2014 Tomas Muller<br>
028 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
029 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
030 * <br>
031 *          This library is free software; you can redistribute it and/or modify
032 *          it under the terms of the GNU Lesser General Public License as
033 *          published by the Free Software Foundation; either version 3 of the
034 *          License, or (at your option) any later version. <br>
035 * <br>
036 *          This library is distributed in the hope that it will be useful, but
037 *          WITHOUT ANY WARRANTY; without even the implied warranty of
038 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
039 *          Lesser General Public License for more details. <br>
040 * <br>
041 *          You should have received a copy of the GNU Lesser General Public
042 *          License along with this library; if not see
043 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
044 */
045
046public class SpreadConstraint extends ConstraintWithContext<Lecture, Placement, SpreadConstraint.SpreadConstraintContext> implements WeakeningConstraint<Lecture, Placement> {
047    private boolean iInteractive = false;
048    private double iSpreadFactor = 1.20;
049    private int iUnassignmentsToWeaken = 250;
050    private String iName = null;
051    private int iFirstDaySlot, iLastDaySlot, iFirstWorkDay, iLastWorkDay;
052
053    public static boolean USE_MOST_IMPROVEMENT_ADEPTS = false;
054
055    public SpreadConstraint(String name, double spreadFactor, int unassignmentsToWeaken, boolean interactiveMode, int firstDaySlot, int lastDaySlot, int firstWorkDay, int lastWorkDay) {
056        iName = name;
057        iSpreadFactor = spreadFactor;
058        iUnassignmentsToWeaken = unassignmentsToWeaken;
059        iInteractive = interactiveMode;
060        iFirstDaySlot = firstDaySlot;
061        iLastDaySlot = lastDaySlot;
062        iFirstWorkDay = firstWorkDay;
063        iLastWorkDay = lastWorkDay;
064        if (iLastWorkDay < iFirstWorkDay) iLastWorkDay += 7;
065    }
066
067    public SpreadConstraint(DataProperties config, String name) {
068        this(name,
069                config.getPropertyDouble("Spread.SpreadFactor", 1.20),
070                config.getPropertyInt("Spread.Unassignments2Weaken", 250),
071                config.getPropertyBoolean("General.InteractiveMode", false),
072                config.getPropertyInt("General.FirstDaySlot", Constants.DAY_SLOTS_FIRST),
073                config.getPropertyInt("General.LastDaySlot", Constants.DAY_SLOTS_LAST),
074                config.getPropertyInt("General.FirstWorkDay", 0),
075                config.getPropertyInt("General.LastWorkDay", Constants.NR_DAYS_WEEK - 1)
076                );
077    }
078    
079    
080    protected Criterion<Lecture, Placement> getCriterion() {
081        return getModel().getCriterion(SameSubpartBalancingPenalty.class);
082    }
083
084    public Placement getAdept(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses, Set<Placement> conflicts) {
085        Placement adept = null;
086        int improvement = 0;
087
088        // take uncommitted placements first
089        for (Lecture lect : variables()) {
090            if (lect.isCommitted())
091                continue;
092            Placement plac = assignment.getValue(lect);
093            if (plac == null || plac.equals(placement) || placement.variable().equals(plac.variable())
094                    || conflicts.contains(plac))
095                continue;
096            int imp = getPenaltyIfUnassigned(assignment, plac, nrCourses);
097            if (imp == 0)
098                continue;
099            if (adept == null || imp > improvement) {
100                adept = plac;
101                improvement = imp;
102            }
103        }
104        if (adept != null)
105            return adept;
106
107        // no uncommitted placement found -- take committed one
108        for (Lecture lect : variables()) {
109            if (!lect.isCommitted())
110                continue;
111            Placement plac = assignment.getValue(lect);
112            if (plac == null || plac.equals(placement) || conflicts.contains(plac))
113                continue;
114            int imp = getPenaltyIfUnassigned(assignment, plac, nrCourses);
115            if (imp == 0)
116                continue;
117            if (adept == null || imp > improvement) {
118                adept = plac;
119                improvement = imp;
120            }
121        }
122
123        return adept;
124    }
125
126    @SuppressWarnings("unchecked")
127    private Set<Placement>[] getAdepts(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses, Set<Placement> conflicts) {
128        SpreadConstraintContext context = getContext(assignment);
129        int firstSlot = placement.getTimeLocation().getStartSlot();
130        if (firstSlot > iLastDaySlot)
131            return null;
132        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
133        if (endSlot < iFirstDaySlot)
134            return null;
135        HashSet<Placement> adepts[] = new HashSet[] { new HashSet<Placement>(), new HashSet<Placement>() };
136        for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
137            for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
138                int dayCode = Constants.DAY_CODES[j % 7];
139                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0 && nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] >= context.getMaxCourses(i, j)) {
140                    for (Placement p : context.getCourses(i, j)) {
141                        if (conflicts.contains(p))
142                            continue;
143                        if (p.equals(placement))
144                            continue;
145                        if (p.variable().equals(placement.variable()))
146                            continue;
147                        adepts[(p.variable()).isCommitted() ? 1 : 0].add(p);
148                    }
149                }
150            }
151        }
152        return adepts;
153        // sLogger.debug("  -- adept "+adept+" selected, penalty will be decreased by "+improvement);
154    }
155
156    private int getPenaltyIfUnassigned(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses) {
157        SpreadConstraintContext context = getContext(assignment);
158        int firstSlot = placement.getTimeLocation().getStartSlot();
159        if (firstSlot > iLastDaySlot)
160            return 0;
161        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
162        if (endSlot < iFirstDaySlot)
163            return 0;
164        int penalty = 0;
165        for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
166            for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
167                int dayCode = Constants.DAY_CODES[j % 7];
168                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0 && nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] > context.getMaxCourses(i, j))
169                    penalty++;
170            }
171        }
172        return penalty;
173    }
174
175    private int tryUnassign(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses) {
176        SpreadConstraintContext context = getContext(assignment);
177        // sLogger.debug("  -- trying to unassign "+placement);
178        int firstSlot = placement.getTimeLocation().getStartSlot();
179        if (firstSlot > iLastDaySlot)
180            return 0;
181        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
182        if (endSlot < iFirstDaySlot)
183            return 0;
184        int improvement = 0;
185        for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
186            for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
187                int dayCode = Constants.DAY_CODES[j % 7];
188                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
189                    if (nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] > context.getMaxCourses(i, j))
190                        improvement++;
191                    nrCourses[i - iFirstDaySlot][j - iFirstWorkDay]--;
192                }
193            }
194        }
195        // sLogger.debug("  -- penalty is decreased by "+improvement);
196        return improvement;
197    }
198
199    private int tryAssign(Assignment<Lecture, Placement> assignment, Placement placement, int[][] nrCourses) {
200        SpreadConstraintContext context = getContext(assignment);
201        // sLogger.debug("  -- trying to assign "+placement);
202        int firstSlot = placement.getTimeLocation().getStartSlot();
203        if (firstSlot > iLastDaySlot)
204            return 0;
205        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
206        if (endSlot < iFirstDaySlot)
207            return 0;
208        int penalty = 0;
209        for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
210            for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
211                int dayCode = Constants.DAY_CODES[j % 7];
212                if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
213                    nrCourses[i - iFirstDaySlot][j - iFirstWorkDay]++;
214                    if (nrCourses[i - iFirstDaySlot][j - iFirstWorkDay] > context.getMaxCourses(i, j))
215                        penalty++;
216                }
217            }
218        }
219        // sLogger.debug("  -- penalty is incremented by "+penalty);
220        return penalty;
221    }
222
223    @Override
224    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement placement, Set<Placement> conflicts) {
225        SpreadConstraintContext context = getContext(assignment);
226        if (context.getUnassignmentsToWeaken() == 0)
227            return;
228        int penalty = context.getCurrentPenalty() + getPenalty(assignment, placement);
229        if (penalty <= context.getMaxAllowedPenalty())
230            return;
231        int firstSlot = placement.getTimeLocation().getStartSlot();
232        if (firstSlot > iLastDaySlot)
233            return;
234        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
235        if (endSlot < iFirstDaySlot)
236            return;
237        // sLogger.debug("-- computing conflict for value "+value+" ... (penalty="+iCurrentPenalty+", penalty with the value="+penalty+", max="+iMaxAllowedPenalty+")");
238        int[][] nrCourses = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
239        for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++)
240            for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++)
241                nrCourses[i][j] = context.getNrCourses(i + iFirstDaySlot, j + iFirstWorkDay, placement);
242        tryAssign(assignment, placement, nrCourses);
243        // sLogger.debug("  -- nrCurses="+fmt(nrCourses));
244        for (Lecture lect : variables()) {
245            if (lect.equals(placement.variable())) continue;
246            if (conflicts.contains(lect)) {
247                penalty -= tryUnassign(assignment, assignment.getValue(lect), nrCourses);
248            }
249            if (penalty <= context.getMaxAllowedPenalty())
250                return;
251        }
252        if (USE_MOST_IMPROVEMENT_ADEPTS) {
253            while (penalty > context.getMaxAllowedPenalty()) {
254                Placement plac = getAdept(assignment, placement, nrCourses, conflicts);
255                if (plac == null)
256                    break;
257                conflicts.add(plac);
258                penalty -= tryUnassign(assignment, plac, nrCourses);
259            }
260        } else {
261            if (penalty > context.getMaxAllowedPenalty()) {
262                Set<Placement> adepts[] = getAdepts(assignment, placement, nrCourses, conflicts);
263                for (int i = 0; penalty > context.getMaxAllowedPenalty() && i < adepts.length; i++) {
264                    while (!adepts[i].isEmpty() && penalty > context.getMaxAllowedPenalty()) {
265                        Placement plac = ToolBox.random(adepts[i]);
266                        adepts[i].remove(plac);
267                        conflicts.add(plac);
268                        // sLogger.debug("  -- conflict "+lect.getAssignment()+" added");
269                        penalty -= tryUnassign(assignment, plac, nrCourses);
270                    }
271                }
272            }
273        }
274    }
275
276    @Override
277    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement placement) {
278        SpreadConstraintContext context = getContext(assignment);
279        if (context.getUnassignmentsToWeaken() == 0) return false;
280        return getPenalty(assignment, placement) + context.getCurrentPenalty() > context.getMaxAllowedPenalty();
281    }
282
283    @Override
284    public void weaken(Assignment<Lecture, Placement> assignment) {
285        getContext(assignment).weaken();
286    }
287
288    @Override
289    public String getName() {
290        return iName;
291    }
292
293    @Override
294    public String toString() {
295        StringBuffer sb = new StringBuffer();
296        sb.append("Time Spread between ");
297        for (Iterator<Lecture> e = variables().iterator(); e.hasNext();) {
298            Lecture v = e.next();
299            sb.append(v.getName());
300            if (e.hasNext())
301                sb.append(", ");
302        }
303        return sb.toString();
304    }
305
306    /** Department balancing penalty for this department 
307     * @param assignment current assignment
308     * @return current penalty
309     **/
310    public int getPenalty(Assignment<Lecture, Placement> assignment) {
311        return getContext(assignment).getCurrentPenalty();
312    }
313
314    public int getPenaltyEstimate(Assignment<Lecture, Placement> assignment) {
315        double histogramPerDay[][] = new double[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
316        int maxCourses[][] = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
317        int nrCourses[][] = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
318        for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++)
319            for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++)
320                histogramPerDay[i][j] = 0.0;
321        int totalUsedSlots = 0;
322        for (Lecture lecture : variables()) {
323            List<Placement>  values = lecture.values(assignment);
324            Placement firstPlacement = (values.isEmpty() ? null : values.get(0));
325            if (firstPlacement != null) {
326                totalUsedSlots += firstPlacement.getTimeLocation().getNrSlotsPerMeeting()
327                        * firstPlacement.getTimeLocation().getNrMeetings();
328            }
329            for (Placement p : values) {
330                int firstSlot = p.getTimeLocation().getStartSlot();
331                if (firstSlot > iLastDaySlot)
332                    continue;
333                int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1;
334                if (endSlot < iFirstDaySlot)
335                    continue;
336                for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
337                    int dayCode = p.getTimeLocation().getDayCode();
338                    for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
339                        if ((dayCode & Constants.DAY_CODES[j % 7]) != 0) {
340                            histogramPerDay[i - iFirstDaySlot][j - iFirstWorkDay] += 1.0 / values.size();
341                        }
342                    }
343                }
344            }
345        }
346        double threshold = iSpreadFactor * ((double) totalUsedSlots / ((iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1)));
347        for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) {
348            for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) {
349                nrCourses[i][j] = 0;
350                maxCourses[i][j] = (int) (0.999 + (histogramPerDay[i][j] <= threshold ? iSpreadFactor * histogramPerDay[i][j] : histogramPerDay[i][j]));
351            }
352        }
353        int currentPenalty = 0;
354        for (Lecture lecture : variables()) {
355            Placement placement = assignment.getValue(lecture);
356            if (placement == null)
357                continue;
358            int firstSlot = placement.getTimeLocation().getStartSlot();
359            if (firstSlot > iLastDaySlot)
360                continue;
361            int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
362            if (endSlot < iFirstDaySlot)
363                continue;
364            for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
365                for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
366                    int dayCode = Constants.DAY_CODES[j % 7];
367                    if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
368                        nrCourses[i - iFirstDaySlot][j - iFirstWorkDay]++;
369                    }
370                }
371            }
372        }
373        for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) {
374            for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) {
375                currentPenalty += Math.max(0, nrCourses[i][j] - maxCourses[i][j]);
376            }
377        }
378        return currentPenalty;
379    }
380
381    public int getMaxPenalty(Assignment<Lecture, Placement> assignment, Placement placement) {
382        SpreadConstraintContext context = getContext(assignment);
383        int penalty = 0;
384        for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) {
385            int slot = e.nextElement();
386            int day = slot / Constants.SLOTS_PER_DAY;
387            int time = slot % Constants.SLOTS_PER_DAY;
388            if (time < iFirstDaySlot || time > iLastDaySlot)
389                continue;
390            if (iLastWorkDay < 7) {
391                if (day < iFirstWorkDay || day > iLastWorkDay)
392                    continue;
393            } else {
394                if (day < iFirstWorkDay && day > iLastWorkDay - 7)
395                    continue;
396                if (day < iFirstWorkDay) day += 7;
397            }
398            int dif = 1 + context.getNrCourses(time, day, placement) - context.getMaxCourses(time, day);
399            if (dif > penalty)
400                penalty = dif;
401        }
402        return penalty;
403    }
404
405    /** Department balancing penalty of the given placement 
406     * @param assignment current assignment
407     * @param placement a placement that is being considered
408     * @return change in the penalty if assigned
409     **/
410    public int getPenalty(Assignment<Lecture, Placement> assignment, Placement placement) {
411        SpreadConstraintContext context = getContext(assignment);
412        int firstSlot = placement.getTimeLocation().getStartSlot();
413        if (firstSlot > iLastDaySlot)
414            return 0;
415        int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
416        if (endSlot < iFirstDaySlot)
417            return 0;
418        int penalty = 0;
419        int min = Math.max(firstSlot, iFirstDaySlot);
420        int max = Math.min(endSlot, iLastDaySlot);
421        for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
422            int dayCode = Constants.DAY_CODES[j % 7];
423            if ((dayCode & placement.getTimeLocation().getDayCode()) == 0)
424                continue;
425            for (int i = min; i <= max; i++) {
426                if (context.getNrCourses(i, j, placement) >= context.getMaxCourses(i, j))
427                    penalty++;
428            }
429        }
430        return penalty;
431    }
432
433    @Override
434    public void addVariable(Lecture lecture) {
435        if (lecture.canShareRoom()) {
436            for (GroupConstraint gc : lecture.groupConstraints()) {
437                if (gc.getType() == GroupConstraint.ConstraintType.MEET_WITH) {
438                    if (gc.variables().indexOf(lecture) > 0)
439                        return;
440                }
441            }
442        }
443        super.addVariable(lecture);
444    }
445
446    @Override
447    public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
448        while (inConflict(assignment, value))
449            getContext(assignment).weaken(getContext(assignment).getCurrentPenalty() + getPenalty(assignment, value));
450    }
451    
452    @Override
453    public SpreadConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
454        return new SpreadConstraintContext(assignment);
455    }
456
457    public class SpreadConstraintContext implements AssignmentConstraintContext<Lecture, Placement> {
458        private int iMaxAllowedPenalty = 0;
459        private long iUnassignment = 0;
460        private Set<Placement>[][] iCourses = null;
461        private int iMaxCourses[][] = null;
462        private int iCurrentPenalty = 0;
463
464        @SuppressWarnings("unchecked")
465        public SpreadConstraintContext(Assignment<Lecture, Placement> assignment) {
466            iCourses = new Set[iLastDaySlot - iFirstDaySlot + 1][(iLastWorkDay - iFirstWorkDay + 1) % 7];
467            if (iInteractive)
468                iUnassignmentsToWeaken = 0;
469            for (int i = 0; i < iCourses.length; i++) {
470                for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) {
471                    iCourses[i][j] = new HashSet<Placement>(10);
472                }
473            }
474            double histogramPerDay[][] = new double[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
475            iMaxCourses = new int[iLastDaySlot - iFirstDaySlot + 1][iLastWorkDay - iFirstWorkDay + 1];
476            for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++)
477                for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++)
478                    histogramPerDay[i][j] = 0.0;
479            int totalUsedSlots = 0;
480            for (Lecture lecture : variables()) {
481                List<Placement>  values = lecture.values(assignment);
482                Placement firstPlacement = (values.isEmpty() ? null : values.get(0));
483                if (firstPlacement != null) {
484                    totalUsedSlots += firstPlacement.getTimeLocation().getNrSlotsPerMeeting() * firstPlacement.getTimeLocation().getNrMeetings();
485                }
486                for (Placement p : values) {
487                    int firstSlot = p.getTimeLocation().getStartSlot();
488                    if (firstSlot > iLastDaySlot)
489                        continue;
490                    int endSlot = firstSlot + p.getTimeLocation().getNrSlotsPerMeeting() - 1;
491                    if (endSlot < iFirstDaySlot)
492                        continue;
493                    for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
494                        int dayCode = p.getTimeLocation().getDayCode();
495                        for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
496                            if ((dayCode & Constants.DAY_CODES[j % 7]) != 0) {
497                                histogramPerDay[i - iFirstDaySlot][j - iFirstWorkDay] += 1.0 / values.size();
498                            }
499                        }
500                    }
501                }
502            }
503            // System.out.println("Histogram for department "+iDepartment+":");
504            double threshold = iSpreadFactor * ((double) totalUsedSlots / ((iLastWorkDay - iFirstWorkDay + 1) * (iLastDaySlot - iFirstDaySlot + 1)));
505            // System.out.println("Threshold["+iDepartment+"] = "+threshold);
506            for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) {
507                // System.out.println("  "+fmt(i+1)+": "+fmt(histogramPerDay[i]));
508                for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) {
509                    iMaxCourses[i][j] = (int) (0.999 + (histogramPerDay[i][j] <= threshold ? iSpreadFactor * histogramPerDay[i][j] : histogramPerDay[i][j]));
510                }
511            }
512            for (Lecture lecture : variables()) {
513                Placement placement = assignment.getValue(lecture);
514                if (placement == null)
515                    continue;
516                int firstSlot = placement.getTimeLocation().getStartSlot();
517                if (firstSlot > iLastDaySlot)
518                    continue;
519                int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
520                if (endSlot < iFirstDaySlot)
521                    continue;
522                for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
523                    for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
524                        int dayCode = Constants.DAY_CODES[j % 7];
525                        if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
526                            iCourses[i - iFirstDaySlot][j - iFirstWorkDay].add(placement);
527                        }
528                    }
529                }
530            }
531            iCurrentPenalty = 0;
532            for (int i = 0; i < iLastDaySlot - iFirstDaySlot + 1; i++) {
533                for (int j = 0; j < iLastWorkDay - iFirstWorkDay + 1; j++) {
534                    iCurrentPenalty += Math.max(0, iCourses[i][j].size() - iMaxCourses[i][j]);
535                }
536            }
537            iMaxAllowedPenalty = iCurrentPenalty;
538            getCriterion().inc(assignment, iCurrentPenalty);
539        }
540        
541
542        @Override
543        public void assigned(Assignment<Lecture, Placement> assignment, Placement placement) {
544            int firstSlot = placement.getTimeLocation().getStartSlot();
545            if (firstSlot > iLastDaySlot)
546                return;
547            int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
548            if (endSlot < iFirstDaySlot)
549                return;
550            getCriterion().inc(assignment, -iCurrentPenalty);
551            for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
552                for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
553                    int dayCode = Constants.DAY_CODES[j % 7];
554                    if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
555                        iCourses[i - iFirstDaySlot][j - iFirstWorkDay].add(placement);
556                        if (iCourses[i - iFirstDaySlot][j - iFirstWorkDay].size() > iMaxCourses[i - iFirstDaySlot][j - iFirstWorkDay])
557                            iCurrentPenalty++;
558                    }
559                }
560            }
561            getCriterion().inc(assignment, iCurrentPenalty);
562        }
563
564        @Override
565        public void unassigned(Assignment<Lecture, Placement> assignment, Placement placement) {
566            int firstSlot = placement.getTimeLocation().getStartSlot();
567            if (firstSlot > iLastDaySlot)
568                return;
569            int endSlot = firstSlot + placement.getTimeLocation().getNrSlotsPerMeeting() - 1;
570            if (endSlot < iFirstDaySlot)
571                return;
572            getCriterion().inc(assignment, -iCurrentPenalty);
573            for (int i = Math.max(firstSlot, iFirstDaySlot); i <= Math.min(endSlot, iLastDaySlot); i++) {
574                for (int j = iFirstWorkDay; j <= iLastWorkDay; j++) {
575                    int dayCode = Constants.DAY_CODES[j % 7];
576                    if ((dayCode & placement.getTimeLocation().getDayCode()) != 0) {
577                        if (iCourses[i - iFirstDaySlot][j - iFirstWorkDay].size() > iMaxCourses[i - iFirstDaySlot][j - iFirstWorkDay])
578                            iCurrentPenalty--;
579                        iCourses[i - iFirstDaySlot][j - iFirstWorkDay].remove(placement);
580                    }
581                }
582            }
583            getCriterion().inc(assignment, iCurrentPenalty);
584        }
585        
586        public int[][] getMaxCourses() {
587            return iMaxCourses;
588        }
589
590        public int getMaxCourses(int time, int day) {
591            return iMaxCourses[time - iFirstDaySlot][day - iFirstWorkDay];
592        }
593
594        public int getNrCourses(int time, int day, Placement placement) {
595            if (placement == null) return getCourses(time, day).size();
596            int nrCourses = 0;
597            for (Placement p: getCourses(time, day))
598                if (!p.variable().equals(placement.variable())) 
599                    nrCourses ++;
600            return nrCourses;
601        }
602        
603        public Set<Placement> getCourses(int time, int day) {
604            return iCourses[time - iFirstDaySlot][day - iFirstWorkDay];
605        }
606        
607        public int getUnassignmentsToWeaken() {
608            return iUnassignmentsToWeaken;
609        }
610        
611        public int getCurrentPenalty() {
612            return iCurrentPenalty;
613        }
614        
615        public int getMaxAllowedPenalty() {
616            return iMaxAllowedPenalty;
617        }
618        
619        public void weaken() {
620            if (iUnassignmentsToWeaken == 0) return;
621            iUnassignment++;
622            if (iUnassignment % iUnassignmentsToWeaken == 0)
623                iMaxAllowedPenalty++;
624        }
625        
626        public void weaken(int penalty) {
627            if (penalty > iMaxAllowedPenalty)
628                iMaxAllowedPenalty = penalty; 
629        }
630
631    }
632}