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 {
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 }