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}