    001package org.cpsolver.coursett.criteria.additional;
    002
    003import java.util.BitSet;
    004import java.util.Collection;
    005import java.util.HashMap;
    006import java.util.HashSet;
    007import java.util.List;
    008import java.util.Map;
    009import java.util.Set;
    010import java.util.TreeSet;
    011
    012import org.cpsolver.coursett.Constants;
    013import org.cpsolver.coursett.constraint.InstructorConstraint;
    014import org.cpsolver.coursett.constraint.InstructorConstraint.InstructorConstraintContext;
    015import org.cpsolver.coursett.criteria.TimetablingCriterion;
    016import org.cpsolver.coursett.model.Lecture;
    017import org.cpsolver.coursett.model.Placement;
    018import org.cpsolver.coursett.model.TimetableModel;
    019import org.cpsolver.ifs.assignment.Assignment;
    020import org.cpsolver.ifs.util.DataProperties;
    021
    022
    023/**
    024 * The class represents various criteria concerning compact timetables of
    025 * instructors. The criteria are checked and updated when a variable is
    026 * (un)assigned.
    027 * <br>
    028 * implemented criterion: lunch break
    029 * <br>
    030 * @version CourseTT 1.3 (University Course Timetabling)<br>
    031 *          Copyright (C) 2012 Matej Lukac<br>
    032 * <br>
    033 *          This library is free software; you can redistribute it and/or modify
    034 *          it under the terms of the GNU Lesser General Public License as
    035 *          published by the Free Software Foundation; either version 3 of the
    036 *          License, or (at your option) any later version. <br>
    037 * <br>
    038 *          This library is distributed in the hope that it will be useful, but
    039 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    040 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    041 *          Lesser General Public License for more details. <br>
    042 * <br>
    043 *          You should have received a copy of the GNU Lesser General Public
    044 *          License along with this library; if not see
    045 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    046 */
    047public class InstructorLunchBreak extends TimetablingCriterion {
    048    // lunch attributes
    049    private double iMultiplier;
    050    private int iLunchStart, iLunchEnd, iLunchLength;
    051    private boolean iFullInfo;
    052    private List<BitSet> iWeeks = null;
    053
    054    public InstructorLunchBreak() {
    055        setValueUpdateType(ValueUpdateType.AfterUnassignedAfterAssigned);
    056    }
    057
    058    @Override
    059    public void configure(DataProperties properties) {
    060        super.configure(properties);
    061
    062        iWeight = properties.getPropertyDouble("InstructorLunch.Weight", 0.3d);
    063
    064        // lunch parameters
    065        iLunchStart = properties.getPropertyInt("InstructorLunch.StartSlot", (11 * 60) / 5);
    066        iLunchEnd = properties.getPropertyInt("InstructorLunch.EndSlot", (13 * 60 + 30) / 5);
    067        iLunchLength = properties.getPropertyInt("InstructorLunch.Length", 30 / 5);
    068        iMultiplier = properties.getPropertyDouble("InstructorLunch.Multiplier", 1.2d);
    069        iFullInfo = properties.getPropertyBoolean("InstructorLunch.InfoShowViolations", false);
    070    }
    071
    072    /**
    073     * The method creates date patterns (bitsets) which represent the weeks of a
    074     * semester.
    075     *
    076     * @return a list of BitSets which represents the weeks of a semester.
    077     */
    078    protected List<BitSet> getWeeks() {
    079        if (iWeeks == null) {
    080            TimetableModel model = (TimetableModel) getModel();
    081            iWeeks = model.getWeeks();
    082        }
    083        return iWeeks;
    084    }
    085
    086    private boolean isEmpty(InstructorConstraintContext ic, int slot, BitSet week, Placement p) {
    087        if (p.getTimeLocation().getStartSlot() <= slot && slot < p.getTimeLocation().getStartSlot() + p.getTimeLocation().getLength() && p.getTimeLocation().shareWeeks(week))
    088            return false;
    089        List<Placement> placements = ic.getPlacements(slot, week);
    090        return placements.isEmpty() || (placements.size() == 1 && placements.get(0).variable().equals(p.variable()));
    091    }
    092
    093    @Override
    094    public double getValue(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    095        double ret = 0.0;
    096        if (value.getTimeLocation().getStartSlot() <= iLunchEnd && value.getTimeLocation().getStartSlot() + value.getTimeLocation().getLength() > iLunchStart) {
    097            InstructorLunchBreakContext context = (InstructorLunchBreakContext)getContext(assignment);
    098            for (InstructorConstraint constraint: value.variable().getInstructorConstraints()) {
    099                InstructorConstraintContext icx = constraint.getContext(assignment);
    100                CompactInfo compactInfo = context.getCompactInfo(constraint);
    101                for (int i = 0; i < Constants.NR_DAYS; i++) {
    102                    // checks only days affected by the placement
    103                    if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) {
    104                        int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart;
    105                        int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd;
    106                        int semesterViolations = 0;
    107                        for (BitSet week : getWeeks()) {
    108                            int maxBreak = 0;
    109                            int currentBreak = 0;
    110                            for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) {
    111                                if (isEmpty(icx, slot, week, value)) {
    112                                    currentBreak++;
    113                                    if (maxBreak < currentBreak) {
    114                                        maxBreak = currentBreak;
    115                                    }
    116                                } else {
    117                                    currentBreak = 0;
    118                                }
    119                            }
    120                            if (maxBreak < iLunchLength) {
    121                                semesterViolations++;
    122                            }
    123                        }
    124                        // add the difference to the result
    125                        ret += semesterViolations - compactInfo.getLunchDayViolations()[i];
    126                    }
    127                }
    128            }
    129        }
    130        return ret;
    131    }
    132
    133    @Override
    134    public double getValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) {
    135        double lunchValue = 0.0d;
    136        Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>();
    137        for (Lecture lecture : variables) {
    138            constraints.addAll(lecture.getInstructorConstraints());
    139        }
    140        for (InstructorConstraint instructor : constraints) {
    141            lunchValue += ((InstructorLunchBreakContext)getContext(assignment)).getLunchPreference(assignment, instructor);
    142        }
    143        return lunchValue;
    144    }
    145
    146    @Override
    147    public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info) {
    148        Set<String> violatedLunchBreaks = new TreeSet<String>();
    149        int lunchViolations = 0;
    150        for (InstructorConstraint c : ((TimetableModel)getModel()).getInstructorConstraints()) {
    151            String days = "";
    152            CompactInfo compactInfo = ((InstructorLunchBreakContext)getContext(assignment)).getCompactInfo(c);
    153            for (int i = 0; i < Constants.NR_DAYS; i++) {
    154                if (compactInfo.getLunchDayViolations()[i] > 0) {
    155                    if (iFullInfo)
    156                        days += (days.isEmpty() ? "" : ", ") + compactInfo.getLunchDayViolations()[i] + " &times; " + Constants.DAY_NAMES_SHORT[i];
    157                    lunchViolations += compactInfo.getLunchDayViolations()[i];
    158                }
    159            }
    160            if (iFullInfo && !days.isEmpty())
    161                violatedLunchBreaks.add(c.getName() + ": " + days);
    162        }
    163        if (lunchViolations > 0) {
    164            info.put("Lunch breaks", getPerc(lunchViolations, 0, ((TimetableModel)getModel()).getInstructorConstraints().size() * Constants.NR_DAYS * getWeeks().size()) + "% (" + lunchViolations + ")");
    165            if (iFullInfo && !violatedLunchBreaks.isEmpty()) {
    166                String message = "";
    167                for (String s: violatedLunchBreaks)
    168                    message += (message.isEmpty() ? "" : "<br>") + s;
    169                info.put("Lunch break violations", message);
    170            }
    171        }
    172    }
    173
    174    @Override
    175    public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info, Collection<Lecture> variables) {
    176        Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>();
    177        for (Lecture lecture : variables) {
    178            for (InstructorConstraint c : lecture.getInstructorConstraints()) {
    179                constraints.add(c);
    180            }
    181        }
    182        Set<String> violatedLunchBreaks = new TreeSet<String>();
    183        int lunchViolations = 0;
    184        for (InstructorConstraint c : constraints) {
    185            String days = "";
    186            CompactInfo compactInfo = ((InstructorLunchBreakContext)getContext(assignment)).getCompactInfo(c);
    187            for (int i = 0; i < Constants.NR_DAYS; i++) {
    188                if (compactInfo.getLunchDayViolations()[i] > 0) {
    189                    if (iFullInfo)
    190                        days += (days.isEmpty() ? "" : ", ") + compactInfo.getLunchDayViolations()[i] + " &times; " + Constants.DAY_NAMES_SHORT[i];
    191                    lunchViolations += compactInfo.getLunchDayViolations()[i];
    192                }
    193            }
    194            if (iFullInfo && !days.isEmpty())
    195                violatedLunchBreaks.add(c.getName() + ": " + days);
    196        }
    197        if (lunchViolations > 0) {
    198            info.put("Lunch breaks", getPerc(lunchViolations, 0, constraints.size() * Constants.NR_DAYS * getWeeks().size()) + "% (" + lunchViolations + ")");
    199            if (iFullInfo && !violatedLunchBreaks.isEmpty()) {
    200                String message = "";
    201                for (String s: violatedLunchBreaks)
    202                    message += (message.isEmpty() ? "" : "; ") + s;
    203                info.put("Lunch break violations", message);
    204            }
    205        }
    206    }
    207
    208    /**
    209     * The class is used as a container of information concerning lunch break
    210     * of instructors. It is designed as an attribute of an
    211     * InstructorConstraint.
    212     */
    213    public static class CompactInfo {
    214        // lunch attributes
    215        private int[] iLunchDayViolations = new int[Constants.NR_DAYS];
    216
    217        public CompactInfo() {
    218        }
    219
    220        public int[] getLunchDayViolations() { return iLunchDayViolations; }
    221    }
    222
    223    public class InstructorLunchBreakContext extends ValueContext {
    224        private Map<InstructorConstraint, CompactInfo> iCompactInfos = new HashMap<InstructorConstraint, CompactInfo>();
    225
    226        protected InstructorLunchBreakContext(Assignment<Lecture, Placement> assignment) {
    227            for (InstructorConstraint constraint: ((TimetableModel)getModel()).getInstructorConstraints())
    228                iTotal += computeLunchPenalty(assignment, constraint);
    229        }
    230
    231        @Override
    232        protected void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
    233            for (InstructorConstraint constraint: value.variable().getInstructorConstraints())
    234                updateCriterion(assignment, constraint, value);
    235        }
    236
    237        @Override
    238        protected void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
    239            for (InstructorConstraint constraint: value.variable().getInstructorConstraints())
    240                updateCriterion(assignment, constraint, value);
    241        }
    242
    243        /**
    244         * Method checks or sets the CompactInfo of an InstructorConstraint. It
    245         * updates the preference of chosen criteria. The update consists of
    246         * decrementing the criterion value by previous preference, finding the
    247         * current preference and incrementing the criterion value by the current
    248         * preference.
    249         *
    250         * @param assignment current assignment
    251         * @param instructorConstraint
    252         *            the Instructor constraint of an instructor checked for
    253         *            criteria
    254         * @param placement
    255         *            placement of a lecture currently (un)assigned
    256         */
    257        public void updateCriterion(Assignment<Lecture, Placement> assignment, InstructorConstraint instructorConstraint, Placement placement) {
    258            iTotal -= getLunchPreference(assignment, instructorConstraint);
    259            updateLunchPenalty(assignment, instructorConstraint, placement);
    260            iTotal += getLunchPreference(assignment, instructorConstraint);
    261        }
    262
    263        /**
    264         * Get compact info that is associated with an instructor constraint.
    265         * Create a new one if none has been created yet.
    266         * @param constraint instructor constraint
    267         * @return compact info for the given constraint
    268         */
    269        protected CompactInfo getCompactInfo(InstructorConstraint constraint) {
    270            CompactInfo info = iCompactInfos.get(constraint);
    271            if (info == null) {
    272                info = new CompactInfo();
    273                iCompactInfos.put(constraint, info);
    274            }
    275            return info;
    276        }
    277
    278        /**
    279         * Method updates number of violations in days (Mo, Tue, Wed,..) considering
    280         * each week in the semester separately. The current number of violations
    281         * for a day is stored in the CompactInfo.lunchDayViolations of the
    282         * constraint, which must be set properly before the calling of the method.
    283         *
    284         * @param assignment current assignment
    285         * @param constraint
    286         *            the Instructor constraint of an instructor checked for a lunch
    287         *            break
    288         * @param p
    289         *            placement of a lecture currently (un)assigned
    290         */
    291        public void updateLunchPenalty(Assignment<Lecture, Placement> assignment, InstructorConstraint constraint, Placement p) {
    292            // checks only placements in the lunch time
    293            if (p.getTimeLocation().getStartSlot() <= iLunchEnd && p.getTimeLocation().getStartSlot() + p.getTimeLocation().getLength() > iLunchStart) {
    294                CompactInfo compactInfo = getCompactInfo(constraint);
    295                for (int i = 0; i < Constants.NR_DAYS; i++) {
    296                    // checks only days affected by the placement
    297                    if ((p.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) {
    298                        int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart;
    299                        int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd;
    300                        int semesterViolations = 0;
    301                        for (BitSet week : getWeeks()) {
    302                            int maxBreak = 0;
    303                            int currentBreak = 0;
    304                            for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) {
    305                                if (constraint.getContext(assignment).getPlacements(slot, week).isEmpty()) {
    306                                    currentBreak++;
    307                                    if (maxBreak < currentBreak) {
    308                                        maxBreak = currentBreak;
    309                                    }
    310                                } else {
    311                                    currentBreak = 0;
    312                                }
    313                            }
    314                            if (maxBreak < iLunchLength) {
    315                                semesterViolations++;
    316                            }
    317                        }
    318                        // saving the result in the CompactInfo of the
    319                        // InstructorConstraint
    320                        compactInfo.getLunchDayViolations()[i] = semesterViolations;
    321                    }
    322                }
    323            }
    324        }
    325
    326        /**
    327         * Method computes number of violations in days (Mo, Tue, Wed,..) considering
    328         * each week in the semester separately. Updates the compact infos accordingly.
    329         * @param assignment current assignment
    330         * @param constraint instructor constraint
    331         * @return current penalty for the given instructor
    332         */
    333        public double computeLunchPenalty(Assignment<Lecture, Placement> assignment, InstructorConstraint constraint) {
    334            double violations = 0d;
    335            CompactInfo compactInfo = getCompactInfo(constraint);
    336            for (int i = 0; i < Constants.NR_DAYS; i++) {
    337                int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart;
    338                int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd;
    339                int semesterViolations = 0;
    340                for (BitSet week : getWeeks()) {
    341                    int maxBreak = 0;
    342                    int currentBreak = 0;
    343                    for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) {
    344                        if (constraint.getContext(assignment).getPlacements(slot, week).isEmpty()) {
    345                            currentBreak++;
    346                            if (maxBreak < currentBreak) {
    347                                maxBreak = currentBreak;
    348                            }
    349                        } else {
    350                            currentBreak = 0;
    351                        }
    352                    }
    353                    if (maxBreak < iLunchLength) {
    354                        semesterViolations++;
    355                    }
    356                }
    357                // saving the result in the CompactInfo of the
    358                // InstructorConstraint
    359                compactInfo.getLunchDayViolations()[i] = semesterViolations;
    360                violations += semesterViolations;
    361            }
    362            return Math.pow(violations, iMultiplier);
    363        }
    364
    365        /**
    366         * Method uses the CompactInfo of the InstructorConstraint and returns the
    367         * lunch preference for this constraint. Calculation formula does not use
    368         * linear function, the number of violations is multiplied by a power of
    369         * iMultiplier.
    370         *
    371         * @param instructorConstraint
    372         *            the Instructor constraint of an instructor checked for a lunch
    373         *            break
    374         * @return the lunch preference for this constraint
    375         */
    376        private double getLunchPreference(Assignment<Lecture, Placement> assignment, InstructorConstraint instructorConstraint) {
    377            double violations = 0d;
    378            CompactInfo info = getCompactInfo(instructorConstraint);
    379            for (int i = 0; i < Constants.NR_DAYS; i++)
    380                violations += info.getLunchDayViolations()[i];
    381            return Math.pow(violations, iMultiplier);
    382        }
    383    }
    384
    385    @Override
    386    public ValueContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
    387        return new InstructorLunchBreakContext(assignment);
    388    }
    389}