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