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