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}