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.ifs.assignment.Assignment; 018import org.cpsolver.ifs.criteria.Criterion; 019import org.cpsolver.ifs.util.ToolBox; 020 021/** 022 * 023 * The MaxDays constraint limits the number of days of week during which the given set of classes are taught.<br> 024 * It has one parameter: a maximal number of week days during which the given set of classes can be placed.<br> 025 * Reference _MaxDays:2_ translates to a maximum number of 2 days a week<br> 026 * 027 * @version CourseTT 1.3 (University Course Timetabling)<br> 028 * Copyright (C) 2015 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 MaxDaysFlexibleConstraint extends FlexibleConstraint { 045 private int iMaxDays; 046 047 public MaxDaysFlexibleConstraint(Long id, String owner, String preference, String reference) { 048 super(id, owner, preference, reference); 049 050 Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_DAYS.getPattern()).matcher(reference); 051 if (matcher.find()) { 052 iMaxDays = Integer.parseInt(matcher.group(2)); 053 iConstraintType = FlexibleConstraintType.MAX_DAYS; 054 } 055 } 056 057 @Override 058 public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) { 059 return ((MaxDaysFlexibleConstraintContext)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 MaxDaysFlexibleConstraintContext context = (MaxDaysFlexibleConstraintContext)getContext(assignment); 067 while (context.nrDays(value, conflicts) > iMaxDays) { 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 ((MaxDaysFlexibleConstraintContext)getContext(assignment)).nrDays(value, null) > iMaxDays; 085 } 086 087 @Override 088 public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 089 return new MaxDaysFlexibleConstraintContext(assignment); 090 } 091 092 public class MaxDaysFlexibleConstraintContext extends FlexibleConstraintContext { 093 private Map<BitSet, Set<Lecture>[]> iWeekDayAssignments = null; 094 private Set<Lecture> iDayAssignments[] = null; 095 096 public MaxDaysFlexibleConstraintContext(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 (hasDay(week, i, value)) 105 dayAssignments[i].add(value.variable()); 106 } 107 } 108 } 109 110 if (!isHard()) { 111 Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class); 112 if (criterion != null) { 113 double pref = nrViolations(null, null); 114 if (pref == 0) 115 iLastPreference = -Math.abs(iPreference); 116 else 117 iLastPreference = Math.abs(iPreference) * pref; 118 criterion.inc(assignment, iLastPreference); 119 } 120 } 121 } 122 123 protected boolean hasDay(BitSet week, int dayOfWeek, Placement value) { 124 if (value == null || value.getTimeLocation() == null) return false; 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 (hasDay(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 (hasDay(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 int ret = 0; 177 for (int i = 0; i < dayAssignments.length; i++) { 178 int cnt = dayAssignments[i].size(); 179 if (value != null) { 180 if (hasDay(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) ret++; 190 } 191 return ret; 192 } 193 194 public int nrDays(Placement value, Set<Placement> conflicts) { 195 int ret = 0; 196 for (BitSet week: getWeeks()) { 197 int days = nrDays(week, value, conflicts); 198 if (days > ret) ret = days; 199 } 200 return ret; 201 } 202 203 public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) { 204 for (BitSet week: getWeeks()) { 205 Set<Lecture>[] dayAssignments = getDayAssignments(week); 206 int bestCnt = 0; 207 int nrDays = 0; 208 List<Integer> bestWeeks = new ArrayList<Integer>(); 209 for (int i = 0; i < dayAssignments.length; i++) { 210 if (hasDay(week, i, value)) { 211 nrDays++; 212 continue; 213 } 214 int cnt = dayAssignments[i].size(); 215 if (dayAssignments[i].contains(value.variable())) cnt --; 216 for (Placement conflict: conflicts) { 217 if (conflict.variable().equals(value.variable())) continue; 218 if (dayAssignments[i].contains(conflict.variable())) cnt --; 219 } 220 if (cnt <= 0) continue; 221 nrDays ++; 222 if (bestWeeks.isEmpty() || bestCnt > cnt) { 223 bestWeeks.clear(); bestWeeks.add(i); bestCnt = cnt; 224 } else if (bestCnt == cnt) { 225 bestWeeks.add(i); 226 } 227 } 228 if (!bestWeeks.isEmpty() && nrDays > iMaxDays) return dayAssignments[ToolBox.random(bestWeeks)]; 229 } 230 return null; 231 } 232 233 public int nrViolations(BitSet week, HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 234 Set<Lecture>[] dayAssignments = getDayAssignments(week); 235 int days = 0; 236 for (int i = 0; i < dayAssignments.length; i++) { 237 int cnt = dayAssignments[i].size(); 238 if (assignments != null) { 239 for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) { 240 Placement assignment = entry.getValue(); 241 if (assignment != null && hasDay(week, i, assignment)) cnt ++; 242 } 243 } 244 if (conflicts != null) 245 for (Placement conflict: conflicts) { 246 if (assignments != null && assignments.containsKey(conflict.variable())) continue; 247 if (dayAssignments[i].contains(conflict.variable())) cnt --; 248 } 249 if (cnt > 0) days ++; 250 } 251 return (days <= iMaxDays ? 0 : days - iMaxDays); 252 } 253 254 public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 255 int ret = 0; 256 for (BitSet week: getWeeks()) { 257 ret += nrViolations(week, assignments, conflicts); 258 } 259 return ret; 260 } 261 } 262}