001package org.cpsolver.coursett.model; 002 003import java.util.ArrayList; 004import java.util.Enumeration; 005import java.util.List; 006 007import org.cpsolver.coursett.Constants; 008import org.cpsolver.coursett.constraint.GroupConstraint; 009import org.cpsolver.coursett.constraint.InstructorConstraint; 010import org.cpsolver.coursett.constraint.SpreadConstraint; 011import org.cpsolver.coursett.preference.PreferenceCombination; 012import org.cpsolver.ifs.assignment.Assignment; 013import org.cpsolver.ifs.criteria.Criterion; 014import org.cpsolver.ifs.model.Value; 015import org.cpsolver.ifs.util.DistanceMetric; 016import org.cpsolver.ifs.util.ToolBox; 017 018 019/** 020 * Placement (value). <br> 021 * <br> 022 * It combines room and time location 023 * 024 * @version CourseTT 1.3 (University Course Timetabling)<br> 025 * Copyright (C) 2006 - 2014 Tomas Muller<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 */ 043 044public class Placement extends Value<Lecture, Placement> { 045 private TimeLocation iTimeLocation; 046 private RoomLocation iRoomLocation; 047 private List<RoomLocation> iRoomLocations = null; 048 private Long iAssignmentId = null; 049 private int iHashCode = 0; 050 051 /** 052 * Constructor 053 * 054 * @param lecture 055 * lecture 056 * @param timeLocation 057 * time location 058 * @param roomLocation 059 * room location 060 */ 061 public Placement(Lecture lecture, TimeLocation timeLocation, RoomLocation roomLocation) { 062 super(lecture); 063 iTimeLocation = timeLocation; 064 iRoomLocation = roomLocation; 065 if (iRoomLocation == null) { 066 iRoomLocations = new ArrayList<RoomLocation>(0); 067 } 068 iHashCode = getName().hashCode(); 069 } 070 071 public Placement(Lecture lecture, TimeLocation timeLocation, java.util.List<RoomLocation> roomLocations) { 072 super(lecture); 073 iTimeLocation = timeLocation; 074 iRoomLocation = (roomLocations.isEmpty() ? null : (RoomLocation) roomLocations.get(0)); 075 if (roomLocations.size() != 1) { 076 iRoomLocations = new ArrayList<RoomLocation>(roomLocations); 077 } 078 iHashCode = getName().hashCode(); 079 } 080 081 /** Time location 082 * @return time of this placement 083 **/ 084 public TimeLocation getTimeLocation() { 085 return iTimeLocation; 086 } 087 088 /** Room location 089 * @return room of this placement 090 **/ 091 public RoomLocation getRoomLocation() { 092 return iRoomLocation; 093 } 094 095 /** Room locations (multi-room placement) 096 * @return rooms of this placement (if there are more than one) 097 **/ 098 public List<RoomLocation> getRoomLocations() { 099 return iRoomLocations; 100 } 101 102 public List<Long> getBuildingIds() { 103 if (isMultiRoom()) { 104 List<Long> ret = new ArrayList<Long>(iRoomLocations.size()); 105 for (RoomLocation r : iRoomLocations) { 106 ret.add(r.getBuildingId()); 107 } 108 return ret; 109 } else { 110 List<Long> ret = new ArrayList<Long>(1); 111 ret.add(iRoomLocation.getBuildingId()); 112 return ret; 113 } 114 } 115 116 public List<Long> getRoomIds() { 117 if (isMultiRoom()) { 118 List<Long> ret = new ArrayList<Long>(iRoomLocations.size()); 119 for (RoomLocation r : iRoomLocations) { 120 ret.add(r.getId()); 121 } 122 return ret; 123 } else { 124 List<Long> ret = new ArrayList<Long>(1); 125 ret.add(iRoomLocation.getId()); 126 return ret; 127 } 128 } 129 130 public List<String> getRoomNames() { 131 if (isMultiRoom()) { 132 List<String> ret = new ArrayList<String>(iRoomLocations.size()); 133 for (RoomLocation r : iRoomLocations) { 134 ret.add(r.getName()); 135 } 136 return ret; 137 } else { 138 List<String> ret = new ArrayList<String>(1); 139 if (iRoomLocation != null) 140 ret.add(iRoomLocation.getName()); 141 return ret; 142 } 143 } 144 145 public List<Integer> getRoomPrefs() { 146 if (isMultiRoom()) { 147 List<Integer> ret = new ArrayList<Integer>(iRoomLocations.size()); 148 for (RoomLocation r : iRoomLocations) { 149 ret.add(r.getPreference()); 150 } 151 return ret; 152 } else { 153 List<Integer> ret = new ArrayList<Integer>(1); 154 if (iRoomLocation != null) 155 ret.add(iRoomLocation.getPreference()); 156 return ret; 157 } 158 } 159 160 public boolean isMultiRoom() { 161 return (iRoomLocations != null && iRoomLocations.size() != 1); 162 } 163 164 public RoomLocation getRoomLocation(Long roomId) { 165 if (isMultiRoom()) { 166 for (RoomLocation r : iRoomLocations) { 167 if (r.getId().equals(roomId)) 168 return r; 169 } 170 } else if (iRoomLocation != null && iRoomLocation.getId().equals(roomId)) 171 return iRoomLocation; 172 return null; 173 } 174 175 public boolean hasRoomLocation(Long roomId) { 176 if (isMultiRoom()) { 177 for (RoomLocation r : iRoomLocations) { 178 if (r.getId().equals(roomId)) 179 return true; 180 } 181 return false; 182 } else 183 return iRoomLocation != null && iRoomLocation.getId().equals(roomId); 184 } 185 186 public String getRoomName(String delim) { 187 if (isMultiRoom()) { 188 StringBuffer sb = new StringBuffer(); 189 for (RoomLocation r : iRoomLocations) { 190 if (sb.length() > 0) 191 sb.append(delim); 192 sb.append(r.getName()); 193 } 194 return sb.toString(); 195 } else { 196 return (getRoomLocation() == null ? "" : getRoomLocation().getName()); 197 } 198 } 199 200 @Override 201 public String getName() { 202 return getName(true); 203 } 204 205 public String getName(boolean useAmPm) { 206 Lecture lecture = variable(); 207 return getTimeLocation().getName(useAmPm) + " " + getRoomName(", ") 208 + (lecture != null && lecture.getInstructorName() != null ? " " + lecture.getInstructorName() : ""); 209 } 210 211 public String getLongName(boolean useAmPm) { 212 Lecture lecture = variable(); 213 if (isMultiRoom()) { 214 StringBuffer sb = new StringBuffer(); 215 for (RoomLocation r : iRoomLocations) { 216 if (sb.length() > 0) 217 sb.append(", "); 218 sb.append(r.getName()); 219 } 220 return getTimeLocation().getLongName(useAmPm) + " " + sb 221 + (lecture.getInstructorName() != null ? " " + lecture.getInstructorName() : ""); 222 } else 223 return getTimeLocation().getLongName(useAmPm) 224 + (getRoomLocation() == null ? "" : " " + getRoomLocation().getName()) 225 + (lecture.getInstructorName() != null ? " " + lecture.getInstructorName() : ""); 226 } 227 228 @Deprecated 229 public String getLongName() { 230 return getLongName(true); 231 } 232 233 public boolean sameRooms(Placement placement) { 234 if (placement.isMultiRoom() != isMultiRoom()) 235 return false; 236 if (isMultiRoom()) { 237 if (placement.getRoomLocations().size() != getRoomLocations().size()) 238 return false; 239 return placement.getRoomLocations().containsAll(getRoomLocations()); 240 } else { 241 if (placement.getRoomLocation() == null) 242 return getRoomLocation() == null; 243 return placement.getRoomLocation().equals(getRoomLocation()); 244 } 245 } 246 247 public boolean shareRooms(Placement placement) { 248 if (isMultiRoom()) { 249 if (placement.isMultiRoom()) { 250 for (RoomLocation rl : getRoomLocations()) { 251 if (rl.getRoomConstraint() == null || !rl.getRoomConstraint().getConstraint()) 252 continue; 253 if (placement.getRoomLocations().contains(rl)) 254 return true; 255 } 256 return false; 257 } else { 258 return getRoomLocations().contains(placement.getRoomLocation()); 259 } 260 } else { 261 if (getRoomLocation().getRoomConstraint() == null || !getRoomLocation().getRoomConstraint().getConstraint()) 262 return false; 263 if (placement.isMultiRoom()) { 264 return placement.getRoomLocations().contains(getRoomLocation()); 265 } else { 266 return getRoomLocation().equals(placement.getRoomLocation()); 267 } 268 } 269 } 270 271 public int nrDifferentRooms(Placement placement) { 272 if (isMultiRoom()) { 273 int ret = 0; 274 for (RoomLocation r : getRoomLocations()) { 275 if (!placement.getRoomLocations().contains(r)) 276 ret++; 277 } 278 return ret; 279 } else { 280 return (placement.getRoomLocation().equals(getRoomLocation()) ? 0 : 1); 281 } 282 } 283 284 public int nrDifferentBuildings(Placement placement) { 285 if (isMultiRoom()) { 286 int ret = 0; 287 for (RoomLocation r : getRoomLocations()) { 288 boolean contains = false; 289 for (RoomLocation q : placement.getRoomLocations()) { 290 if (ToolBox.equals(r.getBuildingId(), q.getBuildingId())) 291 contains = true; 292 } 293 if (!contains) 294 ret++; 295 } 296 return ret; 297 } else { 298 return (ToolBox.equals(placement.getRoomLocation().getBuildingId(), getRoomLocation().getBuildingId()) ? 0 299 : 1); 300 } 301 } 302 303 public int sumRoomPreference() { 304 if (isMultiRoom()) { 305 int ret = 0; 306 for (RoomLocation r : getRoomLocations()) { 307 ret += r.getPreference(); 308 } 309 return ret; 310 } else { 311 return getRoomLocation().getPreference(); 312 } 313 } 314 315 public int getRoomPreference() { 316 if (isMultiRoom()) { 317 PreferenceCombination p = PreferenceCombination.getDefault(); 318 for (RoomLocation r : getRoomLocations()) { 319 p.addPreferenceInt(r.getPreference()); 320 } 321 return p.getPreferenceInt(); 322 } else { 323 return getRoomLocation().getPreference(); 324 } 325 } 326 327 public int getRoomSize() { 328 if (isMultiRoom()) { 329 if (getRoomLocations().isEmpty()) return 0; 330 int roomSize = Integer.MAX_VALUE; 331 for (RoomLocation r : getRoomLocations()) { 332 roomSize = Math.min(roomSize, r.getRoomSize()); 333 } 334 return roomSize; 335 } else { 336 return getRoomLocation().getRoomSize(); 337 } 338 } 339 340 public boolean isHard(Assignment<Lecture, Placement> assignment) { 341 if (Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(getTimeLocation().getPreference()))) 342 return true; 343 if (getRoomLocation() != null && Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(getRoomLocation().getPreference()))) 344 return true; 345 Lecture lecture = variable(); 346 for (GroupConstraint gc : lecture.hardGroupSoftConstraints()) { 347 if (gc.isSatisfied(assignment)) 348 continue; 349 if (Constants.sPreferenceProhibited.equals(gc.getPrologPreference())) 350 return true; 351 if (Constants.sPreferenceRequired.equals(gc.getPrologPreference())) 352 return true; 353 } 354 return false; 355 } 356 357 public boolean sameTime(Placement placement) { 358 return placement.getTimeLocation().equals(getTimeLocation()); 359 } 360 361 @Override 362 public boolean equals(Object object) { 363 if (object == null || !(object instanceof Placement)) 364 return false; 365 Placement placement = (Placement) object; 366 if (placement.getId() == getId()) 367 return true; // quick check 368 Lecture lecture = placement.variable(); 369 Lecture thisLecture = variable(); 370 if (lecture != null && thisLecture != null && !lecture.getClassId().equals(thisLecture.getClassId())) 371 return false; 372 if (!sameRooms(placement)) 373 return false; 374 if (!sameTime(placement)) 375 return false; 376 return true; 377 } 378 379 @Override 380 public int hashCode() { 381 return iHashCode; 382 } 383 384 @Override 385 public String toString() { 386 return variable().getName() + " " + getName(); 387 } 388 389 /** Distance between two placements 390 * @param m distance matrix 391 * @param p1 first placement 392 * @param p2 second placement 393 * @return maximal distance in meters between the two placement 394 **/ 395 public static double getDistanceInMeters(DistanceMetric m, Placement p1, Placement p2) { 396 if (p1.isMultiRoom()) { 397 if (p2.isMultiRoom()) { 398 double dist = 0.0; 399 for (RoomLocation r1 : p1.getRoomLocations()) { 400 for (RoomLocation r2 : p2.getRoomLocations()) { 401 dist = Math.max(dist, r1.getDistanceInMeters(m, r2)); 402 } 403 } 404 return dist; 405 } else { 406 if (p2.getRoomLocation() == null) 407 return 0.0; 408 double dist = 0.0; 409 for (RoomLocation r1 : p1.getRoomLocations()) { 410 dist = Math.max(dist, r1.getDistanceInMeters(m, p2.getRoomLocation())); 411 } 412 return dist; 413 } 414 } else if (p2.isMultiRoom()) { 415 if (p1.getRoomLocation() == null) 416 return 0.0; 417 double dist = 0.0; 418 for (RoomLocation r2 : p2.getRoomLocations()) { 419 dist = Math.max(dist, p1.getRoomLocation().getDistanceInMeters(m, r2)); 420 } 421 return dist; 422 } else { 423 if (p1.getRoomLocation() == null || p2.getRoomLocation() == null) 424 return 0.0; 425 return p1.getRoomLocation().getDistanceInMeters(m, p2.getRoomLocation()); 426 } 427 } 428 429 /** Distance between two placements 430 * @param m distance matrix 431 * @param p1 first placement 432 * @param p2 second placement 433 * @return maximal distance in minutes between the two placement 434 **/ 435 public static int getDistanceInMinutes(DistanceMetric m, Placement p1, Placement p2) { 436 if (p1.isMultiRoom()) { 437 if (p2.isMultiRoom()) { 438 int dist = 0; 439 for (RoomLocation r1 : p1.getRoomLocations()) { 440 for (RoomLocation r2 : p2.getRoomLocations()) { 441 dist = Math.max(dist, r1.getDistanceInMinutes(m, r2)); 442 } 443 } 444 return dist; 445 } else { 446 if (p2.getRoomLocation() == null) 447 return 0; 448 int dist = 0; 449 for (RoomLocation r1 : p1.getRoomLocations()) { 450 dist = Math.max(dist, r1.getDistanceInMinutes(m, p2.getRoomLocation())); 451 } 452 return dist; 453 } 454 } else if (p2.isMultiRoom()) { 455 if (p1.getRoomLocation() == null) 456 return 0; 457 int dist = 0; 458 for (RoomLocation r2 : p2.getRoomLocations()) { 459 dist = Math.max(dist, p1.getRoomLocation().getDistanceInMinutes(m, r2)); 460 } 461 return dist; 462 } else { 463 if (p1.getRoomLocation() == null || p2.getRoomLocation() == null) 464 return 0; 465 return p1.getRoomLocation().getDistanceInMinutes(m, p2.getRoomLocation()); 466 } 467 } 468 469 public int getCommitedConflicts() { 470 int ret = 0; 471 Lecture lecture = variable(); 472 for (Student student : lecture.students()) { 473 ret += student.countConflictPlacements(this); 474 } 475 return ret; 476 } 477 478 public Long getAssignmentId() { 479 return iAssignmentId; 480 } 481 482 public void setAssignmentId(Long assignmentId) { 483 iAssignmentId = assignmentId; 484 } 485 486 public boolean canShareRooms(Placement other) { 487 return (variable()).canShareRoom(other.variable()); 488 } 489 490 public boolean isValid() { 491 Lecture lecture = variable(); 492 if (!lecture.isValid(this)) 493 return false; 494 for (InstructorConstraint ic : lecture.getInstructorConstraints()) { 495 if (!ic.isAvailable(lecture, this)) 496 return false; 497 } 498 if (lecture.getNrRooms() > 0) { 499 if (isMultiRoom()) { 500 for (RoomLocation roomLocation : getRoomLocations()) { 501 if (roomLocation.getRoomConstraint() != null 502 && !roomLocation.getRoomConstraint().isAvailable(lecture, getTimeLocation(), 503 lecture.getScheduler())) 504 return false; 505 } 506 } else { 507 if (getRoomLocation().getRoomConstraint() != null 508 && !getRoomLocation().getRoomConstraint().isAvailable(lecture, getTimeLocation(), 509 lecture.getScheduler())) 510 return false; 511 } 512 } 513 return true; 514 } 515 516 public String getNotValidReason(Assignment<Lecture, Placement> assignment, boolean useAmPm) { 517 Lecture lecture = variable(); 518 String reason = lecture.getNotValidReason(assignment, this, useAmPm); 519 if (reason != null) 520 return reason; 521 for (InstructorConstraint ic : lecture.getInstructorConstraints()) { 522 if (!ic.isAvailable(lecture, this)) { 523 if (!ic.isAvailable(lecture, getTimeLocation())) { 524 for (Placement c: ic.getUnavailabilities()) { 525 if (c.getTimeLocation().hasIntersection(getTimeLocation()) && !lecture.canShareRoom(c.variable())) 526 return "instructor " + ic.getName() + " not available at " + getTimeLocation().getLongName(useAmPm) + " due to " + c.variable().getName(); 527 } 528 return "instructor " + ic.getName() + " not available at " + getTimeLocation().getLongName(useAmPm); 529 } else 530 return "placement " + getTimeLocation().getLongName(useAmPm) + " " + getRoomName(", ") + " is too far for instructor " + ic.getName(); 531 } 532 } 533 if (lecture.getNrRooms() > 0) { 534 if (isMultiRoom()) { 535 for (RoomLocation roomLocation : getRoomLocations()) { 536 if (roomLocation.getRoomConstraint() != null && !roomLocation.getRoomConstraint().isAvailable(lecture, getTimeLocation(), lecture.getScheduler())) { 537 if (roomLocation.getRoomConstraint().getAvailableArray() != null) { 538 for (Enumeration<Integer> e = getTimeLocation().getSlots(); e.hasMoreElements();) { 539 int slot = e.nextElement(); 540 if (roomLocation.getRoomConstraint().getAvailableArray()[slot] != null) { 541 for (Placement c : roomLocation.getRoomConstraint().getAvailableArray()[slot]) { 542 if (c.getTimeLocation().hasIntersection(getTimeLocation()) && !lecture.canShareRoom(c.variable())) { 543 return "room " + roomLocation.getName() + " not available at " + getTimeLocation().getLongName(useAmPm) + " due to " + c.variable().getName(); 544 } 545 } 546 } 547 } 548 } 549 return "room " + roomLocation.getName() + " not available at " + getTimeLocation().getLongName(useAmPm); 550 } 551 } 552 } else { 553 if (getRoomLocation().getRoomConstraint() != null && !getRoomLocation().getRoomConstraint().isAvailable(lecture, getTimeLocation(), lecture.getScheduler())) 554 if (getRoomLocation().getRoomConstraint().getAvailableArray() != null) { 555 for (Enumeration<Integer> e = getTimeLocation().getSlots(); e.hasMoreElements();) { 556 int slot = e.nextElement(); 557 if (getRoomLocation().getRoomConstraint().getAvailableArray()[slot] != null) { 558 for (Placement c : getRoomLocation().getRoomConstraint().getAvailableArray()[slot]) { 559 if (c.getTimeLocation().hasIntersection(getTimeLocation()) && !lecture.canShareRoom(c.variable())) { 560 return "room " + getRoomLocation().getName() + " not available at " + getTimeLocation().getLongName(useAmPm) + " due to " + c.variable().getName(); 561 } 562 } 563 } 564 } 565 } 566 return "room " + getRoomLocation().getName() + " not available at " + getTimeLocation().getLongName(useAmPm); 567 } 568 } 569 return reason; 570 } 571 572 @Deprecated 573 public String getNotValidReason(Assignment<Lecture, Placement> assignment) { 574 return getNotValidReason(assignment, true); 575 } 576 577 public int getNrRooms() { 578 if (iRoomLocations != null) 579 return iRoomLocations.size(); 580 return (iRoomLocation == null ? 0 : 1); 581 } 582 583 public int getSpreadPenalty(Assignment<Lecture, Placement> assignment) { 584 int spread = 0; 585 for (SpreadConstraint sc : variable().getSpreadConstraints()) { 586 spread += sc.getPenalty(assignment, this); 587 } 588 return spread; 589 } 590 591 public int getMaxSpreadPenalty(Assignment<Lecture, Placement> assignment) { 592 int spread = 0; 593 for (SpreadConstraint sc : variable().getSpreadConstraints()) { 594 spread += sc.getMaxPenalty(assignment, this); 595 } 596 return spread; 597 } 598 599 @Override 600 public double toDouble(Assignment<Lecture, Placement> assignment) { 601 double ret = 0.0; 602 for (Criterion<Lecture, Placement> criterion: variable().getModel().getCriteria()) 603 ret += criterion.getWeightedValue(assignment, this, null); 604 return ret; 605 } 606 607 private transient Object iAssignment = null; 608 609 public Object getAssignment() { 610 return iAssignment; 611 } 612 613 public void setAssignment(Object assignment) { 614 iAssignment = assignment; 615 } 616}