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 (week != null && !value.getTimeLocation().getWeekCode().intersects(week)) return false; 124 return (value.getTimeLocation().getDayCode() & Constants.DAY_CODES[dayOfWeek]) != 0; 125 } 126 127 @SuppressWarnings("unchecked") 128 protected Set<Lecture>[] getDayAssignments(BitSet week) { 129 if (week == null) { 130 if (iDayAssignments == null) { 131 iDayAssignments = new Set[Constants.NR_DAYS]; 132 for (int i = 0; i < iDayAssignments.length; i++) 133 iDayAssignments[i] = new HashSet<Lecture>(); 134 } 135 return iDayAssignments; 136 } else { 137 if (iWeekDayAssignments == null) 138 iWeekDayAssignments = new HashMap<BitSet, Set<Lecture>[]>(); 139 Set<Lecture>[] dayAssignments = iWeekDayAssignments.get(week); 140 if (dayAssignments == null) { 141 dayAssignments = new Set[Constants.NR_DAYS]; 142 for (int i = 0; i < dayAssignments.length; i++) 143 dayAssignments[i] = new HashSet<Lecture>(); 144 iWeekDayAssignments.put(week, dayAssignments); 145 } 146 return dayAssignments; 147 } 148 } 149 150 @Override 151 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 152 for (BitSet week: getWeeks()) { 153 Set<Lecture>[] dayAssignments = getDayAssignments(week); 154 for (int i = 0; i < dayAssignments.length; i++) 155 if (overlaps(week, i, value)) 156 dayAssignments[i].add(value.variable()); 157 } 158 updateCriterion(assignment); 159 } 160 161 @Override 162 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 163 for (BitSet week: getWeeks()) { 164 Set<Lecture>[] dayAssignments = getDayAssignments(week); 165 for (int i = 0; i < dayAssignments.length; i++) 166 if (overlaps(week, i, value)) 167 dayAssignments[i].remove(value.variable()); 168 } 169 updateCriterion(assignment); 170 } 171 172 public int nrDays(BitSet week, Placement value, Set<Placement> conflicts) { 173 Set<Lecture>[] dayAssignments = getDayAssignments(week); 174 Integer min = null, max = null; 175 for (int i = 0; i < dayAssignments.length; i++) { 176 int cnt = dayAssignments[i].size(); 177 if (value != null) { 178 if (overlaps(week, i, value)) cnt ++; 179 if (dayAssignments[i].contains(value.variable())) cnt --; 180 } 181 if (conflicts != null) { 182 for (Placement conflict: conflicts) { 183 if (value != null && conflict.variable().equals(value.variable())) continue; 184 if (dayAssignments[i].contains(conflict.variable())) cnt --; 185 } 186 } 187 if (cnt > 0) { 188 if (min == null) min = i; 189 max = i; 190 } 191 } 192 if (min == null) return 0; 193 return max - min + 1; 194 } 195 196 public int nrDays(Placement value, Set<Placement> conflicts) { 197 int ret = 0; 198 for (BitSet week: getWeeks()) { 199 int days = nrDays(week, value, conflicts); 200 if (days > ret) ret = days; 201 } 202 return ret; 203 } 204 205 public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) { 206 for (BitSet week: getWeeks()) { 207 Set<Lecture>[] dayAssignments = getDayAssignments(week); 208 Integer min = null, max = null; 209 Integer minThisPl = null, maxThisPl = null; 210 for (int i = 0; i < dayAssignments.length; i++) { 211 int cnt = dayAssignments[i].size(); 212 if (overlaps(week, i, value)) { 213 if (minThisPl == null) minThisPl = i; 214 maxThisPl = i; 215 cnt ++; 216 } 217 if (dayAssignments[i].contains(value.variable())) cnt --; 218 for (Placement conflict: conflicts) { 219 if (conflict.variable().equals(value.variable())) continue; 220 if (dayAssignments[i].contains(conflict.variable())) cnt --; 221 } 222 if (cnt > 0) { 223 if (min == null) min = i; 224 max = i; 225 } 226 } 227 if (min == null || max - min + 1 <= iMaxDays) continue; 228 if ((minThisPl == null || min < minThisPl) && (maxThisPl == null || maxThisPl < max)) { 229 if (ToolBox.random() <= 0.5) 230 return dayAssignments[min]; 231 else 232 return dayAssignments[max]; 233 } 234 if (minThisPl == null || min < minThisPl) 235 return dayAssignments[min]; 236 if (maxThisPl == null || maxThisPl < max) 237 return dayAssignments[max]; 238 } 239 return null; 240 } 241 242 public int nrViolations(BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 243 Set<Lecture>[] dayAssignments = getDayAssignments(week); 244 Integer min = null, max = null; 245 for (int i = 0; i < dayAssignments.length; i++) { 246 int cnt = dayAssignments[i].size(); 247 if (assignments != null) { 248 for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) { 249 Placement assignment = entry.getValue(); 250 if (assignment != null && overlaps(week, i, assignment)) cnt ++; 251 } 252 } 253 if (conflicts != null) { 254 for (Placement conflict: conflicts) { 255 if (assignments != null && assignments.containsKey(conflict.variable())) continue; 256 if (dayAssignments[i].contains(conflict.variable())) cnt --; 257 } 258 } 259 if (cnt > 0) { 260 if (min == null) min = i; 261 max = i; 262 } 263 } 264 if (min == null) return 0; 265 return (max - min + 1 <= iMaxDays ? 0 : max - min + 1 - iMaxDays); 266 } 267 268 public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 269 int ret = 0; 270 for (BitSet week: getWeeks()) { 271 ret += nrViolations(week, assignments, conflicts); 272 } 273 return ret; 274 } 275 276 } 277}