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