001    package net.sf.cpsolver.coursett.criteria.additional;
002    
003    import java.util.ArrayList;
004    import java.util.BitSet;
005    import java.util.Collection;
006    import java.util.HashMap;
007    import java.util.HashSet;
008    import java.util.List;
009    import java.util.Map;
010    import java.util.Set;
011    import java.util.TreeSet;
012    
013    import net.sf.cpsolver.coursett.Constants;
014    import net.sf.cpsolver.coursett.constraint.InstructorConstraint;
015    import net.sf.cpsolver.coursett.model.Lecture;
016    import net.sf.cpsolver.coursett.model.Placement;
017    import net.sf.cpsolver.coursett.model.TimetableModel;
018    import net.sf.cpsolver.ifs.criteria.AbstractCriterion;
019    import net.sf.cpsolver.ifs.solver.Solver;
020    
021    /**
022     * The class represents various criteria concerning compact timetables of
023     * instructors. The criteria are checked and updated when a variable is
024     * (un)assigned.
025     * <br>
026     * implemented criteria: lunch break
027     * <br>
028     * @version CourseTT 1.2 (University Course Timetabling)<br>
029     *          Copyright (C) 2012 Matej Lukac<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    public class CompactTimetable extends AbstractCriterion<Lecture, Placement> {
046        // lunch attributes
047        private double iMultiplier, iLunchWeight;
048        private int iLunchStart, iLunchEnd, iLunchLength;
049        private boolean iCheckLunchBreak, iFullInfo;
050        private List<BitSet> iWeeks = null;
051        
052        private Map<InstructorConstraint, CompactInfo> iCompactInfos = new HashMap<InstructorConstraint, CompactInfo>();
053    
054        public CompactTimetable() {
055            iValueUpdateType = ValueUpdateType.NoUpdate;
056        }
057    
058        @Override
059        public boolean init(Solver<Lecture, Placement> solver) {
060            super.init(solver);
061    
062            iWeight = solver.getProperties().getPropertyDouble("CompactTimetable.Weight", 1.0d);
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.35d);
069            iLunchWeight = solver.getProperties().getPropertyDouble("InstructorLunch.Weight", 0.3d);
070            iCheckLunchBreak = solver.getProperties().getPropertyBoolean("InstructorLunch.Enabled", true);
071            iFullInfo = solver.getProperties().getPropertyBoolean("InstructorLunch.InfoShowViolations", true);
072    
073            return true;
074        }
075        
076        /**
077         * Get compact info that is associated with an instructor constraint.
078         * Create a new one if none has been created yet.
079         */
080        protected CompactInfo getCompactInfo(InstructorConstraint constraint) {
081            CompactInfo info = iCompactInfos.get(constraint);
082            if (info == null) {
083                info = new CompactInfo();
084                iCompactInfos.put(constraint, info);
085            }
086            return info;
087        }    
088        
089        /**
090         * Update criterion after an assignment.
091         */
092        @Override
093        public void afterAssigned(long iteration, Placement value) {
094            super.afterAssigned(iteration, value);
095            for (InstructorConstraint constraint: value.variable().getInstructorConstraints())
096                updateCriterion(constraint, value);
097        }
098    
099        /**
100         * Update criterion after an unassignment
101         */
102        @Override
103        public void afterUnassigned(long iteration, Placement value) {
104            super.afterUnassigned(iteration, value);
105            for (InstructorConstraint constraint: value.variable().getInstructorConstraints())
106                updateCriterion(constraint, value);
107        }
108    
109        /**
110         * The method creates date patterns (bitsets) which represent the weeks of a
111         * semester.
112         * 
113         * @param s
114         *            default date pattern as combination of "0" and "1".
115         * @return a list of BitSets which represents the weeks of a semester.
116         */
117        protected List<BitSet> getWeeks() {
118            if (iWeeks == null) {
119                String defaultDatePattern = ((TimetableModel)getModel()).getProperties().getProperty("DatePattern.Default");
120                if (defaultDatePattern == null) return null;
121                // Create default date pattern
122                BitSet fullTerm = new BitSet(defaultDatePattern.length());
123                for (int i = 0; i < defaultDatePattern.length(); i++) {
124                    if (defaultDatePattern.charAt(i) == 49) {
125                        fullTerm.set(i);
126                    }
127                }
128                // Cut date pattern into weeks (every week contains 7 positive bits)
129                iWeeks = new ArrayList<BitSet>();
130                int cnt = 0;
131                for (int i = 0; i < fullTerm.length(); i++) {
132                    if (fullTerm.get(i)) {
133                        int w = (cnt++) / 7;
134                        if (iWeeks.size() == w) {
135                            iWeeks.add(new BitSet(fullTerm.length()));
136                        }
137                        iWeeks.get(w).set(i);
138                    }
139                }
140            }
141            return iWeeks;            
142        }
143    
144        /**
145         * Method updates number of violations in days (Mo, Tue, Wed,..) considering
146         * each week in the semester separately. The current number of violations
147         * for a day is stored in the CompactInfo.lunchDayViolations of the
148         * constraint, which must be set properly before the calling of the method.
149         * 
150         * @param constraint
151         *            the Instructor constraint of an instructor checked for a lunch
152         *            break
153         * @param p
154         *            placement of a lecture currently (un)assigned
155         */
156        public void updateLunchPenalty(InstructorConstraint constraint, Placement p) {
157            // checks only placements in the lunch time
158            if (p.getTimeLocation().getStartSlot() <= iLunchEnd && p.getTimeLocation().getStartSlot() + p.getTimeLocation().getLength() > iLunchStart) {
159                CompactInfo compactInfo = getCompactInfo(constraint);
160                for (int i = 0; i < Constants.NR_DAYS; i++) {
161                    // checks only days affected by the placement
162                    if ((p.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) {
163                        int currentLunchStartSlot = Constants.SLOTS_PER_DAY * i + iLunchStart;
164                        int currentLunchEndSlot = Constants.SLOTS_PER_DAY * i + iLunchEnd;
165                        int semesterViolations = 0;
166                        for (BitSet week : getWeeks()) {
167                            int maxBreak = 0;
168                            int currentBreak = 0;
169                            for (int slot = currentLunchStartSlot; slot < currentLunchEndSlot; slot++) {
170                                if (constraint.getPlacements(slot, week).isEmpty()) {
171                                    currentBreak++;
172                                    if (maxBreak < currentBreak) {
173                                        maxBreak = currentBreak;
174                                    }
175                                } else {
176                                    currentBreak = 0;
177                                }
178                            }
179                            if (maxBreak < iLunchLength) {
180                                semesterViolations++;
181                            }
182                        }
183                        // saving the result in the CompactInfo of the
184                        // InstructorConstraint
185                        compactInfo.getLunchDayViolations()[i] = semesterViolations;
186                    }
187                }
188            }
189        }
190    
191        /**
192         * Method checks or sets the CompactInfo of an InstructorConstraint. It
193         * updates the preference of chosen criteria. The update consists of
194         * decrementing the criterion value by previous preference, finding the
195         * current preference and incrementing the criterion value by the current
196         * preference.
197         * 
198         * @param instructorConstraint
199         *            the Instructor constraint of an instructor checked for
200         *            criteria
201         * @param placement
202         *            placement of a lecture currently (un)assigned
203         */
204        public void updateCriterion(InstructorConstraint instructorConstraint, Placement placement) {
205            // manage lunch criterion
206            if (iCheckLunchBreak) {
207                iValue -= getLunchPreference(instructorConstraint) * iLunchWeight;
208                updateLunchPenalty(instructorConstraint, placement);
209                iValue += getLunchPreference(instructorConstraint) * iLunchWeight;
210            }
211        }
212        
213        /**
214         * Method uses the CompactInfo of the InstructorConstraint and returns the
215         * lunch preference for this constraint. Calculation formula does not use
216         * linear function, the number of violations is multiplied by a power of
217         * iMultiplier.
218         * 
219         * @param instructorConstraint
220         *            the Instructor constraint of an instructor checked for a lunch
221         *            break
222         * @return the lunch preference for this constraint
223         */
224        private double getLunchPreference(InstructorConstraint instructorConstraint) {
225            double violations = 0d;
226            CompactInfo info = getCompactInfo(instructorConstraint);
227            for (int i = 0; i < Constants.NR_DAYS; i++)
228                violations += info.getLunchDayViolations()[i];
229            return Math.pow(violations, iMultiplier); 
230        }
231    
232        @Override
233        public double getValue(Placement value, Set<Placement> conflicts) {
234            return iValue;
235        }
236    
237        @Override
238        public double getWeightedValue(Placement value, Set<Placement> conflicts) {
239            return iValue * iWeight;
240        }
241    
242        @Override
243        public double getValue(Collection<Lecture> variables) {
244            double lunchValue = 0.0d;
245            Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>();
246            for (Lecture lecture : variables) {
247                constraints.addAll(lecture.getInstructorConstraints());
248            }
249            for (InstructorConstraint instructor : constraints) {
250                lunchValue += getLunchPreference(instructor);
251            }
252            return lunchValue * iLunchWeight;
253        }
254    
255        @Override
256        public double getWeightedValue(Collection<Lecture> variables) {
257            double lunchValue = 0.0d;
258            Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>();
259            for (Lecture lecture : variables) {
260                constraints.addAll(lecture.getInstructorConstraints());
261            }
262            for (InstructorConstraint instructor : constraints) {
263                lunchValue += getLunchPreference(instructor);
264            }
265            return lunchValue * iLunchWeight * iWeight;
266        }
267    
268        @Override
269        public void getInfo(Map<String, String> info) {
270            Set<String> violatedLunchBreaks = new TreeSet<String>();
271            int lunchViolations = 0;
272            for (InstructorConstraint c : ((TimetableModel)getModel()).getInstructorConstraints()) {
273                String days = "";
274                CompactInfo compactInfo = getCompactInfo(c);
275                for (int i = 0; i < Constants.NR_DAYS; i++) {
276                    if (compactInfo.getLunchDayViolations()[i] > 0) {
277                        if (iFullInfo)
278                            days += (days.isEmpty() ? "" : ", ") + compactInfo.getLunchDayViolations()[i] + " &times; " + Constants.DAY_NAMES_SHORT[i];
279                        lunchViolations += compactInfo.getLunchDayViolations()[i];
280                    }
281                }
282                if (iFullInfo && !days.isEmpty())
283                    violatedLunchBreaks.add(c.getName() + ": " + days);
284            }
285            if (lunchViolations > 0) {
286                info.put("Lunch breaks", getPerc(lunchViolations, 0, ((TimetableModel)getModel()).getInstructorConstraints().size() * Constants.NR_DAYS * getWeeks().size()) + "% (" + lunchViolations + ")");
287                if (iFullInfo && !violatedLunchBreaks.isEmpty()) {
288                    String message = "";
289                    for (String s: violatedLunchBreaks)
290                        message += (message.isEmpty() ? "" : "<br>") + s;
291                    info.put("Lunch break violations", message);
292                }
293            }
294        }
295    
296        @Override
297        public void getInfo(Map<String, String> info, Collection<Lecture> variables) {
298            Set<InstructorConstraint> constraints = new HashSet<InstructorConstraint>();
299            for (Lecture lecture : variables) {
300                for (InstructorConstraint c : lecture.getInstructorConstraints()) {
301                    constraints.add(c);
302                }
303            }
304            Set<String> violatedLunchBreaks = new TreeSet<String>();
305            int lunchViolations = 0;
306            for (InstructorConstraint c : constraints) {
307                String days = "";
308                CompactInfo compactInfo = getCompactInfo(c);
309                for (int i = 0; i < Constants.NR_DAYS; i++) {
310                    if (compactInfo.getLunchDayViolations()[i] > 0) {
311                        if (iFullInfo)
312                            days += (days.isEmpty() ? "" : ", ") + compactInfo.getLunchDayViolations()[i] + " &times; " + Constants.DAY_NAMES_SHORT[i];
313                        lunchViolations += compactInfo.getLunchDayViolations()[i];
314                    }
315                }
316                if (iFullInfo && !days.isEmpty())
317                    violatedLunchBreaks.add(c.getName() + ": " + days);
318            }
319            if (lunchViolations > 0) {
320                info.put("Lunch breaks", getPerc(lunchViolations, 0, constraints.size() * Constants.NR_DAYS * getWeeks().size()) + "% (" + lunchViolations + ")");
321                if (iFullInfo && !violatedLunchBreaks.isEmpty()) {
322                    String message = "";
323                    for (String s: violatedLunchBreaks)
324                        message += (message.isEmpty() ? "" : "<br>") + s;
325                    info.put("Lunch break violations", message);
326                }
327            }
328        }
329        
330        /**
331         * The class is used as a container of information concerning compact
332         * timetables of instructors. It is designed as an attribute of an
333         * InstructorConstraint.
334         */
335        public static class CompactInfo {
336            // lunch attributes
337            private int[] iLunchDayViolations = new int[Constants.NR_DAYS];
338    
339            public CompactInfo() {
340            }
341            
342            public int[] getLunchDayViolations() { return iLunchDayViolations; }
343        }
344    }