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