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    }