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.criteria.FlexibleConstraintCriterion; 014import org.cpsolver.coursett.model.Lecture; 015import org.cpsolver.coursett.model.Placement; 016import org.cpsolver.coursett.model.TimetableModel; 017import org.cpsolver.ifs.assignment.Assignment; 018import org.cpsolver.ifs.criteria.Criterion; 019import org.cpsolver.ifs.util.ToolBox; 020 021/** 022 * 023 * The MaxWeeks constraint limits the number of weeks during which the given set of classes are taught.<br> 024 * It has two parameters: a maximal number of weeks during which the given set of classes can be placed 025 * and a day code indicating what days of week are considered.<br> 026 * Reference _MaxWeeks:3:6_ translates to a maximum number of 3 weeks, but only for classes that are placed on Fridays and Saturdays 027 * (64 for Monday, 32 for Tuesday, 16 for Wednesday, 8 for Thursday, 4 for Friday, 2 for Saturday, and 1 for Sunday). 028 * If the second parameter is zero, all days of week are considered.<br> 029 * 030 * @version CourseTT 1.3 (University Course Timetabling)<br> 031 * Copyright (C) 2013 - 2014 Tomáš Müller<br> 032 * <br> 033 * This library is free software; you can redistribute it and/or modify 034 * it under the terms of the GNU Lesser General Public License as 035 * published by the Free Software Foundation; either version 3 of the 036 * License, or (at your option) any later version. <br> 037 * <br> 038 * This library is distributed in the hope that it will be useful, but 039 * WITHOUT ANY WARRANTY; without even the implied warranty of 040 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 041 * Lesser General Public License for more details. <br> 042 * <br> 043 * You should have received a copy of the GNU Lesser General Public 044 * License along with this library; if not see 045 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 046 */ 047public class MaxWeeksFlexibleConstraint extends FlexibleConstraint { 048 private int iMaxWeeks; 049 private int iDayCode; 050 051 public MaxWeeksFlexibleConstraint(Long id, String owner, String preference, String reference) { 052 super(id, owner, preference, reference); 053 054 Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_WEEKS.getPattern()).matcher(reference); 055 if (matcher.find()) { 056 iMaxWeeks = Integer.parseInt(matcher.group(2)); 057 iDayCode = Integer.parseInt(matcher.group(3)); 058 iConstraintType = FlexibleConstraintType.MAX_WEEKS; 059 } 060 } 061 062 public boolean isCorectDayOfWeek(Placement value) { 063 return value != null && value.getTimeLocation() != null && (iDayCode == 0 || (iDayCode & value.getTimeLocation().getDayCode()) != 0); 064 } 065 066 @Override 067 public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) { 068 return ((MaxWeeksFlexibleConstraintContext)getContext(assignment)).nrViolations(assignments, conflicts); 069 } 070 071 @Override 072 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) { 073 if (!isHard() || !isCorectDayOfWeek(value)) return; 074 075 MaxWeeksFlexibleConstraintContext context = (MaxWeeksFlexibleConstraintContext)getContext(assignment); 076 while (context.nrWeeks(value, conflicts) > iMaxWeeks) { 077 Set<Lecture> candidates = context.candidates(value, conflicts); 078 if (candidates == null) return; 079 for (Lecture candidate: candidates) { 080 Placement conflict = assignment.getValue(candidate); 081 if (conflict != null) 082 conflicts.add(conflict); 083 } 084 } 085 } 086 087 @Override 088 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) { 089 if (!isHard() || !isCorectDayOfWeek(value)) return false; 090 return ((MaxWeeksFlexibleConstraintContext)getContext(assignment)).nrWeeks(value, null) > iMaxWeeks; 091 } 092 093 @Override 094 public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 095 return new MaxWeeksFlexibleConstraintContext(assignment); 096 } 097 098 public class MaxWeeksFlexibleConstraintContext extends FlexibleConstraintContext { 099 private List<BitSet> iWeeks = null; 100 private Set<Lecture> iWeekAssignments[] = null; 101 102 @SuppressWarnings("unchecked") 103 public MaxWeeksFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) { 104 super(); 105 iWeeks = ((TimetableModel)getModel()).getWeeks(); 106 iWeekAssignments = new Set[iWeeks.size()]; 107 for (int i = 0; i < iWeekAssignments.length; i++) 108 iWeekAssignments[i] = new HashSet<Lecture>(); 109 110 for (Lecture variable: variables()) { 111 Placement value = assignment.getValue(variable); 112 if (value != null && isCorectDayOfWeek(value)) { 113 for (int i = 0; i < iWeeks.size(); i++) 114 if (value.getTimeLocation().shareWeeks(iWeeks.get(i))) 115 iWeekAssignments[i].add(value.variable()); 116 } 117 } 118 119 if (!isHard()) { 120 Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class); 121 if (criterion != null) { 122 double pref = nrViolations(null, null); 123 if (pref == 0) 124 iLastPreference = -Math.abs(iPreference); 125 else 126 iLastPreference = Math.abs(iPreference) * pref; 127 criterion.inc(assignment, iLastPreference); 128 } 129 } 130 } 131 132 @Override 133 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 134 if (isCorectDayOfWeek(value)) { 135 for (int i = 0; i < iWeeks.size(); i++) 136 if (value.getTimeLocation().shareWeeks(iWeeks.get(i))) 137 iWeekAssignments[i].add(value.variable()); 138 updateCriterion(assignment); 139 } 140 } 141 142 @Override 143 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 144 if (isCorectDayOfWeek(value)) { 145 for (int i = 0; i < iWeeks.size(); i++) 146 if (value.getTimeLocation().shareWeeks(iWeeks.get(i))) 147 iWeekAssignments[i].remove(value.variable()); 148 updateCriterion(assignment); 149 } 150 } 151 152 public int nrWeeks(Placement value, Set<Placement> conflicts) { 153 int ret = 0; 154 for (int i = 0; i < iWeeks.size(); i++) { 155 BitSet w = iWeeks.get(i); 156 int cnt = iWeekAssignments[i].size(); 157 if (value != null) { 158 if (value.getTimeLocation().shareWeeks(w)) cnt ++; 159 if (iWeekAssignments[i].contains(value.variable())) cnt --; 160 } 161 if (conflicts != null) { 162 for (Placement conflict: conflicts) { 163 if (value != null && conflict.variable().equals(value.variable())) continue; 164 if (iWeekAssignments[i].contains(conflict.variable())) cnt --; 165 } 166 } 167 if (cnt > 0) ret++; 168 } 169 return ret; 170 } 171 172 public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) { 173 int bestCnt = 0; 174 List<Integer> bestWeeks = new ArrayList<Integer>(); 175 for (int i = 0; i < iWeeks.size(); i++) { 176 BitSet w = iWeeks.get(i); 177 if (value.getTimeLocation().shareWeeks(w)) continue; 178 int cnt = iWeekAssignments[i].size(); 179 if (iWeekAssignments[i].contains(value.variable())) cnt --; 180 for (Placement conflict: conflicts) { 181 if (conflict.variable().equals(value.variable())) continue; 182 if (iWeekAssignments[i].contains(conflict.variable())) cnt --; 183 } 184 if (cnt <= 0) continue; 185 if (bestWeeks.isEmpty() || bestCnt > cnt) { 186 bestWeeks.clear(); bestWeeks.add(i); bestCnt = cnt; 187 } else if (bestCnt == cnt) { 188 bestWeeks.add(i); 189 } 190 } 191 return bestWeeks.isEmpty() ? null : iWeekAssignments[ToolBox.random(bestWeeks)]; 192 } 193 194 public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 195 int weeks = 0; 196 for (int i = 0; i < iWeeks.size(); i++) { 197 BitSet w = iWeeks.get(i); 198 int cnt = iWeekAssignments[i].size(); 199 if (assignments != null) { 200 for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) { 201 if (isCorectDayOfWeek(entry.getValue()) && entry.getValue().getTimeLocation().shareWeeks(w)) cnt ++; 202 if (iWeekAssignments[i].contains(entry.getKey())) cnt --; 203 } 204 } 205 if (conflicts != null) 206 for (Placement conflict: conflicts) { 207 if (assignments != null && assignments.containsKey(conflict.variable())) continue; 208 if (iWeekAssignments[i].contains(conflict.variable())) cnt --; 209 } 210 if (cnt > 0) weeks ++; 211 } 212 return (weeks <= iMaxWeeks ? 0 : weeks - iMaxWeeks); 213 } 214 215 } 216}