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