001package net.sf.cpsolver.studentsct.extension; 002 003import java.util.HashSet; 004import java.util.Set; 005 006import org.apache.log4j.Logger; 007 008import net.sf.cpsolver.ifs.extension.Extension; 009import net.sf.cpsolver.ifs.solver.Solver; 010import net.sf.cpsolver.ifs.util.DataProperties; 011import net.sf.cpsolver.studentsct.StudentSectioningModel; 012import net.sf.cpsolver.studentsct.model.Assignment; 013import net.sf.cpsolver.studentsct.model.Enrollment; 014import net.sf.cpsolver.studentsct.model.FreeTimeRequest; 015import net.sf.cpsolver.studentsct.model.Request; 016import net.sf.cpsolver.studentsct.model.Section; 017import 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 Tomáš Müller<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 047public 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}