    001package org.cpsolver.exam.model;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.HashMap;
    006import java.util.HashSet;
    007import java.util.List;
    008import java.util.Map;
    009import java.util.Set;
    010
    011import org.cpsolver.ifs.assignment.Assignment;
    012import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
    013import org.cpsolver.ifs.assignment.context.ConstraintWithContext;
    014import org.cpsolver.ifs.model.Constraint;
    015import org.cpsolver.ifs.model.ConstraintListener;
    016import org.cpsolver.ifs.util.DistanceMetric;
    017
    018
    019/**
    020 * A room. Only one exam can use a room at a time (period). <br>
    021 * <br>
    022 *
    023 * @author  Tomáš Müller
    024 * @version ExamTT 1.3 (Examination Timetabling)<br>
    025 *          Copyright (C) 2008 - 2014 Tomáš Müller<br>
    026 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    027 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    028 * <br>
    029 *          This library is free software; you can redistribute it and/or modify
    030 *          it under the terms of the GNU Lesser General Public License as
    031 *          published by the Free Software Foundation; either version 3 of the
    032 *          License, or (at your option) any later version. <br>
    033 * <br>
    034 *          This library is distributed in the hope that it will be useful, but
    035 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    036 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    037 *          Lesser General Public License for more details. <br>
    038 * <br>
    039 *          You should have received a copy of the GNU Lesser General Public
    040 *          License along with this library; if not see
    041 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    042 */
    043public class ExamRoom extends ConstraintWithContext<Exam, ExamPlacement, ExamRoom.ExamRoomContext> {
    044    private boolean[] iAvailable;
    045    private int[] iPenalty;
    046    private String iName;
    047    private int iSize, iAltSize;
    048    private Double iCoordX, iCoordY;
    049    private boolean iHard = true;
    050
    051    private ExamRoom iParentRoom;
    052    private List<ExamRoom> iPartitions;
    053
    054    /**
    055     * Constructor
    056     *
    057     * @param model
    058     *            examination timetabling model
    059     * @param id
    060     *            unique id
    061     * @param name room name
    062     * @param size
    063     *            room (normal) seating capacity
    064     * @param altSize
    065     *            room alternating seating capacity (to be used when
    066     *            {@link Exam#hasAltSeating()} is true)
    067     * @param coordX
    068     *            x coordinate
    069     * @param coordY
    070     *            y coordinate
    071     */
    072    public ExamRoom(ExamModel model, long id, String name, int size, int altSize, Double coordX, Double coordY) {
    073        super();
    074        iId = id;
    075        iName = name;
    076        iCoordX = coordX;
    077        iCoordY = coordY;
    078        iSize = size;
    079        iAltSize = altSize;
    080        iAvailable = new boolean[model.getNrPeriods()];
    081        iPenalty = new int[model.getNrPeriods()];
    082        for (int i = 0; i < iAvailable.length; i++) {
    083            iAvailable[i] = true;
    084            iPenalty[i] = 0;
    085        }
    086    }
    087
    088    public void setHard(boolean hard) { iHard = hard; }
    089
    090    @Override
    091    public boolean isHard() { return iHard; }
    092
    093    private Map<Long, Double> iDistanceCache = new HashMap<Long, Double>();
    094    /**
    095     * Distance between two rooms. See {@link DistanceMetric}
    096     *
    097     * @param other
    098     *            another room
    099     * @return distance between this and the given room
    100     */
    101    public double getDistanceInMeters(ExamRoom other) {
    102        synchronized (iDistanceCache) {
    103            Double distance = iDistanceCache.get(other.getId());
    104            if (distance == null) {
    105                distance = ((ExamModel)getModel()).getDistanceMetric().getDistanceInMeters(getId(), getCoordX(), getCoordY(), other.getId(), other.getCoordX(), other.getCoordY());
    106                iDistanceCache.put(other.getId(), distance);
    107            }
    108            return distance;
    109        }
    110    }
    111
    112    /**
    113     * Normal seating capacity (to be used when {@link Exam#hasAltSeating()} is
    114     * false)
    115     * @return room normal seating capacity
    116     */
    117    public int getSize() {
    118        return iSize;
    119    }
    120
    121    /**
    122     * Alternating seating capacity (to be used when
    123     * {@link Exam#hasAltSeating()} is true)
    124     * @return room examination seating capacity
    125     */
    126    public int getAltSize() {
    127        return iAltSize;
    128    }
    129
    130    /**
    131     * X coordinate
    132     * @return X-coordinate (latitude)
    133     */
    134    public Double getCoordX() {
    135        return iCoordX;
    136    }
    137
    138    /**
    139     * Y coordinate
    140     * @return Y-coordinate (longitude)
    141     */
    142    public Double getCoordY() {
    143        return iCoordY;
    144    }
    145
    146    /**
    147     * Exams placed at the given period
    148     *
    149     * @param assignment current assignment
    150     * @param period
    151     *            a period
    152     * @return a placement of an exam in this room at the given period, null if
    153     *         unused (multiple placements can be returned if the room is shared between
    154     *         two or more exams)
    155     */
    156    public List<ExamPlacement> getPlacements(Assignment<Exam, ExamPlacement> assignment, ExamPeriod period) {
    157        return getContext(assignment).getPlacements(period.getIndex());
    158    }
    159
    160    /**
    161     * True if the room is available (for examination timetabling) during the
    162     * given period
    163     *
    164     * @param period
    165     *            a period
    166     * @return true if an exam can be scheduled into this room at the given
    167     *         period, false if otherwise
    168     */
    169    public boolean isAvailable(ExamPeriod period) {
    170        return iAvailable[period.getIndex()];
    171    }
    172
    173    public boolean isAvailable(int period) {
    174        return iAvailable[period];
    175    }
    176
    177    /**
    178     * True if the room is available during at least one period,
    179     * @return true if there is an examination period at which the room is available
    180     */
    181    public boolean isAvailable() {
    182        for (boolean a: iAvailable)
    183            if (a) return true;
    184        return false;
    185    }
    186
    187    /**
    188     * Set whether the room is available (for examination timetabling) during
    189     * the given period
    190     *
    191     * @param period
    192     *            a period
    193     * @param available
    194     *            true if an exam can be scheduled into this room at the given
    195     *            period, false if otherwise
    196     */
    197    public void setAvailable(ExamPeriod period, boolean available) {
    198        iAvailable[period.getIndex()] = available;
    199    }
    200
    201    public void setAvailable(int period, boolean available) {
    202        iAvailable[period] = available;
    203    }
    204
    205    /** Return room penalty for given period
    206     * @param period given period
    207     * @return room penalty for the given period
    208     **/
    209    public int getPenalty(ExamPeriod period) {
    210        return iPenalty[period.getIndex()];
    211    }
    212
    213    public int getPenalty(int period) {
    214        return iPenalty[period];
    215    }
    216
    217    /** Set room penalty for given period
    218     * @param period given period
    219     * @param penalty penalty for the given period
    220     **/
    221    public void setPenalty(ExamPeriod period, int penalty) {
    222        iPenalty[period.getIndex()] = penalty;
    223    }
    224
    225    public void setPenalty(int period, int penalty) {
    226        iPenalty[period] = penalty;
    227    }
    228
    229
    230    public ExamRoomSharing getRoomSharing() {
    231        return ((ExamModel)getModel()).getRoomSharing();
    232    }
    233
    234    /**
    235     * Compute conflicts if the given exam is assigned in this room and the given period
    236     */
    237    public void computeConflicts(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamPeriod period, Set<ExamPlacement> conflicts) {
    238        boolean single = exam.getSize() <= (exam.hasAltSeating() ? getAltSize() : getSize());
    239        if (getRoomSharing() == null || !single) {
    240            for (ExamPlacement conflict: getContext(assignment).getPlacements(period.getIndex()))
    241                if (!conflict.variable().equals(exam))
    242                    conflicts.add(conflict);
    243            if (getParentRoom() != null && getParentRoom().isHard()) {
    244                for (ExamPlacement conflict: getParentRoom().getContext(assignment).getPlacements(period.getIndex()))
    245                    if (!conflict.variable().equals(exam))
    246                        conflicts.add(conflict);
    247            }
    248            if (getPartitions() != null) {
    249                for (ExamRoom partition: getPartitions()) {
    250                    if (partition.isHard())
    251                        for (ExamPlacement conflict: partition.getContext(assignment).getPlacements(period.getIndex()))
    252                            if (!conflict.variable().equals(exam))
    253                                conflicts.add(conflict);
    254                }
    255            }
    256        } else {
    257            if (getParentRoom() != null && getParentRoom().isHard()) {
    258                for (ExamPlacement conflict: getParentRoom().getContext(assignment).getPlacements(period.getIndex()))
    259                    if (!conflict.variable().equals(exam))
    260                        conflicts.add(conflict);
    261            }
    262            if (getPartitions() != null) {
    263                for (ExamRoom partition: getPartitions()) {
    264                    if (partition.isHard())
    265                        for (ExamPlacement conflict: partition.getContext(assignment).getPlacements(period.getIndex()))
    266                            if (!conflict.variable().equals(exam))
    267                                conflicts.add(conflict);
    268                }
    269            }
    270            getRoomSharing().computeConflicts(exam, getContext(assignment).getPlacements(period.getIndex()), this, conflicts);
    271        }
    272    }
    273
    274    /**
    275     * Check for conflicts if the given exam is assigned in this room and the given period
    276     */
    277    public boolean inConflict(Assignment<Exam, ExamPlacement> assignment, Exam exam, ExamPeriod period) {
    278        boolean single = exam.getSize() <= (exam.hasAltSeating() ? getAltSize() : getSize());
    279        if (getRoomSharing() == null || !single) {
    280            for (ExamPlacement conflict: getContext(assignment).getPlacements(period.getIndex()))
    281                if (!conflict.variable().equals(exam)) return true;
    282            if (getParentRoom() != null && getParentRoom().isHard()) {
    283                for (ExamPlacement conflict: getParentRoom().getContext(assignment).getPlacements(period.getIndex()))
    284                    if (!conflict.variable().equals(exam)) return true;
    285            }
    286            if (getPartitions() != null) {
    287                for (ExamRoom partition: getPartitions()) {
    288                    if (partition.isHard())
    289                        for (ExamPlacement conflict: partition.getContext(assignment).getPlacements(period.getIndex()))
    290                            if (!conflict.variable().equals(exam)) return true;
    291                }
    292            }
    293            return false;
    294        } else {
    295            if (getParentRoom() != null && getParentRoom().isHard()) {
    296                for (ExamPlacement conflict: getParentRoom().getContext(assignment).getPlacements(period.getIndex()))
    297                    if (!conflict.variable().equals(exam)) return true;
    298            }
    299            if (getPartitions() != null) {
    300                for (ExamRoom partition: getPartitions()) {
    301                    if (partition.isHard())
    302                        for (ExamPlacement conflict: partition.getContext(assignment).getPlacements(period.getIndex()))
    303                            if (!conflict.variable().equals(exam)) return true;
    304                }
    305            }
    306            return getRoomSharing().inConflict(exam, getContext(assignment).getPlacements(period.getIndex()), this);
    307        }
    308    }
    309
    310    /**
    311     * Compute conflicts between the given assignment of an exam and all the
    312     * current assignments (of this room)
    313     */
    314    @Override
    315    public void computeConflicts(Assignment<Exam, ExamPlacement> assignment, ExamPlacement p, Set<ExamPlacement> conflicts) {
    316        if (!isHard()) return;
    317        if (!p.contains(this)) return;
    318
    319        if (getParentRoom() != null && p.contains(getParentRoom())) {
    320            conflicts.add(p); return;
    321        }
    322
    323        computeConflicts(assignment, p.variable(), p.getPeriod(), conflicts);
    324    }
    325
    326    /**
    327     * Checks whether there is a conflict between the given assignment of an
    328     * exam and all the current assignments (of this room)
    329     */
    330    @Override
    331    public boolean inConflict(Assignment<Exam, ExamPlacement> assignment, ExamPlacement p) {
    332        if (!isHard()) return false;
    333        if (!p.contains(this)) return false;
    334        if (getParentRoom() != null && p.contains(getParentRoom())) return false;
    335
    336        return inConflict(assignment, p.variable(), p.getPeriod());
    337    }
    338
    339    /**
    340     * False if the given two assignments are using this room at the same period
    341     */
    342    @Override
    343    public boolean isConsistent(ExamPlacement p1, ExamPlacement p2) {
    344        return !isHard() || (p1.getPeriod() != p2.getPeriod() || !p1.contains(this) || !p2.contains(this));
    345    }
    346
    347    /**
    348     * An exam was assigned, update room assignment table
    349     */
    350    @Override
    351    public void assigned(Assignment<Exam, ExamPlacement> assignment, long iteration, ExamPlacement p) {
    352        if (p.contains(this)) {
    353            if (!getContext(assignment).getPlacements(p.getPeriod().getIndex()).isEmpty() || getParentRoom() != null || getPartitions() != null) {
    354                HashSet<ExamPlacement> confs = new HashSet<ExamPlacement>();
    355                computeConflicts(assignment, p, confs);
    356                for (ExamPlacement conf: confs)
    357                    assignment.unassign(iteration, conf.variable());
    358                if (iConstraintListeners != null) {
    359                    for (ConstraintListener<Exam, ExamPlacement> listener : iConstraintListeners)
    360                        listener.constraintAfterAssigned(assignment, iteration, this, p, confs);
    361                }
    362            }
    363            getContext(assignment).assigned(assignment, p);
    364        }
    365    }
    366
    367    /**
    368     * An exam was unassigned, update room assignment table
    369     */
    370    @Override
    371    public void unassigned(Assignment<Exam, ExamPlacement> assignment, long iteration, ExamPlacement p) {
    372        if (p.contains(this))
    373            getContext(assignment).unassigned(assignment, p);
    374    }
    375
    376    /**
    377     * Checks two rooms for equality
    378     */
    379    @Override
    380    public boolean equals(Object o) {
    381        if (o == null || !(o instanceof ExamRoom))
    382            return false;
    383        ExamRoom r = (ExamRoom) o;
    384        return getId() == r.getId();
    385    }
    386
    387    /**
    388     * Hash code
    389     */
    390    @Override
    391    public int hashCode() {
    392        return (int) (getId() ^ (getId() >>> 32));
    393    }
    394
    395    /**
    396     * Room name
    397     */
    398    @Override
    399    public String getName() {
    400        return (hasName() ? iName : String.valueOf(getId()));
    401    }
    402
    403    /**
    404     * Room name
    405     * @return true if the room name is set and not empty
    406     */
    407    public boolean hasName() {
    408        return (iName != null && iName.length() > 0);
    409    }
    410
    411    /**
    412     * Room unique id
    413     */
    414    @Override
    415    public String toString() {
    416        return getName();
    417    }
    418
    419    /**
    420     * Add partition of this room. This room is unavailable at a time when one of the partition
    421     * is not available and vice versa.
    422     * @param room room partition
    423     */
    424    public void addPartition(ExamRoom room) {
    425        room.iParentRoom = this;
    426        if (iPartitions == null) iPartitions = new ArrayList<ExamRoom>();
    427        iPartitions.add(room);
    428    }
    429
    430    /**
    431     * If this room is a partition of some other room, returns the parent room (which is partitioned).
    432     * @return parent room
    433     */
    434    public ExamRoom getParentRoom() { return iParentRoom; }
    435
    436    /**
    437     * If this room is partitioned into multiple rooms, return room partitions
    438     * @return room partitions
    439     */
    440    public List<ExamRoom> getPartitions() { return iPartitions; }
    441
    442
    443    /**
    444     * Compare two rooms (by unique id)
    445     */
    446    @Override
    447    public int compareTo(Constraint<Exam, ExamPlacement> o) {
    448        return toString().compareTo(o.toString());
    449    }
    450
    451    @Override
    452    public ExamRoomContext createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) {
    453        return new ExamRoomContext(assignment);
    454    }
    455
    456    public class ExamRoomContext implements AssignmentConstraintContext<Exam, ExamPlacement> {
    457        private List<ExamPlacement>[] iTable;
    458
    459        @SuppressWarnings("unchecked")
    460        public ExamRoomContext(Assignment<Exam, ExamPlacement> assignment) {
    461            ExamModel model = (ExamModel)getModel();
    462            iTable = new List[model.getNrPeriods()];
    463            for (int i = 0; i < iTable.length; i++)
    464                iTable[i] = new ArrayList<ExamPlacement>();
    465            for (Exam exam: variables()) {
    466                ExamPlacement placement = assignment.getValue(exam);
    467                if (placement != null && placement.contains(ExamRoom.this))
    468                    iTable[placement.getPeriod().getIndex()].add(placement);
    469            }
    470        }
    471
    472        @Override
    473        public void assigned(Assignment<Exam, ExamPlacement> assignment, ExamPlacement placement) {
    474            if (placement.contains(ExamRoom.this))
    475                iTable[placement.getPeriod().getIndex()].add(placement);
    476        }
    477
    478        @Override
    479        public void unassigned(Assignment<Exam, ExamPlacement> assignment, ExamPlacement placement) {
    480            if (placement.contains(ExamRoom.this))
    481                iTable[placement.getPeriod().getIndex()].remove(placement);
    482        }
    483
    484        public List<ExamPlacement> getPlacements(int period) { return iTable[period]; }
    485    }
    486
    487
    488    /**
    489     * Check that the room and its parent are not used at the same time
    490     */
    491    public static boolean checkParents(Collection<ExamRoomPlacement> roomsSoFar, ExamRoomPlacement room) {
    492        if (room.getRoom().getParentRoom() != null) {
    493            // check if already lists the parent
    494            for (ExamRoomPlacement r: roomsSoFar)
    495                if (r.getRoom().equals(room.getRoom().getParentRoom())) return false;
    496        }
    497        if (room.getRoom().getPartitions() != null) {
    498            // check if has any of the partitions
    499            for (ExamRoomPlacement r: roomsSoFar)
    500                if (room.getRoom().getPartitions().contains(r.getRoom())) return false;
    501        }
    502        return true;
    503    }
    504}