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