Source code

001package org.cpsolver.coursett.constraint;
002
003import java.util.BitSet;
004import java.util.HashMap;
005import java.util.HashSet;
006import java.util.Map;
007import java.util.Set;
008import java.util.regex.Matcher;
009import java.util.regex.Pattern;
010
011import org.cpsolver.coursett.Constants;
012import org.cpsolver.coursett.criteria.FlexibleConstraintCriterion;
013import org.cpsolver.coursett.model.Lecture;
014import org.cpsolver.coursett.model.Placement;
015import org.cpsolver.ifs.assignment.Assignment;
016import org.cpsolver.ifs.criteria.Criterion;
017import org.cpsolver.ifs.util.ToolBox;
018
019/**
020 * 
021 * The MaxConsecutiveDays constraint limits the number of consecutive days of week during which the given set of classes are taught.<br>
022 * It has one parameter: a maximal number of consecutive days during which the given set of classes can be placed.<br>
023 * Reference _MaxConsDays:2_ translates to a maximum number of 2 consecutive days a week (so for instance, Monday &amp; Tuesday,
024 * Tuesday &amp; Wednesday, Wednesday &amp; Thursday, ...)<br>
025 * 
026 * @author  Tomáš Müller
027 * @version CourseTT 1.3 (University Course Timetabling)<br>
028 *          Copyright (C) 2022 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 MaxConsecutiveDaysFlexibleConstraint extends FlexibleConstraint {
045private int iMaxDays;
046    
047    public MaxConsecutiveDaysFlexibleConstraint(Long id, String owner, String preference, String reference) {
048        super(id, owner, preference, reference);     
049
050        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_CONSECUTIVE_DAYS.getPattern()).matcher(reference);
051        if (matcher.find()) {
052            iMaxDays = Integer.parseInt(matcher.group(2));
053            iConstraintType = FlexibleConstraintType.MAX_CONSECUTIVE_DAYS;           
054        }
055    }
056    
057    @Override
058    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
059        return ((MaxConsecutiveDaysFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts);
060    }
061
062    @Override
063    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
064        if (!isHard()) return;
065        
066        MaxConsecutiveDaysFlexibleConstraintContext context = (MaxConsecutiveDaysFlexibleConstraintContext)getContext(assignment);
067        while (context.nrDays(value, conflicts) > iMaxDays && !conflicts.contains(value)) {
068            Set<Lecture> candidates = context.candidates(value, conflicts);
069            if (candidates == null) {
070                conflicts.add(value);
071                return;
072            }
073            for (Lecture candidate: candidates) {
074                Placement conflict = assignment.getValue(candidate);
075                if (conflict != null)
076                    conflicts.add(conflict);
077            }
078        }
079    }
080    
081    @Override
082    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
083        if (!isHard()) return false;
084        return ((MaxConsecutiveDaysFlexibleConstraintContext)getContext(assignment)).nrDays(value, null) > iMaxDays;
085    }
086    
087    @Override
088    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
089        return new MaxConsecutiveDaysFlexibleConstraintContext(assignment);
090    }
091    
092    public class MaxConsecutiveDaysFlexibleConstraintContext extends FlexibleConstraintContext {
093        private Map<BitSet, Set<Lecture>[]> iWeekDayAssignments = null;
094        private Set<Lecture> iDayAssignments[] = null;
095        
096        public MaxConsecutiveDaysFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
097            super();
098            for (BitSet week: getWeeks()) {
099                Set<Lecture>[] dayAssignments = getDayAssignments(week);
100                for (Lecture variable: variables()) {
101                    Placement value = assignment.getValue(variable);
102                    if (value != null) {
103                        for (int i = 0; i < dayAssignments.length; i++)
104                            if (overlaps(week, i, value))
105                                dayAssignments[i].add(value.variable());
106                    }
107                }
108            }
109            if (!isHard()) {
110                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
111                if (criterion != null) {
112                    double pref = nrViolations(null, null);
113                    if (pref == 0)
114                        iLastPreference = -Math.abs(iPreference);
115                    else 
116                        iLastPreference = Math.abs(iPreference) * pref;
117                    criterion.inc(assignment, iLastPreference);  
118                }
119            }
120        }
121        
122        protected boolean overlaps(BitSet week, int dayOfWeek, Placement value) {
123            if (value == null || value.getTimeLocation() == null) return false;
124            if (isPreciseDateComputation())
125                return value.getTimeLocation().hasDate(dayOfWeek, week, getDayOfWeekOffset());
126            if (week != null && !value.getTimeLocation().getWeekCode().intersects(week)) return false;
127            return (value.getTimeLocation().getDayCode() & Constants.DAY_CODES[dayOfWeek]) != 0;
128        }
129        
130        @SuppressWarnings("unchecked")
131        protected Set<Lecture>[] getDayAssignments(BitSet week) {
132            if (week == null) {
133                if (iDayAssignments == null) {
134                    iDayAssignments = new Set[Constants.NR_DAYS];
135                    for (int i = 0; i < iDayAssignments.length; i++)
136                        iDayAssignments[i] = new HashSet<Lecture>();
137                }
138                return iDayAssignments;
139            } else {
140                if (iWeekDayAssignments == null)
141                    iWeekDayAssignments = new HashMap<BitSet, Set<Lecture>[]>();
142                Set<Lecture>[] dayAssignments = iWeekDayAssignments.get(week);
143                if (dayAssignments == null) {
144                    dayAssignments = new Set[Constants.NR_DAYS];
145                    for (int i = 0; i < dayAssignments.length; i++)
146                        dayAssignments[i] = new HashSet<Lecture>();
147                    iWeekDayAssignments.put(week, dayAssignments);
148                }
149                return dayAssignments;
150            }
151        }
152
153        @Override
154        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
155            for (BitSet week: getWeeks()) {
156                Set<Lecture>[] dayAssignments = getDayAssignments(week);
157                for (int i = 0; i < dayAssignments.length; i++)
158                    if (overlaps(week, i, value))
159                        dayAssignments[i].add(value.variable());
160            }
161            updateCriterion(assignment);
162        }
163        
164        @Override
165        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
166            for (BitSet week: getWeeks()) {
167                Set<Lecture>[] dayAssignments = getDayAssignments(week);
168                for (int i = 0; i < dayAssignments.length; i++)
169                    if (overlaps(week, i, value))
170                        dayAssignments[i].remove(value.variable());
171            }
172            updateCriterion(assignment);
173        }
174        
175        public int nrDays(BitSet week, Placement value, Set<Placement> conflicts) {
176            Set<Lecture>[] dayAssignments = getDayAssignments(week);
177            Integer min = null, max = null;
178            for (int i = 0; i < dayAssignments.length; i++) {
179                int cnt = dayAssignments[i].size();
180                if (value != null) {
181                    if (overlaps(week, i, value)) cnt ++;
182                    if (dayAssignments[i].contains(value.variable())) cnt --; 
183                }
184                if (conflicts != null) {
185                    for (Placement conflict: conflicts) {
186                        if (value != null && conflict.variable().equals(value.variable())) continue;
187                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
188                    }
189                }
190                if (cnt > 0) {
191                    if (min == null) min = i;
192                    max = i;
193                }
194            }
195            if (min == null) return 0;
196            return max - min + 1;
197        }
198        
199        public int nrDays(Placement value, Set<Placement> conflicts) {
200            int ret = 0; 
201            for (BitSet week: getWeeks()) {
202                int days = nrDays(week, value, conflicts);
203                if (days > ret) ret = days;
204            }
205            return ret;
206        }
207        
208        public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) {
209            for (BitSet week: getWeeks()) {
210                Set<Lecture>[] dayAssignments = getDayAssignments(week);
211                Integer min = null, max = null;
212                Integer minThisPl = null, maxThisPl = null;
213                for (int i = 0; i < dayAssignments.length; i++) {
214                    int cnt = dayAssignments[i].size();
215                    if (overlaps(week, i, value)) {
216                        if (minThisPl == null) minThisPl = i;
217                        maxThisPl = i;
218                        cnt ++;
219                    }
220                    if (dayAssignments[i].contains(value.variable())) cnt --;
221                    for (Placement conflict: conflicts) {
222                        if (conflict.variable().equals(value.variable())) continue;
223                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
224                    }
225                    if (cnt > 0) {
226                        if (min == null) min = i;
227                        max = i;
228                    }
229                }
230                if (min == null || max - min + 1 <= iMaxDays) continue;
231                if ((minThisPl == null || min < minThisPl) && (maxThisPl == null || maxThisPl < max)) {
232                    if (ToolBox.random() <= 0.5)
233                        return dayAssignments[min];
234                    else
235                        return dayAssignments[max];
236                }
237                if (minThisPl == null || min < minThisPl)
238                    return dayAssignments[min];
239                if (maxThisPl == null || maxThisPl < max)
240                    return dayAssignments[max];
241            }
242            return null;
243        }
244        
245        public int nrViolations(BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
246            Set<Lecture>[] dayAssignments = getDayAssignments(week);
247            Integer min = null, max = null;
248            for (int i = 0; i < dayAssignments.length; i++) {
249                int cnt = dayAssignments[i].size();
250                if (assignments != null) {
251                    for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) {
252                        Placement assignment = entry.getValue();
253                        if (assignment != null && overlaps(week, i, assignment)) cnt ++;
254                    } 
255                }
256                if (conflicts != null) {
257                    for (Placement conflict: conflicts) {
258                        if (assignments != null && assignments.containsKey(conflict.variable())) continue;
259                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
260                    }
261                }
262                if (cnt > 0) {
263                    if (min == null) min = i;
264                    max = i;
265                }
266            }
267            if (min == null) return 0;
268            return (max - min + 1 <= iMaxDays ? 0 : max - min + 1 - iMaxDays);
269        }
270        
271        public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
272            int ret = 0; 
273            for (BitSet week: getWeeks()) {
274                ret += nrViolations(week, assignments, conflicts);
275            }
276            return ret;
277        }
278    
279    }
280}