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