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