    001package net.sf.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 net.sf.cpsolver.ifs.model.GlobalConstraint;
    016import net.sf.cpsolver.ifs.util.CSVFile;
    017import net.sf.cpsolver.ifs.util.DataProperties;
    018import net.sf.cpsolver.studentsct.StudentSectioningModel;
    019import net.sf.cpsolver.studentsct.constraint.ConfigLimit;
    020import net.sf.cpsolver.studentsct.constraint.CourseLimit;
    021import net.sf.cpsolver.studentsct.constraint.SectionLimit;
    022import net.sf.cpsolver.studentsct.model.Course;
    023import net.sf.cpsolver.studentsct.model.CourseRequest;
    024import net.sf.cpsolver.studentsct.model.Enrollment;
    025import net.sf.cpsolver.studentsct.model.Request;
    026import net.sf.cpsolver.studentsct.model.Section;
    027import 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 Tomáš Müller<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
    073public 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}