001package org.cpsolver.coursett.constraint; 002 003import java.util.ArrayList; 004import java.util.BitSet; 005import java.util.Collection; 006import java.util.Enumeration; 007import java.util.HashSet; 008import java.util.List; 009import java.util.Set; 010 011import org.cpsolver.coursett.Constants; 012import org.cpsolver.coursett.criteria.BrokenTimePatterns; 013import org.cpsolver.coursett.criteria.UselessHalfHours; 014import org.cpsolver.coursett.model.Lecture; 015import org.cpsolver.coursett.model.Placement; 016import org.cpsolver.coursett.model.RoomSharingModel; 017import org.cpsolver.coursett.model.TimeLocation; 018import org.cpsolver.coursett.model.TimetableModel; 019import org.cpsolver.ifs.assignment.Assignment; 020import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext; 021import org.cpsolver.ifs.assignment.context.ConstraintWithContext; 022import org.cpsolver.ifs.model.Model; 023import org.cpsolver.ifs.util.DataProperties; 024 025 026/** 027 * Room constraint. <br> 028 * Classes with the same room can not overlap in time. 029 * 030 * @version CourseTT 1.3 (University Course Timetabling)<br> 031 * Copyright (C) 2006 - 2014 Tomáš Müller<br> 032 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 033 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 034 * <br> 035 * This library is free software; you can redistribute it and/or modify 036 * it under the terms of the GNU Lesser General Public License as 037 * published by the Free Software Foundation; either version 3 of the 038 * License, or (at your option) any later version. <br> 039 * <br> 040 * This library is distributed in the hope that it will be useful, but 041 * WITHOUT ANY WARRANTY; without even the implied warranty of 042 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 043 * Lesser General Public License for more details. <br> 044 * <br> 045 * You should have received a copy of the GNU Lesser General Public 046 * License along with this library; if not see 047 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 048 */ 049 050public class RoomConstraint extends ConstraintWithContext<Lecture, Placement, RoomConstraint.RoomConstraintContext> { 051 private Long iResourceId; 052 private String iName; 053 private Long iBuildingId; 054 private int iCapacity = 0; 055 private List<Placement>[] iAvailable = null; 056 private boolean iConstraint = true; 057 058 private Double iPosX = null, iPosY = null; 059 private boolean iIgnoreTooFar = false; 060 061 private RoomSharingModel iRoomSharingModel = null; 062 063 private Long iType = null; 064 private int iDayOfWeekOffset = 0; 065 066 /** 067 * Constructor 068 * @param id room unique id 069 * @param name room name 070 * @param buildingId building unique id 071 * @param capacity room size 072 * @param roomSharingModel room sharing model 073 * @param x X-coordinate (latitude) 074 * @param y Y-coordinate (longitude) 075 * @param ignoreTooFar ignore distances if set to true 076 * @param constraint hard constraint if true (classes cannot overlap in this room) 077 */ 078 public RoomConstraint(Long id, String name, Long buildingId, int capacity, RoomSharingModel roomSharingModel, 079 Double x, Double y, boolean ignoreTooFar, boolean constraint) { 080 iResourceId = id; 081 iName = name; 082 iBuildingId = buildingId; 083 iCapacity = capacity; 084 iConstraint = constraint; 085 iRoomSharingModel = roomSharingModel; 086 iPosX = x; 087 iPosY = y; 088 iIgnoreTooFar = ignoreTooFar; 089 } 090 091 @Override 092 public void setModel(Model<Lecture, Placement> model) { 093 super.setModel(model); 094 if (model != null) { 095 DataProperties config = ((TimetableModel)model).getProperties(); 096 iDayOfWeekOffset = config.getPropertyInt("DatePattern.DayOfWeekOffset", 0); 097 } 098 } 099 100 @SuppressWarnings("unchecked") 101 public void setNotAvailable(Placement placement) { 102 if (iAvailable == null) { 103 iAvailable = new List[Constants.SLOTS_PER_DAY * Constants.NR_DAYS]; 104 for (int i = 0; i < iAvailable.length; i++) 105 iAvailable[i] = null; 106 } 107 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 108 int slot = e.nextElement(); 109 if (iAvailable[slot] == null) 110 iAvailable[slot] = new ArrayList<Placement>(1); 111 iAvailable[slot].add(placement); 112 } 113 for (Lecture lecture: variables()) 114 lecture.clearValueCache(); 115 } 116 117 public boolean isAvailable(int slot) { 118 if (getConstraint() && iAvailable != null && iAvailable[slot] != null && !iAvailable[slot].isEmpty()) 119 return false; 120 if (getSharingModel() != null && getSharingModel().isNotAvailable(slot)) 121 return false; 122 return true; 123 } 124 125 public boolean isAvailable(Lecture lecture, TimeLocation time, Long scheduler) { 126 if (iAvailable != null && getConstraint()) { 127 for (Enumeration<Integer> e = time.getSlots(); e.hasMoreElements();) { 128 int slot = e.nextElement(); 129 if (iAvailable[slot] != null) { 130 for (Placement p : iAvailable[slot]) { 131 if (lecture.canShareRoom(p.variable())) 132 continue; 133 if (time.shareWeeks(p.getTimeLocation())) 134 return false; 135 } 136 } 137 } 138 } 139 if (getSharingModel() != null && !getSharingModel().isAvailable(time, scheduler)) 140 return false; 141 return true; 142 } 143 144 public List<Placement>[] getAvailableArray() { 145 return iAvailable; 146 } 147 148 public RoomSharingModel getSharingModel() { 149 return iRoomSharingModel; 150 } 151 152 /** Room id 153 * @return room unique id 154 **/ 155 public Long getResourceId() { 156 return iResourceId; 157 } 158 159 /** Building id 160 * @return building unique id 161 **/ 162 public Long getBuildingId() { 163 return iBuildingId; 164 } 165 166 /** Room name */ 167 @Override 168 public String getName() { 169 return iName; 170 } 171 172 public String getRoomName() { 173 return iName; 174 } 175 176 /** Capacity 177 * @return room size 178 **/ 179 public int getCapacity() { 180 return iCapacity; 181 } 182 183 @Override 184 public void computeConflicts(Assignment<Lecture, Placement> assignment, Placement placement, Set<Placement> conflicts) { 185 if (!getConstraint()) 186 return; 187 if (!placement.hasRoomLocation(getResourceId())) 188 return; 189 Lecture lecture = placement.variable(); 190 Placement current = assignment.getValue(lecture); 191 Set<Placement> shared = null; 192 BitSet weekCode = placement.getTimeLocation().getWeekCode(); 193 RoomConstraintContext context = getContext(assignment); 194 195 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 196 int slot = e.nextElement(); 197 for (Placement confPlacement : context.getPlacements(slot)) { 198 if (!confPlacement.getTimeLocation().shareWeeks(weekCode)) 199 continue; 200 if (confPlacement.equals(current)) 201 continue; 202 if (shared != null && shared.contains(confPlacement)) 203 continue; 204 if (confPlacement.canShareRooms(placement) && checkRoomSize(placement, shared, confPlacement)) { 205 if (shared == null) shared = new HashSet<Placement>(); 206 shared.add(confPlacement); 207 continue; 208 } 209 conflicts.add(confPlacement); 210 } 211 } 212 } 213 214 public boolean checkRoomSize(Placement placement, Collection<Placement> other, Placement extra) { 215 int day = -1; 216 TimeLocation t1 = placement.getTimeLocation(); 217 while ((day = t1.getWeekCode().nextSetBit(1 + day)) >= 0) { 218 int dow = (day + iDayOfWeekOffset) % 7; 219 if ((t1.getDayCode() & Constants.DAY_CODES[dow]) == 0) continue; 220 if (extra != null) { 221 TimeLocation t2 = extra.getTimeLocation(); 222 if (!t2.hasDay(day) || (t2.getDayCode() & Constants.DAY_CODES[dow]) == 0) continue; 223 } 224 for (int i = 0; i < t1.getLength(); i++) { 225 int slot = t1.getStartSlot() + i; 226 int size = placement.variable().maxRoomUse(); 227 if (extra != null) { 228 TimeLocation t2 = extra.getTimeLocation(); 229 if (t2.getStartSlot() <= slot && slot < t2.getStartSlot() + t2.getLength()) 230 size += extra.variable().maxRoomUse(); 231 else 232 continue; 233 } 234 if (other != null) 235 for (Placement p: other) { 236 TimeLocation t2 = p.getTimeLocation(); 237 if (t2.hasDay(day) && (t2.getDayCode() & Constants.DAY_CODES[dow]) != 0 && t2.getStartSlot() <= slot && slot < t2.getStartSlot() + t2.getLength()) 238 size += p.variable().maxRoomUse(); 239 } 240 if (size > getCapacity()) { 241 return false; 242 } 243 } 244 } 245 return true; 246 } 247 248 public boolean checkRoomSize(Placement placement, Collection<Placement> other) { 249 return checkRoomSize(placement, other, null); 250 } 251 252 @Override 253 public boolean inConflict(Assignment<Lecture, Placement> assignment, Placement placement) { 254 if (!getConstraint()) 255 return false; 256 if (!placement.hasRoomLocation(getResourceId())) 257 return false; 258 Lecture lecture = placement.variable(); 259 Placement current = assignment.getValue(lecture); 260 Set<Placement> shared = null; 261 BitSet weekCode = placement.getTimeLocation().getWeekCode(); 262 RoomConstraintContext context = getContext(assignment); 263 264 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 265 int slot = e.nextElement(); 266 for (Placement confPlacement : context.getPlacements(slot)) { 267 if (!confPlacement.getTimeLocation().shareWeeks(weekCode)) 268 continue; 269 if (confPlacement.equals(current)) 270 continue; 271 if (shared != null && shared.contains(confPlacement)) 272 continue; 273 if (confPlacement.canShareRooms(placement) && checkRoomSize(placement, shared, confPlacement)) { 274 if (shared == null) shared = new HashSet<Placement>(); 275 shared.add(confPlacement); 276 continue; 277 } 278 return true; 279 } 280 } 281 return false; 282 } 283 284 @Override 285 public boolean isConsistent(Placement p1, Placement p2) { 286 if (!getConstraint()) 287 return true; 288 if (!p1.hasRoomLocation(getResourceId())) 289 return false; 290 if (!p2.hasRoomLocation(getResourceId())) 291 return false; 292 if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) { 293 if (!p1.canShareRooms(p2) || (p1.variable()).maxRoomUse() + (p2.variable()).maxRoomUse() > getCapacity()) 294 return true; 295 } 296 return false; 297 } 298 299 @Override 300 public void assigned(Assignment<Lecture, Placement> assignment, long iteration, Placement placement) { 301 if (placement.hasRoomLocation(getResourceId())) 302 super.assigned(assignment, iteration, placement); 303 } 304 305 @Override 306 public void unassigned(Assignment<Lecture, Placement> assignment, long iteration, Placement placement) { 307 if (placement.hasRoomLocation(getResourceId())) 308 super.unassigned(assignment, iteration, placement); 309 } 310 311 /** 312 * Lookup table getResource()[slot] → lecture using this room placed in the 313 * given time slot (null if empty) 314 * @param assignment current assignment 315 * @param slot time slot 316 * @return list of placements in the room in the given time 317 */ 318 public List<Placement> getResource(Assignment<Lecture, Placement> assignment, int slot) { 319 return getContext(assignment).getPlacements(slot); 320 } 321 322 public Placement[] getResourceOfWeek(Assignment<Lecture, Placement> assignment, int startDay) { 323 return getContext(assignment).getResourceOfWeek(startDay); 324 } 325 326 @Override 327 public String toString() { 328 return "Room " + getName(); 329 } 330 331 /** Position of the building 332 * @param x X-coordinate (latitude) 333 * @param y Y-coordinate (longitude) 334 **/ 335 public void setCoordinates(Double x, Double y) { 336 iPosX = x; 337 iPosY = y; 338 } 339 340 /** X-position of the building 341 * @return X-coordinate (latitude) 342 **/ 343 public Double getPosX() { 344 return iPosX; 345 } 346 347 /** Y-position of the building 348 * @return Y-coordinate (longitude) 349 **/ 350 public Double getPosY() { 351 return iPosY; 352 } 353 354 public boolean getIgnoreTooFar() { 355 return iIgnoreTooFar; 356 } 357 358 public boolean getConstraint() { 359 return iConstraint; 360 } 361 362 public Long getType() { 363 return iType; 364 } 365 366 public void setType(Long type) { 367 iType = type; 368 } 369 370 @Override 371 public RoomConstraintContext createAssignmentContext(Assignment<Lecture, Placement> assignment) { 372 return new RoomConstraintContext(assignment); 373 } 374 375 public class RoomConstraintContext implements AssignmentConstraintContext<Lecture, Placement> { 376 private List<Placement>[] iResource; 377 private int iLastUselessHalfHours = 0; 378 private double iLastBrokenTimePatterns = 0; 379 380 @SuppressWarnings("unchecked") 381 public RoomConstraintContext(Assignment<Lecture, Placement> assignment) { 382 iResource = new List[Constants.SLOTS_PER_DAY * Constants.NR_DAYS]; 383 for (int i = 0; i < iResource.length; i++) 384 iResource[i] = new ArrayList<Placement>(3); 385 for (Lecture lecture: variables()) { 386 Placement placement = assignment.getValue(lecture); 387 if (placement != null && placement.hasRoomLocation(getResourceId())) { 388 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 389 int slot = e.nextElement(); 390 iResource[slot].add(placement); 391 } 392 } 393 } 394 iLastUselessHalfHours = UselessHalfHours.countUselessSlotsHalfHours(this); 395 getModel().getCriterion(UselessHalfHours.class).inc(assignment, iLastUselessHalfHours); 396 iLastBrokenTimePatterns = BrokenTimePatterns.countUselessSlotsBrokenTimePatterns(this) / 6.0; 397 getModel().getCriterion(BrokenTimePatterns.class).inc(assignment, iLastBrokenTimePatterns); 398 } 399 400 @Override 401 public void assigned(Assignment<Lecture, Placement> assignment, Placement placement) { 402 if (!placement.hasRoomLocation(getResourceId())) 403 return; 404 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 405 int slot = e.nextElement(); 406 iResource[slot].add(placement); 407 } 408 getModel().getCriterion(UselessHalfHours.class).inc(assignment, -iLastUselessHalfHours); 409 iLastUselessHalfHours = UselessHalfHours.countUselessSlotsHalfHours(this); 410 getModel().getCriterion(UselessHalfHours.class).inc(assignment, iLastUselessHalfHours); 411 getModel().getCriterion(BrokenTimePatterns.class).inc(assignment, -iLastBrokenTimePatterns); 412 iLastBrokenTimePatterns = BrokenTimePatterns.countUselessSlotsBrokenTimePatterns(this) / 6.0; 413 getModel().getCriterion(BrokenTimePatterns.class).inc(assignment, iLastBrokenTimePatterns); 414 } 415 416 @Override 417 public void unassigned(Assignment<Lecture, Placement> assignment, Placement placement) { 418 if (!placement.hasRoomLocation(getResourceId())) 419 return; 420 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 421 int slot = e.nextElement(); 422 iResource[slot].remove(placement); 423 } 424 getModel().getCriterion(UselessHalfHours.class).inc(assignment, -iLastUselessHalfHours); 425 iLastUselessHalfHours = UselessHalfHours.countUselessSlotsHalfHours(this); 426 getModel().getCriterion(UselessHalfHours.class).inc(assignment, iLastUselessHalfHours); 427 getModel().getCriterion(BrokenTimePatterns.class).inc(assignment, -iLastBrokenTimePatterns); 428 iLastBrokenTimePatterns = BrokenTimePatterns.countUselessSlotsBrokenTimePatterns(this) / 6.0; 429 getModel().getCriterion(BrokenTimePatterns.class).inc(assignment, iLastBrokenTimePatterns); 430 } 431 432 public List<Placement> getPlacements(int slot) { return iResource[slot]; } 433 434 public Placement getPlacement(int slot, int day) { 435 for (Placement p : iResource[slot]) { 436 if (p.getTimeLocation().hasDay(day)) 437 return p; 438 } 439 return null; 440 } 441 442 public Placement[] getResourceOfWeek(int startDay) { 443 Placement[] ret = new Placement[iResource.length]; 444 for (int i = 0; i < iResource.length; i++) { 445 ret[i] = getPlacement(i, startDay + (i / Constants.SLOTS_PER_DAY)); 446 } 447 return ret; 448 } 449 450 public boolean inConflict(Lecture lecture, TimeLocation time) { 451 for (Enumeration<Integer> e = time.getSlots(); e.hasMoreElements();) { 452 int slot = e.nextElement(); 453 for (Placement confPlacement : getPlacements(slot)) { 454 if (!confPlacement.getTimeLocation().shareWeeks(time.getWeekCode())) continue; 455 if (confPlacement.variable().equals(lecture)) continue; 456 if (!confPlacement.variable().canShareRoom(lecture)) return true; 457 } 458 } 459 return false; 460 } 461 462 } 463}