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