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}