001    package net.sf.cpsolver.studentsct.report;
002    
003    import java.text.DecimalFormat;
004    import java.util.ArrayList;
005    import java.util.Collections;
006    import java.util.Comparator;
007    import java.util.HashSet;
008    import java.util.HashMap;
009    import java.util.Iterator;
010    import java.util.List;
011    import java.util.Map;
012    import java.util.Set;
013    import java.util.TreeSet;
014    
015    import net.sf.cpsolver.ifs.model.GlobalConstraint;
016    import net.sf.cpsolver.ifs.util.CSVFile;
017    import net.sf.cpsolver.ifs.util.DataProperties;
018    import net.sf.cpsolver.studentsct.StudentSectioningModel;
019    import net.sf.cpsolver.studentsct.constraint.ConfigLimit;
020    import net.sf.cpsolver.studentsct.constraint.CourseLimit;
021    import net.sf.cpsolver.studentsct.constraint.SectionLimit;
022    import net.sf.cpsolver.studentsct.model.Course;
023    import net.sf.cpsolver.studentsct.model.CourseRequest;
024    import net.sf.cpsolver.studentsct.model.Enrollment;
025    import net.sf.cpsolver.studentsct.model.Request;
026    import net.sf.cpsolver.studentsct.model.Section;
027    import 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 Tomas Muller<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    
073    public 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    }