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