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 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);
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);
281 getModel().getCriterion(BrokenTimePatterns.class).inc(iLastBrokenTimePatterns);
282
283 }
284
285 /**
286 * Lookup table getResource()[slot] -> lecture using this room placed in the
287 * given time slot (null if empty)
288 */
289 public List<Placement> getResource(int slot) {
290 return iResource[slot];
291 }
292
293 public Placement[] getResourceOfWeek(int startDay) {
294 Placement[] ret = new Placement[iResource.length];
295 for (int i = 0; i < iResource.length; i++) {
296 ret[i] = getPlacement(i, startDay + (i / Constants.SLOTS_PER_DAY));
297 }
298 return ret;
299 }
300
301 /** Room usage */
302 protected void printUsage(StringBuffer sb) {
303 for (int slot = 0; slot < iResource.length; slot++) {
304 for (Placement p : iResource[slot]) {
305 int day = slot / Constants.SLOTS_PER_DAY;
306 int time = slot * Constants.SLOT_LENGTH_MIN + Constants.FIRST_SLOT_TIME_MIN;
307 int h = time / 60;
308 int m = time % 60;
309 String d = Constants.DAY_NAMES_SHORT[day];
310 int slots = p.getTimeLocation().getLength();
311 time += (30 * slots);
312 int h2 = time / 60;
313 int m2 = time % 60;
314 sb.append(sb.length() == 0 ? "" : ",\n ").append(
315 "[" + d + (h > 12 ? h - 12 : h) + ":" + (m < 10 ? "0" : "") + m + (h >= 12 ? "p" : "a") + "-"
316 + (h2 > 12 ? h2 - 12 : h2) + ":" + (m2 < 10 ? "0" : "") + m2 + (h2 >= 12 ? "p" : "a")
317 + "]=").append(p.variable().getName());
318 slot += slots - 1;
319 // sb.append(sb.length()==0?"":", ").append("s"+(slot+1)+"=").append(((Lecture)getResource()[slot]).getName());
320 }
321 }
322 }
323
324 @Override
325 public String toString() {
326 return "Room " + getName();
327 }
328
329 /** Position of the building */
330 public void setCoordinates(Double x, Double y) {
331 iPosX = x;
332 iPosY = y;
333 }
334
335 /** X-position of the building */
336 public Double getPosX() {
337 return iPosX;
338 }
339
340 /** Y-position of the building */
341 public Double getPosY() {
342 return iPosY;
343 }
344
345 public boolean getIgnoreTooFar() {
346 return iIgnoreTooFar;
347 }
348
349 public boolean getConstraint() {
350 return iConstraint;
351 }
352
353 public Long getType() {
354 return iType;
355 }
356
357 public void setType(Long type) {
358 iType = type;
359 }
360 }