001package org.cpsolver.coursett.model;
002
003import java.util.ArrayList;
004import java.util.Enumeration;
005import java.util.List;
006
007import org.cpsolver.coursett.Constants;
008import org.cpsolver.coursett.constraint.GroupConstraint;
009import org.cpsolver.coursett.constraint.InstructorConstraint;
010import org.cpsolver.coursett.constraint.SpreadConstraint;
011import org.cpsolver.coursett.preference.PreferenceCombination;
012import org.cpsolver.ifs.assignment.Assignment;
013import org.cpsolver.ifs.criteria.Criterion;
014import org.cpsolver.ifs.model.Value;
015import org.cpsolver.ifs.util.DistanceMetric;
016import org.cpsolver.ifs.util.ToolBox;
017
018
019/**
020 * Placement (value). <br>
021 * <br>
022 * It combines room and time location
023 * 
024 * @version CourseTT 1.3 (University Course Timetabling)<br>
025 *          Copyright (C) 2006 - 2014 Tomas Muller<br>
026 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
027 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
028 * <br>
029 *          This library is free software; you can redistribute it and/or modify
030 *          it under the terms of the GNU Lesser General Public License as
031 *          published by the Free Software Foundation; either version 3 of the
032 *          License, or (at your option) any later version. <br>
033 * <br>
034 *          This library is distributed in the hope that it will be useful, but
035 *          WITHOUT ANY WARRANTY; without even the implied warranty of
036 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
037 *          Lesser General Public License for more details. <br>
038 * <br>
039 *          You should have received a copy of the GNU Lesser General Public
040 *          License along with this library; if not see
041 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
042 */
043
044public class Placement extends Value<Lecture, Placement> {
045    private TimeLocation iTimeLocation;
046    private RoomLocation iRoomLocation;
047    private List<RoomLocation> iRoomLocations = null;
048    private Long iAssignmentId = null;
049    private int iHashCode = 0;
050
051    /**
052     * Constructor
053     * 
054     * @param lecture
055     *            lecture
056     * @param timeLocation
057     *            time location
058     * @param roomLocation
059     *            room location
060     */
061    public Placement(Lecture lecture, TimeLocation timeLocation, RoomLocation roomLocation) {
062        super(lecture);
063        iTimeLocation = timeLocation;
064        iRoomLocation = roomLocation;
065        if (iRoomLocation == null) {
066            iRoomLocations = new ArrayList<RoomLocation>(0);
067        }
068        iHashCode = getName().hashCode();
069    }
070
071    public Placement(Lecture lecture, TimeLocation timeLocation, java.util.List<RoomLocation> roomLocations) {
072        super(lecture);
073        iTimeLocation = timeLocation;
074        iRoomLocation = (roomLocations.isEmpty() ? null : (RoomLocation) roomLocations.get(0));
075        if (roomLocations.size() != 1) {
076            iRoomLocations = new ArrayList<RoomLocation>(roomLocations);
077        }
078        iHashCode = getName().hashCode();
079    }
080
081    /** Time location 
082     * @return time of this placement
083     **/
084    public TimeLocation getTimeLocation() {
085        return iTimeLocation;
086    }
087
088    /** Room location 
089     * @return room of this placement
090     **/
091    public RoomLocation getRoomLocation() {
092        return iRoomLocation;
093    }
094
095    /** Room locations (multi-room placement) 
096     * @return rooms of this placement (if there are more than one)
097     **/
098    public List<RoomLocation> getRoomLocations() {
099        return iRoomLocations;
100    }
101
102    public List<Long> getBuildingIds() {
103        if (isMultiRoom()) {
104            List<Long> ret = new ArrayList<Long>(iRoomLocations.size());
105            for (RoomLocation r : iRoomLocations) {
106                ret.add(r.getBuildingId());
107            }
108            return ret;
109        } else {
110            List<Long> ret = new ArrayList<Long>(1);
111            ret.add(iRoomLocation.getBuildingId());
112            return ret;
113        }
114    }
115
116    public List<Long> getRoomIds() {
117        if (isMultiRoom()) {
118            List<Long> ret = new ArrayList<Long>(iRoomLocations.size());
119            for (RoomLocation r : iRoomLocations) {
120                ret.add(r.getId());
121            }
122            return ret;
123        } else {
124            List<Long> ret = new ArrayList<Long>(1);
125            ret.add(iRoomLocation.getId());
126            return ret;
127        }
128    }
129
130    public List<String> getRoomNames() {
131        if (isMultiRoom()) {
132            List<String> ret = new ArrayList<String>(iRoomLocations.size());
133            for (RoomLocation r : iRoomLocations) {
134                ret.add(r.getName());
135            }
136            return ret;
137        } else {
138            List<String> ret = new ArrayList<String>(1);
139            if (iRoomLocation != null)
140                ret.add(iRoomLocation.getName());
141            return ret;
142        }
143    }
144
145    public List<Integer> getRoomPrefs() {
146        if (isMultiRoom()) {
147            List<Integer> ret = new ArrayList<Integer>(iRoomLocations.size());
148            for (RoomLocation r : iRoomLocations) {
149                ret.add(r.getPreference());
150            }
151            return ret;
152        } else {
153            List<Integer> ret = new ArrayList<Integer>(1);
154            if (iRoomLocation != null)
155                ret.add(iRoomLocation.getPreference());
156            return ret;
157        }
158    }
159
160    public boolean isMultiRoom() {
161        return (iRoomLocations != null && iRoomLocations.size() != 1);
162    }
163
164    public RoomLocation getRoomLocation(Long roomId) {
165        if (isMultiRoom()) {
166            for (RoomLocation r : iRoomLocations) {
167                if (r.getId().equals(roomId))
168                    return r;
169            }
170        } else if (iRoomLocation != null && iRoomLocation.getId().equals(roomId))
171            return iRoomLocation;
172        return null;
173    }
174
175    public boolean hasRoomLocation(Long roomId) {
176        if (isMultiRoom()) {
177            for (RoomLocation r : iRoomLocations) {
178                if (r.getId().equals(roomId))
179                    return true;
180            }
181            return false;
182        } else
183            return iRoomLocation != null && iRoomLocation.getId().equals(roomId);
184    }
185
186    public String getRoomName(String delim) {
187        if (isMultiRoom()) {
188            StringBuffer sb = new StringBuffer();
189            for (RoomLocation r : iRoomLocations) {
190                if (sb.length() > 0)
191                    sb.append(delim);
192                sb.append(r.getName());
193            }
194            return sb.toString();
195        } else {
196            return (getRoomLocation() == null ? "" : getRoomLocation().getName());
197        }
198    }
199
200    @Override
201    public String getName() {
202        return getName(true);
203    }
204    
205    public String getName(boolean useAmPm) {
206        Lecture lecture = variable();
207        return getTimeLocation().getName(useAmPm) + " " + getRoomName(", ")
208                + (lecture != null && lecture.getInstructorName() != null ? " " + lecture.getInstructorName() : "");
209    }
210
211    public String getLongName(boolean useAmPm) {
212        Lecture lecture = variable();
213        if (isMultiRoom()) {
214            StringBuffer sb = new StringBuffer();
215            for (RoomLocation r : iRoomLocations) {
216                if (sb.length() > 0)
217                    sb.append(", ");
218                sb.append(r.getName());
219            }
220            return getTimeLocation().getLongName(useAmPm) + " " + sb
221                    + (lecture.getInstructorName() != null ? " " + lecture.getInstructorName() : "");
222        } else
223            return getTimeLocation().getLongName(useAmPm)
224                    + (getRoomLocation() == null ? "" : " " + getRoomLocation().getName())
225                    + (lecture.getInstructorName() != null ? " " + lecture.getInstructorName() : "");
226    }
227    
228    @Deprecated
229    public String getLongName() {
230        return getLongName(true);
231    }
232
233    public boolean sameRooms(Placement placement) {
234        if (placement.isMultiRoom() != isMultiRoom())
235            return false;
236        if (isMultiRoom()) {
237            if (placement.getRoomLocations().size() != getRoomLocations().size())
238                return false;
239            return placement.getRoomLocations().containsAll(getRoomLocations());
240        } else {
241            if (placement.getRoomLocation() == null)
242                return getRoomLocation() == null;
243            return placement.getRoomLocation().equals(getRoomLocation());
244        }
245    }
246
247    public boolean shareRooms(Placement placement) {
248        if (isMultiRoom()) {
249            if (placement.isMultiRoom()) {
250                for (RoomLocation rl : getRoomLocations()) {
251                    if (rl.getRoomConstraint() == null || !rl.getRoomConstraint().getConstraint())
252                        continue;
253                    if (placement.getRoomLocations().contains(rl))
254                        return true;
255                }
256                return false;
257            } else {
258                return getRoomLocations().contains(placement.getRoomLocation());
259            }
260        } else {
261            if (getRoomLocation().getRoomConstraint() == null || !getRoomLocation().getRoomConstraint().getConstraint())
262                return false;
263            if (placement.isMultiRoom()) {
264                return placement.getRoomLocations().contains(getRoomLocation());
265            } else {
266                return getRoomLocation().equals(placement.getRoomLocation());
267            }
268        }
269    }
270
271    public int nrDifferentRooms(Placement placement) {
272        if (isMultiRoom()) {
273            int ret = 0;
274            for (RoomLocation r : getRoomLocations()) {
275                if (!placement.getRoomLocations().contains(r))
276                    ret++;
277            }
278            return ret;
279        } else {
280            return (placement.getRoomLocation().equals(getRoomLocation()) ? 0 : 1);
281        }
282    }
283
284    public int nrDifferentBuildings(Placement placement) {
285        if (isMultiRoom()) {
286            int ret = 0;
287            for (RoomLocation r : getRoomLocations()) {
288                boolean contains = false;
289                for (RoomLocation q : placement.getRoomLocations()) {
290                    if (ToolBox.equals(r.getBuildingId(), q.getBuildingId()))
291                        contains = true;
292                }
293                if (!contains)
294                    ret++;
295            }
296            return ret;
297        } else {
298            return (ToolBox.equals(placement.getRoomLocation().getBuildingId(), getRoomLocation().getBuildingId()) ? 0
299                    : 1);
300        }
301    }
302
303    public int sumRoomPreference() {
304        if (isMultiRoom()) {
305            int ret = 0;
306            for (RoomLocation r : getRoomLocations()) {
307                ret += r.getPreference();
308            }
309            return ret;
310        } else {
311            return getRoomLocation().getPreference();
312        }
313    }
314
315    public int getRoomPreference() {
316        if (isMultiRoom()) {
317            PreferenceCombination p = PreferenceCombination.getDefault();
318            for (RoomLocation r : getRoomLocations()) {
319                p.addPreferenceInt(r.getPreference());
320            }
321            return p.getPreferenceInt();
322        } else {
323            return getRoomLocation().getPreference();
324        }
325    }
326
327    public int getRoomSize() {
328        if (isMultiRoom()) {
329            if (getRoomLocations().isEmpty()) return 0;
330            int roomSize = Integer.MAX_VALUE;
331            for (RoomLocation r : getRoomLocations()) {
332                roomSize = Math.min(roomSize, r.getRoomSize());
333            }
334            return roomSize;
335        } else {
336            return getRoomLocation().getRoomSize();
337        }
338    }
339
340    public boolean isHard(Assignment<Lecture, Placement> assignment) {
341        if (Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(getTimeLocation().getPreference())))
342            return true;
343        if (getRoomLocation() != null && Constants.sPreferenceProhibited.equals(Constants.preferenceLevel2preference(getRoomLocation().getPreference())))
344            return true;
345        Lecture lecture = variable();
346        for (GroupConstraint gc : lecture.hardGroupSoftConstraints()) {
347            if (gc.isSatisfied(assignment))
348                continue;
349            if (Constants.sPreferenceProhibited.equals(gc.getPrologPreference()))
350                return true;
351            if (Constants.sPreferenceRequired.equals(gc.getPrologPreference()))
352                return true;
353        }
354        return false;
355    }
356
357    public boolean sameTime(Placement placement) {
358        return placement.getTimeLocation().equals(getTimeLocation());
359    }
360
361    @Override
362    public boolean equals(Object object) {
363        if (object == null || !(object instanceof Placement))
364            return false;
365        Placement placement = (Placement) object;
366        if (placement.getId() == getId())
367            return true; // quick check
368        Lecture lecture = placement.variable();
369        Lecture thisLecture = variable();
370        if (lecture != null && thisLecture != null && !lecture.getClassId().equals(thisLecture.getClassId()))
371            return false;
372        if (!sameRooms(placement))
373            return false;
374        if (!sameTime(placement))
375            return false;
376        return true;
377    }
378
379    @Override
380    public int hashCode() {
381        return iHashCode;
382    }
383
384    @Override
385    public String toString() {
386        return variable().getName() + " " + getName();
387    }
388
389    /** Distance between two placements 
390     * @param m distance matrix
391     * @param p1 first placement
392     * @param p2 second placement
393     * @return maximal distance in meters between the two placement
394     **/
395    public static double getDistanceInMeters(DistanceMetric m, Placement p1, Placement p2) {
396        if (p1.isMultiRoom()) {
397            if (p2.isMultiRoom()) {
398                double dist = 0.0;
399                for (RoomLocation r1 : p1.getRoomLocations()) {
400                    for (RoomLocation r2 : p2.getRoomLocations()) {
401                        dist = Math.max(dist, r1.getDistanceInMeters(m, r2));
402                    }
403                }
404                return dist;
405            } else {
406                if (p2.getRoomLocation() == null)
407                    return 0.0;
408                double dist = 0.0;
409                for (RoomLocation r1 : p1.getRoomLocations()) {
410                    dist = Math.max(dist, r1.getDistanceInMeters(m, p2.getRoomLocation()));
411                }
412                return dist;
413            }
414        } else if (p2.isMultiRoom()) {
415            if (p1.getRoomLocation() == null)
416                return 0.0;
417            double dist = 0.0;
418            for (RoomLocation r2 : p2.getRoomLocations()) {
419                dist = Math.max(dist, p1.getRoomLocation().getDistanceInMeters(m, r2));
420            }
421            return dist;
422        } else {
423            if (p1.getRoomLocation() == null || p2.getRoomLocation() == null)
424                return 0.0;
425            return p1.getRoomLocation().getDistanceInMeters(m, p2.getRoomLocation());
426        }
427    }
428    
429    /** Distance between two placements 
430     * @param m distance matrix
431     * @param p1 first placement
432     * @param p2 second placement
433     * @return maximal distance in minutes between the two placement
434     **/
435    public static int getDistanceInMinutes(DistanceMetric m, Placement p1, Placement p2) {
436        if (p1.isMultiRoom()) {
437            if (p2.isMultiRoom()) {
438                int dist = 0;
439                for (RoomLocation r1 : p1.getRoomLocations()) {
440                    for (RoomLocation r2 : p2.getRoomLocations()) {
441                        dist = Math.max(dist, r1.getDistanceInMinutes(m, r2));
442                    }
443                }
444                return dist;
445            } else {
446                if (p2.getRoomLocation() == null)
447                    return 0;
448                int dist = 0;
449                for (RoomLocation r1 : p1.getRoomLocations()) {
450                    dist = Math.max(dist, r1.getDistanceInMinutes(m, p2.getRoomLocation()));
451                }
452                return dist;
453            }
454        } else if (p2.isMultiRoom()) {
455            if (p1.getRoomLocation() == null)
456                return 0;
457            int dist = 0;
458            for (RoomLocation r2 : p2.getRoomLocations()) {
459                dist = Math.max(dist, p1.getRoomLocation().getDistanceInMinutes(m, r2));
460            }
461            return dist;
462        } else {
463            if (p1.getRoomLocation() == null || p2.getRoomLocation() == null)
464                return 0;
465            return p1.getRoomLocation().getDistanceInMinutes(m, p2.getRoomLocation());
466        }
467    }
468
469    public int getCommitedConflicts() {
470        int ret = 0;
471        Lecture lecture = variable();
472        for (Student student : lecture.students()) {
473            ret += student.countConflictPlacements(this);
474        }
475        return ret;
476    }
477
478    public Long getAssignmentId() {
479        return iAssignmentId;
480    }
481
482    public void setAssignmentId(Long assignmentId) {
483        iAssignmentId = assignmentId;
484    }
485
486    public boolean canShareRooms(Placement other) {
487        return (variable()).canShareRoom(other.variable());
488    }
489
490    public boolean isValid() {
491        Lecture lecture = variable();
492        if (!lecture.isValid(this))
493            return false;
494        for (InstructorConstraint ic : lecture.getInstructorConstraints()) {
495            if (!ic.isAvailable(lecture, this))
496                return false;
497        }
498        if (lecture.getNrRooms() > 0) {
499            if (isMultiRoom()) {
500                for (RoomLocation roomLocation : getRoomLocations()) {
501                    if (roomLocation.getRoomConstraint() != null
502                            && !roomLocation.getRoomConstraint().isAvailable(lecture, getTimeLocation(),
503                                    lecture.getScheduler()))
504                        return false;
505                }
506            } else {
507                if (getRoomLocation().getRoomConstraint() != null
508                        && !getRoomLocation().getRoomConstraint().isAvailable(lecture, getTimeLocation(),
509                                lecture.getScheduler()))
510                    return false;
511            }
512        }
513        return true;
514    }
515
516    public String getNotValidReason(Assignment<Lecture, Placement> assignment, boolean useAmPm) {
517        Lecture lecture = variable();
518        String reason = lecture.getNotValidReason(assignment, this, useAmPm);
519        if (reason != null)
520            return reason;
521        for (InstructorConstraint ic : lecture.getInstructorConstraints()) {
522            if (!ic.isAvailable(lecture, this)) {
523                if (!ic.isAvailable(lecture, getTimeLocation())) {
524                    for (Placement c: ic.getUnavailabilities()) {
525                        if (c.getTimeLocation().hasIntersection(getTimeLocation()) && !lecture.canShareRoom(c.variable()))
526                            return "instructor " + ic.getName() + " not available at " + getTimeLocation().getLongName(useAmPm) + " due to " + c.variable().getName();
527                    }
528                    return "instructor " + ic.getName() + " not available at " + getTimeLocation().getLongName(useAmPm);
529                } else
530                    return "placement " + getTimeLocation().getLongName(useAmPm) + " " + getRoomName(", ") + " is too far for instructor " + ic.getName();
531            }
532        }
533        if (lecture.getNrRooms() > 0) {
534            if (isMultiRoom()) {
535                for (RoomLocation roomLocation : getRoomLocations()) {
536                    if (roomLocation.getRoomConstraint() != null && !roomLocation.getRoomConstraint().isAvailable(lecture, getTimeLocation(), lecture.getScheduler())) {
537                        if (roomLocation.getRoomConstraint().getAvailableArray() != null) {
538                            for (Enumeration<Integer> e = getTimeLocation().getSlots(); e.hasMoreElements();) {
539                                int slot = e.nextElement();
540                                if (roomLocation.getRoomConstraint().getAvailableArray()[slot] != null) {
541                                    for (Placement c : roomLocation.getRoomConstraint().getAvailableArray()[slot]) {
542                                        if (c.getTimeLocation().hasIntersection(getTimeLocation()) && !lecture.canShareRoom(c.variable())) {
543                                            return "room " + roomLocation.getName() + " not available at " + getTimeLocation().getLongName(useAmPm) + " due to " + c.variable().getName();
544                                        }
545                                    }
546                                }
547                            }
548                        }
549                        return "room " + roomLocation.getName() + " not available at " + getTimeLocation().getLongName(useAmPm);
550                    }
551                }
552            } else {
553                if (getRoomLocation().getRoomConstraint() != null && !getRoomLocation().getRoomConstraint().isAvailable(lecture, getTimeLocation(), lecture.getScheduler()))
554                    if (getRoomLocation().getRoomConstraint().getAvailableArray() != null) {
555                        for (Enumeration<Integer> e = getTimeLocation().getSlots(); e.hasMoreElements();) {
556                            int slot = e.nextElement();
557                            if (getRoomLocation().getRoomConstraint().getAvailableArray()[slot] != null) {
558                                for (Placement c : getRoomLocation().getRoomConstraint().getAvailableArray()[slot]) {
559                                    if (c.getTimeLocation().hasIntersection(getTimeLocation()) && !lecture.canShareRoom(c.variable())) {
560                                        return "room " + getRoomLocation().getName() + " not available at " + getTimeLocation().getLongName(useAmPm) + " due to " + c.variable().getName();
561                                    }
562                                }
563                            }
564                        }
565                    }
566                    return "room " + getRoomLocation().getName() + " not available at " + getTimeLocation().getLongName(useAmPm);
567            }
568        }
569        return reason;
570    }
571    
572    @Deprecated
573    public String getNotValidReason(Assignment<Lecture, Placement> assignment) {
574        return getNotValidReason(assignment, true);
575    }
576
577    public int getNrRooms() {
578        if (iRoomLocations != null)
579            return iRoomLocations.size();
580        return (iRoomLocation == null ? 0 : 1);
581    }
582
583    public int getSpreadPenalty(Assignment<Lecture, Placement> assignment) {
584        int spread = 0;
585        for (SpreadConstraint sc : variable().getSpreadConstraints()) {
586            spread += sc.getPenalty(assignment, this);
587        }
588        return spread;
589    }
590
591    public int getMaxSpreadPenalty(Assignment<Lecture, Placement> assignment) {
592        int spread = 0;
593        for (SpreadConstraint sc : variable().getSpreadConstraints()) {
594            spread += sc.getMaxPenalty(assignment, this);
595        }
596        return spread;
597    }
598
599    @Override
600    public double toDouble(Assignment<Lecture, Placement> assignment) {
601        double ret = 0.0;
602        for (Criterion<Lecture, Placement> criterion: variable().getModel().getCriteria())
603            ret += criterion.getWeightedValue(assignment, this, null);
604        return ret;
605    }
606
607    private transient Object iAssignment = null;
608
609    public Object getAssignment() {
610        return iAssignment;
611    }
612
613    public void setAssignment(Object assignment) {
614        iAssignment = assignment;
615    }
616}