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