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