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    }