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