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