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