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 * @version CourseTT 1.3 (University Course Timetabling)<br>
028 *          Copyright (C) 2013 - 2017 Tomáš Müller<br>
029 * <br>
030 *          This library is free software; you can redistribute it and/or modify
031 *          it under the terms of the GNU Lesser General Public License as
032 *          published by the Free Software Foundation; either version 3 of the
033 *          License, or (at your option) any later version. <br>
034 * <br>
035 *          This library is distributed in the hope that it will be useful, but
036 *          WITHOUT ANY WARRANTY; without even the implied warranty of
037 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
038 *          Lesser General Public License for more details. <br>
039 * <br>
040 *          You should have received a copy of the GNU Lesser General Public
041 *          License along with this library; if not see
042 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
043 */
044public class MaxHolesFlexibleConstraint extends FlexibleConstraint implements WeakeningConstraint<Lecture, Placement> {
045    private int iMaxHolesOnADay = 288;
046    
047    public MaxHolesFlexibleConstraint(Long id, String owner, String preference, String reference) {
048        super(id, owner, preference, reference);     
049
050        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_HOLES.getPattern()).matcher(reference);
051        if (matcher.find()) {                
052            iMaxHolesOnADay = Integer.parseInt(matcher.group(2)) / Constants.SLOT_LENGTH_MIN;
053            iConstraintType = FlexibleConstraintType.MAX_HOLES;           
054        }
055    }
056    
057    /**
058     * Count number of holes (free slots) between the given classes on given day and week.
059     * @param assignment current assignment
060     * @param dayCode representation of days in week combination
061     * @param conflicts placements to be unassigned
062     * @param value placement to be assigned
063     * @param assignments placements of variables
064     * @param week bitset representing a date pattern
065     * @return number of holes (free slots) that are over the limit
066     */
067    public int countHoles(Assignment<Lecture, Placement> assignment, int dayCode, Set<Placement> conflicts, Placement value, HashMap<Lecture, Placement> assignments, BitSet week) {
068        List<Placement> placements = new ArrayList<Placement>(getRelevantPlacements(assignment, dayCode, conflicts, value, assignments, week));
069        Collections.sort(placements, new PlacementTimeComparator());
070        
071        int lastSlot = -1;
072        int holes = 0;
073        for (Placement placement: placements) {
074            if (lastSlot >= 0 && placement.getTimeLocation().getStartSlot() > lastSlot) {
075                holes += (placement.getTimeLocation().getStartSlot() - lastSlot);
076            }
077            lastSlot = Math.max(lastSlot, placement.getTimeLocation().getStartSlot() + placement.getTimeLocation().getLength());
078        }
079        return holes;
080    }
081
082    /**
083     * Count violations, that is weekly average free time that is over the limit in hours.
084     * @param assignment current assignment
085     * @param conflicts placements to be unassigned
086     * @param assignments placements of variables
087     * @return weekly average free time that is over the limit in hours
088     */
089    @Override
090    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
091        double penalty = 0;
092        // constraint is checked for every day in week
093        for (int dayCode : Constants.DAY_CODES) {
094            // constraint is checked for every week in semester (or for the whole semester)
095            for (BitSet week : getWeeks()) {
096                // count holes in the week and day
097                int holes = countHoles(assignment, dayCode, conflicts, null, assignments, week);
098                if (holes > iMaxHolesOnADay)
099                    penalty += (holes - iMaxHolesOnADay);
100            }
101        }
102        // return average holes in a week, in hours
103        return penalty / (12.0 * getWeeks().size());
104    }
105
106    @Override
107    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
108        if (!isHard()) return;
109        
110        MaxHolesFlexibleConstraintContext context = (MaxHolesFlexibleConstraintContext)getContext(assignment);
111        
112        // constraint is checked for every day in week
113        for (int dayCode : Constants.DAY_CODES) {
114            if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
115            // constraint is checked for every week in semester (or for the whole semester)
116            for (BitSet week : getWeeks()) {
117                if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
118                // check penalty
119                int penalty = countHoles(assignment, dayCode, conflicts, value, null, week);
120                while (penalty > context.getMaxHoles(dayCode, week)) {
121                    // too many holes -> identify adepts for unassignment
122                    List<Placement> adepts = new ArrayList<Placement>();
123                    for (Placement placement: getRelevantPlacements(assignment, dayCode, conflicts, value, null, week)) {
124                        if (placement.equals(value)) continue; // skip given value
125                        // check if removing placement would improve the penalty
126                        HashMap<Lecture, Placement> assignments = new HashMap<Lecture, Placement>(); assignments.put(placement.variable(), null);
127                        int newPenalty = countHoles(assignment, dayCode, conflicts, value, assignments, week);
128                        if (newPenalty <= penalty)
129                            adepts.add(placement);
130                    }
131                    
132                    // no adepts -> fail
133                    if (adepts.isEmpty()) {
134                        conflicts.add(value); return;
135                    }
136                    
137                    // pick one randomly
138                    conflicts.add(ToolBox.random(adepts));
139                    penalty = countHoles(assignment, dayCode, conflicts, value, null, week);
140                }
141            }
142        }
143    }
144
145    @Override
146    public void weaken(Assignment<Lecture, Placement> assignment) {
147    }
148    
149    @Override
150    public boolean isConsistent(Placement value1, Placement value2) {
151        // there is no way to check without trying to put other placements in between
152        return true;
153    }
154
155    @Override
156    public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
157        if (isHard())
158            ((MaxHolesFlexibleConstraintContext)getContext(assignment)).weaken(assignment, value);
159    }
160    
161    @Override
162    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
163        return new MaxHolesFlexibleConstraintContext(assignment);
164    }
165
166    public class MaxHolesFlexibleConstraintContext extends FlexibleConstraintContext {
167        private Map<Integer, Map<BitSet, Integer>> iMaxHoles = new HashMap<Integer, Map<BitSet, Integer>>();
168        
169        public MaxHolesFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
170            super(assignment);
171        }
172
173        public void weaken(Assignment<Lecture, Placement> assignment, Placement value) {
174            if (!isHard()) return;
175            for (int dayCode : Constants.DAY_CODES) {
176                if ((value.getTimeLocation().getDayCode() & dayCode) == 0) continue; // ignore other days
177                for (BitSet week : getWeeks()) {
178                    if (week != null && !week.intersects(value.getTimeLocation().getWeekCode())) continue; // ignore other weeks
179                    int penalty = countHoles(assignment, dayCode, null, value, null, week);
180                    if (penalty > iMaxHolesOnADay) {
181                        Map<BitSet, Integer> holes = iMaxHoles.get(dayCode);
182                        if (holes == null) {
183                            holes = new HashMap<BitSet, Integer>();
184                            iMaxHoles.put(dayCode, holes);
185                        }
186                        Integer oldPenalty = holes.get(week);
187                        if (oldPenalty != null && oldPenalty >= penalty) continue;
188                        holes.put(week, penalty);
189                    }
190                }
191            }
192        }
193        
194        public int getMaxHoles(int dayCode, BitSet week) {
195            Map<BitSet, Integer> holes = iMaxHoles.get(dayCode);
196            if (holes == null) return iMaxHolesOnADay;
197            Integer penalty = holes.get(week);
198            if (penalty == null || penalty < iMaxHolesOnADay) return iMaxHolesOnADay;
199            return penalty;
200        }
201    }
202    
203}