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 & Tuesday,
024 * Tuesday & Wednesday, Wednesday & Thursday, ...)<br>
025 * 
026 * @version CourseTT 1.3 (University Course Timetabling)<br>
027 *          Copyright (C) 2022 Tomáš Müller<br>
028 * <br>
029 *          This library is free software; you can redistribute it and/or modify
030 *          it under the terms of the GNU Lesser General Public License as
031 *          published by the Free Software Foundation; either version 3 of the
032 *          License, or (at your option) any later version. <br>
033 * <br>
034 *          This library is distributed in the hope that it will be useful, but
035 *          WITHOUT ANY WARRANTY; without even the implied warranty of
036 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
037 *          Lesser General Public License for more details. <br>
038 * <br>
039 *          You should have received a copy of the GNU Lesser General Public
040 *          License along with this library; if not see
041 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
042 */
043public class MaxConsecutiveDaysFlexibleConstraint extends FlexibleConstraint {
044private int iMaxDays;
045    
046    public MaxConsecutiveDaysFlexibleConstraint(Long id, String owner, String preference, String reference) {
047        super(id, owner, preference, reference);     
048
049        Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_CONSECUTIVE_DAYS.getPattern()).matcher(reference);
050        if (matcher.find()) {
051            iMaxDays = Integer.parseInt(matcher.group(2));
052            iConstraintType = FlexibleConstraintType.MAX_CONSECUTIVE_DAYS;           
053        }
054    }
055    
056    @Override
057    public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) {
058        return ((MaxConsecutiveDaysFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts);
059    }
060
061    @Override
062    public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
063        if (!isHard()) return;
064        
065        MaxConsecutiveDaysFlexibleConstraintContext context = (MaxConsecutiveDaysFlexibleConstraintContext)getContext(assignment);
066        while (context.nrDays(value, conflicts) > iMaxDays && !conflicts.contains(value)) {
067            Set<Lecture> candidates = context.candidates(value, conflicts);
068            if (candidates == null) {
069                conflicts.add(value);
070                return;
071            }
072            for (Lecture candidate: candidates) {
073                Placement conflict = assignment.getValue(candidate);
074                if (conflict != null)
075                    conflicts.add(conflict);
076            }
077        }
078    }
079    
080    @Override
081    public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) {
082        if (!isHard()) return false;
083        return ((MaxConsecutiveDaysFlexibleConstraintContext)getContext(assignment)).nrDays(value, null) > iMaxDays;
084    }
085    
086    @Override
087    public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) {
088        return new MaxConsecutiveDaysFlexibleConstraintContext(assignment);
089    }
090    
091    public class MaxConsecutiveDaysFlexibleConstraintContext extends FlexibleConstraintContext {
092        private Map<BitSet, Set<Lecture>[]> iWeekDayAssignments = null;
093        private Set<Lecture> iDayAssignments[] = null;
094        
095        public MaxConsecutiveDaysFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) {
096            super();
097            for (BitSet week: getWeeks()) {
098                Set<Lecture>[] dayAssignments = getDayAssignments(week);
099                for (Lecture variable: variables()) {
100                    Placement value = assignment.getValue(variable);
101                    if (value != null) {
102                        for (int i = 0; i < dayAssignments.length; i++)
103                            if (overlaps(week, i, value))
104                                dayAssignments[i].add(value.variable());
105                    }
106                }
107            }
108            if (!isHard()) {
109                Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class);
110                if (criterion != null) {
111                    double pref = nrViolations(null, null);
112                    if (pref == 0)
113                        iLastPreference = -Math.abs(iPreference);
114                    else 
115                        iLastPreference = Math.abs(iPreference) * pref;
116                    criterion.inc(assignment, iLastPreference);  
117                }
118            }
119        }
120        
121        protected boolean overlaps(BitSet week, int dayOfWeek, Placement value) {
122            if (value == null || value.getTimeLocation() == null) return false;
123            if (isPreciseDateComputation())
124                return value.getTimeLocation().hasDate(dayOfWeek, week, getDayOfWeekOffset());
125            if (week != null && !value.getTimeLocation().getWeekCode().intersects(week)) return false;
126            return (value.getTimeLocation().getDayCode() & Constants.DAY_CODES[dayOfWeek]) != 0;
127        }
128        
129        @SuppressWarnings("unchecked")
130        protected Set<Lecture>[] getDayAssignments(BitSet week) {
131            if (week == null) {
132                if (iDayAssignments == null) {
133                    iDayAssignments = new Set[Constants.NR_DAYS];
134                    for (int i = 0; i < iDayAssignments.length; i++)
135                        iDayAssignments[i] = new HashSet<Lecture>();
136                }
137                return iDayAssignments;
138            } else {
139                if (iWeekDayAssignments == null)
140                    iWeekDayAssignments = new HashMap<BitSet, Set<Lecture>[]>();
141                Set<Lecture>[] dayAssignments = iWeekDayAssignments.get(week);
142                if (dayAssignments == null) {
143                    dayAssignments = new Set[Constants.NR_DAYS];
144                    for (int i = 0; i < dayAssignments.length; i++)
145                        dayAssignments[i] = new HashSet<Lecture>();
146                    iWeekDayAssignments.put(week, dayAssignments);
147                }
148                return dayAssignments;
149            }
150        }
151
152        @Override
153        public void assigned(Assignment<Lecture, Placement> assignment, Placement value) {
154            for (BitSet week: getWeeks()) {
155                Set<Lecture>[] dayAssignments = getDayAssignments(week);
156                for (int i = 0; i < dayAssignments.length; i++)
157                    if (overlaps(week, i, value))
158                        dayAssignments[i].add(value.variable());
159            }
160            updateCriterion(assignment);
161        }
162        
163        @Override
164        public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) {
165            for (BitSet week: getWeeks()) {
166                Set<Lecture>[] dayAssignments = getDayAssignments(week);
167                for (int i = 0; i < dayAssignments.length; i++)
168                    if (overlaps(week, i, value))
169                        dayAssignments[i].remove(value.variable());
170            }
171            updateCriterion(assignment);
172        }
173        
174        public int nrDays(BitSet week, Placement value, Set<Placement> conflicts) {
175            Set<Lecture>[] dayAssignments = getDayAssignments(week);
176            Integer min = null, max = null;
177            for (int i = 0; i < dayAssignments.length; i++) {
178                int cnt = dayAssignments[i].size();
179                if (value != null) {
180                    if (overlaps(week, i, value)) cnt ++;
181                    if (dayAssignments[i].contains(value.variable())) cnt --; 
182                }
183                if (conflicts != null) {
184                    for (Placement conflict: conflicts) {
185                        if (value != null && conflict.variable().equals(value.variable())) continue;
186                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
187                    }
188                }
189                if (cnt > 0) {
190                    if (min == null) min = i;
191                    max = i;
192                }
193            }
194            if (min == null) return 0;
195            return max - min + 1;
196        }
197        
198        public int nrDays(Placement value, Set<Placement> conflicts) {
199            int ret = 0; 
200            for (BitSet week: getWeeks()) {
201                int days = nrDays(week, value, conflicts);
202                if (days > ret) ret = days;
203            }
204            return ret;
205        }
206        
207        public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) {
208            for (BitSet week: getWeeks()) {
209                Set<Lecture>[] dayAssignments = getDayAssignments(week);
210                Integer min = null, max = null;
211                Integer minThisPl = null, maxThisPl = null;
212                for (int i = 0; i < dayAssignments.length; i++) {
213                    int cnt = dayAssignments[i].size();
214                    if (overlaps(week, i, value)) {
215                        if (minThisPl == null) minThisPl = i;
216                        maxThisPl = i;
217                        cnt ++;
218                    }
219                    if (dayAssignments[i].contains(value.variable())) cnt --;
220                    for (Placement conflict: conflicts) {
221                        if (conflict.variable().equals(value.variable())) continue;
222                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
223                    }
224                    if (cnt > 0) {
225                        if (min == null) min = i;
226                        max = i;
227                    }
228                }
229                if (min == null || max - min + 1 <= iMaxDays) continue;
230                if ((minThisPl == null || min < minThisPl) && (maxThisPl == null || maxThisPl < max)) {
231                    if (ToolBox.random() <= 0.5)
232                        return dayAssignments[min];
233                    else
234                        return dayAssignments[max];
235                }
236                if (minThisPl == null || min < minThisPl)
237                    return dayAssignments[min];
238                if (maxThisPl == null || maxThisPl < max)
239                    return dayAssignments[max];
240            }
241            return null;
242        }
243        
244        public int nrViolations(BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
245            Set<Lecture>[] dayAssignments = getDayAssignments(week);
246            Integer min = null, max = null;
247            for (int i = 0; i < dayAssignments.length; i++) {
248                int cnt = dayAssignments[i].size();
249                if (assignments != null) {
250                    for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) {
251                        Placement assignment = entry.getValue();
252                        if (assignment != null && overlaps(week, i, assignment)) cnt ++;
253                    } 
254                }
255                if (conflicts != null) {
256                    for (Placement conflict: conflicts) {
257                        if (assignments != null && assignments.containsKey(conflict.variable())) continue;
258                        if (dayAssignments[i].contains(conflict.variable())) cnt --;
259                    }
260                }
261                if (cnt > 0) {
262                    if (min == null) min = i;
263                    max = i;
264                }
265            }
266            if (min == null) return 0;
267            return (max - min + 1 <= iMaxDays ? 0 : max - min + 1 - iMaxDays);
268        }
269        
270        public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) {
271            int ret = 0; 
272            for (BitSet week: getWeeks()) {
273                ret += nrViolations(week, assignments, conflicts);
274            }
275            return ret;
276        }
277    
278    }
279}