001 package net.sf.cpsolver.coursett.constraint; 002 003 import java.util.ArrayList; 004 import java.util.BitSet; 005 import java.util.Enumeration; 006 import java.util.HashSet; 007 import java.util.List; 008 import java.util.Set; 009 010 import net.sf.cpsolver.coursett.Constants; 011 import net.sf.cpsolver.coursett.criteria.BrokenTimePatterns; 012 import net.sf.cpsolver.coursett.criteria.UselessHalfHours; 013 import net.sf.cpsolver.coursett.model.Lecture; 014 import net.sf.cpsolver.coursett.model.Placement; 015 import net.sf.cpsolver.coursett.model.RoomSharingModel; 016 import net.sf.cpsolver.coursett.model.TimeLocation; 017 import 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 Tomas Muller<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 043 public 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 int 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 } 095 096 public boolean isAvailable(int slot) { 097 if (iAvailable != null && iAvailable[slot] != null && !iAvailable[slot].isEmpty()) 098 return false; 099 if (getSharingModel() != null && getSharingModel().isNotAvailable(slot)) 100 return false; 101 return true; 102 } 103 104 public boolean isAvailable(Lecture lecture, TimeLocation time, Long scheduler) { 105 if (iAvailable != null) { 106 for (Enumeration<Integer> e = time.getSlots(); e.hasMoreElements();) { 107 int slot = e.nextElement(); 108 if (iAvailable[slot] != null) { 109 for (Placement p : iAvailable[slot]) { 110 if (lecture.canShareRoom(p.variable())) 111 continue; 112 if (time.shareWeeks(p.getTimeLocation())) 113 return false; 114 } 115 } 116 } 117 } 118 if (getSharingModel() != null && !getSharingModel().isAvailable(time, scheduler)) 119 return false; 120 return true; 121 } 122 123 public List<Placement>[] getAvailableArray() { 124 return iAvailable; 125 } 126 127 public RoomSharingModel getSharingModel() { 128 return iRoomSharingModel; 129 } 130 131 /** Room id */ 132 public Long getResourceId() { 133 return iResourceId; 134 } 135 136 /** Building id */ 137 public Long getBuildingId() { 138 return iBuildingId; 139 } 140 141 /** Room name */ 142 @Override 143 public String getName() { 144 return iName; 145 } 146 147 public String getRoomName() { 148 return iName; 149 } 150 151 /** Capacity */ 152 public int getCapacity() { 153 return iCapacity; 154 } 155 156 public Placement getPlacement(int slot, int day) { 157 for (Placement p : iResource[slot]) { 158 if (p.getTimeLocation().hasDay(day)) 159 return p; 160 } 161 return null; 162 } 163 164 @Override 165 public void computeConflicts(Placement placement, Set<Placement> conflicts) { 166 if (!getConstraint()) 167 return; 168 if (!placement.hasRoomLocation(getResourceId())) 169 return; 170 Lecture lecture = placement.variable(); 171 boolean canShareRoom = lecture.canShareRoom(); 172 int size = lecture.maxRoomUse(); 173 HashSet<Placement> skipPlacements = null; 174 BitSet weekCode = placement.getTimeLocation().getWeekCode(); 175 176 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 177 int slot = e.nextElement(); 178 for (Placement confPlacement : iResource[slot]) { 179 if (!confPlacement.getTimeLocation().shareWeeks(weekCode)) 180 continue; 181 if (confPlacement.equals(lecture.getAssignment())) 182 continue; 183 Lecture confLecture = confPlacement.variable(); 184 if (skipPlacements != null && skipPlacements.contains(confPlacement)) 185 continue; 186 if (canShareRoom && confPlacement.canShareRooms(placement) 187 && confLecture.maxRoomUse() + size <= getCapacity()) { 188 size += confLecture.maxRoomUse(); 189 if (skipPlacements == null) 190 skipPlacements = new HashSet<Placement>(); 191 skipPlacements.add(confPlacement); 192 continue; 193 } 194 conflicts.add(confPlacement); 195 } 196 } 197 } 198 199 @Override 200 public boolean inConflict(Placement placement) { 201 if (!getConstraint()) 202 return false; 203 Lecture lecture = placement.variable(); 204 if (!placement.hasRoomLocation(getResourceId())) 205 return false; 206 int size = lecture.maxRoomUse(); 207 HashSet<Placement> skipPlacements = null; 208 BitSet weekCode = placement.getTimeLocation().getWeekCode(); 209 210 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 211 int slot = e.nextElement(); 212 for (Placement confPlacement : iResource[slot]) { 213 if (!confPlacement.getTimeLocation().shareWeeks(weekCode)) 214 continue; 215 if (confPlacement.equals(lecture.getAssignment())) 216 continue; 217 Lecture confLecture = confPlacement.variable(); 218 if (skipPlacements != null && skipPlacements.contains(confPlacement)) 219 continue; 220 if (confPlacement.canShareRooms(placement) && confLecture.maxRoomUse() + size <= getCapacity()) { 221 size += confLecture.maxRoomUse(); 222 if (skipPlacements == null) 223 skipPlacements = new HashSet<Placement>(); 224 skipPlacements.add(confPlacement); 225 continue; 226 } 227 return true; 228 } 229 } 230 return false; 231 } 232 233 @Override 234 public boolean isConsistent(Placement p1, Placement p2) { 235 if (!getConstraint()) 236 return true; 237 if (!p1.hasRoomLocation(getResourceId())) 238 return false; 239 if (!p2.hasRoomLocation(getResourceId())) 240 return false; 241 if (p1.getTimeLocation().hasIntersection(p2.getTimeLocation())) { 242 if (!p1.canShareRooms(p2) || (p1.variable()).maxRoomUse() + (p2.variable()).maxRoomUse() > getCapacity()) 243 return true; 244 } 245 return false; 246 } 247 248 @Override 249 public void assigned(long iteration, Placement placement) { 250 super.assigned(iteration, placement); 251 if (!placement.hasRoomLocation(getResourceId())) 252 return; 253 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 254 int slot = e.nextElement(); 255 iResource[slot].add(placement); 256 } 257 getModel().getCriterion(UselessHalfHours.class).inc(-iLastUselessHalfHours); 258 iLastUselessHalfHours = UselessHalfHours.countUselessSlotsHalfHours(this); 259 getModel().getCriterion(UselessHalfHours.class).inc(iLastUselessHalfHours); 260 getModel().getCriterion(BrokenTimePatterns.class).inc(-iLastBrokenTimePatterns); 261 iLastBrokenTimePatterns = BrokenTimePatterns.countUselessSlotsBrokenTimePatterns(this); 262 getModel().getCriterion(BrokenTimePatterns.class).inc(iLastBrokenTimePatterns); 263 } 264 265 @Override 266 public void unassigned(long iteration, Placement placement) { 267 super.unassigned(iteration, placement); 268 if (!placement.hasRoomLocation(getResourceId())) 269 return; 270 for (Enumeration<Integer> e = placement.getTimeLocation().getSlots(); e.hasMoreElements();) { 271 int slot = e.nextElement(); 272 iResource[slot].remove(placement); 273 } 274 getModel().getCriterion(UselessHalfHours.class).inc(-iLastUselessHalfHours); 275 iLastUselessHalfHours = UselessHalfHours.countUselessSlotsHalfHours(this); 276 getModel().getCriterion(UselessHalfHours.class).inc(iLastUselessHalfHours); 277 getModel().getCriterion(BrokenTimePatterns.class).inc(-iLastBrokenTimePatterns); 278 iLastBrokenTimePatterns = BrokenTimePatterns.countUselessSlotsBrokenTimePatterns(this); 279 getModel().getCriterion(BrokenTimePatterns.class).inc(iLastBrokenTimePatterns); 280 281 } 282 283 /** 284 * Lookup table getResource()[slot] -> lecture using this room placed in the 285 * given time slot (null if empty) 286 */ 287 public List<Placement> getResource(int slot) { 288 return iResource[slot]; 289 } 290 291 public Placement[] getResourceOfWeek(int startDay) { 292 Placement[] ret = new Placement[iResource.length]; 293 for (int i = 0; i < iResource.length; i++) { 294 ret[i] = getPlacement(i, startDay + (i / Constants.SLOTS_PER_DAY)); 295 } 296 return ret; 297 } 298 299 /** Room usage */ 300 protected void printUsage(StringBuffer sb) { 301 for (int slot = 0; slot < iResource.length; slot++) { 302 for (Placement p : iResource[slot]) { 303 int day = slot / Constants.SLOTS_PER_DAY; 304 int time = slot * Constants.SLOT_LENGTH_MIN + Constants.FIRST_SLOT_TIME_MIN; 305 int h = time / 60; 306 int m = time % 60; 307 String d = Constants.DAY_NAMES_SHORT[day]; 308 int slots = p.getTimeLocation().getLength(); 309 time += (30 * slots); 310 int h2 = time / 60; 311 int m2 = time % 60; 312 sb.append(sb.length() == 0 ? "" : ",\n ").append( 313 "[" + d + (h > 12 ? h - 12 : h) + ":" + (m < 10 ? "0" : "") + m + (h >= 12 ? "p" : "a") + "-" 314 + (h2 > 12 ? h2 - 12 : h2) + ":" + (m2 < 10 ? "0" : "") + m2 + (h2 >= 12 ? "p" : "a") 315 + "]=").append(p.variable().getName()); 316 slot += slots - 1; 317 // sb.append(sb.length()==0?"":", ").append("s"+(slot+1)+"=").append(((Lecture)getResource()[slot]).getName()); 318 } 319 } 320 } 321 322 @Override 323 public String toString() { 324 return "Room " + getName(); 325 } 326 327 /** Position of the building */ 328 public void setCoordinates(Double x, Double y) { 329 iPosX = x; 330 iPosY = y; 331 } 332 333 /** X-position of the building */ 334 public Double getPosX() { 335 return iPosX; 336 } 337 338 /** Y-position of the building */ 339 public Double getPosY() { 340 return iPosY; 341 } 342 343 public boolean getIgnoreTooFar() { 344 return iIgnoreTooFar; 345 } 346 347 public boolean getConstraint() { 348 return iConstraint; 349 } 350 351 public Long getType() { 352 return iType; 353 } 354 355 public void setType(Long type) { 356 iType = type; 357 } 358 }