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