001 package net.sf.cpsolver.studentsct.report;
002
003 import java.text.DecimalFormat;
004 import java.util.Collections;
005 import java.util.Comparator;
006 import java.util.Enumeration;
007 import java.util.HashSet;
008 import java.util.Hashtable;
009 import java.util.Iterator;
010 import java.util.Map;
011 import java.util.Set;
012 import java.util.TreeSet;
013 import java.util.Vector;
014
015 import net.sf.cpsolver.ifs.util.CSVFile;
016 import net.sf.cpsolver.ifs.util.DataProperties;
017 import net.sf.cpsolver.studentsct.StudentSectioningModel;
018 import net.sf.cpsolver.studentsct.constraint.SectionLimit;
019 import net.sf.cpsolver.studentsct.model.Course;
020 import net.sf.cpsolver.studentsct.model.CourseRequest;
021 import net.sf.cpsolver.studentsct.model.Enrollment;
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 lists conflicting courses in a {@link CSVFile} comma separated text file.
028 * <br><br>
029 *
030 * Each line represent a course that has some unassigned course requests (column UnasgnCrs),
031 * course that was conflicting with that course (column ConflCrs), and number of students with
032 * that conflict. So, for instance if there was a student which cannot attend course A with
033 * weight 1.5 (e.g., 10 last-like students projected to 15), and when A had two possible assignments
034 * for that student, one conflicting with C (assigned to that student) and the other with D,
035 * then 0.75 (1.5/2) was added to rows A, B and A, C. The column NoAlt is Y when every possible
036 * enrollment of the first course is overlapping with every possible enrollment of the second
037 * course (it is N otherwise) and a column Reason which lists the overlapping sections.
038 *
039 * <br><br>
040 *
041 * Usage: new CourseConflictTable(model),createTable(true, true).save(aFile);
042 *
043 * <br><br>
044 *
045 * @version
046 * StudentSct 1.1 (Student Sectioning)<br>
047 * Copyright (C) 2007 Tomáš Müller<br>
048 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
049 * Lazenska 391, 76314 Zlin, Czech Republic<br>
050 * <br>
051 * This library is free software; you can redistribute it and/or
052 * modify it under the terms of the GNU Lesser General Public
053 * License as published by the Free Software Foundation; either
054 * version 2.1 of the License, or (at your option) any later version.
055 * <br><br>
056 * This library is distributed in the hope that it will be useful,
057 * but WITHOUT ANY WARRANTY; without even the implied warranty of
058 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
059 * Lesser General Public License for more details.
060 * <br><br>
061 * You should have received a copy of the GNU Lesser General Public
062 * License along with this library; if not, write to the Free Software
063 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
064 */
065
066 public class CourseConflictTable {
067 private static org.apache.log4j.Logger sLog = org.apache.log4j.Logger.getLogger(CourseConflictTable.class);
068 private static DecimalFormat sDF = new DecimalFormat("0.000");
069
070 private StudentSectioningModel iModel = null;
071
072 /**
073 * Constructor
074 * @param model student sectioning model
075 */
076 public CourseConflictTable(StudentSectioningModel model) {
077 iModel = model;
078 }
079
080 /** Return student sectioning model */
081 public StudentSectioningModel getModel() {
082 return iModel;
083 }
084
085 /**
086 * True, if there is no pair of enrollments of r1 and r2 that is not in a hard conflict
087 */
088 private boolean areInHardConfict(Request r1, Request r2) {
089 for (Enumeration e=r1.values().elements();e.hasMoreElements();) {
090 Enrollment e1 = (Enrollment)e.nextElement();
091 for (Enumeration f=r2.values().elements();f.hasMoreElements();) {
092 Enrollment e2 = (Enrollment)f.nextElement();
093 if (!e1.isOverlapping(e2)) return false;
094 }
095 }
096 return true;
097 }
098
099 /**
100 * Return a set of explanations (Strings) for conflicts between the given enrollments
101 * @param enrl an enrollment
102 * @param conflict an enrollment conflicting with enrl
103 * @return a set of explanations, (e.g., AB 101 Lec 1 MWF 7:30 - 8:20 vs AB 201 Lec 1 F 7:30 - 9:20)
104 */
105 private HashSet explanations(Enrollment enrl, Enrollment conflict) {
106 HashSet expl = new HashSet();
107 for (Iterator i=enrl.getAssignments().iterator();i.hasNext();) {
108 Section s1 = (Section)i.next();
109 for (Iterator j=conflict.getAssignments().iterator();j.hasNext();) {
110 Section s2 = (Section)j.next();
111 if (s1.isOverlapping(s2))
112 expl.add(s1.getSubpart().getName()+" "+s1.getTime().getLongName()+" vs "+s2.getSubpart().getName()+" "+s2.getTime().getLongName());
113 }
114 }
115 for (Iterator i=enrl.getAssignments().iterator();i.hasNext();) {
116 Section s1 = (Section)i.next();
117 if (conflict.getAssignments().contains(s1) && SectionLimit.getEnrollmentWeight(s1, enrl.getRequest())>s1.getLimit()) {
118 expl.add(s1.getSubpart().getName()+" n/a");
119 }
120 }
121 return expl;
122 }
123
124 /**
125 * Create report
126 * @param includeLastLikeStudents true, if last-like students should be included (i.e., {@link Student#isDummy()} is true)
127 * @param includeRealStudents true, if real students should be included (i.e., {@link Student#isDummy()} is false)
128 * @return report as comma separated text file
129 */
130 public CSVFile createTable(boolean includeLastLikeStudents, boolean includeRealStudents) {
131 CSVFile csv = new CSVFile();
132 csv.setHeader(new CSVFile.CSVField[] {
133 new CSVFile.CSVField("UnasgnCrs"),
134 new CSVFile.CSVField("ConflCrs"),
135 new CSVFile.CSVField("NrStud"),
136 new CSVFile.CSVField("StudWeight"),
137 new CSVFile.CSVField("NoAlt"),
138 new CSVFile.CSVField("Reason")
139 });
140 Hashtable unassignedCourseTable = new Hashtable();
141 for (Enumeration e=new Vector(getModel().unassignedVariables()).elements();e.hasMoreElements();) {
142 Request request = (Request)e.nextElement();
143 if (request.getStudent().isDummy() && !includeLastLikeStudents) continue;
144 if (!request.getStudent().isDummy() && !includeRealStudents) continue;
145 if (request instanceof CourseRequest) {
146 CourseRequest courseRequest = (CourseRequest)request;
147 if (courseRequest.getStudent().isComplete()) continue;
148
149 Vector values = courseRequest.values();
150 SectionLimit limitConstraint = new SectionLimit(new DataProperties());
151 Vector availableValues = new Vector(values.size());
152 for (Enumeration f=values.elements();f.hasMoreElements();) {
153 Enrollment enrollment = (Enrollment)f.nextElement();
154 if (!limitConstraint.inConflict(enrollment))
155 availableValues.addElement(enrollment);
156 }
157
158 if (availableValues.isEmpty()) {
159 Course course = (Course)courseRequest.getCourses().firstElement();
160 Hashtable conflictCourseTable = (Hashtable)unassignedCourseTable.get(course);
161 if (conflictCourseTable==null) {
162 conflictCourseTable = new Hashtable();
163 unassignedCourseTable.put(course, conflictCourseTable);
164 }
165 Object[] weight = (Object[])conflictCourseTable.get(course);
166 double nrStud = (weight==null?0.0:((Double)weight[0]).doubleValue()) + 1.0;
167 double nrStudW = (weight==null?0.0:((Double)weight[1]).doubleValue()) + request.getWeight();
168 boolean noAlt = (weight==null?true:((Boolean)weight[2]).booleanValue());
169 HashSet expl = (weight==null?new HashSet():(HashSet)weight[3]);
170 expl.add(course.getName()+" n/a");
171 conflictCourseTable.put(course, new Object[] {new Double(nrStud), new Double(nrStudW),new Boolean(noAlt),expl});
172 }
173
174 for (Enumeration f=availableValues.elements();f.hasMoreElements();) {
175 Enrollment enrollment = (Enrollment)f.nextElement();
176 Set conflicts = getModel().conflictValues(enrollment);
177 if (conflicts.isEmpty()) {
178 sLog.warn("Request "+courseRequest+" of student "+courseRequest.getStudent()+" not assigned, however, no conflicts were returned.");
179 courseRequest.assign(0, enrollment);
180 break;
181 }
182 Course course = null;
183 for (Enumeration g=courseRequest.getCourses().elements();g.hasMoreElements();) {
184 Course c = (Course)g.nextElement();
185 if (c.getOffering().equals(enrollment.getConfig().getOffering())) {
186 course = c; break;
187 }
188 }
189 if (course==null) {
190 sLog.warn("Course not found for request "+courseRequest+" of student "+courseRequest.getStudent()+".");
191 continue;
192 }
193 Hashtable conflictCourseTable = (Hashtable)unassignedCourseTable.get(course);
194 if (conflictCourseTable==null) {
195 conflictCourseTable = new Hashtable();
196 unassignedCourseTable.put(course, conflictCourseTable);
197 }
198 for (Iterator i=conflicts.iterator();i.hasNext();) {
199 Enrollment conflict = (Enrollment)i.next();
200 if (conflict.variable() instanceof CourseRequest) {
201 CourseRequest conflictCourseRequest = (CourseRequest)conflict.variable();
202 Course conflictCourse = null;
203 for (Enumeration g=conflictCourseRequest.getCourses().elements();g.hasMoreElements();) {
204 Course c = (Course)g.nextElement();
205 if (c.getOffering().equals(conflict.getConfig().getOffering())) {
206 conflictCourse = c; break;
207 }
208 }
209 if (conflictCourse==null) {
210 sLog.warn("Course not found for request "+conflictCourseRequest+" of student "+conflictCourseRequest.getStudent()+".");
211 continue;
212 }
213 double weightThisConflict = request.getWeight() / availableValues.size() / conflicts.size();
214 double partThisConflict = 1.0 / availableValues.size() / conflicts.size();
215 Object[] weight = (Object[])conflictCourseTable.get(conflictCourse);
216 double nrStud = (weight==null?0.0:((Double)weight[0]).doubleValue()) + partThisConflict;
217 double nrStudW = (weight==null?0.0:((Double)weight[1]).doubleValue()) + weightThisConflict;
218 boolean noAlt = (weight==null?areInHardConfict(request, conflict.getRequest()):((Boolean)weight[2]).booleanValue());
219 HashSet expl = (weight==null?new HashSet():(HashSet)weight[3]);
220 expl.addAll(explanations(enrollment, conflict));
221 conflictCourseTable.put(conflictCourse, new Object[] {new Double(nrStud),new Double(nrStudW),new Boolean(noAlt),expl});
222 }
223 }
224 }
225 }
226 }
227 for (Iterator i=unassignedCourseTable.entrySet().iterator();i.hasNext();) {
228 Map.Entry entry = (Map.Entry)i.next();
229 Course unassignedCourse = (Course)entry.getKey();
230 Hashtable conflictCourseTable = (Hashtable)entry.getValue();
231 for (Iterator j=conflictCourseTable.entrySet().iterator();j.hasNext();) {
232 Map.Entry entry2 = (Map.Entry)j.next();
233 Course conflictCourse = (Course)entry2.getKey();
234 Object[] weight = (Object[])entry2.getValue();
235 HashSet expl = (HashSet)weight[3];
236 String explStr = "";
237 for (Iterator k=new TreeSet(expl).iterator();k.hasNext();)
238 explStr += k.next() + (k.hasNext()?"\n":"");
239 csv.addLine(new CSVFile.CSVField[] {
240 new CSVFile.CSVField(unassignedCourse.getName()),
241 new CSVFile.CSVField(conflictCourse.getName()),
242 new CSVFile.CSVField(sDF.format((Double)weight[0])),
243 new CSVFile.CSVField(sDF.format((Double)weight[1])),
244 new CSVFile.CSVField(((Boolean)weight[2]).booleanValue()?"Y":"N"),
245 new CSVFile.CSVField(explStr)
246 });
247 }
248 }
249 if (csv.getLines()!=null)
250 Collections.sort(csv.getLines(), new Comparator() {
251 public int compare(Object o1, Object o2) {
252 CSVFile.CSVLine l1 = (CSVFile.CSVLine)o1;
253 CSVFile.CSVLine l2 = (CSVFile.CSVLine)o2;
254 //int cmp = l2.getField(3).toString().compareTo(l1.getField(3).toString());
255 //if (cmp!=0) return cmp;
256 int cmp = Double.compare(l2.getField(2).toDouble(),l1.getField(2).toDouble());
257 if (cmp!=0) return cmp;
258 cmp = l1.getField(0).toString().compareTo(l2.getField(0).toString());
259 if (cmp!=0) return cmp;
260 return l1.getField(1).toString().compareTo(l2.getField(1).toString());
261 }
262 });
263 return csv;
264 }
265 }