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 double 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 = 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 }