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