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.solver.Solver;
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 boolean init(Solver<Lecture, Placement> solver) {
060        super.init(solver);
061
062        iWeight = solver.getProperties().getPropertyDouble("InstructorLunch.Weight", 0.3d);
063
064        // lunch parameters
065        iLunchStart = solver.getProperties().getPropertyInt("InstructorLunch.StartSlot", (11 * 60) / 5);
066        iLunchEnd = solver.getProperties().getPropertyInt("InstructorLunch.EndSlot", (13 * 60 + 30) / 5);
067        iLunchLength = solver.getProperties().getPropertyInt("InstructorLunch.Length", 30 / 5);
068        iMultiplier = solver.getProperties().getPropertyDouble("InstructorLunch.Multiplier", 1.2d);
069        iFullInfo = solver.getProperties().getPropertyBoolean("InstructorLunch.InfoShowViolations", false);
070
071        return true;
072    }
073    
074    /**
075     * The method creates date patterns (bitsets) which represent the weeks of a
076     * semester.
077     * 
078     * @return a list of BitSets which represents the weeks of a semester.
079     */
080    protected List<BitSet> getWeeks() {
081        if (iWeeks == null) {
082            TimetableModel model = (TimetableModel) getModel();
083            iWeeks = model.getWeeks();
084        }
085        return iWeeks;            
086    }
087
088    private boolean isEmpty(InstructorConstraintContext ic, int slot, BitSet week, Placement p) {
089        if (p.getTimeLocation().getStartSlot() <= slot && slot < p.getTimeLocation().getStartSlot() + p.getTimeLocation().getLength() && p.getTimeLocation().shareWeeks(week))
090            return false;
091        List<Placement> placements = ic.getPlacements(slot, week);
092        return placements.isEmpty() || (placements.size() == 1 && placements.get(0).variable().equals(p.variable()));
093    }
094    
095    @Override
096    public double getValue(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
097        double ret = 0.0;
098        if (value.getTimeLocation().getStartSlot() <= iLunchEnd && value.getTimeLocation().getStartSlot() + value.getTimeLocation().getLength() > iLunchStart) {
099            InstructorLunchBreakContext context = (InstructorLunchBreakContext)getContext(assignment);
100            for (InstructorConstraint constraint: value.variable().getInstructorConstraints()) {
101                InstructorConstraintContext icx = constraint.getContext(assignment);
102                CompactInfo compactInfo = context.getCompactInfo(constraint);
103                for (int i = 0; i < Constants.NR_DAYS; i++) {
104                    // checks only days affected by the placement
105                    if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) {
106                        int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart;
107                        int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd;
108                        int semesterViolations = 0;
109                        for (BitSet week : getWeeks()) {
110                            int maxBreak = 0;
111                            int currentBreak = 0;
112                            for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) {
113                                if (isEmpty(icx, slot, week, value)) {
114                                    currentBreak++;
115                                    if (maxBreak < currentBreak) {
116                                        maxBreak = currentBreak;
117                                    }
118                                } else {
119                                    currentBreak = 0;
120                                }
121                            }
122                            if (maxBreak < iLunchLength) {
123                                semesterViolations++;
124                            }
125                        }
126                        // add the difference to the result
127                        ret += semesterViolations - compactInfo.getLunchDayViolations()[i];
128                    }
129                }
130            }
131        }
132        return ret;
133    }
134
135    @Override
136    public double getValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) {
137        double lunchValue = 0.0d;
138        Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>();
139        for (Lecture lecture : variables) {
140            constraints.addAll(lecture.getInstructorConstraints());
141        }
142        for (InstructorConstraint instructor : constraints) {
143            lunchValue += ((InstructorLunchBreakContext)getContext(assignment)).getLunchPreference(assignment, instructor);
144        }
145        return lunchValue;
146    }
147
148    @Override
149    public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info) {
150        Set<String> violatedLunchBreaks = new TreeSet<String>();
151        int lunchViolations = 0;
152        for (InstructorConstraint c : ((TimetableModel)getModel()).getInstructorConstraints()) {
153            String days = "";
154            CompactInfo compactInfo = ((InstructorLunchBreakContext)getContext(assignment)).getCompactInfo(c);
155            for (int i = 0; i < Constants.NR_DAYS; i++) {
156                if (compactInfo.getLunchDayViolations()[i] > 0) {
157                    if (iFullInfo)
158                        days += (days.isEmpty() ? "" : ", ") + compactInfo.getLunchDayViolations()[i] + " &times; " + Constants.DAY_NAMES_SHORT[i];
159                    lunchViolations += compactInfo.getLunchDayViolations()[i];
160                }
161            }
162            if (iFullInfo && !days.isEmpty())
163                violatedLunchBreaks.add(c.getName() + ": " + days);
164        }
165        if (lunchViolations > 0) {
166            info.put("Lunch breaks", getPerc(lunchViolations, 0, ((TimetableModel)getModel()).getInstructorConstraints().size() * Constants.NR_DAYS * getWeeks().size()) + "% (" + lunchViolations + ")");
167            if (iFullInfo && !violatedLunchBreaks.isEmpty()) {
168                String message = "";
169                for (String s: violatedLunchBreaks)
170                    message += (message.isEmpty() ? "" : "<br>") + s;
171                info.put("Lunch break violations", message);
172            }
173        }
174    }
175
176    @Override
177    public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info, Collection<Lecture> variables) {
178        Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>();
179        for (Lecture lecture : variables) {
180            for (InstructorConstraint c : lecture.getInstructorConstraints()) {
181                constraints.add(c);
182            }
183        }
184        Set<String> violatedLunchBreaks = new TreeSet<String>();
185        int lunchViolations = 0;
186        for (InstructorConstraint c : constraints) {
187            String days = "";
188            CompactInfo compactInfo = ((InstructorLunchBreakContext)getContext(assignment)).getCompactInfo(c);
189            for (int i = 0; i < Constants.NR_DAYS; i++) {
190                if (compactInfo.getLunchDayViolations()[i] > 0) {
191                    if (iFullInfo)
192                        days += (days.isEmpty() ? "" : ", ") + compactInfo.getLunchDayViolations()[i] + " &times; " + Constants.DAY_NAMES_SHORT[i];
193                    lunchViolations += compactInfo.getLunchDayViolations()[i];
194                }
195            }
196            if (iFullInfo && !days.isEmpty())
197                violatedLunchBreaks.add(c.getName() + ": " + days);
198        }
199        if (lunchViolations > 0) {
200            info.put("Lunch breaks", getPerc(lunchViolations, 0, constraints.size() * Constants.NR_DAYS * getWeeks().size()) + "% (" + lunchViolations + ")");
201            if (iFullInfo && !violatedLunchBreaks.isEmpty()) {
202                String message = "";
203                for (String s: violatedLunchBreaks)
204                    message += (message.isEmpty() ? "" : "; ") + s;
205                info.put("Lunch break violations", message);
206            }
207        }
208    }
209    
210    /**
211     * The class is used as a container of information concerning lunch break
212     * of instructors. It is designed as an attribute of an
213     * InstructorConstraint.
214     */
215    public static class CompactInfo {
216        // lunch attributes
217        private int[] iLunchDayViolations = new int[Constants.NR_DAYS];
218
219        public CompactInfo() {
220        }
221        
222        public int[] getLunchDayViolations() { return iLunchDayViolations; }
223    }
224    
225    public class InstructorLunchBreakContext extends ValueContext {
226        private Map<InstructorConstraint, CompactInfo> iCompactInfos = new HashMap<InstructorConstraint, CompactInfo>();
227
228        protected InstructorLunchBreakContext(Assignment<Lecture, Placement> assignment) {
229            for (InstructorConstraint constraint: ((TimetableModel)getModel()).getInstructorConstraints())
230                iTotal += computeLunchPenalty(assignment, constraint);
231        }
232        
233        @Override
234        protected void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
235            for (InstructorConstraint constraint: value.variable().getInstructorConstraints())
236                updateCriterion(assignment, constraint, value);
237        }
238        
239        @Override
240        protected void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
241            for (InstructorConstraint constraint: value.variable().getInstructorConstraints())
242                updateCriterion(assignment, constraint, value);
243        }
244        
245        /**
246         * Method checks or sets the CompactInfo of an InstructorConstraint. It
247         * updates the preference of chosen criteria. The update consists of
248         * decrementing the criterion value by previous preference, finding the
249         * current preference and incrementing the criterion value by the current
250         * preference.
251         * 
252         * @param assignment current assignment 
253         * @param instructorConstraint
254         *            the Instructor constraint of an instructor checked for
255         *            criteria
256         * @param placement
257         *            placement of a lecture currently (un)assigned
258         */
259        public void updateCriterion(Assignment<Lecture, Placement> assignment, InstructorConstraint instructorConstraint, Placement placement) {
260            iTotal -= getLunchPreference(assignment, instructorConstraint);
261            updateLunchPenalty(assignment, instructorConstraint, placement);
262            iTotal += getLunchPreference(assignment, instructorConstraint);       
263        }
264
265        /**
266         * Get compact info that is associated with an instructor constraint.
267         * Create a new one if none has been created yet.
268         * @param constraint instructor constraint
269         * @return compact info for the given constraint
270         */
271        protected CompactInfo getCompactInfo(InstructorConstraint constraint) {
272            CompactInfo info = iCompactInfos.get(constraint);
273            if (info == null) {
274                info = new CompactInfo();
275                iCompactInfos.put(constraint, info);
276            }
277            return info;
278        }
279        
280        /**
281         * Method updates number of violations in days (Mo, Tue, Wed,..) considering
282         * each week in the semester separately. The current number of violations
283         * for a day is stored in the CompactInfo.lunchDayViolations of the
284         * constraint, which must be set properly before the calling of the method.
285         * 
286         * @param assignment current assignment 
287         * @param constraint
288         *            the Instructor constraint of an instructor checked for a lunch
289         *            break
290         * @param p
291         *            placement of a lecture currently (un)assigned
292         */
293        public void updateLunchPenalty(Assignment<Lecture, Placement> assignment, InstructorConstraint constraint, Placement p) {
294            // checks only placements in the lunch time
295            if (p.getTimeLocation().getStartSlot() <= iLunchEnd && p.getTimeLocation().getStartSlot() + p.getTimeLocation().getLength() > iLunchStart) {
296                CompactInfo compactInfo = getCompactInfo(constraint);
297                for (int i = 0; i < Constants.NR_DAYS; i++) {
298                    // checks only days affected by the placement
299                    if ((p.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) {
300                        int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart;
301                        int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd;
302                        int semesterViolations = 0;
303                        for (BitSet week : getWeeks()) {
304                            int maxBreak = 0;
305                            int currentBreak = 0;
306                            for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) {
307                                if (constraint.getContext(assignment).getPlacements(slot, week).isEmpty()) {
308                                    currentBreak++;
309                                    if (maxBreak < currentBreak) {
310                                        maxBreak = currentBreak;
311                                    }
312                                } else {
313                                    currentBreak = 0;
314                                }
315                            }
316                            if (maxBreak < iLunchLength) {
317                                semesterViolations++;
318                            }
319                        }
320                        // saving the result in the CompactInfo of the
321                        // InstructorConstraint
322                        compactInfo.getLunchDayViolations()[i] = semesterViolations;
323                    }
324                }
325            }
326        }
327        
328        /**
329         * Method computes number of violations in days (Mo, Tue, Wed,..) considering
330         * each week in the semester separately. Updates the compact infos accordingly.
331         * @param assignment current assignment 
332         * @param constraint instructor constraint
333         * @return current penalty for the given instructor
334         */
335        public double computeLunchPenalty(Assignment<Lecture, Placement> assignment, InstructorConstraint constraint) {
336            double violations = 0d;
337            CompactInfo compactInfo = getCompactInfo(constraint);
338            for (int i = 0; i < Constants.NR_DAYS; i++) {
339                int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart;
340                int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd;
341                int semesterViolations = 0;
342                for (BitSet week : getWeeks()) {
343                    int maxBreak = 0;
344                    int currentBreak = 0;
345                    for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) {
346                        if (constraint.getContext(assignment).getPlacements(slot, week).isEmpty()) {
347                            currentBreak++;
348                            if (maxBreak < currentBreak) {
349                                maxBreak = currentBreak;
350                            }
351                        } else {
352                            currentBreak = 0;
353                        }
354                    }
355                    if (maxBreak < iLunchLength) {
356                        semesterViolations++;
357                    }
358                }
359                // saving the result in the CompactInfo of the
360                // InstructorConstraint
361                compactInfo.getLunchDayViolations()[i] = semesterViolations;
362                violations += semesterViolations;
363            }
364            return Math.pow(violations, iMultiplier);
365        }
366        
367        /**
368         * Method uses the CompactInfo of the InstructorConstraint and returns the
369         * lunch preference for this constraint. Calculation formula does not use
370         * linear function, the number of violations is multiplied by a power of
371         * iMultiplier.
372         * 
373         * @param instructorConstraint
374         *            the Instructor constraint of an instructor checked for a lunch
375         *            break
376         * @return the lunch preference for this constraint
377         */
378        private double getLunchPreference(Assignment<Lecture, Placement> assignment, InstructorConstraint instructorConstraint) {
379            double violations = 0d;
380            CompactInfo info = getCompactInfo(instructorConstraint);
381            for (int i = 0; i < Constants.NR_DAYS; i++)
382                violations += info.getLunchDayViolations()[i];
383            return Math.pow(violations, iMultiplier); 
384        }
385    }
386    
387    @Override
388    public ValueContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
389        return new InstructorLunchBreakContext(assignment);
390    }
391}