001    package net.sf.cpsolver.exam.model;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.Collections;
006    import java.util.Comparator;
007    import java.util.HashSet;
008    import java.util.HashMap;
009    import java.util.Iterator;
010    import java.util.List;
011    import java.util.Locale;
012    import java.util.Map;
013    import java.util.Set;
014    import java.util.TreeSet;
015    
016    import net.sf.cpsolver.exam.criteria.DistributionPenalty;
017    import net.sf.cpsolver.exam.criteria.ExamRotationPenalty;
018    import net.sf.cpsolver.exam.criteria.RoomPenalty;
019    import net.sf.cpsolver.exam.criteria.RoomSizePenalty;
020    import net.sf.cpsolver.exam.criteria.RoomSplitPenalty;
021    import net.sf.cpsolver.ifs.model.Constraint;
022    import net.sf.cpsolver.ifs.model.Model;
023    import net.sf.cpsolver.ifs.model.Variable;
024    import net.sf.cpsolver.ifs.util.Progress;
025    import net.sf.cpsolver.ifs.util.ToolBox;
026    
027    import org.apache.log4j.Logger;
028    
029    /**
030     * Representation of an exam (problem variable). Each exam has defined a length
031     * (in minutes), type (whether it is a section or a course exam), seating type
032     * (whether it requires normal or alternate seating) and a maximal number of
033     * rooms. If the maximal number of rooms is zero, the exam will be timetabled
034     * only in time (it does not require a room). <br>
035     * <br>
036     * An exam can be only assigned to a period {@link ExamPeriod} that is long
037     * enough (see {@link ExamPeriod#getLength()}) and that is available for the
038     * exam (see {@link Exam#getPeriodPlacements()}). <br>
039     * <br>
040     * A set of rooms that are available in the given period (see
041     * {@link ExamRoom#isAvailable(ExamPeriod)},
042     * {@link ExamRoomPlacement#isAvailable(ExamPeriod)}), and which together cover
043     * the size of exam (number of students attending the exam) has to be assigned
044     * to an exam. Based on the type of seating (see {@link Exam#hasAltSeating()}),
045     * either room sizes (see {@link ExamRoom#getSize()}) or alternative seating
046     * sizes (see {@link ExamRoom#getAltSize()}) are used. An exam has a list of
047     * available rooms with their penalties assiciated with (see
048     * {@link Exam#getRoomPlacements()}). <br>
049     * <br>
050     * Various penalties for an assignment of a period or a set of rooms may apply.
051     * See {@link ExamPlacement} for more details. <br>
052     * <br>
053     * 
054     * @version ExamTT 1.2 (Examination Timetabling)<br>
055     *          Copyright (C) 2008 - 2010 Tomas Muller<br>
056     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
057     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
058     * <br>
059     *          This library is free software; you can redistribute it and/or modify
060     *          it under the terms of the GNU Lesser General Public License as
061     *          published by the Free Software Foundation; either version 3 of the
062     *          License, or (at your option) any later version. <br>
063     * <br>
064     *          This library is distributed in the hope that it will be useful, but
065     *          WITHOUT ANY WARRANTY; without even the implied warranty of
066     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
067     *          Lesser General Public License for more details. <br>
068     * <br>
069     *          You should have received a copy of the GNU Lesser General Public
070     *          License along with this library; if not see
071     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
072     */
073    public class Exam extends Variable<Exam, ExamPlacement> {
074        private static boolean sAlterMaxSize = false;
075        private static Logger sLog = Logger.getLogger(Exam.class);
076        protected static java.text.DecimalFormat sDoubleFormat = new java.text.DecimalFormat("0.00",
077                new java.text.DecimalFormatSymbols(Locale.US));
078    
079        private ArrayList<ExamStudent> iStudents = new ArrayList<ExamStudent>();
080        private ArrayList<ExamInstructor> iInstructors = new ArrayList<ExamInstructor>();
081        private ArrayList<ExamDistributionConstraint> iDistConstraints = new ArrayList<ExamDistributionConstraint>();
082    
083        private boolean iAllowDirectConflicts = true;
084    
085        private String iName = null;
086        private int iLength = 0;
087        private int iMaxRooms = 0;
088        private int iMinSize = 0;
089        private boolean iAltSeating = false;
090        private int iAveragePeriod = -1;
091        private Integer iSize = null;
092        private Integer iPrintOffset = null;
093    
094        private ArrayList<ExamOwner> iOwners = new ArrayList<ExamOwner>();
095        private List<ExamPeriodPlacement> iPeriodPlacements = null;
096        private List<ExamRoomPlacement> iRoomPlacements = null;
097    
098        /**
099         * Constructor
100         * 
101         * @param id
102         *            exam unique id
103         * @param length
104         *            exam length in minutes
105         * @param altSeating
106         *            true if alternative seating is requested
107         * @param maxRooms
108         *            maximum number of rooms to be used
109         * @param minSize
110         *            minimal size of rooms into which an exam can be assigned (see
111         *            {@link Exam#getSize()})
112         * @param periodPlacements
113         *            list of periods and their penalties
114         *            {@link ExamPeriodPlacement} into which an exam can be assigned
115         * @param roomPlacements
116         *            list of rooms and their penalties {@link ExamRoomPlacement}
117         *            into which an exam can be assigned
118         */
119        public Exam(long id, String name, int length, boolean altSeating, int maxRooms, int minSize,
120                java.util.List<ExamPeriodPlacement> periodPlacements, java.util.List<ExamRoomPlacement> roomPlacements) {
121            super();
122            iId = id;
123            iName = name;
124            iLength = length;
125            iAltSeating = altSeating;
126            iMaxRooms = maxRooms;
127            iMinSize = minSize;
128            iPeriodPlacements = new ArrayList<ExamPeriodPlacement>(periodPlacements);
129            Collections.sort(iPeriodPlacements, new Comparator<ExamPeriodPlacement>() {
130                @Override
131                public int compare(ExamPeriodPlacement p1, ExamPeriodPlacement p2) {
132                    return p1.getPeriod().compareTo(p2.getPeriod());
133                }
134            });
135            iRoomPlacements = new ArrayList<ExamRoomPlacement>(roomPlacements);
136            Collections.sort(iRoomPlacements, new Comparator<ExamRoomPlacement>() {
137                @Override
138                public int compare(ExamRoomPlacement p1, ExamRoomPlacement p2) {
139                    int cmp = -Double.compare(p1.getSize(hasAltSeating()), p2.getSize(hasAltSeating()));
140                    if (cmp != 0)
141                        return cmp;
142                    return p1.getRoom().compareTo(p2.getRoom());
143                }
144            });
145        }
146    
147        /**
148         * Exam size, it is bigger from {@link Exam#getMinSize()} and the number of
149         * students enrolled into the exam {@link Exam#getStudents()}. If
150         * {@link Exam#getMaxRooms()} is greater than zero, an exam must be assigned
151         * into rooms which overall size (or alternative seating size if
152         * {@link Exam#hasAltSeating()}) must be equal or greater than this size.
153         */
154        public int getSize() {
155            return (iSize == null ? Math.max(iMinSize, getStudents().size()) : iSize.intValue());
156        }
157    
158        /**
159         * Override exam size with given value (revert to default when null)
160         */
161        public void setSizeOverride(Integer size) {
162            iSize = size;
163        }
164    
165        /**
166         * Override exam size with given value (revert to default when null)
167         */
168        public Integer getSizeOverride() {
169            return iSize;
170        }
171    
172        /**
173         * Print offset -- for reporting purposes
174         */
175        public Integer getPrintOffset() {
176            return iPrintOffset;
177        }
178    
179        /**
180         * Print offset -- for reporting purposes
181         */
182        public void setPrintOffset(Integer printOffset) {
183            iPrintOffset = printOffset;
184        }
185    
186        /**
187         * Minimal exam size, see {@link Exam#getSize()}
188         */
189        public int getMinSize() {
190            return iMinSize;
191        }
192    
193        /**
194         * Minimal exam size, see {@link Exam#getSize()}
195         */
196        public void setMinSize(int minSize) {
197            iMinSize = minSize;
198        }
199    
200        /**
201         * Values (assignment of a period and a set of rooms)
202         * 
203         * @return list of {@link ExamPlacement}
204         */
205        @Override
206        public List<ExamPlacement> values() {
207            if (super.values() == null)
208                init();
209            return super.values();
210        }
211    
212        /**
213         * Return list of possible room placements.
214         * 
215         * @return list of {@link ExamRoomPlacement}
216         */
217        public List<ExamRoomPlacement> getRoomPlacements() {
218            return iRoomPlacements;
219        }
220    
221        /**
222         * Return list of possible period placements.
223         * 
224         * @return list of {@link ExamPeriodPlacement}
225         */
226        public List<ExamPeriodPlacement> getPeriodPlacements() {
227            return iPeriodPlacements;
228        }
229    
230        /**
231         * Initialize exam's domain.
232         */
233        private boolean init() {
234            if (sAlterMaxSize && iRoomPlacements.size() > 50) {
235                ExamRoomPlacement med = iRoomPlacements.get(Math.min(50, iRoomPlacements.size() / 2));
236                setMaxRooms(Math.min(getMaxRooms(), 1 + getSize() / med.getSize(hasAltSeating())));
237            }
238            ArrayList<ExamPlacement> values = new ArrayList<ExamPlacement>();
239            if (getMaxRooms() == 0) {
240                for (ExamPeriodPlacement periodPlacement : getPeriodPlacements()) {
241                    values.add(new ExamPlacement(this, periodPlacement, new HashSet<ExamRoomPlacement>()));
242                }
243            } else {
244                if (getRoomPlacements().isEmpty()) {
245                    sLog.error("  Exam " + getName() + " has no rooms.");
246                    setValues(new ArrayList<ExamPlacement>(0));
247                    return false;
248                }
249                for (ExamPeriodPlacement periodPlacement : getPeriodPlacements()) {
250                    TreeSet<RoomSet> roomSets = new TreeSet<RoomSet>();
251                    genRoomSets(periodPlacement.getPeriod(), Math.min(100, iRoomPlacements.size()), roomSets, 0,
252                            getMaxRooms(), new HashSet<ExamRoomPlacement>(), 0, 0);
253                    for (RoomSet roomSet : roomSets) {
254                        values.add(new ExamPlacement(this, periodPlacement, roomSet.rooms()));
255                    }
256                }
257            }
258            if (values.isEmpty())
259                sLog.error("Exam " + getName() + " has no placement.");
260            setValues(values);
261            return !values.isEmpty();
262        }
263    
264        private void genRoomSets(ExamPeriod period, int maxRoomSets, TreeSet<RoomSet> roomSets, int roomIdx, int maxRooms,
265                Set<ExamRoomPlacement> roomsSoFar, int sizeSoFar, int penaltySoFar) {
266            if (sizeSoFar >= getSize()) {
267                double penalty = 
268                        getModel().getCriterion(RoomSplitPenalty.class).getWeight() * (roomsSoFar.size() - 1) * (roomsSoFar.size() - 1) +
269                        getModel().getCriterion(RoomSizePenalty.class).getWeight() * (sizeSoFar - getSize()) +
270                        getModel().getCriterion(RoomPenalty.class).getWeight() * penaltySoFar;
271                if (roomSets.size() >= maxRoomSets) {
272                    RoomSet last = roomSets.last();
273                    if (penalty < last.penalty()) {
274                        roomSets.remove(last);
275                        roomSets.add(new RoomSet(roomsSoFar, penalty));
276                    }
277                } else
278                    roomSets.add(new RoomSet(roomsSoFar, penalty));
279                return;
280            }
281            if (!roomSets.isEmpty()) {
282                RoomSet roomSet = roomSets.first();
283                maxRooms = Math.min(maxRooms, (1 + roomSet.rooms().size()) - roomsSoFar.size());
284            }
285            if (maxRooms == 0)
286                return;
287            int sizeBound = sizeSoFar;
288            for (int i = 0; i < maxRooms && roomIdx + i < iRoomPlacements.size(); i++)
289                sizeBound += iRoomPlacements.get(roomIdx + i).getSize(hasAltSeating());
290            while (roomIdx < iRoomPlacements.size()) {
291                if (sizeBound < getSize())
292                    break;
293                ExamRoomPlacement room = iRoomPlacements.get(roomIdx);
294                if (!room.isAvailable(period))
295                    continue;
296                roomsSoFar.add(room);
297                genRoomSets(period, maxRoomSets, roomSets, roomIdx + 1, maxRooms - 1, roomsSoFar, sizeSoFar
298                        + room.getSize(hasAltSeating()), penaltySoFar + room.getPenalty(period));
299                roomsSoFar.remove(room);
300                sizeBound -= room.getSize(hasAltSeating());
301                if (roomIdx + maxRooms < iRoomPlacements.size())
302                    sizeBound += iRoomPlacements.get(roomIdx + maxRooms).getSize(hasAltSeating());
303                roomIdx++;
304                if (roomSets.size() == maxRoomSets) {
305                    RoomSet last = roomSets.last();
306                    if (last.rooms().size() < roomsSoFar.size() + 1)
307                        return;
308                }
309            }
310        }
311    
312        private class RoomSet implements Comparable<RoomSet> {
313            private Set<ExamRoomPlacement> iRooms;
314            private double iPenalty;
315    
316            public RoomSet(Set<ExamRoomPlacement> rooms, double penalty) {
317                iRooms = new HashSet<ExamRoomPlacement>(rooms);
318                iPenalty = penalty;
319            }
320    
321            public Set<ExamRoomPlacement> rooms() {
322                return iRooms;
323            }
324    
325            public double penalty() {
326                return iPenalty;
327            }
328    
329            public int compareTo(Set<ExamRoomPlacement> rooms, double penalty) {
330                int cmp = Double.compare(iRooms.size(), rooms.size());
331                if (cmp != 0)
332                    return cmp;
333                cmp = Double.compare(penalty(), penalty);
334                if (cmp != 0)
335                    return cmp;
336                return rooms().toString().compareTo(rooms.toString());
337            }
338    
339            @Override
340            public int compareTo(RoomSet r) {
341                return compareTo(r.rooms(), r.penalty());
342            }
343        }
344    
345        /**
346         * True if alternative seating is required ({@link ExamRoom#getAltSize()} is
347         * to be used), false if normal seating is required (
348         * {@link ExamRoom#getSize()} is to be used).
349         * 
350         * @return true if alternative seating is required, false otherwise
351         */
352        public boolean hasAltSeating() {
353            return iAltSeating;
354        }
355    
356        /**
357         * Length of the exam in minutes. The assigned period has to be of the same
358         * or greater length.
359         * 
360         * @return length of the exam in minutes
361         */
362        public int getLength() {
363            return iLength;
364        }
365    
366        /**
367         * Set average period. This represents an average period that the exam was
368         * assigned to in the past. If set, it is used in exam rotation penalty
369         * {@link ExamRotationPenalty} in order to put more weight on
370         * exams that were badly assigned last time(s) and ensuring some form of
371         * fairness.
372         * 
373         * @param period
374         *            average period
375         */
376        public void setAveragePeriod(int period) {
377            iAveragePeriod = period;
378        }
379    
380        /**
381         * Average period. This represents an average period that the exam was
382         * assigned to in the past. If set, it is used in exam rotation penalty
383         * {@link ExamRotationPenalty} in order to put more weight on
384         * exams that were badly assigned last time(s) and ensuring some form of
385         * fairness.
386         * 
387         * @return average period
388         */
389        public int getAveragePeriod() {
390            return iAveragePeriod;
391        }
392    
393        /**
394         * True if there is an average period assigned to the exam. This represents
395         * an average period that the exam was assigned to in the past. If set, it
396         * is used in exam rotation penalty
397         * {@link ExamRotationPenalty} in order to put more weight on
398         * exams that were badly assigned last time(s) and ensuring some form of
399         * fairness.
400         */
401        public boolean hasAveragePeriod() {
402            return iAveragePeriod >= 0;
403        }
404    
405        /**
406         * True if a direct student conflict is allowed, see
407         * {@link ExamStudent#canConflict(Exam, Exam)}
408         * 
409         * @return true if a direct student conflict is allowed
410         */
411        public boolean isAllowDirectConflicts() {
412            return iAllowDirectConflicts;
413        }
414    
415        /**
416         * Set whether a direct student conflict is allowed, see
417         * {@link ExamStudent#canConflict(Exam, Exam)}
418         * 
419         * @param allowDirectConflicts
420         *            true if a direct student conflict is allowed
421         */
422        public void setAllowDirectConflicts(boolean allowDirectConflicts) {
423            iAllowDirectConflicts = allowDirectConflicts;
424        }
425    
426        /**
427         * Adds a constraint. Called automatically when the constraint is added to
428         * the model, i.e., {@link Model#addConstraint(Constraint)} is called.
429         * 
430         * @param constraint
431         *            added constraint
432         */
433        @Override
434        public void addContstraint(Constraint<Exam, ExamPlacement> constraint) {
435            if (constraint instanceof ExamStudent)
436                iStudents.add((ExamStudent) constraint);
437            if (constraint instanceof ExamDistributionConstraint)
438                iDistConstraints.add((ExamDistributionConstraint) constraint);
439            if (constraint instanceof ExamInstructor)
440                iInstructors.add((ExamInstructor) constraint);
441            super.addContstraint(constraint);
442        }
443    
444        /**
445         * Removes a constraint. Called automatically when the constraint is removed
446         * from the model, i.e., {@link Model#removeConstraint(Constraint)} is
447         * called.
448         * 
449         * @param constraint
450         *            added constraint
451         */
452        @Override
453        public void removeContstraint(Constraint<Exam, ExamPlacement> constraint) {
454            if (constraint instanceof ExamStudent)
455                iStudents.remove(constraint);
456            if (constraint instanceof ExamDistributionConstraint)
457                iDistConstraints.remove(constraint);
458            if (constraint instanceof ExamInstructor)
459                iInstructors.remove(constraint);
460            super.removeContstraint(constraint);
461        }
462    
463        /**
464         * List of students that are enrolled in the exam
465         * 
466         * @return list of {@link ExamStudent}
467         */
468        public List<ExamStudent> getStudents() {
469            return iStudents;
470        }
471    
472        /**
473         * List of distribution constraints that this exam is involved in
474         * 
475         * @return list of {@link ExamDistributionConstraint}
476         */
477        public List<ExamDistributionConstraint> getDistributionConstraints() {
478            return iDistConstraints;
479        }
480    
481        /**
482         * List of instructors that are assigned to this exam
483         * 
484         * @return list of {@link ExamInstructor}
485         */
486        public List<ExamInstructor> getInstructors() {
487            return iInstructors;
488        }
489    
490        /**
491         * Check all distribution constraint that this exam is involved in
492         * 
493         * @param period
494         *            a period to be assigned to this exam
495         * @return true, if there is no assignment of some other exam in conflict
496         *         with the given period
497         */
498        public boolean checkDistributionConstraints(ExamPeriodPlacement period) {
499            for (ExamDistributionConstraint dc : iDistConstraints) {
500                if (!dc.isHard())
501                    continue;
502                boolean before = true;
503                for (Exam exam : dc.variables()) {
504                    if (exam.equals(this)) {
505                        before = false;
506                        continue;
507                    }
508                    ExamPlacement placement = exam.getAssignment();
509                    if (placement == null)
510                        continue;
511                    switch (dc.getType()) {
512                        case ExamDistributionConstraint.sDistSamePeriod:
513                            if (period.getIndex() != placement.getPeriod().getIndex())
514                                return false;
515                            break;
516                        case ExamDistributionConstraint.sDistDifferentPeriod:
517                            if (period.getIndex() == placement.getPeriod().getIndex())
518                                return false;
519                            break;
520                        case ExamDistributionConstraint.sDistPrecedence:
521                            if (before) {
522                                if (period.getIndex() <= placement.getPeriod().getIndex())
523                                    return false;
524                            } else {
525                                if (period.getIndex() >= placement.getPeriod().getIndex())
526                                    return false;
527                            }
528                            break;
529                        case ExamDistributionConstraint.sDistPrecedenceRev:
530                            if (before) {
531                                if (period.getIndex() >= placement.getPeriod().getIndex())
532                                    return false;
533                            } else {
534                                if (period.getIndex() <= placement.getPeriod().getIndex())
535                                    return false;
536                            }
537                            break;
538                    }
539                }
540            }
541            return true;
542        }
543    
544        /**
545         * Check all distribution constraint that this exam is involved in
546         * 
547         * @param room
548         *            a room to be assigned to this exam
549         * @return true, if there is no assignment of some other exam in conflict
550         *         with the given room
551         */
552        public boolean checkDistributionConstraints(ExamRoomPlacement room) {
553            for (ExamDistributionConstraint dc : iDistConstraints) {
554                if (!dc.isHard())
555                    continue;
556                for (Exam exam : dc.variables()) {
557                    if (exam.equals(this))
558                        continue;
559                    ExamPlacement placement = exam.getAssignment();
560                    if (placement == null)
561                        continue;
562                    switch (dc.getType()) {
563                        case ExamDistributionConstraint.sDistSameRoom:
564                            if (!placement.getRoomPlacements().contains(room))
565                                return false;
566                            break;
567                        case ExamDistributionConstraint.sDistDifferentRoom:
568                            if (placement.getRoomPlacements().contains(room))
569                                return false;
570                            break;
571                    }
572                }
573            }
574            return true;
575        }
576    
577        /**
578         * Check all soft distribution constraint that this exam is involved in
579         * 
580         * @param room
581         *            a room to be assigned to this exam
582         * @return sum of penalties of violated distribution constraints
583         */
584        public int getDistributionConstraintPenalty(ExamRoomPlacement room) {
585            int penalty = 0;
586            for (ExamDistributionConstraint dc : iDistConstraints) {
587                if (dc.isHard())
588                    continue;
589                for (Exam exam : dc.variables()) {
590                    if (exam.equals(this))
591                        continue;
592                    ExamPlacement placement = exam.getAssignment();
593                    if (placement == null)
594                        continue;
595                    switch (dc.getType()) {
596                        case ExamDistributionConstraint.sDistSameRoom:
597                            if (!placement.getRoomPlacements().contains(room))
598                                penalty += dc.getWeight();
599                            break;
600                        case ExamDistributionConstraint.sDistDifferentRoom:
601                            if (placement.getRoomPlacements().contains(room))
602                                penalty += dc.getWeight();
603                            break;
604                    }
605                }
606            }
607            return penalty;
608        }
609    
610        /**
611         * Maximal number of rooms that can be assigned to the exam
612         * 
613         * @return maximal number of rooms that can be assigned to the exam
614         */
615        public int getMaxRooms() {
616            return iMaxRooms;
617        }
618    
619        /**
620         * Set maximal number of rooms that can be assigned to the exam
621         * 
622         * @param maxRooms
623         *            maximal number of rooms that can be assigned to the exam
624         */
625        public void setMaxRooms(int maxRooms) {
626            iMaxRooms = maxRooms;
627        }
628    
629        /**
630         * Find best available rooms for the exam in the given period. First of all,
631         * it tries to find the minimal number of rooms that cover the size of the
632         * exam. Among these, a set of rooms of total smallest size is preferred. If
633         * the original room is available and of enough size, it is returned. All
634         * necessary checks are made (availability of rooms, room penalties, room
635         * sizes etc.).
636         * 
637         * @param period
638         *            given period.
639         * @return best available rooms for the exam in the given period, null if
640         *         there is no valid assignment
641         */
642        public Set<ExamRoomPlacement> findBestAvailableRooms(ExamPeriodPlacement period) {
643            if (getMaxRooms() == 0)
644                return new HashSet<ExamRoomPlacement>();
645            double sw = getModel().getCriterion(RoomSizePenalty.class).getWeight();
646            double pw = getModel().getCriterion(RoomPenalty.class).getWeight();
647            double cw = getModel().getCriterion(DistributionPenalty.class).getWeight();
648            ExamRoomSharing sharing = ((ExamModel) getModel()).getRoomSharing();
649            loop: for (int nrRooms = 1; nrRooms <= getMaxRooms(); nrRooms++) {
650                HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>();
651                int size = 0;
652                while (rooms.size() < nrRooms && size < getSize()) {
653                    int minSize = (getSize() - size) / (nrRooms - rooms.size());
654                    ExamRoomPlacement best = null;
655                    double bestWeight = 0;
656                    int bestSize = 0;
657                    for (ExamRoomPlacement room : getRoomPlacements()) {
658                        if (!room.isAvailable(period.getPeriod()))
659                            continue;
660                        if (nrRooms == 1 && sharing != null) {
661                            if (sharing.inConflict(this, room.getRoom().getPlacements(period.getPeriod()), room.getRoom()))
662                                continue;
663                        } else {
664                            if (!room.getRoom().getPlacements(period.getPeriod()).isEmpty())
665                                continue;
666                        }
667                        if (rooms.contains(room))
668                            continue;
669                        if (!checkDistributionConstraints(room))
670                            continue;
671                        int s = room.getSize(hasAltSeating());
672                        if (s < minSize)
673                            break;
674                        int p = room.getPenalty(period.getPeriod());
675                        double w = pw * p + sw * (s - minSize) + cw * getDistributionConstraintPenalty(room);
676                        double d = 0;
677                        if (!rooms.isEmpty()) {
678                            for (ExamRoomPlacement r : rooms) {
679                                d += r.getDistanceInMeters(room);
680                            }
681                            w += d / rooms.size();
682                        }
683                        if (best == null || bestWeight > w) {
684                            best = room;
685                            bestSize = s;
686                            bestWeight = w;
687                        }
688                    }
689                    if (best == null)
690                        continue loop;
691                    rooms.add(best);
692                    size += bestSize;
693                }
694                if (size >= getSize())
695                    return rooms;
696            }
697            return null;
698        }
699    
700        /**
701         * Randomly find a set of available rooms for the exam in the given period.
702         * First of all, it tries to find the minimal number of rooms that cover the
703         * size of the exam. Among these, a set of rooms of total smallest size is
704         * preferred. All necessary checks are made (availability of rooms, room
705         * penalties, room sizes etc.).
706         * 
707         * @param period
708         *            given period.
709         * @return randomly computed set of available rooms for the exam in the
710         *         given period, null if there is no valid assignment
711         */
712        public Set<ExamRoomPlacement> findRoomsRandom(ExamPeriodPlacement period) {
713            return findRoomsRandom(period, true);
714        }
715    
716        /**
717         * Randomly find a set of available rooms for the exam in the given period.
718         * First of all, it tries to find the minimal number of rooms that cover the
719         * size of the exam. Among these, a set of rooms of total smallest size is
720         * preferred. All necessary checks are made (availability of rooms, room
721         * penalties, room sizes etc.).
722         * 
723         * @param period
724         *            given period.
725         * @param checkConflicts
726         *            if false, room and distribution conflicts are not checked
727         * @return randomly computed set of available rooms for the exam in the
728         *         given period, null if there is no valid assignment
729         */
730        public Set<ExamRoomPlacement> findRoomsRandom(ExamPeriodPlacement period, boolean checkConflicts) {
731            if (getMaxRooms() == 0)
732                return new HashSet<ExamRoomPlacement>();
733            HashSet<ExamRoomPlacement> rooms = new HashSet<ExamRoomPlacement>();
734            int size = 0;
735            ExamRoomSharing sharing = ((ExamModel) getModel()).getRoomSharing();
736            loop: while (rooms.size() < getMaxRooms()) {
737                int rx = ToolBox.random(getRoomPlacements().size());
738                int minSize = (getSize() - size + (getMaxRooms() - rooms.size() - 1)) / (getMaxRooms() - rooms.size());
739                for (int r = 0; r < getRoomPlacements().size(); r++) {
740                    ExamRoomPlacement room = getRoomPlacements().get((r + rx) % getRoomPlacements().size());
741                    int s = room.getSize(hasAltSeating());
742                    if (s < minSize)
743                        continue;
744                    if (!room.isAvailable(period.getPeriod()))
745                        continue;
746                    if (checkConflicts) {
747                        if (rooms.isEmpty() && sharing != null && !room.getRoom().getPlacements(period.getPeriod()).isEmpty()) {
748                            if (sharing.inConflict(this, room.getRoom().getPlacements(period.getPeriod()), room.getRoom()))
749                                continue;
750                        } else {
751                            if (!room.getRoom().getPlacements(period.getPeriod()).isEmpty())
752                                continue;
753                        }
754                    }
755                    if (rooms.contains(room))
756                        continue;
757                    if (checkConflicts && !checkDistributionConstraints(room))
758                        continue;
759                    size += s;
760                    rooms.add(room);
761                    if (size >= getSize()) {
762                        for (Iterator<ExamRoomPlacement> j = rooms.iterator(); j.hasNext();) {
763                            ExamRoomPlacement rp = j.next();
764                            if (size - rp.getSize(hasAltSeating()) >= getSize()) {
765                                j.remove();
766                                size -= rp.getSize(hasAltSeating());
767                            }
768                        }
769                        return rooms;
770                    }
771                    continue loop;
772                }
773                break;
774            }
775            return null;
776        }
777    
778        private HashSet<Exam> iCorrelatedExams = null;
779    
780        /**
781         * Number of exams that are correlated with this exam (there is at least one
782         * student attending both exams).
783         * 
784         * @return number of correlated exams
785         */
786        public int nrStudentCorrelatedExams() {
787            return getStudentCorrelatedExams().size();
788        }
789        
790        /**
791         * Exams that are correlated with this exam (there is at least one
792         * student attending both exams).
793         * 
794         * @return number of correlated exams
795         */
796        public Set<Exam> getStudentCorrelatedExams() {
797            if (iCorrelatedExams == null) {
798                iCorrelatedExams = new HashSet<Exam>();
799                for (ExamStudent student : iStudents) {
800                    iCorrelatedExams.addAll(student.variables());
801                }
802                iCorrelatedExams.remove(this);
803            }
804            return iCorrelatedExams;
805        }
806    
807        private Integer iEstimatedDomainSize = null;
808    
809        private int estimatedDomainSize() {
810            if (iEstimatedDomainSize == null) {
811                int periods = getPeriodPlacements().size();
812                int rooms = -1;
813                int split = 0;
814                while (rooms < split && split <= getMaxRooms()) {
815                    rooms = 0;
816                    split++;
817                    for (ExamRoomPlacement room : getRoomPlacements()) {
818                        if (room.getSize(hasAltSeating()) >= (getSize() / split))
819                            rooms++;
820                    }
821                }
822                iEstimatedDomainSize = new Integer(periods * rooms / split);
823            }
824            return iEstimatedDomainSize.intValue();
825        }
826    
827        /**
828         * An exam with more correlated exams is preferred (
829         * {@link Exam#nrStudentCorrelatedExams()}). If it is the same, ratio number
830         * of students / number of available periods is used. If the same, exam ids
831         * are used.
832         */
833        @Override
834        public int compareTo(Exam o) {
835            Exam e = o;
836            int cmp = Double.compare(estimatedDomainSize(), e.estimatedDomainSize());
837            if (cmp != 0)
838                return cmp;
839            cmp = -Double.compare(nrStudentCorrelatedExams(), e.nrStudentCorrelatedExams());
840            if (cmp != 0)
841                return cmp;
842            cmp = -Double.compare(((double) getSize()) / getPeriodPlacements().size(), ((double) e.getSize())
843                    / e.getPeriodPlacements().size());
844            if (cmp != 0)
845                return cmp;
846            return super.compareTo(o);
847        }
848    
849        /**
850         * True, if there is a student of this exam (that does not have direct
851         * conflicts allowed, see {@link ExamStudent#canConflict(Exam, Exam)}) that
852         * attends some other exam in the given period.
853         * 
854         * @param period
855         *            a period
856         * @return true if there is a student conflict
857         */
858        public boolean hasStudentConflictWithPreAssigned(ExamPeriod period) {
859            for (ExamStudent s : getStudents()) {
860                for (Exam exam : s.getExams(period)) {
861                    if (exam.equals(this))
862                        continue;
863                    if (s.canConflict(this, exam))
864                        continue;
865                }
866            }
867            return false;
868        }
869    
870        /**
871         * Number of students of this exam (that does not have direct conflicts
872         * allowed, see {@link ExamStudent#canConflict(Exam, Exam)}) that attend
873         * some other exam in the given period.
874         * 
875         * @param period
876         *            a period
877         * @return number of direct student conflicts that are prohibited
878         */
879        public int countStudentConflicts(ExamPeriodPlacement period) {
880            int conf = 0;
881            for (ExamStudent s : getStudents()) {
882                for (Exam exam : s.getExams(period.getPeriod())) {
883                    if (exam.equals(this))
884                        continue;
885                    if (s.canConflict(this, exam))
886                        continue;
887                    conf++;
888                }
889            }
890            return conf;
891        }
892    
893        /**
894         * List of exams that are assigned to the given period and share one or more
895         * students with this exam (that does not have direct conflicts allowed, see
896         * {@link ExamStudent#canConflict(Exam, Exam)}).
897         * 
898         * @param period
899         *            a period
900         * @return list of {@link Exam} (other than this exam, that are placed in
901         *         the given period and create prohibited direct conflicts)
902         */
903        public HashSet<Exam> getStudentConflicts(ExamPeriod period) {
904            HashSet<Exam> conf = new HashSet<Exam>();
905            for (ExamStudent s : getStudents()) {
906                for (Exam exam : s.getExams(period)) {
907                    if (exam.equals(this))
908                        continue;
909                    if (!s.canConflict(this, exam))
910                        conf.add(exam);
911                }
912            }
913            return conf;
914        }
915    
916        /**
917         * Allow all direct student conflict for the given period (see
918         * {@link ExamStudent#canConflict(Exam, Exam)}).
919         * 
920         * @param period
921         *            a period
922         */
923        public void allowAllStudentConflicts(ExamPeriod period) {
924            for (ExamStudent s : getStudents()) {
925                for (Exam exam : s.getExams(period)) {
926                    if (exam.equals(this))
927                        continue;
928                    exam.setAllowDirectConflicts(true);
929                    setAllowDirectConflicts(true);
930                    s.setAllowDirectConflicts(true);
931                }
932            }
933        }
934    
935        /**
936         * String representation
937         * 
938         * @return exam id (periods: number of periods, rooms: number of rooms,
939         *         student: number of students, maxRooms: max rooms[, alt if
940         *         alternate seating is required])
941         */
942        @Override
943        public String toString() {
944            return getName() + " (periods:" + getPeriodPlacements().size() + ", rooms:" + getRoomPlacements().size()
945                    + ", size:" + getSize() + " ,maxRooms:" + getMaxRooms() + (hasAltSeating() ? ", alt" : "") + ")";
946        }
947    
948        /** Exam name */
949        @Override
950        public String getName() {
951            return (hasName() ? iName : String.valueOf(getId()));
952        }
953    
954        /** Exam name */
955        public void setName(String name) {
956            iName = name;
957        }
958    
959        /** Exam name */
960        public boolean hasName() {
961            return iName != null && iName.length() > 0;
962        }
963    
964        private HashMap<Exam, List<ExamStudent>> iJenrls = null;
965    
966        /**
967         * Joint enrollments
968         * 
969         * @return table {@link Exam} (an exam that has at least one student in
970         *         common with this exam) -> {@link List} (list of students in
971         *         common)
972         */
973        public Map<Exam, List<ExamStudent>> getJointEnrollments() {
974            if (iJenrls != null)
975                return iJenrls;
976            iJenrls = new HashMap<Exam, List<ExamStudent>>();
977            for (ExamStudent student : getStudents()) {
978                for (Exam other : student.variables()) {
979                    if (other.equals(this))
980                        continue;
981                    List<ExamStudent> students = iJenrls.get(other);
982                    if (students == null) {
983                        students = new ArrayList<ExamStudent>();
984                        iJenrls.put(other, students);
985                    }
986                    students.add(student);
987                }
988            }
989            return iJenrls;
990        }
991    
992        /**
993         * Courses and/or sections that are having this exam
994         * 
995         * @return list of {@link ExamOwner}
996         */
997        public List<ExamOwner> getOwners() {
998            return iOwners;
999        }
1000    
1001        /**
1002         * Courses/sections of this exam into which the given student is enrolled
1003         * into
1004         * 
1005         * @param student
1006         *            a student that is enrolled into this exam
1007         * @return list of courses/sections {@link ExamOwner} which are having this
1008         *         exam with the given student enrolled in
1009         */
1010        public Collection<ExamOwner> getOwners(ExamStudent student) {
1011            Collection<ExamOwner> ret = new ArrayList<ExamOwner>();
1012            for (ExamOwner owner : iOwners) {
1013                if (owner.getStudents().contains(student))
1014                    ret.add(owner);
1015            }
1016            return ret;
1017        }
1018    
1019        /**
1020         * Courses/sections of this exam into which the given instructor is enrolled
1021         * into
1022         * 
1023         * @param instructor
1024         *            an instructor that is enrolled into this exam
1025         * @return list of courses/sections {@link ExamOwner} which are having this
1026         *         exam with the given instructor enrolled in
1027         */
1028        public Collection<ExamOwner> getOwners(ExamInstructor instructor) {
1029            Collection<ExamOwner> ret = new ArrayList<ExamOwner>();
1030            for (ExamOwner owner : iOwners) {
1031                if (owner.getIntructors().contains(instructor))
1032                    ret.add(owner);
1033            }
1034            return ret;
1035        }
1036    
1037        /**
1038         * Returns appropriate {@link ExamPeriodPlacement} for the given period, if
1039         * it is available for this exam, null otherwise.
1040         */
1041        public ExamPeriodPlacement getPeriodPlacement(Long periodId) {
1042            for (ExamPeriodPlacement periodPlacement : iPeriodPlacements) {
1043                if (periodPlacement.getId().equals(periodId))
1044                    return periodPlacement;
1045            }
1046            return null;
1047        }
1048    
1049        /**
1050         * Returns appropriate {@link ExamRoomPlacement} for the given room, if it
1051         * is available for this exam, null otherwise.
1052         */
1053        public ExamRoomPlacement getRoomPlacement(long roomId) {
1054            for (ExamRoomPlacement roomPlacement : iRoomPlacements) {
1055                if (roomPlacement.getId() == roomId)
1056                    return roomPlacement;
1057            }
1058            return null;
1059        }
1060    
1061        /**
1062         * Returns appropriate {@link ExamPeriodPlacement} for the given period, if
1063         * it is available for this exam, null otherwise.
1064         */
1065        public ExamPeriodPlacement getPeriodPlacement(ExamPeriod period) {
1066            for (ExamPeriodPlacement periodPlacement : getPeriodPlacements()) {
1067                if (periodPlacement.getPeriod().equals(period))
1068                    return periodPlacement;
1069            }
1070            return null;
1071        }
1072    
1073        /**
1074         * Returns appropriate {@link ExamRoomPlacement} for the given room, if it
1075         * is available for this exam, null otherwise.
1076         */
1077        public ExamRoomPlacement getRoomPlacement(ExamRoom room) {
1078            for (ExamRoomPlacement roomPlacement : getRoomPlacements()) {
1079                if (roomPlacement.getRoom().equals(room))
1080                    return roomPlacement;
1081            }
1082            return null;
1083        }
1084    
1085        /** Return true if there are some values in the domain of this variable */
1086        @Override
1087        public boolean hasValues() {
1088            return !getPeriodPlacements().isEmpty() && (getMaxRooms() == 0 || !getRoomPlacements().isEmpty());
1089        }
1090    
1091        @Override
1092        public void assign(long iteration, ExamPlacement placement) {
1093            if (getMaxRooms() > 0) {
1094                int size = 0;
1095                for (ExamRoomPlacement room : placement.getRoomPlacements()) {
1096                    size += room.getSize(hasAltSeating());
1097                }
1098                if (size < getSize() && !placement.getRoomPlacements().isEmpty()) {
1099                    Progress.getInstance(getModel()).warn(
1100                            "Selected room(s) are too small " + size + "<" + getSize() + " (" + getName() + " "
1101                                    + placement.getName() + ")");
1102                }
1103            }
1104            super.assign(iteration, placement);
1105        }
1106    }