001package net.sf.cpsolver.studentsct.report; 002 003import java.text.DecimalFormat; 004import java.util.ArrayList; 005import java.util.Comparator; 006import java.util.HashMap; 007import java.util.HashSet; 008import java.util.List; 009import java.util.Map; 010import java.util.Set; 011import java.util.TreeSet; 012 013import net.sf.cpsolver.ifs.model.GlobalConstraint; 014import net.sf.cpsolver.ifs.util.CSVFile; 015import net.sf.cpsolver.ifs.util.DataProperties; 016import net.sf.cpsolver.studentsct.StudentSectioningModel; 017import net.sf.cpsolver.studentsct.constraint.SectionLimit; 018import net.sf.cpsolver.studentsct.model.Course; 019import net.sf.cpsolver.studentsct.model.CourseRequest; 020import net.sf.cpsolver.studentsct.model.Enrollment; 021import net.sf.cpsolver.studentsct.model.FreeTimeRequest; 022import net.sf.cpsolver.studentsct.model.Request; 023import net.sf.cpsolver.studentsct.model.Section; 024import 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 Tomáš Müller<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 */ 073public class SectionConflictTable implements StudentSectioningReport { 074 private static DecimalFormat sDF1 = new DecimalFormat("0.####"); 075 private static DecimalFormat sDF2 = new DecimalFormat("0.0000"); 076 077 private StudentSectioningModel iModel = null; 078 private Type iType; 079 private boolean iOverlapsAllEnrollments = true; 080 081 /** 082 * Report type 083 */ 084 public static enum Type { 085 /** Time conflicts */ 086 OVERLAPS(true, false), 087 /** Availability conflicts */ 088 UNAVAILABILITIES(false, true), 089 /** Both time and availability conflicts */ 090 OVERLAPS_AND_UNAVAILABILITIES(true, true), 091 ; 092 093 boolean iOveralps, iUnavailabilities; 094 Type(boolean overlaps, boolean unavailabilities) { 095 iOveralps = overlaps; 096 iUnavailabilities = unavailabilities; 097 } 098 099 /** Has time conflicts */ 100 public boolean hasOverlaps() { return iOveralps; } 101 102 /** Has availability conflicts */ 103 public boolean hasUnavailabilities() { return iUnavailabilities; } 104 } 105 106 /** 107 * Constructor 108 * 109 * @param model 110 * student sectioning model 111 */ 112 public SectionConflictTable(StudentSectioningModel model, Type type) { 113 iModel = model; 114 iType = type; 115 } 116 117 public SectionConflictTable(StudentSectioningModel model) { 118 this(model, Type.OVERLAPS_AND_UNAVAILABILITIES); 119 } 120 121 /** Return student sectioning model */ 122 public StudentSectioningModel getModel() { 123 return iModel; 124 } 125 126 private boolean canIgnore(Enrollment enrollment, Section section, List<Enrollment> other) { 127 e: for (Enrollment e: other) { 128 Section a = null; 129 for (Section s: e.getSections()) { 130 if (s.getSubpart().equals(section.getSubpart())) { 131 if (s.equals(section)) continue e; 132 a = s; 133 } else if (!enrollment.getSections().contains(s)) 134 continue e; 135 } 136 if (a == null) continue e; 137 for (Request r: enrollment.getStudent().getRequests()) 138 if (!enrollment.getRequest().equals(r) && r.getAssignment() != null && r instanceof CourseRequest && !r.getAssignment().isAllowOverlap()) 139 for (Section b: r.getAssignment().getSections()) 140 if (!b.isAllowOverlap() && !b.isToIgnoreStudentConflictsWith(section.getId()) && b.getTime() != null && a.getTime() != null && !a.isAllowOverlap() && b.getTime().hasIntersection(a.getTime())) 141 continue e; 142 return true; 143 } 144 return false; 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 public CSVFile createTable(boolean includeLastLikeStudents, boolean includeRealStudents) { 159 HashMap<Course, Map<Section, Double[]>> unavailabilities = new HashMap<Course, Map<Section,Double[]>>(); 160 HashMap<Course, Set<Long>> totals = new HashMap<Course, Set<Long>>(); 161 HashMap<CourseSection, Map<CourseSection, Double>> conflictingPairs = new HashMap<CourseSection, Map<CourseSection,Double>>(); 162 HashMap<CourseSection, Double> sectionOverlaps = new HashMap<CourseSection, Double>(); 163 164 for (Request request : new ArrayList<Request>(getModel().unassignedVariables())) { 165 if (request.getStudent().isDummy() && !includeLastLikeStudents) continue; 166 if (!request.getStudent().isDummy() && !includeRealStudents) continue; 167 if (request instanceof CourseRequest) { 168 CourseRequest courseRequest = (CourseRequest) request; 169 if (courseRequest.getStudent().isComplete()) continue; 170 171 List<Enrollment> values = courseRequest.values(); 172 173 SectionLimit limitConstraint = null; 174 for (GlobalConstraint<Request, Enrollment> c: getModel().globalConstraints()) { 175 if (c instanceof SectionLimit) { 176 limitConstraint = (SectionLimit)c; 177 break; 178 } 179 } 180 if (limitConstraint == null) { 181 limitConstraint = new SectionLimit(new DataProperties()); 182 limitConstraint.setModel(getModel()); 183 } 184 List<Enrollment> notAvailableValues = new ArrayList<Enrollment>(values.size()); 185 List<Enrollment> availableValues = new ArrayList<Enrollment>(values.size()); 186 for (Enrollment enrollment : values) { 187 if (limitConstraint.inConflict(enrollment)) 188 notAvailableValues.add(enrollment); 189 else 190 availableValues.add(enrollment); 191 } 192 193 if (!notAvailableValues.isEmpty() && iType.hasUnavailabilities()) { 194 List<Enrollment> notOverlappingEnrollments = new ArrayList<Enrollment>(values.size()); 195 enrollments: for (Enrollment enrollment: notAvailableValues) { 196 for (Request other : request.getStudent().getRequests()) { 197 if (other.equals(request) || other.getAssignment() == null || other instanceof FreeTimeRequest) continue; 198 if (other.getAssignment().isOverlapping(enrollment)) continue enrollments; 199 } 200 // not overlapping 201 notOverlappingEnrollments.add(enrollment); 202 } 203 204 if (notOverlappingEnrollments.isEmpty() && availableValues.isEmpty() && iOverlapsAllEnrollments) { 205 double fraction = request.getWeight() / notAvailableValues.size(); 206 Set<CourseSection> ones = new HashSet<CourseSection>(); 207 for (Enrollment enrollment: notAvailableValues) { 208 boolean hasConflict = false; 209 for (Section s: enrollment.getSections()) { 210 if (s.getLimit() >= 0 && s.getEnrollmentWeight(request) + request.getWeight() > s.getLimit()) { 211 hasConflict = true; 212 break; 213 } 214 } 215 216 Map<Section, Double[]> sections = unavailabilities.get(enrollment.getCourse()); 217 if (sections == null) { 218 sections = new HashMap<Section, Double[]>(); 219 unavailabilities.put(enrollment.getCourse(), sections); 220 } 221 for (Section s: enrollment.getSections()) { 222 if (hasConflict && s.getLimit() < 0 || s.getEnrollmentWeight(request) + request.getWeight() <= s.getLimit()) continue; 223 Double[] total = sections.get(s); 224 sections.put(s, new Double[] { 225 fraction + (total == null ? 0.0 : total[0].doubleValue()), 226 (total == null ? 0.0 : total[1].doubleValue()) 227 }); 228 ones.add(new CourseSection(enrollment.getCourse(), s)); 229 } 230 Set<Long> total = totals.get(enrollment.getCourse()); 231 if (total == null) { 232 total = new HashSet<Long>(); 233 totals.put(enrollment.getCourse(), total); 234 } 235 total.add(enrollment.getStudent().getId()); 236 } 237 } else if (!notOverlappingEnrollments.isEmpty()) { 238 double fraction = request.getWeight() / notOverlappingEnrollments.size(); 239 Set<CourseSection> ones = new HashSet<CourseSection>(); 240 for (Enrollment enrollment: notOverlappingEnrollments) { 241 boolean hasConflict = false; 242 for (Section s: enrollment.getSections()) { 243 if (s.getLimit() >= 0 && s.getEnrollmentWeight(request) + request.getWeight() > s.getLimit()) { 244 hasConflict = true; 245 break; 246 } 247 } 248 249 Map<Section, Double[]> sections = unavailabilities.get(enrollment.getCourse()); 250 if (sections == null) { 251 sections = new HashMap<Section, Double[]>(); 252 unavailabilities.put(enrollment.getCourse(), sections); 253 } 254 for (Section s: enrollment.getSections()) { 255 if (hasConflict && s.getLimit() < 0 || s.getEnrollmentWeight(request) + request.getWeight() <= s.getLimit()) continue; 256 Double[] total = sections.get(s); 257 sections.put(s, new Double[] { 258 fraction + (total == null ? 0.0 : total[0].doubleValue()), 259 (total == null ? 0.0 : total[1].doubleValue()) 260 }); 261 ones.add(new CourseSection(enrollment.getCourse(), s)); 262 } 263 Set<Long> total = totals.get(enrollment.getCourse()); 264 if (total == null) { 265 total = new HashSet<Long>(); 266 totals.put(enrollment.getCourse(), total); 267 } 268 total.add(enrollment.getStudent().getId()); 269 } 270 for (CourseSection section: ones) { 271 Map<Section, Double[]> sections = unavailabilities.get(section.getCourse()); 272 Double[] total = sections.get(section.getSection()); 273 sections.put(section.getSection(), new Double[] { 274 (total == null ? 0.0 : total[0].doubleValue()), 275 request.getWeight() + (total == null ? 0.0 : total[1].doubleValue()) 276 }); 277 } 278 } 279 } 280 281 if (iOverlapsAllEnrollments) 282 availableValues = values; 283 if (!availableValues.isEmpty() && iType.hasOverlaps()) { 284 List<Map<CourseSection, List<CourseSection>>> conflicts = new ArrayList<Map<CourseSection, List<CourseSection>>>(); 285 for (Enrollment enrollment: availableValues) { 286 Map<CourseSection, List<CourseSection>> overlaps = new HashMap<CourseSection, List<CourseSection>>(); 287 for (Request other : request.getStudent().getRequests()) { 288 if (other.equals(request) || other.getAssignment() == null || other instanceof FreeTimeRequest) continue; 289 Enrollment otherEnrollment = other.getAssignment(); 290 if (enrollment.isOverlapping(otherEnrollment)) 291 for (Section a: enrollment.getSections()) 292 for (Section b: other.getAssignment().getSections()) 293 if (a.getTime() != null && b.getTime() != null && !a.isAllowOverlap() && !b.isAllowOverlap() && !a.isToIgnoreStudentConflictsWith(b.getId()) && a.getTime().hasIntersection(b.getTime()) && !canIgnore(enrollment, a, availableValues)) { 294 List<CourseSection> x = overlaps.get(new CourseSection(enrollment.getCourse(), a)); 295 if (x == null) { x = new ArrayList<CourseSection>(); overlaps.put(new CourseSection(enrollment.getCourse(), a), x); } 296 x.add(new CourseSection(other.getAssignment().getCourse(), b)); 297 } 298 } 299 if (!overlaps.isEmpty()) { 300 conflicts.add(overlaps); 301 Set<Long> total = totals.get(enrollment.getCourse()); 302 if (total == null) { 303 total = new HashSet<Long>(); 304 totals.put(enrollment.getCourse(), total); 305 } 306 total.add(enrollment.getStudent().getId()); 307 } 308 } 309 310 double fraction = request.getWeight() / conflicts.size(); 311 for (Map<CourseSection, List<CourseSection>> overlaps: conflicts) { 312 for (Map.Entry<CourseSection, List<CourseSection>> entry: overlaps.entrySet()) { 313 CourseSection a = entry.getKey(); 314 Double total = sectionOverlaps.get(a); 315 sectionOverlaps.put(a, fraction + (total == null ? 0.0 : total.doubleValue())); 316 Map<CourseSection, Double> pair = conflictingPairs.get(a); 317 if (pair == null) { 318 pair = new HashMap<CourseSection, Double>(); 319 conflictingPairs.put(a, pair); 320 } 321 for (CourseSection b: entry.getValue()) { 322 Double prev = pair.get(b); 323 pair.put(b, fraction + (prev == null ? 0.0 : prev.doubleValue())); 324 } 325 } 326 } 327 } 328 } 329 } 330 Comparator<Course> courseComparator = new Comparator<Course>() { 331 @Override 332 public int compare(Course a, Course b) { 333 int cmp = a.getName().compareTo(b.getName()); 334 if (cmp != 0) return cmp; 335 return a.getId() < b.getId() ? -1 : a.getId() == b.getId() ? 0 : 1; 336 } 337 }; 338 Comparator<Section> sectionComparator = new Comparator<Section>() { 339 @Override 340 public int compare(Section a, Section b) { 341 int cmp = a.getSubpart().getConfig().getOffering().getName().compareTo(b.getSubpart().getConfig().getOffering().getName()); 342 if (cmp != 0) return cmp; 343 cmp = a.getSubpart().getInstructionalType().compareTo(b.getSubpart().getInstructionalType()); 344 // if (cmp != 0) return cmp; 345 // cmp = a.getName().compareTo(b.getName()); 346 if (cmp != 0) return cmp; 347 return a.getId() < b.getId() ? -1 : a.getId() == b.getId() ? 0 : 1; 348 } 349 }; 350 351 CSVFile csv = new CSVFile(); 352 List<CSVFile.CSVField> headers = new ArrayList<CSVFile.CSVField>(); 353 headers.add(new CSVFile.CSVField("Course")); 354 headers.add(new CSVFile.CSVField("Total\nConflicts")); 355 if (iType.hasUnavailabilities()) { 356 headers.add(new CSVFile.CSVField("Course\nEnrollment")); 357 headers.add(new CSVFile.CSVField("Course\nLimit")); 358 } 359 headers.add(new CSVFile.CSVField("Class")); 360 headers.add(new CSVFile.CSVField("Meeting Time")); 361 if (iType.hasUnavailabilities()) { 362 headers.add(new CSVFile.CSVField("Availability\nConflicts")); 363 headers.add(new CSVFile.CSVField("% of Total\nConflicts")); 364 } 365 if (iType.hasOverlaps()) { 366 headers.add(new CSVFile.CSVField("Time\nConflicts")); 367 headers.add(new CSVFile.CSVField("% of Total\nConflicts")); 368 } 369 if (iType.hasUnavailabilities()) { 370 headers.add(new CSVFile.CSVField("Class\nEnrollment")); 371 headers.add(new CSVFile.CSVField("Class\nLimit")); 372 if (!iType.hasOverlaps()) 373 headers.add(new CSVFile.CSVField("Class\nPotential")); 374 } 375 if (iType.hasOverlaps()) { 376 headers.add(new CSVFile.CSVField("Conflicting\nClass")); 377 headers.add(new CSVFile.CSVField("Conflicting\nMeeting Time")); 378 headers.add(new CSVFile.CSVField("Joined\nConflicts")); 379 headers.add(new CSVFile.CSVField("% of Total\nConflicts")); 380 } 381 csv.setHeader(headers); 382 383 TreeSet<Course> courses = new TreeSet<Course>(courseComparator); 384 courses.addAll(totals.keySet()); 385 386 for (Course course: courses) { 387 Map<Section, Double[]> sectionUnavailability = unavailabilities.get(course); 388 Set<Long> total = totals.get(course); 389 390 TreeSet<Section> sections = new TreeSet<Section>(sectionComparator); 391 if (sectionUnavailability != null) 392 sections.addAll(sectionUnavailability.keySet()); 393 for (Map.Entry<CourseSection, Double> entry: sectionOverlaps.entrySet()) 394 if (course.equals(entry.getKey().getCourse())) 395 sections.add(entry.getKey().getSection()); 396 397 boolean firstCourse = true; 398 for (Section section: sections) { 399 Double[] sectionUnavailable = (sectionUnavailability == null ? null : sectionUnavailability.get(section)); 400 Double sectionOverlap = sectionOverlaps.get(new CourseSection(course, section)); 401 Map<CourseSection, Double> pair = conflictingPairs.get(new CourseSection(course, section)); 402 403 if (pair == null) { 404 List<CSVFile.CSVField> line = new ArrayList<CSVFile.CSVField>(); 405 line.add(new CSVFile.CSVField(firstCourse ? course.getName() : "")); 406 line.add(new CSVFile.CSVField(firstCourse ? total.size() : "")); 407 if (iType.hasUnavailabilities()) { 408 line.add(new CSVFile.CSVField(firstCourse ? sDF1.format(course.getEnrollmentWeight(null)) : "")); 409 line.add(new CSVFile.CSVField(firstCourse ? course.getLimit() < 0 ? "" : String.valueOf(course.getLimit()) : "")); 410 } 411 412 line.add(new CSVFile.CSVField(section.getSubpart().getName() + " " + section.getName(course.getId()))); 413 line.add(new CSVFile.CSVField(section.getTime() == null ? "" : section.getTime().getDayHeader() + " " + section.getTime().getStartTimeHeader() + " - " + section.getTime().getEndTimeHeader())); 414 415 if (iType.hasUnavailabilities()) { 416 line.add(new CSVFile.CSVField(sectionUnavailable != null ? sDF2.format(sectionUnavailable[0]) : "")); 417 line.add(new CSVFile.CSVField(sectionUnavailable != null ? sDF2.format(sectionUnavailable[0] / total.size()) : "")); 418 } 419 if (iType.hasOverlaps()) { 420 line.add(new CSVFile.CSVField(sectionOverlap != null ? sDF2.format(sectionOverlap) : "")); 421 line.add(new CSVFile.CSVField(sectionOverlap != null ? sDF2.format(sectionOverlap / total.size()) : "")); 422 } 423 if (iType.hasUnavailabilities()) { 424 line.add(new CSVFile.CSVField(sDF1.format(section.getEnrollmentWeight(null)))); 425 line.add(new CSVFile.CSVField(section.getLimit() < 0 ? "" : String.valueOf(section.getLimit()))); 426 if (!iType.hasOverlaps()) 427 line.add(new CSVFile.CSVField(sectionUnavailable != null ? sDF1.format(sectionUnavailable[1]) : "")); 428 } 429 430 csv.addLine(line); 431 } else { 432 boolean firstClass = true; 433 for (CourseSection other: new TreeSet<CourseSection>(pair.keySet())) { 434 List<CSVFile.CSVField> line = new ArrayList<CSVFile.CSVField>(); 435 line.add(new CSVFile.CSVField(firstCourse && firstClass ? course.getName() : "")); 436 line.add(new CSVFile.CSVField(firstCourse && firstClass ? total.size() : "")); 437 if (iType.hasUnavailabilities()) { 438 line.add(new CSVFile.CSVField(firstCourse && firstClass ? sDF1.format(course.getEnrollmentWeight(null)) : "")); 439 line.add(new CSVFile.CSVField(firstCourse && firstClass ? course.getLimit() < 0 ? "" : String.valueOf(course.getLimit()) : "")); 440 } 441 442 line.add(new CSVFile.CSVField(firstClass ? section.getSubpart().getName() + " " + section.getName(course.getId()): "")); 443 line.add(new CSVFile.CSVField(firstClass ? section.getTime() == null ? "" : section.getTime().getDayHeader() + " " + section.getTime().getStartTimeHeader() + " - " + section.getTime().getEndTimeHeader(): "")); 444 445 if (iType.hasUnavailabilities()) { 446 line.add(new CSVFile.CSVField(firstClass && sectionUnavailable != null ? sDF2.format(sectionUnavailable[0]): "")); 447 line.add(new CSVFile.CSVField(sectionUnavailable != null ? sDF2.format(sectionUnavailable[0] / total.size()) : "")); 448 } 449 line.add(new CSVFile.CSVField(firstClass && sectionOverlap != null ? sDF2.format(sectionOverlap): "")); 450 line.add(new CSVFile.CSVField(firstClass && sectionOverlap != null ? sDF2.format(sectionOverlap / total.size()) : "")); 451 if (iType.hasUnavailabilities()) { 452 line.add(new CSVFile.CSVField(firstClass ? sDF1.format(section.getEnrollmentWeight(null)): "")); 453 line.add(new CSVFile.CSVField(firstClass ? section.getLimit() < 0 ? "" : String.valueOf(section.getLimit()): "")); 454 } 455 456 line.add(new CSVFile.CSVField(other.getCourse().getName() + " " + other.getSection().getSubpart().getName() + " " + other.getSection().getName(other.getCourse().getId()))); 457 line.add(new CSVFile.CSVField(other.getSection().getTime().getDayHeader() + " " + other.getSection().getTime().getStartTimeHeader() + " - " + other.getSection().getTime().getEndTimeHeader())); 458 line.add(new CSVFile.CSVField(sDF2.format(pair.get(other)))); 459 line.add(new CSVFile.CSVField(sDF2.format(pair.get(other) / total.size()))); 460 461 csv.addLine(line); 462 firstClass = false; 463 } 464 } 465 466 firstCourse = false; 467 } 468 469 csv.addLine(); 470 } 471 return csv; 472 } 473 474 @Override 475 public CSVFile create(DataProperties properties) { 476 iType = Type.valueOf(properties.getProperty("type", iType.name())); 477 iOverlapsAllEnrollments = properties.getPropertyBoolean("overlapsIncludeAll", true); 478 return createTable(properties.getPropertyBoolean("lastlike", false), properties.getPropertyBoolean("real", true)); 479 } 480}