001 package net.sf.cpsolver.studentsct.report; 002 003 import java.text.DecimalFormat; 004 import java.util.ArrayList; 005 import java.util.Comparator; 006 import java.util.HashMap; 007 import java.util.HashSet; 008 import java.util.List; 009 import java.util.Map; 010 import java.util.Set; 011 import java.util.TreeSet; 012 013 import net.sf.cpsolver.ifs.model.GlobalConstraint; 014 import net.sf.cpsolver.ifs.util.CSVFile; 015 import net.sf.cpsolver.ifs.util.DataProperties; 016 import net.sf.cpsolver.studentsct.StudentSectioningModel; 017 import net.sf.cpsolver.studentsct.constraint.SectionLimit; 018 import net.sf.cpsolver.studentsct.model.Course; 019 import net.sf.cpsolver.studentsct.model.CourseRequest; 020 import net.sf.cpsolver.studentsct.model.Enrollment; 021 import net.sf.cpsolver.studentsct.model.FreeTimeRequest; 022 import net.sf.cpsolver.studentsct.model.Request; 023 import net.sf.cpsolver.studentsct.model.Section; 024 import net.sf.cpsolver.studentsct.model.Student; 025 026 /** 027 * This class computes time and availability conflicts on classes in a {@link CSVFile} comma separated 028 * text file. <br> 029 * <br> 030 * The first report (type OVERLAPS) shows time conflicts between pairs of classes. Each such enrollment 031 * is given a weight of 1/n, where n is the number of available enrollments of the student into the course. 032 * This 1/n is added to each class that is present in a conflict. These numbers are aggregated on 033 * individual classes and on pairs of classes (that are in a time conflict). 034 * <br> 035 * The second report (type UNAVAILABILITIES) shows for each course how many students could not get into 036 * the course because of the limit constraints. It considers all the not-conflicting, but unavailable enrollments 037 * of a student into the course. For each such an enrollment 1/n is added to each class. So, in a way, the 038 * Availability Conflicts column shows how much space is missing in each class. The Class Potential column 039 * can be handy as well. If the class would be unlimited, this is the number of students (out of all the 040 * conflicting students) that can get into the class. 041 * <br> 042 * The last report (type OVERLAPS_AND_UNAVAILABILITIES) show the two reports together. It is possible that 043 * there is a course where some students cannot get in because of availabilities (all not-conflicting enrollments 044 * have no available space) as well as time conflicts (all available enrollments are conflicting with some other 045 * classes the student has). 046 * <br> 047 * <br> 048 * 049 * Usage: new SectionConflictTable(model, type),createTable(true, true).save(aFile); 050 * 051 * <br> 052 * <br> 053 * 054 * @version StudentSct 1.2 (Student Sectioning)<br> 055 * Copyright (C) 2013 Tomas Muller<br> 056 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 057 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 058 * <br> 059 * This library is free software; you can redistribute it and/or modify 060 * it under the terms of the GNU Lesser General Public License as 061 * published by the Free Software Foundation; either version 3 of the 062 * License, or (at your option) any later version. <br> 063 * <br> 064 * This library is distributed in the hope that it will be useful, but 065 * WITHOUT ANY WARRANTY; without even the implied warranty of 066 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 067 * Lesser General Public License for more details. <br> 068 * <br> 069 * You should have received a copy of the GNU Lesser General Public 070 * License along with this library; if not see 071 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 072 */ 073 public class SectionConflictTable implements StudentSectioningReport { 074 private static DecimalFormat sDF = new DecimalFormat("0.0000"); 075 076 private StudentSectioningModel iModel = null; 077 private Type iType; 078 079 /** 080 * Report type 081 */ 082 public static enum Type { 083 /** Time conflicts */ 084 OVERLAPS(true, false), 085 /** Availability conflicts */ 086 UNAVAILABILITIES(false, true), 087 /** Both time and availability conflicts */ 088 OVERLAPS_AND_UNAVAILABILITIES(true, true), 089 ; 090 091 boolean iOveralps, iUnavailabilities; 092 Type(boolean overlaps, boolean unavailabilities) { 093 iOveralps = overlaps; 094 iUnavailabilities = unavailabilities; 095 } 096 097 /** Has time conflicts */ 098 public boolean hasOverlaps() { return iOveralps; } 099 100 /** Has availability conflicts */ 101 public boolean hasUnavailabilities() { return iUnavailabilities; } 102 } 103 104 /** 105 * Constructor 106 * 107 * @param model 108 * student sectioning model 109 */ 110 public SectionConflictTable(StudentSectioningModel model, Type type) { 111 iModel = model; 112 iType = type; 113 } 114 115 public SectionConflictTable(StudentSectioningModel model) { 116 this(model, Type.OVERLAPS_AND_UNAVAILABILITIES); 117 } 118 119 /** Return student sectioning model */ 120 public StudentSectioningModel getModel() { 121 return iModel; 122 } 123 124 private boolean canIgnore(Enrollment enrollment, Section section, List<Enrollment> other) { 125 e: for (Enrollment e: other) { 126 Section a = null; 127 for (Section s: e.getSections()) { 128 if (s.getSubpart().equals(section.getSubpart())) { 129 if (s.equals(section)) continue e; 130 a = s; 131 } else if (!enrollment.getSections().contains(s)) 132 continue e; 133 } 134 if (a == null) continue e; 135 for (Request r: enrollment.getStudent().getRequests()) 136 if (!enrollment.getRequest().equals(r) && r.getAssignment() != null && r instanceof CourseRequest && !r.getAssignment().isAllowOverlap()) 137 for (Section b: r.getAssignment().getSections()) 138 if (!b.isAllowOverlap() && !b.isToIgnoreStudentConflictsWith(section.getId()) && b.getTime() != null && a.getTime() != null && !a.isAllowOverlap() && b.getTime().hasIntersection(a.getTime())) 139 continue e; 140 return true; 141 } 142 return false; 143 } 144 145 /** 146 * Create report 147 * 148 * @param includeLastLikeStudents 149 * true, if last-like students should be included (i.e., 150 * {@link Student#isDummy()} is true) 151 * @param includeRealStudents 152 * true, if real students should be included (i.e., 153 * {@link Student#isDummy()} is false) 154 * @return report as comma separated text file 155 */ 156 public CSVFile createTable(boolean includeLastLikeStudents, boolean includeRealStudents) { 157 HashMap<Course, Map<Section, Double[]>> unavailabilities = new HashMap<Course, Map<Section,Double[]>>(); 158 HashMap<Course, Set<Long>> totals = new HashMap<Course, Set<Long>>(); 159 HashMap<CourseSection, Map<CourseSection, Double>> conflictingPairs = new HashMap<CourseSection, Map<CourseSection,Double>>(); 160 HashMap<CourseSection, Double> sectionOverlaps = new HashMap<CourseSection, Double>(); 161 162 for (Request request : new ArrayList<Request>(getModel().unassignedVariables())) { 163 if (request.getStudent().isDummy() && !includeLastLikeStudents) continue; 164 if (!request.getStudent().isDummy() && !includeRealStudents) continue; 165 if (request instanceof CourseRequest) { 166 CourseRequest courseRequest = (CourseRequest) request; 167 if (courseRequest.getStudent().isComplete()) continue; 168 169 List<Enrollment> values = courseRequest.values(); 170 171 SectionLimit limitConstraint = null; 172 for (GlobalConstraint<Request, Enrollment> c: getModel().globalConstraints()) { 173 if (c instanceof SectionLimit) { 174 limitConstraint = (SectionLimit)c; 175 break; 176 } 177 } 178 if (limitConstraint == null) { 179 limitConstraint = new SectionLimit(new DataProperties()); 180 limitConstraint.setModel(getModel()); 181 } 182 List<Enrollment> notAvailableValues = new ArrayList<Enrollment>(values.size()); 183 List<Enrollment> availableValues = new ArrayList<Enrollment>(values.size()); 184 for (Enrollment enrollment : values) { 185 if (limitConstraint.inConflict(enrollment)) 186 notAvailableValues.add(enrollment); 187 else 188 availableValues.add(enrollment); 189 } 190 191 if (!notAvailableValues.isEmpty() && iType.hasUnavailabilities()) { 192 List<Enrollment> notOverlappingEnrollments = new ArrayList<Enrollment>(values.size()); 193 enrollments: for (Enrollment enrollment: notAvailableValues) { 194 for (Request other : request.getStudent().getRequests()) { 195 if (other.equals(request) || other.getAssignment() == null || other instanceof FreeTimeRequest) continue; 196 if (other.getAssignment().isOverlapping(enrollment)) continue enrollments; 197 } 198 // not overlapping 199 notOverlappingEnrollments.add(enrollment); 200 } 201 202 if (notOverlappingEnrollments.isEmpty()) continue; 203 204 double fraction = request.getWeight() / notOverlappingEnrollments.size(); 205 Set<CourseSection> ones = new HashSet<CourseSection>(); 206 for (Enrollment enrollment: notOverlappingEnrollments) { 207 boolean hasConflict = false; 208 for (Section s: enrollment.getSections()) { 209 if (s.getLimit() >= 0 && s.getEnrollmentWeight(request) + request.getWeight() > s.getLimit()) { 210 hasConflict = true; 211 break; 212 } 213 } 214 215 Map<Section, Double[]> sections = unavailabilities.get(enrollment.getCourse()); 216 if (sections == null) { 217 sections = new HashMap<Section, Double[]>(); 218 unavailabilities.put(enrollment.getCourse(), sections); 219 } 220 for (Section s: enrollment.getSections()) { 221 if (hasConflict && s.getLimit() < 0 || s.getEnrollmentWeight(request) + request.getWeight() <= s.getLimit()) continue; 222 Double[] total = sections.get(s); 223 sections.put(s, new Double[] { 224 fraction + (total == null ? 0.0 : total[0].doubleValue()), 225 (total == null ? 0.0 : total[1].doubleValue()) 226 }); 227 ones.add(new CourseSection(enrollment.getCourse(), s)); 228 } 229 Set<Long> total = totals.get(enrollment.getCourse()); 230 if (total == null) { 231 total = new HashSet<Long>(); 232 totals.put(enrollment.getCourse(), total); 233 } 234 total.add(enrollment.getStudent().getId()); 235 } 236 for (CourseSection section: ones) { 237 Map<Section, Double[]> sections = unavailabilities.get(section.getCourse()); 238 Double[] total = sections.get(section.getSection()); 239 sections.put(section.getSection(), new Double[] { 240 (total == null ? 0.0 : total[0].doubleValue()), 241 request.getWeight() + (total == null ? 0.0 : total[1].doubleValue()) 242 }); 243 } 244 } 245 246 if (!availableValues.isEmpty() && iType.hasOverlaps()) { 247 List<Map<CourseSection, List<CourseSection>>> conflicts = new ArrayList<Map<CourseSection, List<CourseSection>>>(); 248 for (Enrollment enrollment: availableValues) { 249 Map<CourseSection, List<CourseSection>> overlaps = new HashMap<CourseSection, List<CourseSection>>(); 250 for (Request other : request.getStudent().getRequests()) { 251 if (other.equals(request) || other.getAssignment() == null || other instanceof FreeTimeRequest) continue; 252 Enrollment otherEnrollment = other.getAssignment(); 253 if (enrollment.isOverlapping(otherEnrollment)) 254 for (Section a: enrollment.getSections()) 255 for (Section b: other.getAssignment().getSections()) 256 if (a.getTime() != null && b.getTime() != null && !a.isAllowOverlap() && !b.isAllowOverlap() && !a.isToIgnoreStudentConflictsWith(b.getId()) && a.getTime().hasIntersection(b.getTime()) && !canIgnore(enrollment, a, availableValues)) { 257 List<CourseSection> x = overlaps.get(new CourseSection(enrollment.getCourse(), a)); 258 if (x == null) { x = new ArrayList<CourseSection>(); overlaps.put(new CourseSection(enrollment.getCourse(), a), x); } 259 x.add(new CourseSection(other.getAssignment().getCourse(), b)); 260 } 261 } 262 if (!overlaps.isEmpty()) { 263 conflicts.add(overlaps); 264 Set<Long> total = totals.get(enrollment.getCourse()); 265 if (total == null) { 266 total = new HashSet<Long>(); 267 totals.put(enrollment.getCourse(), total); 268 } 269 total.add(enrollment.getStudent().getId()); 270 } 271 } 272 273 double fraction = request.getWeight() / conflicts.size(); 274 for (Map<CourseSection, List<CourseSection>> overlaps: conflicts) { 275 for (Map.Entry<CourseSection, List<CourseSection>> entry: overlaps.entrySet()) { 276 CourseSection a = entry.getKey(); 277 Double total = sectionOverlaps.get(a); 278 sectionOverlaps.put(a, fraction + (total == null ? 0.0 : total.doubleValue())); 279 Map<CourseSection, Double> pair = conflictingPairs.get(a); 280 if (pair == null) { 281 pair = new HashMap<CourseSection, Double>(); 282 conflictingPairs.put(a, pair); 283 } 284 for (CourseSection b: entry.getValue()) { 285 Double prev = pair.get(b); 286 pair.put(b, fraction + (prev == null ? 0.0 : prev.doubleValue())); 287 } 288 } 289 } 290 } 291 } 292 } 293 Comparator<Course> courseComparator = new Comparator<Course>() { 294 @Override 295 public int compare(Course a, Course b) { 296 int cmp = a.getName().compareTo(b.getName()); 297 if (cmp != 0) return cmp; 298 return a.getId() < b.getId() ? -1 : a.getId() == b.getId() ? 0 : 1; 299 } 300 }; 301 Comparator<Section> sectionComparator = new Comparator<Section>() { 302 @Override 303 public int compare(Section a, Section b) { 304 int cmp = a.getSubpart().getConfig().getOffering().getName().compareTo(b.getSubpart().getConfig().getOffering().getName()); 305 if (cmp != 0) return cmp; 306 cmp = a.getSubpart().getInstructionalType().compareTo(b.getSubpart().getInstructionalType()); 307 // if (cmp != 0) return cmp; 308 // cmp = a.getName().compareTo(b.getName()); 309 if (cmp != 0) return cmp; 310 return a.getId() < b.getId() ? -1 : a.getId() == b.getId() ? 0 : 1; 311 } 312 }; 313 314 CSVFile csv = new CSVFile(); 315 List<CSVFile.CSVField> headers = new ArrayList<CSVFile.CSVField>(); 316 headers.add(new CSVFile.CSVField("Course")); 317 headers.add(new CSVFile.CSVField("Total\nConflicts")); 318 if (iType.hasUnavailabilities()) { 319 headers.add(new CSVFile.CSVField("Course\nEnrollment")); 320 headers.add(new CSVFile.CSVField("Course\nLimit")); 321 } 322 headers.add(new CSVFile.CSVField("Class")); 323 headers.add(new CSVFile.CSVField("Meeting Time")); 324 if (iType.hasUnavailabilities()) { 325 headers.add(new CSVFile.CSVField("Availability\nConflicts")); 326 headers.add(new CSVFile.CSVField("% of Total\nConflicts")); 327 } 328 if (iType.hasOverlaps()) { 329 headers.add(new CSVFile.CSVField("Time\nConflicts")); 330 headers.add(new CSVFile.CSVField("% of Total\nConflicts")); 331 } 332 if (iType.hasUnavailabilities()) { 333 headers.add(new CSVFile.CSVField("Class\nEnrollment")); 334 headers.add(new CSVFile.CSVField("Class\nLimit")); 335 if (!iType.hasOverlaps()) 336 headers.add(new CSVFile.CSVField("Class\nPotential")); 337 } 338 if (iType.hasOverlaps()) { 339 headers.add(new CSVFile.CSVField("Conflicting\nClass")); 340 headers.add(new CSVFile.CSVField("Conflicting\nMeeting Time")); 341 headers.add(new CSVFile.CSVField("Joined\nConflicts")); 342 headers.add(new CSVFile.CSVField("% of Total\nConflicts")); 343 } 344 csv.setHeader(headers); 345 346 TreeSet<Course> courses = new TreeSet<Course>(courseComparator); 347 courses.addAll(totals.keySet()); 348 349 for (Course course: courses) { 350 Map<Section, Double[]> sectionUnavailability = unavailabilities.get(course); 351 Set<Long> total = totals.get(course); 352 353 TreeSet<Section> sections = new TreeSet<Section>(sectionComparator); 354 if (sectionUnavailability != null) 355 sections.addAll(sectionUnavailability.keySet()); 356 for (Map.Entry<CourseSection, Double> entry: sectionOverlaps.entrySet()) 357 if (course.equals(entry.getKey().getCourse())) 358 sections.add(entry.getKey().getSection()); 359 360 boolean firstCourse = true; 361 for (Section section: sections) { 362 Double[] sectionUnavailable = (sectionUnavailability == null ? null : sectionUnavailability.get(section)); 363 Double sectionOverlap = sectionOverlaps.get(new CourseSection(course, section)); 364 Map<CourseSection, Double> pair = conflictingPairs.get(new CourseSection(course, section)); 365 366 if (pair == null) { 367 List<CSVFile.CSVField> line = new ArrayList<CSVFile.CSVField>(); 368 line.add(new CSVFile.CSVField(firstCourse ? course.getName() : "")); 369 line.add(new CSVFile.CSVField(firstCourse ? total.size() : "")); 370 if (iType.hasUnavailabilities()) { 371 line.add(new CSVFile.CSVField(firstCourse ? sDF.format(course.getEnrollmentWeight(null)) : "")); 372 line.add(new CSVFile.CSVField(firstCourse ? course.getLimit() < 0 ? "-" : String.valueOf(course.getLimit()) : "")); 373 } 374 375 line.add(new CSVFile.CSVField(section.getSubpart().getName() + " " + section.getName(course.getId()))); 376 line.add(new CSVFile.CSVField(section.getTime() == null ? "" : section.getTime().getDayHeader() + " " + section.getTime().getStartTimeHeader() + " - " + section.getTime().getEndTimeHeader())); 377 378 if (iType.hasUnavailabilities()) { 379 line.add(new CSVFile.CSVField(sectionUnavailable != null ? sDF.format(sectionUnavailable[0]) : "")); 380 line.add(new CSVFile.CSVField(sectionUnavailable != null ? sDF.format(sectionUnavailable[0] / total.size()) : "")); 381 } 382 if (iType.hasOverlaps()) { 383 line.add(new CSVFile.CSVField(sectionOverlap != null ? sDF.format(sectionOverlap) : "")); 384 line.add(new CSVFile.CSVField(sectionOverlap != null ? sDF.format(sectionOverlap / total.size()) : "")); 385 } 386 if (iType.hasUnavailabilities()) { 387 line.add(new CSVFile.CSVField(sDF.format(section.getEnrollmentWeight(null)))); 388 line.add(new CSVFile.CSVField(section.getLimit() < 0 ? "-" : String.valueOf(section.getLimit()))); 389 if (!iType.hasOverlaps()) 390 line.add(new CSVFile.CSVField(sectionUnavailable != null ? sDF.format(sectionUnavailable[1]) : "")); 391 } 392 393 csv.addLine(line); 394 } else { 395 boolean firstClass = true; 396 for (CourseSection other: new TreeSet<CourseSection>(pair.keySet())) { 397 List<CSVFile.CSVField> line = new ArrayList<CSVFile.CSVField>(); 398 line.add(new CSVFile.CSVField(firstCourse && firstClass ? course.getName() : "")); 399 line.add(new CSVFile.CSVField(firstCourse && firstClass ? total.size() : "")); 400 if (iType.hasUnavailabilities()) { 401 line.add(new CSVFile.CSVField(firstCourse && firstClass ? sDF.format(course.getEnrollmentWeight(null)) : "")); 402 line.add(new CSVFile.CSVField(firstCourse && firstClass ? course.getLimit() < 0 ? "-" : String.valueOf(course.getLimit()) : "")); 403 } 404 405 line.add(new CSVFile.CSVField(firstClass ? section.getSubpart().getName() + " " + section.getName(course.getId()): "")); 406 line.add(new CSVFile.CSVField(firstClass ? section.getTime() == null ? "" : section.getTime().getDayHeader() + " " + section.getTime().getStartTimeHeader() + " - " + section.getTime().getEndTimeHeader(): "")); 407 408 if (iType.hasUnavailabilities()) { 409 line.add(new CSVFile.CSVField(firstClass && sectionUnavailable != null ? sDF.format(sectionUnavailable[0]): "")); 410 line.add(new CSVFile.CSVField(sectionUnavailable != null ? sDF.format(sectionUnavailable[0] / total.size()) : "")); 411 } 412 line.add(new CSVFile.CSVField(firstClass && sectionOverlap != null ? sDF.format(sectionOverlap): "")); 413 line.add(new CSVFile.CSVField(firstClass && sectionOverlap != null ? sDF.format(sectionOverlap / total.size()) : "")); 414 if (iType.hasUnavailabilities()) { 415 line.add(new CSVFile.CSVField(firstClass ? sDF.format(section.getEnrollmentWeight(null)): "")); 416 line.add(new CSVFile.CSVField(firstClass ? section.getLimit() < 0 ? "-" : String.valueOf(section.getLimit()): "")); 417 } 418 419 line.add(new CSVFile.CSVField(other.getCourse().getName() + " " + other.getSection().getSubpart().getName() + " " + other.getSection().getName(other.getCourse().getId()))); 420 line.add(new CSVFile.CSVField(other.getSection().getTime().getDayHeader() + " " + other.getSection().getTime().getStartTimeHeader() + " - " + other.getSection().getTime().getEndTimeHeader())); 421 line.add(new CSVFile.CSVField(sDF.format(pair.get(other)))); 422 line.add(new CSVFile.CSVField(sDF.format(pair.get(other) / total.size()))); 423 424 csv.addLine(line); 425 firstClass = false; 426 } 427 } 428 429 firstCourse = false; 430 } 431 432 csv.addLine(); 433 } 434 return csv; 435 } 436 437 @Override 438 public CSVFile create(DataProperties properties) { 439 iType = Type.valueOf(properties.getProperty("type", iType.name())); 440 return createTable(properties.getPropertyBoolean("lastlike", false), properties.getPropertyBoolean("real", true)); 441 } 442 }