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