001package org.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.BitSet; 005import java.util.HashMap; 006import java.util.HashSet; 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.criteria.FlexibleConstraintCriterion; 015import org.cpsolver.coursett.model.Lecture; 016import org.cpsolver.coursett.model.Placement; 017import org.cpsolver.coursett.model.TimeLocation; 018import org.cpsolver.coursett.model.TimetableModel; 019import org.cpsolver.ifs.assignment.Assignment; 020import org.cpsolver.ifs.criteria.Criterion; 021import org.cpsolver.ifs.model.Model; 022import org.cpsolver.ifs.util.ToolBox; 023 024/** 025 * 026 * The MaxHalfDays constraint limits the number of half-days of week during which the given set of classes are taught.<br> 027 * It has one parameter: a maximal number of week half-days during which the given set of classes can be placed.<br> 028 * A day is split by noon (which can be changed using General.HalfDaySlot parameter). A class starting before noon is considered 029 * a morning class (despite of its end), a class starting at noon or later is considered an afternoon class.<br> 030 * Reference _MaxHalfDays:4_ translates to a maximum number of 4 half-days a week<br> 031 * 032 * @version CourseTT 1.3 (University Course Timetabling)<br> 033 * Copyright (C) 2017 Tomáš Müller<br> 034 * <br> 035 * This library is free software; you can redistribute it and/or modify 036 * it under the terms of the GNU Lesser General Public License as 037 * published by the Free Software Foundation; either version 3 of the 038 * License, or (at your option) any later version. <br> 039 * <br> 040 * This library is distributed in the hope that it will be useful, but 041 * WITHOUT ANY WARRANTY; without even the implied warranty of 042 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 043 * Lesser General Public License for more details. <br> 044 * <br> 045 * You should have received a copy of the GNU Lesser General Public 046 * License along with this library; if not see 047 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 048 */ 049public class MaxHalfDaysFlexibleConstraint extends FlexibleConstraint { 050 private int iMaxHalfDays; 051 private int iNoonSlot = 144; 052 053 public MaxHalfDaysFlexibleConstraint(Long id, String owner, String preference, String reference) { 054 super(id, owner, preference, reference); 055 056 Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_HALF_DAYS.getPattern()).matcher(reference); 057 if (matcher.find()) { 058 iMaxHalfDays = Integer.parseInt(matcher.group(2)); 059 iConstraintType = FlexibleConstraintType.MAX_HALF_DAYS; 060 } 061 } 062 063 @Override 064 public void setModel(Model<Lecture, Placement> model) { 065 super.setModel(model); 066 iNoonSlot = ((TimetableModel)model).getProperties().getPropertyInt("General.HalfDaySlot", iNoonSlot); 067 } 068 069 /** 070 * Returns number of half-days in a day 071 */ 072 protected int getNrHalfDays() { 073 return 2; 074 } 075 076 /** 077 * Returns index of the half day 078 * @param time given time 079 * @return 0 for morning, 1 for evening 080 */ 081 protected int getHalfDay(TimeLocation time) { 082 return (time.getStartSlot() < iNoonSlot ? 0 : 1); 083 } 084 085 @Override 086 public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) { 087 return ((MaxHalfDaysFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts); 088 } 089 090 @Override 091 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 092 if (!isHard()) return; 093 094 MaxHalfDaysFlexibleConstraintContext context = (MaxHalfDaysFlexibleConstraintContext)getContext(assignment); 095 while (context.nrHalfDays(value, conflicts) > iMaxHalfDays) { 096 Set<Lecture> candidates = context.candidates(value, conflicts); 097 if (candidates == null) { 098 conflicts.add(value); 099 return; 100 } 101 for (Lecture candidate: candidates) { 102 Placement conflict = assignment.getValue(candidate); 103 if (conflict != null) 104 conflicts.add(conflict); 105 } 106 } 107 } 108 109 @Override 110 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) { 111 if (!isHard()) return false; 112 return ((MaxHalfDaysFlexibleConstraintContext)getContext(assignment)).nrHalfDays(value, null) > iMaxHalfDays; 113 } 114 115 @Override 116 public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 117 return new MaxHalfDaysFlexibleConstraintContext(assignment); 118 } 119 120 public class MaxHalfDaysFlexibleConstraintContext extends FlexibleConstraintContext { 121 private Map<BitSet, Set<Lecture>[]> iHalfWeekDayAssignments = null; 122 private Set<Lecture> iHalfDayAssignments[] = null; 123 124 public MaxHalfDaysFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) { 125 super(); 126 for (BitSet week: getWeeks()) { 127 Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week); 128 for (Lecture variable: variables()) { 129 Placement value = assignment.getValue(variable); 130 if (value != null) { 131 for (int i = 0; i < Constants.DAY_CODES.length; i++) 132 if (hasDay(week, i, value)) 133 halfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].add(value.variable()); 134 } 135 } 136 } 137 if (!isHard()) { 138 Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class); 139 if (criterion != null) { 140 double pref = nrViolations(null, null); 141 if (pref == 0) 142 iLastPreference = -Math.abs(iPreference); 143 else 144 iLastPreference = Math.abs(iPreference) * pref; 145 criterion.inc(assignment, iLastPreference); 146 } 147 } 148 } 149 150 protected boolean hasDay(BitSet week, int dayOfWeek, Placement value) { 151 if (value == null || value.getTimeLocation() == null) return false; 152 if (week != null && !value.getTimeLocation().getWeekCode().intersects(week)) return false; 153 return (value.getTimeLocation().getDayCode() & Constants.DAY_CODES[dayOfWeek]) != 0; 154 } 155 156 @SuppressWarnings("unchecked") 157 protected Set<Lecture>[] getHalfDayAssignments(BitSet week) { 158 if (week == null) { 159 if (iHalfDayAssignments == null) { 160 iHalfDayAssignments = new Set[getNrHalfDays() * Constants.NR_DAYS]; 161 for (int i = 0; i < iHalfDayAssignments.length; i++) 162 iHalfDayAssignments[i] = new HashSet<Lecture>(); 163 } 164 return iHalfDayAssignments; 165 } else { 166 if (iHalfWeekDayAssignments == null) 167 iHalfWeekDayAssignments = new HashMap<BitSet, Set<Lecture>[]>(); 168 Set<Lecture>[] dayAssignments = iHalfWeekDayAssignments.get(week); 169 if (dayAssignments == null) { 170 dayAssignments = new Set[getNrHalfDays() * Constants.NR_DAYS]; 171 for (int i = 0; i < dayAssignments.length; i++) 172 dayAssignments[i] = new HashSet<Lecture>(); 173 iHalfWeekDayAssignments.put(week, dayAssignments); 174 } 175 return dayAssignments; 176 } 177 } 178 179 @Override 180 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 181 for (BitSet week: getWeeks()) { 182 Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week); 183 for (int i = 0; i < Constants.DAY_CODES.length; i++) 184 if (hasDay(week, i, value)) 185 halfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].add(value.variable()); 186 } 187 updateCriterion(assignment); 188 } 189 190 @Override 191 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 192 for (BitSet week: getWeeks()) { 193 Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week); 194 for (int i = 0; i < Constants.DAY_CODES.length; i++) 195 if (hasDay(week, i, value)) 196 halfDayAssignments[i * getNrHalfDays() + getHalfDay(value.getTimeLocation())].remove(value.variable()); 197 } 198 updateCriterion(assignment); 199 } 200 201 public int nrHalfDays(BitSet week, Placement value, Set<Placement> conflicts) { 202 Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week); 203 int ret = 0; 204 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 205 for (int j = 0; j < getNrHalfDays(); j++) { 206 int idx = i * getNrHalfDays() + j; 207 int cnt = halfDayAssignments[idx].size(); 208 if (value != null) { 209 if (hasDay(week, i, value) && j == getHalfDay(value.getTimeLocation())) cnt ++; 210 if (halfDayAssignments[idx].contains(value.variable())) cnt --; 211 } 212 if (conflicts != null) { 213 for (Placement conflict: conflicts) { 214 if (value != null && conflict.variable().equals(value.variable())) continue; 215 if (halfDayAssignments[idx].contains(conflict.variable())) cnt --; 216 } 217 } 218 if (cnt > 0) ret++; 219 } 220 } 221 return ret; 222 } 223 224 public int nrHalfDays(Placement value, Set<Placement> conflicts) { 225 int ret = 0; 226 for (BitSet week: getWeeks()) { 227 int days = nrHalfDays(week, value, conflicts); 228 if (days > ret) ret = days; 229 } 230 return ret; 231 } 232 233 public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) { 234 for (BitSet week: getWeeks()) { 235 Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week); 236 int bestCnt = 0; 237 int nrHalfDays = 0; 238 List<Integer> bestHalfDays = new ArrayList<Integer>(); 239 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 240 for (int j = 0; j < getNrHalfDays(); j++) { 241 int idx = i * getNrHalfDays() + j; 242 if (hasDay(week, i, value) && j == getHalfDay(value.getTimeLocation())) { 243 nrHalfDays ++; 244 continue; 245 } 246 int cnt = halfDayAssignments[idx].size(); 247 if (halfDayAssignments[idx].contains(value.variable())) cnt --; 248 for (Placement conflict: conflicts) { 249 if (conflict.variable().equals(value.variable())) continue; 250 if (halfDayAssignments[idx].contains(conflict.variable())) cnt --; 251 } 252 if (cnt <= 0) continue; 253 nrHalfDays ++; 254 if (bestHalfDays.isEmpty() || bestCnt > cnt) { 255 bestHalfDays.clear(); bestHalfDays.add(idx); bestCnt = cnt; 256 } else if (bestCnt == cnt) { 257 bestHalfDays.add(idx); 258 } 259 } 260 } 261 if (!bestHalfDays.isEmpty() && nrHalfDays > iMaxHalfDays) return halfDayAssignments[ToolBox.random(bestHalfDays)]; 262 } 263 return null; 264 } 265 266 public int nrViolations(BitSet week,HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 267 Set<Lecture>[] halfDayAssignments = getHalfDayAssignments(week); 268 int halfDays = 0; 269 for (int i = 0; i < Constants.DAY_CODES.length; i++) { 270 for (int j = 0; j < getNrHalfDays(); j++) { 271 int idx = i * getNrHalfDays() + j; 272 int cnt = halfDayAssignments[idx].size(); 273 if (assignments != null) { 274 for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) { 275 Placement assignment = entry.getValue(); 276 if (assignment != null && hasDay(week, i, assignment) && j == getHalfDay(assignment.getTimeLocation())) cnt ++; 277 } 278 } 279 if (conflicts != null) 280 for (Placement conflict: conflicts) { 281 if (assignments != null && assignments.containsKey(conflict.variable())) continue; 282 if (halfDayAssignments[idx].contains(conflict.variable())) cnt --; 283 } 284 if (cnt > 0) halfDays ++; 285 } 286 } 287 return (halfDays <= iMaxHalfDays ? 0 : halfDays - iMaxHalfDays); 288 } 289 290 public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 291 int ret = 0; 292 for (BitSet week: getWeeks()) { 293 ret += nrViolations(week, assignments, conflicts); 294 } 295 return ret; 296 } 297 } 298}