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    }