001package net.sf.cpsolver.studentsct.report; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.Collections; 006import java.util.Comparator; 007import java.util.HashSet; 008import java.util.HashMap; 009import java.util.Iterator; 010import java.util.List; 011import java.util.Map; 012import java.util.Set; 013import java.util.TreeSet; 014 015import net.sf.cpsolver.ifs.model.GlobalConstraint; 016import net.sf.cpsolver.ifs.util.CSVFile; 017import net.sf.cpsolver.ifs.util.DataProperties; 018import net.sf.cpsolver.studentsct.StudentSectioningModel; 019import net.sf.cpsolver.studentsct.constraint.ConfigLimit; 020import net.sf.cpsolver.studentsct.constraint.CourseLimit; 021import net.sf.cpsolver.studentsct.constraint.SectionLimit; 022import net.sf.cpsolver.studentsct.model.Course; 023import net.sf.cpsolver.studentsct.model.CourseRequest; 024import net.sf.cpsolver.studentsct.model.Enrollment; 025import net.sf.cpsolver.studentsct.model.Request; 026import net.sf.cpsolver.studentsct.model.Section; 027import net.sf.cpsolver.studentsct.model.Student; 028 029/** 030 * This class lists conflicting courses in a {@link CSVFile} comma separated 031 * text file. <br> 032 * <br> 033 * 034 * Each line represent a course that has some unassigned course requests (column 035 * UnasgnCrs), course that was conflicting with that course (column ConflCrs), 036 * and number of students with that conflict. So, for instance if there was a 037 * student which cannot attend course A with weight 1.5 (e.g., 10 last-like 038 * students projected to 15), and when A had two possible assignments for that 039 * student, one conflicting with C (assigned to that student) and the other with 040 * D, then 0.75 (1.5/2) was added to rows A, B and A, C. The column NoAlt is Y 041 * when every possible enrollment of the first course is overlapping with every 042 * possible enrollment of the second course (it is N otherwise) and a column 043 * Reason which lists the overlapping sections. 044 * 045 * <br> 046 * <br> 047 * 048 * Usage: new CourseConflictTable(model),createTable(true, true).save(aFile); 049 * 050 * <br> 051 * <br> 052 * 053 * @version StudentSct 1.2 (Student Sectioning)<br> 054 * Copyright (C) 2007 - 2010 Tomáš Müller<br> 055 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 056 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 057 * <br> 058 * This library is free software; you can redistribute it and/or modify 059 * it under the terms of the GNU Lesser General Public License as 060 * published by the Free Software Foundation; either version 3 of the 061 * License, or (at your option) any later version. <br> 062 * <br> 063 * This library is distributed in the hope that it will be useful, but 064 * WITHOUT ANY WARRANTY; without even the implied warranty of 065 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 066 * Lesser General Public License for more details. <br> 067 * <br> 068 * You should have received a copy of the GNU Lesser General Public 069 * License along with this library; if not see 070 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 071 */ 072 073public class CourseConflictTable implements StudentSectioningReport { 074 private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(CourseConflictTable.class); 075 private static DecimalFormat sDF = new DecimalFormat("0.000"); 076 077 private StudentSectioningModel iModel = null; 078 079 /** 080 * Constructor 081 * 082 * @param model 083 * student sectioning model 084 */ 085 public CourseConflictTable(StudentSectioningModel model) { 086 iModel = model; 087 } 088 089 /** Return student sectioning model */ 090 public StudentSectioningModel getModel() { 091 return iModel; 092 } 093 094 /** 095 * True, if there is no pair of enrollments of r1 and r2 that is not in a 096 * hard conflict 097 */ 098 private boolean areInHardConfict(Request r1, Request r2) { 099 for (Enrollment e1 : r1.values()) { 100 for (Enrollment e2 : r2.values()) { 101 if (!e1.isOverlapping(e2)) 102 return false; 103 } 104 } 105 return true; 106 } 107 108 /** 109 * Return a set of explanations (Strings) for conflicts between the given 110 * enrollments 111 * 112 * @param enrl 113 * an enrollment 114 * @param conflict 115 * an enrollment conflicting with enrl 116 * @return a set of explanations, (e.g., AB 101 Lec 1 MWF 7:30 - 8:20 vs AB 117 * 201 Lec 1 F 7:30 - 9:20) 118 */ 119 private Set<String> explanations(Enrollment enrl, Enrollment conflict) { 120 Set<String> expl = new HashSet<String>(); 121 for (Section s1 : enrl.getSections()) { 122 for (Section s2 : conflict.getSections()) { 123 if (s1.isOverlapping(s2)) 124 expl.add(s1.getSubpart().getName() + " " + s1.getTime().getLongName() + " vs " 125 + s2.getSubpart().getName() + " " + s2.getTime().getLongName()); 126 } 127 } 128 for (Section s1 : enrl.getSections()) { 129 if (conflict.getAssignments().contains(s1) 130 && SectionLimit.getEnrollmentWeight(s1, enrl.getRequest()) > s1.getLimit()) { 131 expl.add(s1.getSubpart().getName() + " n/a"); 132 } 133 } 134 if (enrl.getConfig() != null && enrl.getConfig().equals(conflict.getConfig())) { 135 if (ConfigLimit.getEnrollmentWeight(enrl.getConfig(), enrl.getRequest()) > enrl.getConfig().getLimit()) { 136 expl.add(enrl.getConfig().getName() + " n/a"); 137 } 138 } 139 if (enrl.getCourse() != null && enrl.getCourse().equals(conflict.getCourse())) { 140 if (CourseLimit.getEnrollmentWeight(enrl.getCourse(), enrl.getRequest()) > enrl.getCourse().getLimit()) { 141 expl.add(enrl.getCourse().getName() + " n/a"); 142 } 143 } 144 return expl; 145 } 146 147 /** 148 * Create report 149 * 150 * @param includeLastLikeStudents 151 * true, if last-like students should be included (i.e., 152 * {@link Student#isDummy()} is true) 153 * @param includeRealStudents 154 * true, if real students should be included (i.e., 155 * {@link Student#isDummy()} is false) 156 * @return report as comma separated text file 157 */ 158 @SuppressWarnings("unchecked") 159 public CSVFile createTable(boolean includeLastLikeStudents, boolean includeRealStudents) { 160 CSVFile csv = new CSVFile(); 161 csv.setHeader(new CSVFile.CSVField[] { new CSVFile.CSVField("UnasgnCrs"), new CSVFile.CSVField("ConflCrs"), 162 new CSVFile.CSVField("NrStud"), new CSVFile.CSVField("StudWeight"), new CSVFile.CSVField("NoAlt"), 163 new CSVFile.CSVField("Reason") }); 164 HashMap<Course, HashMap<Course, Object[]>> unassignedCourseTable = new HashMap<Course, HashMap<Course, Object[]>>(); 165 for (Request request : new ArrayList<Request>(getModel().unassignedVariables())) { 166 if (request.getStudent().isDummy() && !includeLastLikeStudents) 167 continue; 168 if (!request.getStudent().isDummy() && !includeRealStudents) 169 continue; 170 if (request instanceof CourseRequest) { 171 CourseRequest courseRequest = (CourseRequest) request; 172 if (courseRequest.getStudent().isComplete()) 173 continue; 174 175 List<Enrollment> values = courseRequest.values(); 176 SectionLimit limitConstraint = null; 177 for (GlobalConstraint<Request, Enrollment> c: getModel().globalConstraints()) { 178 if (c instanceof SectionLimit) { 179 limitConstraint = (SectionLimit)c; 180 break; 181 } 182 } 183 if (limitConstraint == null) { 184 limitConstraint = new SectionLimit(new DataProperties()); 185 limitConstraint.setModel(getModel()); 186 } 187 List<Enrollment> availableValues = new ArrayList<Enrollment>(values.size()); 188 for (Enrollment enrollment : values) { 189 if (!limitConstraint.inConflict(enrollment)) 190 availableValues.add(enrollment); 191 } 192 193 if (availableValues.isEmpty()) { 194 Course course = courseRequest.getCourses().get(0); 195 HashMap<Course, Object[]> conflictCourseTable = unassignedCourseTable.get(course); 196 if (conflictCourseTable == null) { 197 conflictCourseTable = new HashMap<Course, Object[]>(); 198 unassignedCourseTable.put(course, conflictCourseTable); 199 } 200 Object[] weight = conflictCourseTable.get(course); 201 double nrStud = (weight == null ? 0.0 : ((Double) weight[0]).doubleValue()) + 1.0; 202 double nrStudW = (weight == null ? 0.0 : ((Double) weight[1]).doubleValue()) + request.getWeight(); 203 boolean noAlt = (weight == null ? true : ((Boolean) weight[2]).booleanValue()); 204 HashSet<String> expl = (weight == null ? new HashSet<String>() : (HashSet<String>) weight[3]); 205 expl.add(course.getName() + " n/a"); 206 conflictCourseTable.put(course, new Object[] { new Double(nrStud), new Double(nrStudW), 207 new Boolean(noAlt), expl }); 208 } 209 210 for (Enrollment enrollment : availableValues) { 211 Set<Enrollment> conflicts = getModel().conflictValues(enrollment); 212 if (conflicts.isEmpty()) { 213 sLog.warn("Request " + courseRequest + " of student " + courseRequest.getStudent() 214 + " not assigned, however, no conflicts were returned."); 215 courseRequest.assign(0, enrollment); 216 break; 217 } 218 Course course = null; 219 for (Course c : courseRequest.getCourses()) { 220 if (c.getOffering().equals(enrollment.getConfig().getOffering())) { 221 course = c; 222 break; 223 } 224 } 225 if (course == null) { 226 sLog.warn("Course not found for request " + courseRequest + " of student " 227 + courseRequest.getStudent() + "."); 228 continue; 229 } 230 HashMap<Course, Object[]> conflictCourseTable = unassignedCourseTable.get(course); 231 if (conflictCourseTable == null) { 232 conflictCourseTable = new HashMap<Course, Object[]>(); 233 unassignedCourseTable.put(course, conflictCourseTable); 234 } 235 for (Enrollment conflict : conflicts) { 236 if (conflict.variable() instanceof CourseRequest) { 237 CourseRequest conflictCourseRequest = (CourseRequest) conflict.variable(); 238 Course conflictCourse = null; 239 for (Course c : conflictCourseRequest.getCourses()) { 240 if (c.getOffering().equals(conflict.getConfig().getOffering())) { 241 conflictCourse = c; 242 break; 243 } 244 } 245 if (conflictCourse == null) { 246 sLog.warn("Course not found for request " + conflictCourseRequest + " of student " 247 + conflictCourseRequest.getStudent() + "."); 248 continue; 249 } 250 double weightThisConflict = request.getWeight() / availableValues.size() / conflicts.size(); 251 double partThisConflict = 1.0 / availableValues.size() / conflicts.size(); 252 Object[] weight = conflictCourseTable.get(conflictCourse); 253 double nrStud = (weight == null ? 0.0 : ((Double) weight[0]).doubleValue()) 254 + partThisConflict; 255 double nrStudW = (weight == null ? 0.0 : ((Double) weight[1]).doubleValue()) 256 + weightThisConflict; 257 boolean noAlt = (weight == null ? areInHardConfict(request, conflict.getRequest()) 258 : ((Boolean) weight[2]).booleanValue()); 259 HashSet<String> expl = (weight == null ? new HashSet<String>() 260 : (HashSet<String>) weight[3]); 261 expl.addAll(explanations(enrollment, conflict)); 262 conflictCourseTable.put(conflictCourse, new Object[] { new Double(nrStud), 263 new Double(nrStudW), new Boolean(noAlt), expl }); 264 } 265 } 266 } 267 } 268 } 269 for (Map.Entry<Course, HashMap<Course, Object[]>> entry : unassignedCourseTable.entrySet()) { 270 Course unassignedCourse = entry.getKey(); 271 HashMap<Course, Object[]> conflictCourseTable = entry.getValue(); 272 for (Map.Entry<Course, Object[]> entry2 : conflictCourseTable.entrySet()) { 273 Course conflictCourse = entry2.getKey(); 274 Object[] weight = entry2.getValue(); 275 HashSet<String> expl = (HashSet<String>) weight[3]; 276 String explStr = ""; 277 for (Iterator<String> k = new TreeSet<String>(expl).iterator(); k.hasNext();) 278 explStr += k.next() + (k.hasNext() ? "\n" : ""); 279 csv.addLine(new CSVFile.CSVField[] { new CSVFile.CSVField(unassignedCourse.getName()), 280 new CSVFile.CSVField(conflictCourse.getName()), new CSVFile.CSVField(sDF.format(weight[0])), 281 new CSVFile.CSVField(sDF.format(weight[1])), 282 new CSVFile.CSVField(((Boolean) weight[2]).booleanValue() ? "Y" : "N"), 283 new CSVFile.CSVField(explStr) }); 284 } 285 } 286 if (csv.getLines() != null) 287 Collections.sort(csv.getLines(), new Comparator<CSVFile.CSVLine>() { 288 @Override 289 public int compare(CSVFile.CSVLine l1, CSVFile.CSVLine l2) { 290 // int cmp = 291 // l2.getField(3).toString().compareTo(l1.getField(3).toString()); 292 // if (cmp!=0) return cmp; 293 int cmp = Double.compare(l2.getField(2).toDouble(), l1.getField(2).toDouble()); 294 if (cmp != 0) 295 return cmp; 296 cmp = l1.getField(0).toString().compareTo(l2.getField(0).toString()); 297 if (cmp != 0) 298 return cmp; 299 return l1.getField(1).toString().compareTo(l2.getField(1).toString()); 300 } 301 }); 302 return csv; 303 } 304 305 @Override 306 public CSVFile create(DataProperties properties) { 307 return createTable(properties.getPropertyBoolean("lastlike", false), properties.getPropertyBoolean("real", true)); 308 } 309}