001 package net.sf.cpsolver.coursett.model; 002 003 import java.util.ArrayList; 004 import java.util.Collections; 005 import java.util.Comparator; 006 import java.util.HashSet; 007 import java.util.HashMap; 008 import java.util.Iterator; 009 import java.util.List; 010 import java.util.Map; 011 import java.util.Set; 012 013 import net.sf.cpsolver.coursett.Constants; 014 import net.sf.cpsolver.coursett.constraint.ClassLimitConstraint; 015 import net.sf.cpsolver.coursett.constraint.DepartmentSpreadConstraint; 016 import net.sf.cpsolver.coursett.constraint.GroupConstraint; 017 import net.sf.cpsolver.coursett.constraint.IgnoreStudentConflictsConstraint; 018 import net.sf.cpsolver.coursett.constraint.InstructorConstraint; 019 import net.sf.cpsolver.coursett.constraint.JenrlConstraint; 020 import net.sf.cpsolver.coursett.constraint.RoomConstraint; 021 import net.sf.cpsolver.coursett.constraint.SpreadConstraint; 022 import net.sf.cpsolver.coursett.constraint.WeakeningConstraint; 023 import net.sf.cpsolver.coursett.criteria.StudentCommittedConflict; 024 import net.sf.cpsolver.coursett.criteria.StudentConflict; 025 import net.sf.cpsolver.ifs.constant.ConstantVariable; 026 import net.sf.cpsolver.ifs.model.Constraint; 027 import net.sf.cpsolver.ifs.model.Variable; 028 import net.sf.cpsolver.ifs.util.DistanceMetric; 029 030 /** 031 * Lecture (variable). 032 * 033 * @version CourseTT 1.2 (University Course Timetabling)<br> 034 * Copyright (C) 2006 - 2010 Tomas Muller<br> 035 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 036 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 037 * <br> 038 * This library is free software; you can redistribute it and/or modify 039 * it under the terms of the GNU Lesser General Public License as 040 * published by the Free Software Foundation; either version 3 of the 041 * License, or (at your option) any later version. <br> 042 * <br> 043 * This library is distributed in the hope that it will be useful, but 044 * WITHOUT ANY WARRANTY; without even the implied warranty of 045 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 046 * Lesser General Public License for more details. <br> 047 * <br> 048 * You should have received a copy of the GNU Lesser General Public 049 * License along with this library; if not see 050 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 051 */ 052 053 public class Lecture extends Variable<Lecture, Placement> implements ConstantVariable { 054 private Long iClassId; 055 private Long iSolverGroupId; 056 private Long iSchedulingSubpartId; 057 private String iName; 058 private Long iDept; 059 private Long iScheduler; 060 private List<TimeLocation> iTimeLocations; 061 private List<RoomLocation> iRoomLocations; 062 private String iNote = null; 063 064 private int iMinClassLimit; 065 private int iMaxClassLimit; 066 private double iRoomToLimitRatio; 067 private int iNrRooms; 068 private int iOrd; 069 070 private Set<Student> iStudents = new HashSet<Student>(); 071 private DepartmentSpreadConstraint iDeptSpreadConstraint = null; 072 private Set<SpreadConstraint> iSpreadConstraints = new HashSet<SpreadConstraint>(); 073 private Set<Constraint<Lecture, Placement>> iWeakeningConstraints = new HashSet<Constraint<Lecture, Placement>>(); 074 private List<InstructorConstraint> iInstructorConstraints = new ArrayList<InstructorConstraint>(); 075 private Set<Long> iIgnoreStudentConflictsWith = null; 076 private ClassLimitConstraint iClassLimitConstraint = null; 077 078 private Lecture iParent = null; 079 private HashMap<Long, List<Lecture>> iChildren = null; 080 private java.util.List<Lecture> iSameSubpartLectures = null; 081 private Configuration iParentConfiguration = null; 082 083 private Set<JenrlConstraint> iActiveJenrls = new HashSet<JenrlConstraint>(); 084 private List<JenrlConstraint> iJenrlConstraints = new ArrayList<JenrlConstraint>(); 085 private HashMap<Lecture, JenrlConstraint> iJenrlConstraintsHash = new HashMap<Lecture, JenrlConstraint>(); 086 private HashMap<Placement, Integer> iCommitedConflicts = new HashMap<Placement, Integer>(); 087 private Set<GroupConstraint> iGroupConstraints = new HashSet<GroupConstraint>(); 088 private Set<GroupConstraint> iHardGroupSoftConstraints = new HashSet<GroupConstraint>(); 089 private Set<GroupConstraint> iCanShareRoomGroupConstraints = new HashSet<GroupConstraint>(); 090 091 public boolean iCommitted = false; 092 093 public static boolean sSaveMemory = false; 094 public static boolean sAllowBreakHard = false; 095 096 private Integer iCacheMinRoomSize = null; 097 private Integer iCacheMaxRoomSize = null; 098 private Integer iCacheMaxAchievableClassLimit = null; 099 100 /** 101 * Constructor 102 * 103 * @param id 104 * unique identification 105 * @param name 106 * class name 107 * @param timeLocations 108 * set of time locations 109 * @param roomLocations 110 * set of room location 111 * @param initialPlacement 112 * initial placement 113 */ 114 public Lecture(Long id, Long solverGroupId, Long schedulingSubpartId, String name, 115 java.util.List<TimeLocation> timeLocations, java.util.List<RoomLocation> roomLocations, int nrRooms, 116 Placement initialPlacement, int minClassLimit, int maxClassLimit, double room2limitRatio) { 117 super(initialPlacement); 118 iClassId = id; 119 iSchedulingSubpartId = schedulingSubpartId; 120 iTimeLocations = new ArrayList<TimeLocation>(timeLocations); 121 iRoomLocations = new ArrayList<RoomLocation>(roomLocations); 122 iName = name; 123 iMinClassLimit = minClassLimit; 124 iMaxClassLimit = maxClassLimit; 125 iRoomToLimitRatio = room2limitRatio; 126 iNrRooms = nrRooms; 127 iSolverGroupId = solverGroupId; 128 } 129 130 public Lecture(Long id, Long solverGroupId, String name) { 131 super(null); 132 iClassId = id; 133 iSolverGroupId = solverGroupId; 134 iName = name; 135 } 136 137 public Long getSolverGroupId() { 138 return iSolverGroupId; 139 } 140 141 /** 142 * Add active jenrl constraint (active mean that there is at least one 143 * student between its classes) 144 */ 145 public void addActiveJenrl(JenrlConstraint constr) { 146 iActiveJenrls.add(constr); 147 } 148 149 /** 150 * Active jenrl constraints (active mean that there is at least one student 151 * between its classes) 152 */ 153 public Set<JenrlConstraint> activeJenrls() { 154 return iActiveJenrls; 155 } 156 157 /** 158 * Remove active jenrl constraint (active mean that there is at least one 159 * student between its classes) 160 */ 161 public void removeActiveJenrl(JenrlConstraint constr) { 162 iActiveJenrls.remove(constr); 163 } 164 165 /** Class id */ 166 public Long getClassId() { 167 return iClassId; 168 } 169 170 public Long getSchedulingSubpartId() { 171 return iSchedulingSubpartId; 172 } 173 174 /** Class name */ 175 @Override 176 public String getName() { 177 return iName; 178 } 179 180 /** Class id */ 181 @Override 182 public long getId() { 183 return iClassId.longValue(); 184 } 185 186 /** Instructor name */ 187 public List<String> getInstructorNames() { 188 List<String> ret = new ArrayList<String>(); 189 for (InstructorConstraint ic : iInstructorConstraints) { 190 ret.add(ic.getName()); 191 } 192 return ret; 193 } 194 195 public String getInstructorName() { 196 StringBuffer sb = new StringBuffer(); 197 for (InstructorConstraint ic : iInstructorConstraints) { 198 if (sb.length() > 0) 199 sb.append(", "); 200 sb.append(ic.getName()); 201 } 202 return sb.toString(); 203 } 204 205 /** List of enrolled students */ 206 public Set<Student> students() { 207 return iStudents; 208 } 209 210 public double nrWeightedStudents() { 211 double w = 0.0; 212 for (Student s : iStudents) { 213 w += s.getOfferingWeight(getConfiguration()); 214 } 215 return w; 216 } 217 218 /** Add an enrolled student */ 219 public void addStudent(Student student) { 220 if (!iStudents.add(student)) 221 return; 222 if (getAssignment() != null && getModel() != null) 223 getModel().getCriterion(StudentCommittedConflict.class).inc(student.countConflictPlacements(getAssignment())); 224 iCommitedConflicts.clear(); 225 } 226 227 public void removeStudent(Student student) { 228 if (!iStudents.remove(student)) 229 return; 230 if (getAssignment() != null && getModel() != null) 231 if (getAssignment() != null && getModel() != null) 232 getModel().getCriterion(StudentCommittedConflict.class).inc(-student.countConflictPlacements(getAssignment())); 233 iCommitedConflicts.clear(); 234 } 235 236 /** Returns true if the given student is enrolled */ 237 public boolean hasStudent(Student student) { 238 return iStudents.contains(student); 239 } 240 241 /** Set of lectures of the same class (only section is different) */ 242 public void setSameSubpartLectures(java.util.List<Lecture> sameSubpartLectures) { 243 iSameSubpartLectures = sameSubpartLectures; 244 } 245 246 /** Set of lectures of the same class (only section is different) */ 247 public java.util.List<Lecture> sameSubpartLectures() { 248 return iSameSubpartLectures; 249 } 250 251 /** List of students enrolled in this class as well as in the given class */ 252 public Set<Student> sameStudents(Lecture lecture) { 253 JenrlConstraint jenrl = jenrlConstraint(lecture); 254 return (jenrl == null ? new HashSet<Student>() : jenrl.getStudents()); 255 } 256 257 /** List of students of this class in conflict with the given assignment */ 258 public Set<Student> conflictStudents(Placement value) { 259 if (value == null) 260 return new HashSet<Student>(); 261 if (value.equals(getAssignment())) 262 return conflictStudents(); 263 Set<Student> ret = new HashSet<Student>(); 264 for (JenrlConstraint jenrl : jenrlConstraints()) { 265 if (jenrl.jenrl(this, value) > 0) 266 ret.addAll(sameStudents(jenrl.another(this))); 267 } 268 return ret; 269 } 270 271 /** 272 * List of students of this class which are in conflict with any other 273 * assignment 274 */ 275 public Set<Student> conflictStudents() { 276 Set<Student> ret = new HashSet<Student>(); 277 if (getAssignment() == null) 278 return ret; 279 for (JenrlConstraint jenrl : activeJenrls()) { 280 ret.addAll(sameStudents(jenrl.another(this))); 281 } 282 Placement placement = getAssignment(); 283 for (Student student : students()) { 284 if (student.countConflictPlacements(placement) > 0) 285 ret.add(student); 286 } 287 return ret; 288 } 289 290 /** 291 * Lectures different from this one, where it is student conflict of the 292 * given student between this and the lecture 293 */ 294 public List<Lecture> conflictLectures(Student student) { 295 List<Lecture> ret = new ArrayList<Lecture>(); 296 if (getAssignment() == null) 297 return ret; 298 for (JenrlConstraint jenrl : activeJenrls()) { 299 Lecture lect = jenrl.another(this); 300 if (lect.students().contains(student)) 301 ret.add(lect); 302 } 303 return ret; 304 } 305 306 /** True if this lecture is in a student conflict with the given student */ 307 public int isInConflict(Student student) { 308 if (getAssignment() == null) 309 return 0; 310 int ret = 0; 311 for (JenrlConstraint jenrl : activeJenrls()) { 312 Lecture lect = jenrl.another(this); 313 if (lect.students().contains(student)) 314 ret++; 315 } 316 return ret; 317 } 318 319 private void computeValues(List<Placement> values, boolean allowBreakHard, TimeLocation timeLocation, 320 List<RoomLocation> roomLocations, int idx) { 321 if (roomLocations.size() == iNrRooms) { 322 Placement p = new Placement(this, timeLocation, roomLocations); 323 p.setVariable(this); 324 if (sSaveMemory && !isValid(p)) 325 return; 326 if (getInitialAssignment() != null && p.equals(getInitialAssignment())) 327 setInitialAssignment(p); 328 if (getAssignment() != null && getAssignment().equals(p)) 329 iValue = getAssignment(); 330 if (getBestAssignment() != null && getBestAssignment().equals(p)) 331 setBestAssignment(p); 332 values.add(p); 333 return; 334 } 335 for (int i = idx; i < iRoomLocations.size(); i++) { 336 RoomLocation roomLocation = iRoomLocations.get(i); 337 if (!allowBreakHard 338 && Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(roomLocation 339 .getPreference()))) 340 continue; 341 342 if (roomLocation.getRoomConstraint() != null 343 && !roomLocation.getRoomConstraint().isAvailable(this, timeLocation, getScheduler())) 344 continue; 345 roomLocations.add(roomLocation); 346 computeValues(values, allowBreakHard, timeLocation, roomLocations, i + 1); 347 roomLocations.remove(roomLocations.size() - 1); 348 } 349 } 350 351 /** Domain -- all combinations of room and time locations */ 352 public List<Placement> computeValues(boolean allowBreakHard) { 353 List<Placement> values = new ArrayList<Placement>(iRoomLocations.size() * iTimeLocations.size()); 354 for (TimeLocation timeLocation : iTimeLocations) { 355 if (!allowBreakHard 356 && Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(timeLocation 357 .getPreference()))) 358 continue; 359 if (timeLocation.getPreference() > 500) 360 continue; 361 boolean notAvailable = false; 362 for (InstructorConstraint ic : getInstructorConstraints()) { 363 if (!ic.isAvailable(this, timeLocation)) { 364 notAvailable = true; 365 break; 366 } 367 } 368 if (notAvailable) 369 continue; 370 if (iNrRooms == 0) { 371 Placement p = new Placement(this, timeLocation, (RoomLocation) null); 372 for (InstructorConstraint ic : getInstructorConstraints()) { 373 if (!ic.isAvailable(this, p)) { 374 notAvailable = true; 375 break; 376 } 377 } 378 if (notAvailable) 379 continue; 380 p.setVariable(this); 381 if (sSaveMemory && !isValid(p)) 382 continue; 383 if (getInitialAssignment() != null && p.equals(getInitialAssignment())) 384 setInitialAssignment(p); 385 if (getAssignment() != null && getAssignment().equals(p)) 386 iValue = getAssignment(); 387 if (getBestAssignment() != null && getBestAssignment().equals(p)) 388 setBestAssignment(p); 389 values.add(p); 390 } else if (iNrRooms == 1) { 391 for (RoomLocation roomLocation : iRoomLocations) { 392 if (!allowBreakHard 393 && Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(roomLocation 394 .getPreference()))) 395 continue; 396 if (roomLocation.getPreference() > 500) 397 continue; 398 if (roomLocation.getRoomConstraint() != null 399 && !roomLocation.getRoomConstraint().isAvailable(this, timeLocation, getScheduler())) 400 continue; 401 Placement p = new Placement(this, timeLocation, roomLocation); 402 p.setVariable(this); 403 if (sSaveMemory && !isValid(p)) 404 continue; 405 if (getInitialAssignment() != null && p.equals(getInitialAssignment())) 406 setInitialAssignment(p); 407 if (getAssignment() != null && getAssignment().equals(p)) 408 iValue = getAssignment(); 409 if (getBestAssignment() != null && getBestAssignment().equals(p)) 410 setBestAssignment(p); 411 values.add(p); 412 } 413 } else { 414 computeValues(values, allowBreakHard, timeLocation, new ArrayList<RoomLocation>(iNrRooms), 0); 415 } 416 } 417 return values; 418 } 419 420 public void clearValueCache() { 421 super.setValues(null); 422 } 423 424 /** All values */ 425 @Override 426 public List<Placement> values() { 427 if (super.values() == null) { 428 if (getInitialAssignment() != null && iTimeLocations.size() == 1 && iRoomLocations.size() == getNrRooms()) { 429 List<Placement> values = new ArrayList<Placement>(1); 430 values.add(getInitialAssignment()); 431 setValues(values); 432 } else { 433 if (isCommitted() || !sSaveMemory) 434 setValues(computeValues(sAllowBreakHard)); 435 } 436 } 437 if (isCommitted()) 438 return super.values(); 439 if (sSaveMemory) { 440 return computeValues(sAllowBreakHard); 441 } else 442 return super.values(); 443 } 444 445 @Override 446 public boolean equals(Object o) { 447 if (o == null || !(o instanceof Lecture)) 448 return false; 449 return getClassId().equals(((Lecture) o).getClassId()); 450 } 451 452 /** Best time preference of this lecture */ 453 private Double iBestTimePreferenceCache = null; 454 455 public double getBestTimePreference() { 456 if (iBestTimePreferenceCache == null) { 457 double ret = Double.MAX_VALUE; 458 for (TimeLocation time : iTimeLocations) { 459 ret = Math.min(ret, time.getNormalizedPreference()); 460 } 461 iBestTimePreferenceCache = new Double(ret); 462 } 463 return iBestTimePreferenceCache.doubleValue(); 464 } 465 466 /** Best room preference of this lecture */ 467 public int getBestRoomPreference() { 468 int ret = Integer.MAX_VALUE; 469 for (RoomLocation room : iRoomLocations) { 470 ret = Math.min(ret, room.getPreference()); 471 } 472 return ret; 473 } 474 475 /** 476 * Number of student conflicts caused by the given assignment of this 477 * lecture 478 */ 479 public int countStudentConflicts(Placement value) { 480 int studentConflictsSum = 0; 481 for (JenrlConstraint jenrl : jenrlConstraints()) { 482 studentConflictsSum += jenrl.jenrl(this, value); 483 } 484 return studentConflictsSum; 485 } 486 487 public int countStudentConflictsOfTheSameProblem(Placement value) { 488 int studentConflictsSum = 0; 489 for (JenrlConstraint jenrl : jenrlConstraints()) { 490 if (!jenrl.isOfTheSameProblem()) 491 continue; 492 studentConflictsSum += jenrl.jenrl(this, value); 493 } 494 return studentConflictsSum; 495 } 496 497 public int countHardStudentConflicts(Placement value) { 498 int studentConflictsSum = 0; 499 if (!isSingleSection()) 500 return 0; 501 for (JenrlConstraint jenrl : jenrlConstraints()) { 502 if (!jenrl.areStudentConflictsHard()) 503 continue; 504 studentConflictsSum += jenrl.jenrl(this, value); 505 } 506 return studentConflictsSum; 507 } 508 509 public int countCommittedStudentConflictsOfTheSameProblem(Placement value) { 510 int studentConflictsSum = 0; 511 for (JenrlConstraint jenrl : jenrlConstraints()) { 512 if (!jenrl.isOfTheSameProblem()) 513 continue; 514 if (!jenrl.areStudentConflictsCommitted()) 515 continue; 516 studentConflictsSum += jenrl.jenrl(this, value); 517 } 518 return studentConflictsSum; 519 } 520 521 public int countCommittedStudentConflicts(Placement value) { 522 int studentConflictsSum = 0; 523 for (JenrlConstraint jenrl : jenrlConstraints()) { 524 if (!jenrl.areStudentConflictsCommitted()) 525 continue; 526 studentConflictsSum += jenrl.jenrl(this, value); 527 } 528 return studentConflictsSum; 529 } 530 531 public int countHardStudentConflictsOfTheSameProblem(Placement value) { 532 int studentConflictsSum = 0; 533 for (JenrlConstraint jenrl : jenrlConstraints()) { 534 if (!jenrl.isOfTheSameProblem()) 535 continue; 536 if (!jenrl.areStudentConflictsHard()) 537 continue; 538 studentConflictsSum += jenrl.jenrl(this, value); 539 } 540 return studentConflictsSum; 541 } 542 543 public int countDistanceStudentConflicts(Placement value) { 544 int studentConflictsSum = 0; 545 for (JenrlConstraint jenrl : jenrlConstraints()) { 546 if (!jenrl.areStudentConflictsDistance(value)) 547 continue; 548 studentConflictsSum += jenrl.jenrl(this, value); 549 } 550 return studentConflictsSum; 551 } 552 553 public int countDistanceStudentConflictsOfTheSameProblem(Placement value) { 554 int studentConflictsSum = 0; 555 for (JenrlConstraint jenrl : jenrlConstraints()) { 556 if (!jenrl.isOfTheSameProblem()) 557 continue; 558 if (!jenrl.areStudentConflictsDistance(value)) 559 continue; 560 studentConflictsSum += jenrl.jenrl(this, value); 561 } 562 return studentConflictsSum; 563 } 564 565 private DistanceMetric getDistanceMetric() { 566 return ((TimetableModel)getModel()).getDistanceMetric(); 567 } 568 569 /** 570 * Number of student conflicts caused by the initial assignment of this 571 * lecture 572 */ 573 public int countInitialStudentConflicts() { 574 Placement value = getInitialAssignment(); 575 if (value == null) 576 return 0; 577 int studentConflictsSum = 0; 578 for (JenrlConstraint jenrl : jenrlConstraints()) { 579 Lecture another = jenrl.another(this); 580 if (another.getInitialAssignment() != null) 581 if (JenrlConstraint.isInConflict(value, another.getInitialAssignment(), getDistanceMetric())) 582 studentConflictsSum += jenrl.getJenrl(); 583 } 584 return studentConflictsSum; 585 } 586 587 /** 588 * Table of student conflicts caused by the initial assignment of this 589 * lecture in format (another lecture, number) 590 */ 591 public Map<Lecture, Long> getInitialStudentConflicts() { 592 Placement value = getInitialAssignment(); 593 if (value == null) 594 return null; 595 Map<Lecture, Long> ret = new HashMap<Lecture, Long>(); 596 for (JenrlConstraint jenrl : jenrlConstraints()) { 597 Lecture another = jenrl.another(this); 598 if (another.getInitialAssignment() != null) 599 if (JenrlConstraint.isInConflict(value, another.getInitialAssignment(), getDistanceMetric())) 600 ret.put(another, jenrl.getJenrl()); 601 } 602 return ret; 603 } 604 605 /** 606 * List of student conflicts caused by the initial assignment of this 607 * lecture 608 */ 609 public Set<Student> initialStudentConflicts() { 610 Placement value = getInitialAssignment(); 611 if (value == null) 612 return null; 613 HashSet<Student> ret = new HashSet<Student>(); 614 for (JenrlConstraint jenrl : jenrlConstraints()) { 615 Lecture another = jenrl.another(this); 616 if (another.getInitialAssignment() != null) 617 if (JenrlConstraint.isInConflict(value, another.getInitialAssignment(), getDistanceMetric())) 618 ret.addAll(sameStudents(another)); 619 } 620 return ret; 621 } 622 623 @Override 624 public void addContstraint(Constraint<Lecture, Placement> constraint) { 625 super.addContstraint(constraint); 626 627 if (constraint instanceof WeakeningConstraint) 628 iWeakeningConstraints.add(constraint); 629 630 if (constraint instanceof JenrlConstraint) { 631 JenrlConstraint jenrl = (JenrlConstraint) constraint; 632 Lecture another = jenrl.another(this); 633 if (another != null) { 634 iJenrlConstraints.add(jenrl); 635 another.iJenrlConstraints.add(jenrl); 636 iJenrlConstraintsHash.put(another, (JenrlConstraint) constraint); 637 another.iJenrlConstraintsHash.put(this, (JenrlConstraint) constraint); 638 } 639 } else if (constraint instanceof DepartmentSpreadConstraint) 640 iDeptSpreadConstraint = (DepartmentSpreadConstraint) constraint; 641 else if (constraint instanceof SpreadConstraint) 642 iSpreadConstraints.add((SpreadConstraint) constraint); 643 else if (constraint instanceof InstructorConstraint) { 644 InstructorConstraint ic = (InstructorConstraint) constraint; 645 if (ic.getResourceId() != null && ic.getResourceId().longValue() > 0) 646 iInstructorConstraints.add(ic); 647 } else if (constraint instanceof ClassLimitConstraint) 648 iClassLimitConstraint = (ClassLimitConstraint) constraint; 649 else if (constraint instanceof GroupConstraint) { 650 GroupConstraint gc = (GroupConstraint) constraint; 651 if (gc.canShareRoom()) { 652 iCanShareRoomGroupConstraints.add((GroupConstraint) constraint); 653 } else { 654 iGroupConstraints.add((GroupConstraint) constraint); 655 if (Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(gc.getPreference())) 656 || Constants.sPreferenceRequired.equals(Constants 657 .preferenceLevel2preference(gc.getPreference()))) 658 iHardGroupSoftConstraints.add((GroupConstraint) constraint); 659 } 660 } 661 } 662 663 @Override 664 public void removeContstraint(Constraint<Lecture, Placement> constraint) { 665 super.removeContstraint(constraint); 666 667 if (constraint instanceof WeakeningConstraint) 668 iWeakeningConstraints.remove(constraint); 669 670 if (constraint instanceof JenrlConstraint) { 671 JenrlConstraint jenrl = (JenrlConstraint) constraint; 672 Lecture another = jenrl.another(this); 673 if (another != null) { 674 iJenrlConstraints.remove(jenrl); 675 another.iJenrlConstraints.remove(jenrl); 676 iJenrlConstraintsHash.remove(another); 677 another.iJenrlConstraintsHash.remove(this); 678 } 679 } else if (constraint instanceof GroupConstraint) { 680 iCanShareRoomGroupConstraints.remove(constraint); 681 iHardGroupSoftConstraints.remove(constraint); 682 iGroupConstraints.remove(constraint); 683 } else if (constraint instanceof DepartmentSpreadConstraint) 684 iDeptSpreadConstraint = null; 685 else if (constraint instanceof SpreadConstraint) 686 iSpreadConstraints.remove(constraint); 687 else if (constraint instanceof InstructorConstraint) 688 iInstructorConstraints.remove(constraint); 689 else if (constraint instanceof ClassLimitConstraint) 690 iClassLimitConstraint = null; 691 } 692 693 /** All JENRL constraints of this lecture */ 694 public JenrlConstraint jenrlConstraint(Lecture another) { 695 /* 696 * for (Enumeration e=iJenrlConstraints.elements();e.hasMoreElements();) 697 * { JenrlConstraint jenrl = (JenrlConstraint)e.nextElement(); if 698 * (jenrl.another(this).equals(another)) return jenrl; } return null; 699 */ 700 return iJenrlConstraintsHash.get(another); 701 } 702 703 public List<JenrlConstraint> jenrlConstraints() { 704 return iJenrlConstraints; 705 } 706 707 public int minClassLimit() { 708 return iMinClassLimit; 709 } 710 711 public int maxClassLimit() { 712 return iMaxClassLimit; 713 } 714 715 public int maxAchievableClassLimit() { 716 if (iCacheMaxAchievableClassLimit != null) 717 return iCacheMaxAchievableClassLimit.intValue(); 718 719 int maxAchievableClassLimit = Math.min(maxClassLimit(), (int) Math.floor(maxRoomSize() / roomToLimitRatio())); 720 721 if (hasAnyChildren()) { 722 723 for (Long subpartId: getChildrenSubpartIds()) { 724 int maxAchievableChildrenLimit = 0; 725 726 for (Lecture child : getChildren(subpartId)) { 727 maxAchievableChildrenLimit += child.maxAchievableClassLimit(); 728 } 729 730 maxAchievableClassLimit = Math.min(maxAchievableClassLimit, maxAchievableChildrenLimit); 731 } 732 } 733 734 maxAchievableClassLimit = Math.max(minClassLimit(), maxAchievableClassLimit); 735 iCacheMaxAchievableClassLimit = new Integer(maxAchievableClassLimit); 736 return maxAchievableClassLimit; 737 } 738 739 public int classLimit() { 740 if (minClassLimit() == maxClassLimit()) 741 return minClassLimit(); 742 return classLimit(null, null); 743 } 744 745 public int classLimit(Placement assignment, Set<Placement> conflicts) { 746 Placement a = getAssignment(); 747 if (assignment != null && assignment.variable().equals(this)) 748 a = assignment; 749 if (conflicts != null && a != null && conflicts.contains(a)) 750 a = null; 751 int classLimit = (a == null ? maxAchievableClassLimit() : Math.min(maxClassLimit(), (int) Math.floor(a.getRoomSize() / roomToLimitRatio()))); 752 753 if (!hasAnyChildren()) 754 return classLimit; 755 756 for (Long subpartId: getChildrenSubpartIds()) { 757 int childrenClassLimit = 0; 758 759 for (Lecture child : getChildren(subpartId)) { 760 childrenClassLimit += child.classLimit(assignment, conflicts); 761 } 762 763 classLimit = Math.min(classLimit, childrenClassLimit); 764 } 765 766 return Math.max(minClassLimit(), classLimit); 767 } 768 769 public double roomToLimitRatio() { 770 return iRoomToLimitRatio; 771 } 772 773 public int minRoomUse() { 774 return (int) Math.ceil(iMinClassLimit * iRoomToLimitRatio); 775 } 776 777 public int maxRoomUse() { 778 return (int) Math.ceil(iMaxClassLimit * iRoomToLimitRatio); 779 } 780 781 @Override 782 public String toString() { 783 return getName(); 784 } 785 786 public String getValuesString() { 787 StringBuffer sb = new StringBuffer(); 788 for (Placement p : values()) { 789 if (sb.length() > 0) 790 sb.append(", "); 791 sb.append(p.getName()); 792 } 793 return sb.toString(); 794 } 795 796 /** Controlling Course Offering Department */ 797 public Long getDepartment() { 798 return iDept; 799 } 800 801 /** Controlling Course Offering Department */ 802 public void setDepartment(Long dept) { 803 iDept = dept; 804 } 805 806 /** Scheduler (Managing Department) */ 807 public Long getScheduler() { 808 return iScheduler; 809 } 810 811 /** Scheduler (Managing Department) */ 812 public void setScheduler(Long scheduler) { 813 iScheduler = scheduler; 814 } 815 816 /** Departmental spreading constraint */ 817 public DepartmentSpreadConstraint getDeptSpreadConstraint() { 818 return iDeptSpreadConstraint; 819 } 820 821 /** Instructor constraint */ 822 public List<InstructorConstraint> getInstructorConstraints() { 823 return iInstructorConstraints; 824 } 825 826 public ClassLimitConstraint getClassLimitConstraint() { 827 return iClassLimitConstraint; 828 } 829 830 public Set<SpreadConstraint> getSpreadConstraints() { 831 return iSpreadConstraints; 832 } 833 834 public Set<Constraint<Lecture, Placement>> getWeakeningConstraints() { 835 return iWeakeningConstraints; 836 } 837 838 /** All room locations */ 839 public List<RoomLocation> roomLocations() { 840 return iRoomLocations; 841 } 842 843 /** All time locations */ 844 public List<TimeLocation> timeLocations() { 845 return iTimeLocations; 846 } 847 848 public int nrTimeLocations() { 849 int ret = 0; 850 for (TimeLocation time : iTimeLocations) { 851 if (!Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(time.getPreference()))) 852 ret++; 853 } 854 return ret; 855 } 856 857 public int nrRoomLocations() { 858 int ret = 0; 859 for (RoomLocation room : iRoomLocations) { 860 if (!Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(room.getPreference()))) 861 ret++; 862 } 863 return ret; 864 } 865 866 public int nrValues() { 867 int ret = 0; 868 for (Placement placement : values()) { 869 if (!Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(placement 870 .getRoomPreference())) 871 && !Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(placement 872 .getTimeLocation().getPreference()))) 873 ret++; 874 } 875 return ret; 876 } 877 878 public int nrValues(TimeLocation time) { 879 int ret = 0; 880 for (RoomLocation room : iRoomLocations) { 881 if (!Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(room.getPreference())) 882 && (room.getRoomConstraint() == null || room.getRoomConstraint().isAvailable(this, time, 883 getScheduler()))) 884 ret++; 885 } 886 return ret; 887 } 888 889 public int nrValues(RoomLocation room) { 890 int ret = 0; 891 for (TimeLocation time : iTimeLocations) { 892 if (!Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(time.getPreference())) 893 && (room.getRoomConstraint() == null || room.getRoomConstraint().isAvailable(this, time, 894 getScheduler()))) 895 ret++; 896 } 897 return ret; 898 } 899 900 public int nrValues(List<RoomLocation> rooms) { 901 int ret = 0; 902 for (TimeLocation time : iTimeLocations) { 903 boolean available = true; 904 for (RoomLocation room : rooms) { 905 if (Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(time.getPreference())) 906 || (room.getRoomConstraint() != null && !room.getRoomConstraint().isAvailable(this, time, 907 getScheduler()))) 908 available = false; 909 } 910 if (available) 911 ret++; 912 } 913 return ret; 914 } 915 916 public boolean allowBreakHard() { 917 return sAllowBreakHard; 918 } 919 920 public int getNrRooms() { 921 return iNrRooms; 922 } 923 924 public Lecture getParent() { 925 return iParent; 926 } 927 928 public void setParent(Lecture parent) { 929 iParent = parent; 930 iParent.addChild(this); 931 } 932 933 public boolean hasParent() { 934 return (iParent != null); 935 } 936 937 public boolean hasChildren(Long subpartId) { 938 return (iChildren != null && iChildren.get(subpartId) != null && !iChildren.get(subpartId).isEmpty()); 939 } 940 941 public boolean hasAnyChildren() { 942 return (iChildren != null && !iChildren.isEmpty()); 943 } 944 945 public List<Lecture> getChildren(Long subpartId) { 946 return iChildren.get(subpartId); 947 } 948 949 public Set<Long> getChildrenSubpartIds() { 950 return (iChildren == null ? null : iChildren.keySet()); 951 } 952 953 private void addChild(Lecture child) { 954 if (iChildren == null) 955 iChildren = new HashMap<Long, List<Lecture>>(); 956 List<Lecture> childrenThisSubpart = iChildren.get(child.getSchedulingSubpartId()); 957 if (childrenThisSubpart == null) { 958 childrenThisSubpart = new ArrayList<Lecture>(); 959 iChildren.put(child.getSchedulingSubpartId(), childrenThisSubpart); 960 } 961 childrenThisSubpart.add(child); 962 } 963 964 public boolean isSingleSection() { 965 return (iSameSubpartLectures == null || iSameSubpartLectures.size() <= 1); 966 /* 967 if (iParent == null) 968 return (iSameSubpartLectures == null || iSameSubpartLectures.size() <= 1); 969 return (iParent.getChildren(getSchedulingSubpartId()).size() <= 1); 970 */ 971 } 972 973 public java.util.List<Lecture> sameStudentsLectures() { 974 return (hasParent() ? getParent().getChildren(getSchedulingSubpartId()) : sameSubpartLectures()); 975 } 976 977 public Lecture getChild(Student student, Long subpartId) { 978 if (!hasAnyChildren()) 979 return null; 980 List<Lecture> children = getChildren(subpartId); 981 if (children == null) 982 return null; 983 for (Lecture child : children) { 984 if (child.students().contains(student)) 985 return child; 986 } 987 return null; 988 } 989 990 public int getCommitedConflicts(Placement placement) { 991 Integer ret = iCommitedConflicts.get(placement); 992 if (ret == null) { 993 ret = new Integer(placement.getCommitedConflicts()); 994 iCommitedConflicts.put(placement, ret); 995 } 996 return ret.intValue(); 997 } 998 999 public Set<GroupConstraint> hardGroupSoftConstraints() { 1000 return iHardGroupSoftConstraints; 1001 } 1002 1003 public Set<GroupConstraint> groupConstraints() { 1004 return iGroupConstraints; 1005 } 1006 1007 public int minRoomSize() { 1008 if (iCacheMinRoomSize != null) 1009 return iCacheMinRoomSize.intValue(); 1010 if (getNrRooms() <= 1) { 1011 int min = Integer.MAX_VALUE; 1012 for (RoomLocation r : roomLocations()) { 1013 if (r.getPreference() <= Constants.sPreferenceLevelProhibited / 2) 1014 min = Math.min(min, r.getRoomSize()); 1015 } 1016 iCacheMinRoomSize = new Integer(min); 1017 return min; 1018 } else { 1019 List<RoomLocation> rooms = new ArrayList<RoomLocation>(); 1020 for (RoomLocation r: roomLocations()) 1021 if (r.getPreference() <= Constants.sPreferenceLevelProhibited / 2) 1022 rooms.add(r); 1023 Collections.sort(rooms, new Comparator<RoomLocation>() { 1024 @Override 1025 public int compare(RoomLocation r1, RoomLocation r2) { 1026 if (r1.getRoomSize() < r2.getRoomSize()) return -1; 1027 if (r1.getRoomSize() > r2.getRoomSize()) return 1; 1028 return r1.compareTo(r2); 1029 } 1030 }); 1031 int min = rooms.isEmpty() ? 0 : rooms.get(Math.min(getNrRooms(), rooms.size()) - 1).getRoomSize(); 1032 iCacheMinRoomSize = new Integer(min); 1033 return min; 1034 } 1035 } 1036 1037 public int maxRoomSize() { 1038 if (iCacheMaxRoomSize != null) 1039 return iCacheMaxRoomSize.intValue(); 1040 if (getNrRooms() <= 1) { 1041 int max = Integer.MIN_VALUE; 1042 for (RoomLocation r : roomLocations()) { 1043 if (r.getPreference() <= Constants.sPreferenceLevelProhibited / 2) 1044 max = Math.max(max, r.getRoomSize()); 1045 } 1046 iCacheMaxRoomSize = new Integer(max); 1047 return max; 1048 } else { 1049 List<RoomLocation> rooms = new ArrayList<RoomLocation>(); 1050 for (RoomLocation r: roomLocations()) 1051 if (r.getPreference() <= Constants.sPreferenceLevelProhibited / 2) rooms.add(r); 1052 Collections.sort(rooms, new Comparator<RoomLocation>() { 1053 @Override 1054 public int compare(RoomLocation r1, RoomLocation r2) { 1055 if (r1.getRoomSize() > r2.getRoomSize()) return -1; 1056 if (r1.getRoomSize() < r2.getRoomSize()) return 1; 1057 return r1.compareTo(r2); 1058 } 1059 }); 1060 int max = rooms.isEmpty() ? 0 : rooms.get(Math.min(getNrRooms(), rooms.size()) - 1).getRoomSize(); 1061 iCacheMaxRoomSize = new Integer(max); 1062 return max; 1063 } 1064 } 1065 1066 public boolean canShareRoom() { 1067 return (!iCanShareRoomGroupConstraints.isEmpty()); 1068 } 1069 1070 public boolean canShareRoom(Lecture other) { 1071 if (other.equals(this)) 1072 return true; 1073 for (GroupConstraint gc : iCanShareRoomGroupConstraints) { 1074 if (gc.variables().contains(other)) 1075 return true; 1076 } 1077 return false; 1078 } 1079 1080 public Set<GroupConstraint> canShareRoomConstraints() { 1081 return iCanShareRoomGroupConstraints; 1082 } 1083 1084 public boolean isSingleton() { 1085 return values().size() == 1; 1086 } 1087 1088 public boolean isValid(Placement placement) { 1089 TimetableModel model = (TimetableModel) getModel(); 1090 if (model == null) 1091 return true; 1092 if (model.hasConstantVariables()) { 1093 for (Placement confPlacement : model.conflictValuesSkipWeakeningConstraints(placement)) { 1094 Lecture lecture = confPlacement.variable(); 1095 if (lecture.isCommitted()) 1096 return false; 1097 if (confPlacement.equals(placement)) 1098 return false; 1099 } 1100 } else { 1101 if (model.conflictValues(placement).contains(placement)) 1102 return false; 1103 } 1104 return true; 1105 } 1106 1107 public String getNotValidReason(Placement placement) { 1108 TimetableModel model = (TimetableModel) getModel(); 1109 if (model == null) 1110 return "no model for class " + getName(); 1111 Map<Constraint<Lecture, Placement>, Set<Placement>> conflictConstraints = model.conflictConstraints(placement); 1112 for (Map.Entry<Constraint<Lecture, Placement>, Set<Placement>> entry : conflictConstraints.entrySet()) { 1113 Constraint<Lecture, Placement> constraint = entry.getKey(); 1114 Set<Placement> conflicts = entry.getValue(); 1115 String cname = constraint.getName(); 1116 if (constraint instanceof RoomConstraint) { 1117 cname = "Room " + constraint.getName(); 1118 } else if (constraint instanceof InstructorConstraint) { 1119 cname = "Instructor " + constraint.getName(); 1120 } else if (constraint instanceof GroupConstraint) { 1121 cname = "Distribution " + constraint.getName(); 1122 } else if (constraint instanceof DepartmentSpreadConstraint) { 1123 cname = "Balancing of department " + constraint.getName(); 1124 } else if (constraint instanceof SpreadConstraint) { 1125 cname = "Same subpart spread " + constraint.getName(); 1126 } else if (constraint instanceof ClassLimitConstraint) { 1127 cname = "Class limit " + constraint.getName(); 1128 } 1129 for (Placement confPlacement : conflicts) { 1130 Lecture lecture = confPlacement.variable(); 1131 if (lecture.isCommitted()) { 1132 return placement.getLongName() + " conflicts with " + lecture.getName() + " " 1133 + confPlacement.getLongName() + " due to constraint " + cname; 1134 } 1135 if (confPlacement.equals(placement)) { 1136 return placement.getLongName() + " is not valid due to constraint " + cname; 1137 } 1138 } 1139 } 1140 return null; 1141 } 1142 1143 public void purgeInvalidValues(boolean interactiveMode) { 1144 if (isCommitted() || Lecture.sSaveMemory) 1145 return; 1146 TimetableModel model = (TimetableModel) getModel(); 1147 if (model == null) 1148 return; 1149 List<Placement> newValues = new ArrayList<Placement>(values().size()); 1150 for (Placement placement : values()) { 1151 if (placement.isValid()) 1152 newValues.add(placement); 1153 } 1154 if (!interactiveMode && newValues.size() != values().size()) { 1155 for (Iterator<TimeLocation> i = timeLocations().iterator(); i.hasNext();) { 1156 TimeLocation timeLocation = i.next(); 1157 boolean hasPlacement = false; 1158 for (Placement placement : newValues) { 1159 if (timeLocation.equals(placement.getTimeLocation())) { 1160 hasPlacement = true; 1161 break; 1162 } 1163 } 1164 if (!hasPlacement) 1165 i.remove(); 1166 } 1167 for (Iterator<RoomLocation> i = roomLocations().iterator(); i.hasNext();) { 1168 RoomLocation roomLocation = i.next(); 1169 boolean hasPlacement = false; 1170 for (Placement placement : newValues) { 1171 if (placement.isMultiRoom()) { 1172 if (placement.getRoomLocations().contains(roomLocation)) { 1173 hasPlacement = true; 1174 break; 1175 } 1176 } else { 1177 if (roomLocation.equals(placement.getRoomLocation())) { 1178 hasPlacement = true; 1179 break; 1180 } 1181 } 1182 } 1183 if (!hasPlacement) 1184 i.remove(); 1185 } 1186 } 1187 setValues(newValues); 1188 } 1189 1190 public void setCommitted(boolean committed) { 1191 iCommitted = committed; 1192 } 1193 1194 public boolean isCommitted() { 1195 return iCommitted; 1196 } 1197 1198 @Override 1199 public boolean isConstant() { 1200 return iCommitted; 1201 } 1202 1203 public int getSpreadPenalty() { 1204 int spread = 0; 1205 for (SpreadConstraint sc : getSpreadConstraints()) { 1206 spread += sc.getPenalty(); 1207 } 1208 return spread; 1209 } 1210 1211 @Override 1212 public int hashCode() { 1213 return getClassId().hashCode(); 1214 } 1215 1216 public Configuration getConfiguration() { 1217 Lecture lecture = this; 1218 while (lecture.getParent() != null) 1219 lecture = lecture.getParent(); 1220 return lecture.iParentConfiguration; 1221 } 1222 1223 public void setConfiguration(Configuration configuration) { 1224 Lecture lecture = this; 1225 while (lecture.getParent() != null) 1226 lecture = lecture.getParent(); 1227 lecture.iParentConfiguration = configuration; 1228 configuration.addTopLecture(lecture); 1229 } 1230 1231 private int[] iMinMaxRoomPreference = null; 1232 1233 public int[] getMinMaxRoomPreference() { 1234 if (iMinMaxRoomPreference == null) { 1235 if (getNrRooms() <= 0 || roomLocations().isEmpty()) { 1236 iMinMaxRoomPreference = new int[] { 0, 0 }; 1237 } else { 1238 Integer minRoomPref = null, maxRoomPref = null; 1239 for (RoomLocation r : roomLocations()) { 1240 int pref = r.getPreference(); 1241 if (pref >= Constants.sPreferenceLevelRequired / 2 && pref <= Constants.sPreferenceLevelProhibited / 2) { 1242 minRoomPref = (minRoomPref == null ? pref : Math.min(minRoomPref, pref)); 1243 maxRoomPref = (maxRoomPref == null ? pref : Math.max(maxRoomPref, pref)); 1244 } 1245 } 1246 iMinMaxRoomPreference = new int[] { minRoomPref == null ? 0 : minRoomPref, maxRoomPref == null ? 0 : maxRoomPref }; 1247 } 1248 } 1249 return iMinMaxRoomPreference; 1250 } 1251 1252 private double[] iMinMaxTimePreference = null; 1253 1254 public double[] getMinMaxTimePreference() { 1255 if (iMinMaxTimePreference == null) { 1256 Double minTimePref = null, maxTimePref = null; 1257 for (TimeLocation t : timeLocations()) { 1258 double npref = t.getNormalizedPreference(); 1259 int pref = t.getPreference(); 1260 if (pref >= Constants.sPreferenceLevelRequired / 2 && pref <= Constants.sPreferenceLevelProhibited / 2) { 1261 minTimePref = (minTimePref == null ? npref : Math.min(minTimePref, npref)); 1262 maxTimePref = (maxTimePref == null ? npref : Math.max(maxTimePref, npref)); 1263 } 1264 } 1265 iMinMaxTimePreference = new double[] { minTimePref == null ? 0.0 : minTimePref, maxTimePref == null ? 0.0 : maxTimePref }; 1266 } 1267 return iMinMaxTimePreference; 1268 } 1269 1270 public void setOrd(int ord) { 1271 iOrd = ord; 1272 } 1273 1274 public int getOrd() { 1275 return iOrd; 1276 } 1277 1278 @Override 1279 public int compareTo(Lecture o) { 1280 int cmp = Double.compare(getOrd(), o.getOrd()); 1281 if (cmp != 0) 1282 return cmp; 1283 return super.compareTo(o); 1284 } 1285 1286 public String getNote() { 1287 return iNote; 1288 } 1289 1290 public void setNote(String note) { 1291 iNote = note; 1292 } 1293 1294 public boolean areStudentConflictsHard(Lecture other) { 1295 return StudentConflict.hard(this, other); 1296 } 1297 1298 public void clearIgnoreStudentConflictsWithCache() { 1299 iIgnoreStudentConflictsWith = null; 1300 } 1301 1302 /** 1303 * Returns true if there is {@link IgnoreStudentConflictsConstraint} between the two lectures. 1304 */ 1305 public boolean isToIgnoreStudentConflictsWith(Lecture other) { 1306 if (iIgnoreStudentConflictsWith == null) { 1307 iIgnoreStudentConflictsWith = new HashSet<Long>(); 1308 for (Constraint<Lecture, Placement> constraint: constraints()) { 1309 if (constraint instanceof IgnoreStudentConflictsConstraint) 1310 for (Lecture x: constraint.variables()) { 1311 if (!x.equals(this)) iIgnoreStudentConflictsWith.add(x.getClassId()); 1312 } 1313 } 1314 } 1315 return iIgnoreStudentConflictsWith.contains(other.getClassId()); 1316 } 1317 }