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