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