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