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