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