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