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