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