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    }