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