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