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