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