001package org.cpsolver.coursett.constraint;
002
003import java.util.ArrayList;
004import java.util.BitSet;
005import java.util.Collections;
006import java.util.HashMap;
007import java.util.List;
008import java.util.Map;
009import java.util.Set;
010import java.util.regex.Matcher;
011import java.util.regex.Pattern;
012
013import org.cpsolver.coursett.Constants;
014import org.cpsolver.coursett.model.Lecture;
015import org.cpsolver.coursett.model.Placement;
016import org.cpsolver.ifs.assignment.Assignment;
017import org.cpsolver.ifs.model.WeakeningConstraint;
018import org.cpsolver.ifs.util.ToolBox;
019
020
021/**
022 * 
023 * The MaxHoles constraint limits the number of free time (holes) for an instructor on a day.<br>
024 * It has one parameter: a maximal amount of free time (holes) that an instructor have on a day in minutes.<br>
025 * Reference _MaxHoles:120_ translates to a maximum number of two hours on a day (between the first and the last class on a day).<br>
026 * 
027 * @author  Tomáš Müller
028 * @version CourseTT 1.3 (University Course Timetabling)<br>
029 *          Copyright (C) 2013 - 2017 Tomáš Müller<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 */
045public class MaxHolesFlexibleConstraint extends FlexibleConstraint implements WeakeningConstraint<Lecture, Placement> {
046    private int iMaxHolesOnADay = 288;
047    
048    public MaxHolesFlexibleConstraint(Long id, String owner, String preference, String reference) {
049        super(id, owner, preference, reference);     
050
051        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_HOLES.getPattern()).matcher(reference);
052        if (matcher.find()) {                
053            iMaxHolesOnADay = Integer.parseInt(matcher.group(2)) / Constants.SLOT_LENGTH_MIN;
054            iConstraintType = FlexibleConstraintType.MAX_HOLES;           
055        }
056    }
057    
058    /**
059     * Count number of holes (free slots) between the given classes on given day and week.
060     * @param assignment current assignment
061     * @param dayCode representation of days in week combination
062     * @param conflicts placements to be unassigned
063     * @param value placement to be assigned
064     * @param assignments placements of variables
065     * @param week bitset representing a date pattern
066     * @return number of holes (free slots) that are over the limit
067     */
068    public int countHoles(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {
069        List<Placement> placements = new ArrayList<Placement>(getRelevantPlacements(assignment, dayCode, conflicts, value, assignments, week));
070        Collections.sort(placements, new PlacementTimeComparator());
071        
072        int lastSlot = -1;
073        int holes = 0;
074        for (Placement placement: placements) {
075            if (lastSlot >= 0 && placement.getTimeLocation().getStartSlot() > lastSlot) {
076                holes += (placement.getTimeLocation().getStartSlot() - lastSlot);
077            }
078            lastSlot = Math.max(lastSlot, placement.getTimeLocation().getStartSlot() + placement.getTimeLocation().getLength());
079        }
080        return holes;
081    }
082
083    /**
084     * Count violations, that is weekly average free time that is over the limit in hours.
085     * @param assignment current assignment
086     * @param conflicts placements to be unassigned
087     * @param assignments placements of variables
088     * @return weekly average free time that is over the limit in hours
089     */
090    @Override
091    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
092        double penalty = 0;
093        // constraint is checked for every day in week
094        for (int dayCode : Constants.DAY_CODES) {
095            // constraint is checked for every week in semester (or for the whole semester)
096            for (BitSet week : getWeeks()) {
097                // count holes in the week and day
098                int holes = countHoles(assignment, dayCode, conflicts, null, assignments, week);
099                if (holes > iMaxHolesOnADay)
100                    penalty += (holes - iMaxHolesOnADay);
101            }
102        }
103        // return average holes in a week, in hours
104        return penalty / (12.0 * getWeeks().size());
105    }
106
107    @Override
108    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
109        if (!isHard()) return;
110        
111        MaxHolesFlexibleConstraintContext context = (MaxHolesFlexibleConstraintContext)getContext(assignment);
112        
113        // constraint is checked for every day in week
114        for (int dayCode : Constants.DAY_CODES) {
115            if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
116            // constraint is checked for every week in semester (or for the whole semester)
117            for (BitSet week : getWeeks()) {
118                if (isPreciseDateComputation()) {
119                    if (!value.getTimeLocation().overlaps(dayCode, week, getDayOfWeekOffset())) continue;
120                } else {
121                    if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
122                }
123                // check penalty
124                int penalty = countHoles(assignment, dayCode, conflicts, value, null, week);
125                while (penalty > context.getMaxHoles(dayCode, week)) {
126                    // too many holes -> identify adepts for unassignment
127                    List<Placement> adepts = new ArrayList<Placement>();
128                    for (Placement placement: getRelevantPlacements(assignment, dayCode, conflicts, value, null, week)) {
129                        if (placement.equals(value)) continue; // skip given value
130                        // check if removing placement would improve the penalty
131                        HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); assignments.put(placement.variable(), null);
132                        int newPenalty = countHoles(assignment, dayCode, conflicts, value, assignments, week);
133                        if (newPenalty <= penalty)
134                            adepts.add(placement);
135                    }
136                    
137                    // no adepts -> fail
138                    if (adepts.isEmpty()) {
139                        conflicts.add(value); return;
140                    }
141                    
142                    // pick one randomly
143                    conflicts.add(ToolBox.random(adepts));
144                    penalty = countHoles(assignment, dayCode, conflicts, value, null, week);
145                }
146            }
147        }
148    }
149
150    @Override
151    public void weaken(Assignment<Lecture, Placement> assignment) {
152    }
153    
154    @Override
155    public boolean isConsistent(Placement value1, Placement value2) {
156        // there is no way to check without trying to put other placements in between
157        return true;
158    }
159
160    @Override
161    public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
162        if (isHard())
163            ((MaxHolesFlexibleConstraintContext)getContext(assignment)).weaken(assignment, value);
164    }
165    
166    @Override
167    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
168        return new MaxHolesFlexibleConstraintContext(assignment);
169    }
170
171    public class MaxHolesFlexibleConstraintContext extends FlexibleConstraintContext {
172        private Map<Integer, Map<BitSet, Integer>> iMaxHoles = new HashMap<Integer, Map<BitSet, Integer>>();
173        
174        public MaxHolesFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
175            super(assignment);
176        }
177
178        public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
179            if (!isHard()) return;
180            for (int dayCode : Constants.DAY_CODES) {
181                if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
182                for (BitSet week : getWeeks()) {
183                    if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
184                    int penalty = countHoles(assignment, dayCode, null, value, null, week);
185                    if (penalty > iMaxHolesOnADay) {
186                        Map<BitSet, Integer> holes = iMaxHoles.get(dayCode);
187                        if (holes == null) {
188                            holes = new HashMap<BitSet, Integer>();
189                            iMaxHoles.put(dayCode, holes);
190                        }
191                        Integer oldPenalty = holes.get(week);
192                        if (oldPenalty != null && oldPenalty >= penalty) continue;
193                        holes.put(week, penalty);
194                    }
195                }
196            }
197        }
198        
199        public int getMaxHoles(int dayCode, BitSet week) {
200            Map<BitSet, Integer> holes = iMaxHoles.get(dayCode);
201            if (holes == null) return iMaxHolesOnADay;
202            Integer penalty = holes.get(week);
203            if (penalty == null || penalty < iMaxHolesOnADay) return iMaxHolesOnADay;
204            return penalty;
205        }
206    }
207    
208}