001 package net.sf.cpsolver.exam.model;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.List;
006 import java.util.Set;
007
008 import org.dom4j.Element;
009
010 import net.sf.cpsolver.coursett.IdConvertor;
011 import net.sf.cpsolver.ifs.model.Model;
012 import net.sf.cpsolver.ifs.util.DataProperties;
013 import net.sf.cpsolver.ifs.util.ToolBox;
014
015 /**
016 * Abstract room sharing model. Defines when and under what conditions two or more exams can share a room.<br>
017 * <br>
018 *
019 * @version ExamTT 1.2 (Examination Timetabling)<br>
020 * Copyright (C) 2008 - 2012 Tomas Muller<br>
021 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
022 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
023 * <br>
024 * This library is free software; you can redistribute it and/or modify
025 * it under the terms of the GNU Lesser General Public License as
026 * published by the Free Software Foundation; either version 3 of the
027 * License, or (at your option) any later version. <br>
028 * <br>
029 * This library is distributed in the hope that it will be useful, but
030 * WITHOUT ANY WARRANTY; without even the implied warranty of
031 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
032 * Lesser General Public License for more details. <br>
033 * <br>
034 * You should have received a copy of the GNU Lesser General Public
035 * License along with this library; if not see
036 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
037 */
038 public abstract class ExamRoomSharing {
039
040 public ExamRoomSharing(Model<Exam, ExamPlacement> model, DataProperties config) {}
041
042 /**
043 * True if given examination can not be placed in the same room at the same period as the other examinations
044 * @param exam examination placement in question
045 * @param other exams currently assigned in the room at the requested period
046 * @param room examination room in questions
047 * @return true if there is a conflict
048 */
049 public boolean inConflict(ExamPlacement exam, Collection<ExamPlacement> other, ExamRoom room) {
050 if (exam.getRoomPlacements().size() != 1)
051 return !other.isEmpty();
052
053 return inConflict(exam.variable(), other, room);
054 }
055
056 /**
057 * True if given examination can not be placed in the same room at the same period as the other examinations
058 * @param exam examination in question
059 * @param other exams currently assigned in the room at the requested period
060 * @param room examination room in questions
061 * @return true if there is a conflict
062 */
063 public boolean inConflict(Exam exam, Collection<ExamPlacement> other, ExamRoom room) {
064 int total = exam.getSize();
065 boolean altSeating = exam.hasAltSeating();
066 for (ExamPlacement x: other) {
067 if (x.variable().equals(exam)) continue;
068 if (x.getRoomPlacements().size() != 1) return true; // already split into multiple rooms
069 if (!canShareRoom(exam, x.variable())) return true; // sharing not allowed between the pair
070 total += x.variable().getSize();
071 if (x.variable().hasAltSeating()) altSeating = true;
072 }
073
074 return total > (altSeating ? room.getAltSize() : room.getSize()); // check size limit
075 }
076
077 /**
078 * Compute conflicting placement for the case when a given examination needs to be placed in the same room at the same period as the other examinations
079 * @param exam examination placement in question
080 * @param other exams currently assigned in the room at the requested period
081 * @param room examination room in questions
082 */
083 public void computeConflicts(ExamPlacement exam, Collection<ExamPlacement> other, ExamRoom room, Set<ExamPlacement> conflicts) {
084 // more than one room is required -> no sharing
085 if (exam.getRoomPlacements().size() != 1) {
086 conflicts.addAll(other);
087 return;
088 }
089
090 computeConflicts(exam.variable(), other, room, conflicts);
091 }
092
093 /**
094 * Compute conflicting placement for the case when a given examination needs to be placed in the same room at the same period as the other examinations
095 * @param exam examination in question
096 * @param other exams currently assigned in the room at the requested period
097 * @param room examination room in questions
098 */
099 public void computeConflicts(Exam exam, Collection<ExamPlacement> other, ExamRoom room, Set<ExamPlacement> conflicts) {
100 int total = exam.getSize();
101 boolean altSeating = exam.hasAltSeating();
102 List<ExamPlacement> adepts = new ArrayList<ExamPlacement>();
103 for (ExamPlacement x: other) {
104 if (x.variable().equals(exam)) continue;
105 // already split into multiple rooms
106 if (x.getRoomPlacements().size() != 1) {
107 conflicts.add(x); continue;
108 }
109 // sharing not allowed between the pair
110 if (!canShareRoom(exam, x.variable())) {
111 conflicts.add(x); continue;
112 }
113 if (x.variable().hasAltSeating()) altSeating = true;
114 total += x.variable().getSize();
115 adepts.add(x);
116 }
117
118 // fix the total size if needed
119 while (total > (altSeating ? room.getAltSize() : room.getSize()) && !adepts.isEmpty()) {
120 ExamPlacement x = ToolBox.random(adepts);
121 adepts.remove(x);
122 conflicts.add(x);
123 total -= x.variable().getSize();
124 }
125 }
126
127
128 /**
129 * True if given two exams can share a room
130 */
131 public abstract boolean canShareRoom(Exam x1, Exam x2);
132
133 /**
134 * Save sharing information (if needed) for a given exam
135 */
136 public void save(Exam exam, Element element, IdConvertor idConvertor) {}
137
138 /**
139 * Load sharing information (if needed) for a given exam
140 */
141 public void load(Exam exam, Element element) {}
142 }