001package org.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.HashMap; 005import java.util.HashSet; 006import java.util.List; 007import java.util.Map; 008import java.util.Set; 009import java.util.regex.Matcher; 010import java.util.regex.Pattern; 011 012import org.cpsolver.coursett.Constants; 013import org.cpsolver.coursett.criteria.FlexibleConstraintCriterion; 014import org.cpsolver.coursett.model.Lecture; 015import org.cpsolver.coursett.model.Placement; 016import org.cpsolver.ifs.assignment.Assignment; 017import org.cpsolver.ifs.criteria.Criterion; 018import org.cpsolver.ifs.util.ToolBox; 019 020/** 021 * 022 * The MaxDays constraint limits the number of days of week during which the given set of classes are taught.<br> 023 * It has one parameter: a maximal number of week days during which the given set of classes can be placed.<br> 024 * Reference _MaxDays:2_ translates to a maximum number of 2 days a week<br> 025 * 026 * @version CourseTT 1.3 (University Course Timetabling)<br> 027 * Copyright (C) 2015 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 MaxDaysFlexibleConstraint extends FlexibleConstraint { 044 private int iMaxDays; 045 046 public MaxDaysFlexibleConstraint(Long id, String owner, String preference, String reference) { 047 super(id, owner, preference, reference); 048 049 Matcher matcher = Pattern.compile(FlexibleConstraintType.MAX_DAYS.getPattern()).matcher(reference); 050 if (matcher.find()) { 051 iMaxDays = Integer.parseInt(matcher.group(2)); 052 iConstraintType = FlexibleConstraintType.MAX_DAYS; 053 } 054 } 055 056 @Override 057 public double getNrViolations(Assignment<Lecture, Placement> assignment, Set<Placement> conflicts, HashMap<Lecture, Placement> assignments) { 058 return ((MaxDaysFlexibleConstraintContext)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 MaxDaysFlexibleConstraintContext context = (MaxDaysFlexibleConstraintContext)getContext(assignment); 066 while (context.nrDays(value, conflicts) > iMaxDays) { 067 Set<Lecture> candidates = context.candidates(value, conflicts); 068 if (candidates == null) return; 069 for (Lecture candidate: candidates) { 070 Placement conflict = assignment.getValue(candidate); 071 if (conflict != null) 072 conflicts.add(conflict); 073 } 074 } 075 } 076 077 @Override 078 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement value) { 079 if (!isHard()) return false; 080 return ((MaxDaysFlexibleConstraintContext)getContext(assignment)).nrDays(value, null) > iMaxDays; 081 } 082 083 @Override 084 public FlexibleConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 085 return new MaxDaysFlexibleConstraintContext(assignment); 086 } 087 088 public class MaxDaysFlexibleConstraintContext extends FlexibleConstraintContext { 089 private Set<Lecture> iDayAssignments[] = null; 090 091 @SuppressWarnings("unchecked") 092 public MaxDaysFlexibleConstraintContext(Assignment<Lecture, Placement> assignment) { 093 super(); 094 iDayAssignments = new Set[Constants.NR_DAYS]; 095 for (int i = 0; i < iDayAssignments.length; i++) 096 iDayAssignments[i] = new HashSet<Lecture>(); 097 098 for (Lecture variable: variables()) { 099 Placement value = assignment.getValue(variable); 100 if (value != null) { 101 for (int i = 0; i < iDayAssignments.length; i++) 102 if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) 103 iDayAssignments[i].add(value.variable()); 104 } 105 } 106 107 if (!isHard()) { 108 Criterion<Lecture, Placement> criterion = getModel().getCriterion(FlexibleConstraintCriterion.class); 109 if (criterion != null) { 110 double pref = nrViolations(null, null); 111 if (pref == 0) 112 iLastPreference = -Math.abs(iPreference); 113 else 114 iLastPreference = Math.abs(iPreference) * pref; 115 criterion.inc(assignment, iLastPreference); 116 } 117 } 118 } 119 120 @Override 121 public void assigned(Assignment<Lecture, Placement> assignment, Placement value) { 122 for (int i = 0; i < iDayAssignments.length; i++) 123 if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) 124 iDayAssignments[i].add(value.variable()); 125 updateCriterion(assignment); 126 } 127 128 @Override 129 public void unassigned(Assignment<Lecture, Placement> assignment, Placement value) { 130 for (int i = 0; i < iDayAssignments.length; i++) 131 if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) 132 iDayAssignments[i].remove(value.variable()); 133 updateCriterion(assignment); 134 } 135 136 public int nrDays(Placement value, Set<Placement> conflicts) { 137 int ret = 0; 138 for (int i = 0; i < iDayAssignments.length; i++) { 139 int cnt = iDayAssignments[i].size(); 140 if (value != null) { 141 if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) cnt ++; 142 if (iDayAssignments[i].contains(value.variable())) cnt --; 143 } 144 if (conflicts != null) { 145 for (Placement conflict: conflicts) { 146 if (value != null && conflict.variable().equals(value.variable())) continue; 147 if (iDayAssignments[i].contains(conflict.variable())) cnt --; 148 } 149 } 150 if (cnt > 0) ret++; 151 } 152 return ret; 153 } 154 155 public Set<Lecture> candidates(Placement value, Set<Placement> conflicts) { 156 int bestCnt = 0; 157 List<Integer> bestWeeks = new ArrayList<Integer>(); 158 for (int i = 0; i < iDayAssignments.length; i++) { 159 if ((value.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) continue; 160 int cnt = iDayAssignments[i].size(); 161 if (iDayAssignments[i].contains(value.variable())) cnt --; 162 for (Placement conflict: conflicts) { 163 if (conflict.variable().equals(value.variable())) continue; 164 if (iDayAssignments[i].contains(conflict.variable())) cnt --; 165 } 166 if (cnt <= 0) continue; 167 if (bestWeeks.isEmpty() || bestCnt > cnt) { 168 bestWeeks.clear(); bestWeeks.add(i); bestCnt = cnt; 169 } else if (bestCnt == cnt) { 170 bestWeeks.add(i); 171 } 172 } 173 return bestWeeks.isEmpty() ? null : iDayAssignments[ToolBox.random(bestWeeks)]; 174 } 175 176 public int nrViolations(HashMap<Lecture, Placement> assignments, Set<Placement> conflicts) { 177 int days = 0; 178 for (int i = 0; i < iDayAssignments.length; i++) { 179 int cnt = iDayAssignments[i].size(); 180 if (assignments != null) { 181 for (Map.Entry<Lecture, Placement> entry: assignments.entrySet()) { 182 Placement assignment = entry.getValue(); 183 if (assignment != null && (assignment.getTimeLocation().getDayCode() & Constants.DAY_CODES[i]) != 0) cnt ++; 184 } 185 } 186 if (conflicts != null) 187 for (Placement conflict: conflicts) { 188 if (assignments != null && assignments.containsKey(conflict.variable())) continue; 189 if (iDayAssignments[i].contains(conflict.variable())) cnt --; 190 } 191 if (cnt > 0) days ++; 192 } 193 return (days <= iMaxDays ? 0 : days - iMaxDays); 194 } 195 196 } 197}