001 package net.sf.cpsolver.studentsct.extension;
002
003 import java.util.HashSet;
004 import java.util.Set;
005
006 import org.apache.log4j.Logger;
007
008 import net.sf.cpsolver.ifs.extension.Extension;
009 import net.sf.cpsolver.ifs.solver.Solver;
010 import net.sf.cpsolver.ifs.util.DataProperties;
011 import net.sf.cpsolver.studentsct.StudentSectioningModel;
012 import net.sf.cpsolver.studentsct.model.Assignment;
013 import net.sf.cpsolver.studentsct.model.Enrollment;
014 import net.sf.cpsolver.studentsct.model.FreeTimeRequest;
015 import net.sf.cpsolver.studentsct.model.Request;
016 import net.sf.cpsolver.studentsct.model.Section;
017 import net.sf.cpsolver.studentsct.model.Student;
018
019 /**
020 * This extension computes time overlaps. Only sections that allow overlaps
021 * (see {@link Assignment#isAllowOverlap()}) can overlap. This class counts
022 * how many overlapping slots there are so that this number can be minimized.
023 *
024 * <br>
025 * <br>
026 *
027 * @version StudentSct 1.2 (Student Sectioning)<br>
028 * Copyright (C) 2007 - 2010 Tomas Muller<br>
029 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
030 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
031 * <br>
032 * This library is free software; you can redistribute it and/or modify
033 * it under the terms of the GNU Lesser General Public License as
034 * published by the Free Software Foundation; either version 3 of the
035 * License, or (at your option) any later version. <br>
036 * <br>
037 * This library is distributed in the hope that it will be useful, but
038 * WITHOUT ANY WARRANTY; without even the implied warranty of
039 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
040 * Lesser General Public License for more details. <br>
041 * <br>
042 * You should have received a copy of the GNU Lesser General Public
043 * License along with this library; if not see
044 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
045 */
046
047 public class TimeOverlapsCounter extends Extension<Request, Enrollment> {
048 private static Logger sLog = Logger.getLogger(TimeOverlapsCounter.class);
049 private int iTotalNrConflicts = 0;
050 private Set<Conflict> iAllConflicts = new HashSet<Conflict>();
051 /** Debug flag */
052 public static boolean sDebug = false;
053 private Request iOldVariable = null;
054 private Enrollment iUnassignedValue = null;
055
056 /**
057 * Constructor. Beside of other things, this constructor also uses
058 * {@link StudentSectioningModel#setTimeOverlaps(TimeOverlapsCounter)} to
059 * set the this instance to the model.
060 *
061 * @param solver
062 * constraint solver
063 * @param properties
064 * configuration
065 */
066 public TimeOverlapsCounter(Solver<Request, Enrollment> solver, DataProperties properties) {
067 super(solver, properties);
068 if (solver != null)
069 ((StudentSectioningModel) solver.currentSolution().getModel()).setTimeOverlaps(this);
070 }
071
072 /**
073 * Initialize extension
074 */
075 @Override
076 public boolean init(Solver<Request, Enrollment> solver) {
077 iTotalNrConflicts = countTotalNrConflicts();
078 if (sDebug)
079 iAllConflicts = computeAllConflicts();
080 StudentSectioningModel m = (StudentSectioningModel)solver.currentSolution().getModel();
081 for (Conflict c: computeAllConflicts())
082 m.add(c);
083 return true;
084 }
085
086 @Override
087 public String toString() {
088 return "TimeOverlaps";
089 }
090
091 /**
092 * Return true if the given two assignments are overlapping.
093 *
094 * @param a1
095 * an assignment
096 * @param a2
097 * an assignment
098 * @return true, if the given sections are in an overlapping conflict
099 */
100 public boolean inConflict(Assignment a1, Assignment a2) {
101 if (a1.getTime() == null || a2.getTime() == null) return false;
102 if (a1 instanceof Section && a2 instanceof Section && ((Section)a1).isToIgnoreStudentConflictsWith(a2.getId())) return false;
103 return a1.getTime().hasIntersection(a2.getTime());
104 }
105
106 /**
107 * If the two sections are overlapping, return the number of slots of the overlap.
108 *
109 * @param a1
110 * an assignment
111 * @param a2
112 * an assignment
113 * @return the number of overlapping slots against the number of slots of the smallest section
114 */
115 public int share(Assignment a1, Assignment a2) {
116 if (!inConflict(a1, a2)) return 0;
117 return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime());
118 }
119
120
121 /**
122 * Return number of time overlapping conflicts that are between two enrollments. It
123 * is the total share between pairs of assignments of these enrollments that are in a
124 * time overlap.
125 *
126 * @param e1
127 * an enrollment
128 * @param e2
129 * an enrollment
130 * @return number of time overlapping conflict between given enrollments
131 */
132 public int nrConflicts(Enrollment e1, Enrollment e2) {
133 if (!e1.getStudent().equals(e2.getStudent())) return 0;
134 if (e1.getRequest() instanceof FreeTimeRequest && e2.getRequest() instanceof FreeTimeRequest) return 0;
135 int cnt = 0;
136 for (Assignment s1 : e1.getAssignments()) {
137 for (Assignment s2 : e2.getAssignments()) {
138 if (inConflict(s1, s2))
139 cnt += share(s1, s2);
140 }
141 }
142 return cnt;
143 }
144
145 /**
146 * Return a set of time overlapping conflicts ({@link Conflict} objects) between
147 * given (course) enrollments.
148 *
149 * @param e1
150 * an enrollment
151 * @param e2
152 * an enrollment
153 * @return list of time overlapping conflicts that are between assignment of the
154 * given enrollments
155 */
156 public Set<Conflict> conflicts(Enrollment e1, Enrollment e2) {
157 Set<Conflict> ret = new HashSet<Conflict>();
158 if (!e1.getStudent().equals(e2.getStudent())) return ret;
159 if (e1.getRequest() instanceof FreeTimeRequest && e2.getRequest() instanceof FreeTimeRequest) return ret;
160 for (Assignment s1 : e1.getAssignments()) {
161 for (Assignment s2 : e2.getAssignments()) {
162 if (inConflict(s1, s2))
163 ret.add(new Conflict(e1.getStudent(), share(s1, s2), e1, s1, e2, s2));
164 }
165 }
166 return ret;
167 }
168
169 /**
170 * Total sum of all conflict of the given enrollment and other enrollments
171 * that are assigned to the same student.
172 */
173 public int nrAllConflicts(Enrollment enrollment) {
174 if (enrollment.getRequest() instanceof FreeTimeRequest) return 0;
175 int cnt = 0;
176 for (Request request : enrollment.getStudent().getRequests()) {
177 if (request.equals(enrollment.getRequest())) continue;
178 if (request instanceof FreeTimeRequest) {
179 FreeTimeRequest ft = (FreeTimeRequest)request;
180 cnt += nrConflicts(enrollment, ft.createEnrollment());
181 } else if (request.getAssignment() != null && !request.equals(iOldVariable)) {
182 cnt += nrConflicts(enrollment, request.getAssignment());
183 }
184 }
185 return cnt;
186 }
187
188 /**
189 * Total sum of all free time conflict of the given enrollment.
190 */
191 public int nrFreeTimeConflicts(Enrollment enrollment) {
192 if (enrollment.getRequest() instanceof FreeTimeRequest) return 0;
193 int cnt = 0;
194 for (Request request : enrollment.getStudent().getRequests()) {
195 if (request instanceof FreeTimeRequest) {
196 FreeTimeRequest ft = (FreeTimeRequest)request;
197 for (Assignment section: enrollment.getAssignments())
198 cnt += share(section, ft);
199 }
200 }
201 return cnt;
202 }
203
204 /**
205 * Return a set of free time conflict of the given enrollment.
206 */
207 public Set<Conflict> freeTimeConflicts(Enrollment enrollment) {
208 Set<Conflict> ret = new HashSet<Conflict>();
209 if (enrollment.getRequest() instanceof FreeTimeRequest) return ret;
210 for (Request request : enrollment.getStudent().getRequests()) {
211 if (request instanceof FreeTimeRequest) {
212 FreeTimeRequest ft = (FreeTimeRequest)request;
213 for (Assignment section: enrollment.getAssignments()) {
214 if (inConflict(section, ft))
215 ret.add(new Conflict(enrollment.getStudent(), share(section, ft), enrollment, section, ft.createEnrollment(), ft));
216 }
217 }
218 }
219 return ret;
220 }
221
222 /**
223 * The set of all conflicts ({@link Conflict} objects) of the given
224 * enrollment and other enrollments that are assigned to the same student.
225 */
226 public Set<Conflict> allConflicts(Enrollment enrollment) {
227 Set<Conflict> ret = new HashSet<Conflict>();
228 if (enrollment.getRequest() instanceof FreeTimeRequest) return ret;
229 for (Request request : enrollment.getStudent().getRequests()) {
230 if (request.equals(enrollment.getRequest())) continue;
231 if (request instanceof FreeTimeRequest) {
232 FreeTimeRequest ft = (FreeTimeRequest)request;
233 ret.addAll(conflicts(enrollment, ft.createEnrollment()));
234 continue;
235 } else if (request.getAssignment() != null && !request.equals(iOldVariable)) {
236 ret.addAll(conflicts(enrollment, request.getAssignment()));
237 }
238 }
239 return ret;
240 }
241
242 /**
243 * Called when a value is assigned to a variable. Internal number of
244 * time overlapping conflicts is updated, see
245 * {@link TimeOverlapsCounter#getTotalNrConflicts()}.
246 */
247 public void assigned(long iteration, Enrollment value) {
248 StudentSectioningModel m = (StudentSectioningModel)value.variable().getModel();
249 for (Conflict c: allConflicts(value)) {
250 iTotalNrConflicts += c.getShare();
251 m.add(c);
252 }
253 if (sDebug) {
254 sLog.debug("A:" + value.variable() + " := " + value);
255 int inc = nrAllConflicts(value);
256 if (inc != 0) {
257 sLog.debug("-- TOC+" + inc + " A: " + value.variable() + " := " + value);
258 for (Conflict c: allConflicts(value)) {
259 sLog.debug(" -- " + c);
260 iAllConflicts.add(c);
261 inc -= c.getShare();
262 }
263 if (inc != 0) {
264 sLog.error("Different number of conflicts for the assigned value (difference: " + inc + ")!");
265 }
266 }
267 }
268 }
269
270 /**
271 * Called when a value is unassigned from a variable. Internal number of
272 * time overlapping conflicts is updated, see
273 * {@link TimeOverlapsCounter#getTotalNrConflicts()}.
274 */
275 public void unassigned(long iteration, Enrollment value) {
276 StudentSectioningModel m = (StudentSectioningModel)value.variable().getModel();
277 for (Conflict c: allConflicts(value)) {
278 iTotalNrConflicts -= c.getShare();
279 m.remove(c);
280 }
281 if (sDebug) {
282 sLog.debug("U:" + value.variable() + " := " + value);
283 int dec = nrAllConflicts(value);
284 if (dec != 0) {
285 sLog.debug("-- TOC-" + dec + " U: " + value.variable() + " := " + value);
286 for (Conflict c: allConflicts(value)) {
287 sLog.debug(" -- " + c);
288 iAllConflicts.remove(c);
289 dec -= c.getShare();
290 }
291 if (dec != 0) {
292 sLog.error("Different number of conflicts for the unassigned value (difference: " + dec + ")!");
293 }
294 }
295 }
296 }
297
298 /** Actual number of all time overlapping conflicts */
299 public int getTotalNrConflicts() {
300 return iTotalNrConflicts;
301 }
302
303 public void checkTotalNrConflicts() {
304 int total = countTotalNrConflicts();
305 if (total != iTotalNrConflicts) {
306 sLog.error("Number of conflicts does not match (actual: " + total + ", count: " + iTotalNrConflicts + ")!");
307 iTotalNrConflicts = total;
308 if (sDebug) {
309 Set<Conflict> conflicts = computeAllConflicts();
310 for (Conflict c: conflicts) {
311 if (!iAllConflicts.contains(c))
312 sLog.debug(" +add+ " + c);
313 }
314 for (Conflict c: iAllConflicts) {
315 if (!conflicts.contains(c))
316 sLog.debug(" -rem- " + c);
317 }
318 for (Conflict c: conflicts) {
319 for (Conflict d: iAllConflicts) {
320 if (c.equals(d) && c.getShare() != d.getShare()) {
321 sLog.debug(" -dif- " + c + " (other: " + d.getShare() + ")");
322 }
323 }
324 }
325 iAllConflicts = conflicts;
326 // getSolver().stopSolver(false);
327 }
328 }
329 }
330
331 /**
332 * Compute the actual number of all time overlapping conflicts. Should be equal to
333 * {@link TimeOverlapsCounter#getTotalNrConflicts()}.
334 */
335 public int countTotalNrConflicts() {
336 int total = 0;
337 for (Request r1 : getModel().variables()) {
338 if (r1.getAssignment() == null || r1 instanceof FreeTimeRequest || r1.equals(iOldVariable))
339 continue;
340 for (Request r2 : r1.getStudent().getRequests()) {
341 if (r2 instanceof FreeTimeRequest) {
342 FreeTimeRequest ft = (FreeTimeRequest)r2;
343 total += nrConflicts(r1.getAssignment(), ft.createEnrollment());
344 } else if (r2.getAssignment() != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) {
345 total += nrConflicts(r1.getAssignment(), r2.getAssignment());
346 }
347 }
348 }
349 return total;
350 }
351
352 /**
353 * Compute a set of all time overlapping conflicts ({@link Conflict} objects).
354 */
355 public Set<Conflict> computeAllConflicts() {
356 Set<Conflict> ret = new HashSet<Conflict>();
357 for (Request r1 : getModel().variables()) {
358 if (r1.getAssignment() == null || r1 instanceof FreeTimeRequest || r1.equals(iOldVariable))
359 continue;
360 for (Request r2 : r1.getStudent().getRequests()) {
361 if (r2 instanceof FreeTimeRequest) {
362 FreeTimeRequest ft = (FreeTimeRequest)r2;
363 ret.addAll(conflicts(r1.getAssignment(), ft.createEnrollment()));
364 } else if (r2.getAssignment() != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) {
365 ret.addAll(conflicts(r1.getAssignment(), r2.getAssignment()));
366 }
367 }
368 }
369 return ret;
370 }
371
372 /**
373 * Return a set of all time overlapping conflicts ({@link Conflict} objects).
374 */
375 public Set<Conflict> getAllConflicts() {
376 return iAllConflicts;
377 }
378
379 /**
380 * Called before a value is assigned to a variable.
381 */
382 @Override
383 public void beforeAssigned(long iteration, Enrollment value) {
384 if (value != null) {
385 if (value.variable().getAssignment() != null) {
386 iUnassignedValue = value.variable().getAssignment();
387 unassigned(iteration, value.variable().getAssignment());
388 }
389 iOldVariable = value.variable();
390 }
391 }
392
393 /**
394 * Called after a value is assigned to a variable.
395 */
396 @Override
397 public void afterAssigned(long iteration, Enrollment value) {
398 iOldVariable = null;
399 iUnassignedValue = null;
400 if (value != null) {
401 assigned(iteration, value);
402 }
403 }
404
405 /**
406 * Called after a value is unassigned from a variable.
407 */
408 @Override
409 public void afterUnassigned(long iteration, Enrollment value) {
410 if (value != null && !value.equals(iUnassignedValue)) {
411 unassigned(iteration, value);
412 }
413 }
414
415 /** A representation of a time overlapping conflict */
416 public static class Conflict {
417 private int iShare;
418 private Student iStudent;
419 private Assignment iA1, iA2;
420 private Enrollment iE1, iE2;
421 private int iHashCode;
422
423 /**
424 * Constructor
425 *
426 * @param student
427 * related student
428 * @param a1
429 * first conflicting section
430 * @param a2
431 * second conflicting section
432 */
433 public Conflict(Student student, int share, Enrollment e1, Assignment a1, Enrollment e2, Assignment a2) {
434 iStudent = student;
435 if (a1.compareById(a2) < 0 ) {
436 iA1 = a1;
437 iA2 = a2;
438 iE1 = e1;
439 iE2 = e2;
440 } else {
441 iA1 = a2;
442 iA2 = a1;
443 iE1 = e2;
444 iE2 = e1;
445 }
446 iHashCode = (iStudent.getId() + ":" + iA1.getId() + ":" + iA2.getId()).hashCode();
447 iShare = share;
448 }
449
450 /** Related student */
451 public Student getStudent() {
452 return iStudent;
453 }
454
455 /** First section */
456 public Assignment getS1() {
457 return iA1;
458 }
459
460 /** Second section */
461 public Assignment getS2() {
462 return iA2;
463 }
464
465 /** First request */
466 public Request getR1() {
467 return iE1.getRequest();
468 }
469
470 /** Second request */
471 public Request getR2() {
472 return iE2.getRequest();
473 }
474
475 /** First enrollment */
476 public Enrollment getE1() {
477 return iE1;
478 }
479
480 /** Second enrollment */
481 public Enrollment getE2() {
482 return iE2;
483 }
484
485 @Override
486 public int hashCode() {
487 return iHashCode;
488 }
489
490 /** The number of overlapping slots against the number of slots of the smallest section */
491 public int getShare() {
492 return iShare;
493 }
494
495 @Override
496 public boolean equals(Object o) {
497 if (o == null || !(o instanceof Conflict)) return false;
498 Conflict c = (Conflict) o;
499 return getStudent().equals(c.getStudent()) && getS1().equals(c.getS1()) && getS2().equals(c.getS2());
500 }
501
502 @Override
503 public String toString() {
504 return getStudent() + ": (s:" + getShare() + ") " + getS1() + " -- " + getS2();
505 }
506 }
507 }