001package net.sf.cpsolver.studentsct.extension;
002
003import java.util.HashMap;
004import java.util.HashSet;
005import java.util.Iterator;
006import java.util.Map;
007import java.util.Set;
008
009import org.apache.log4j.Logger;
010
011import net.sf.cpsolver.coursett.Constants;
012import net.sf.cpsolver.coursett.model.Placement;
013import net.sf.cpsolver.coursett.model.RoomLocation;
014import net.sf.cpsolver.coursett.model.TimeLocation;
015import net.sf.cpsolver.ifs.extension.Extension;
016import net.sf.cpsolver.ifs.model.ModelListener;
017import net.sf.cpsolver.ifs.solver.Solver;
018import net.sf.cpsolver.ifs.util.DataProperties;
019import net.sf.cpsolver.ifs.util.DistanceMetric;
020import net.sf.cpsolver.studentsct.StudentSectioningModel;
021import net.sf.cpsolver.studentsct.model.CourseRequest;
022import net.sf.cpsolver.studentsct.model.Enrollment;
023import net.sf.cpsolver.studentsct.model.Request;
024import net.sf.cpsolver.studentsct.model.Section;
025import net.sf.cpsolver.studentsct.model.Student;
026
027/**
028 * This extension computes student distant conflicts. Two sections that are
029 * attended by the same student are considered in a distance conflict if they
030 * are back-to-back taught in locations that are two far away. This means that
031 * the (walking) distance in minutes between the two classes are longer than
032 * the break time of the earlier class. See {@link DistanceMetric} for more details.
033 * 
034 * @see TimeLocation
035 * @see Placement
036 * 
037 * <br>
038 * <br>
039 * 
040 * @version StudentSct 1.2 (Student Sectioning)<br>
041 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
042 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
043 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
044 * <br>
045 *          This library is free software; you can redistribute it and/or modify
046 *          it under the terms of the GNU Lesser General Public License as
047 *          published by the Free Software Foundation; either version 3 of the
048 *          License, or (at your option) any later version. <br>
049 * <br>
050 *          This library is distributed in the hope that it will be useful, but
051 *          WITHOUT ANY WARRANTY; without even the implied warranty of
052 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
053 *          Lesser General Public License for more details. <br>
054 * <br>
055 *          You should have received a copy of the GNU Lesser General Public
056 *          License along with this library; if not see
057 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
058 */
059
060public class DistanceConflict extends Extension<Request, Enrollment> implements ModelListener<Request, Enrollment> {
061    private static Logger sLog = Logger.getLogger(DistanceConflict.class);
062    private Set<Conflict> iAllConflicts = new HashSet<Conflict>();
063    /** Debug flag */
064    public static boolean sDebug = false;
065    private Request iOldVariable = null;
066    private Enrollment iUnassignedValue = null;
067    private DistanceMetric iDistanceMetric = null;
068
069    /**
070     * Constructor. Beside of other thigs, this constructor also uses
071     * {@link StudentSectioningModel#setDistanceConflict(DistanceConflict)} to
072     * set the this instance to the model.
073     * 
074     * @param solver
075     *            constraint solver
076     * @param properties
077     *            configuration
078     */
079    public DistanceConflict(Solver<Request, Enrollment> solver, DataProperties properties) {
080        super(solver, properties);
081        if (solver != null)
082            ((StudentSectioningModel) solver.currentSolution().getModel()).setDistanceConflict(this);
083        iDistanceMetric = new DistanceMetric(properties);
084    }
085    
086    /**
087     * Alternative constructor (for online student sectioning)
088     * @param metrics distance metrics
089     * @param properties configuration
090     */
091    public DistanceConflict(DistanceMetric metrics, DataProperties properties) {
092        super(null, properties);
093        iDistanceMetric = metrics;
094    }
095
096    /**
097     * Initialize extension
098     */
099    @Override
100    public boolean init(Solver<Request, Enrollment> solver) {
101        StudentSectioningModel m = (StudentSectioningModel)solver.currentSolution().getModel();
102        iAllConflicts = computeAllConflicts();
103        for (Conflict c: iAllConflicts)
104            m.add(c);
105        return true;
106    }
107
108    @Override
109    public String toString() {
110        return "DistanceConstraint";
111    }
112    
113    public DistanceMetric getDistanceMetric() {
114        return iDistanceMetric;
115    }
116    
117    
118    private Map<Long, Map<Long, Integer>> iDistanceCache = new HashMap<Long, Map<Long,Integer>>();
119    protected int getDistanceInMinutes(RoomLocation r1, RoomLocation r2) {
120        if (r1.getId().compareTo(r2.getId()) > 0) return getDistanceInMinutes(r2, r1);
121        if (r1.getId().equals(r2.getId()) || r1.getIgnoreTooFar() || r2.getIgnoreTooFar())
122            return 0;
123        if (r1.getPosX() == null || r1.getPosY() == null || r2.getPosX() == null || r2.getPosY() == null)
124            return iDistanceMetric.getMaxTravelDistanceInMinutes();
125        Map<Long, Integer> other2distance = iDistanceCache.get(r1.getId());
126        if (other2distance == null) {
127            other2distance = new HashMap<Long, Integer>();
128            iDistanceCache.put(r1.getId(), other2distance);
129        }
130        Integer distance = other2distance.get(r2.getId());
131        if (distance == null) {
132            distance = iDistanceMetric.getDistanceInMinutes(r1.getId(), r1.getPosX(), r1.getPosY(), r2.getId(), r2.getPosX(), r2.getPosY());
133            other2distance.put(r2.getId(), distance);    
134        }
135        return distance;
136    }
137
138    protected int getDistanceInMinutes(Placement p1, Placement p2) {
139        if (p1.isMultiRoom()) {
140            if (p2.isMultiRoom()) {
141                int dist = 0;
142                for (RoomLocation r1 : p1.getRoomLocations()) {
143                    for (RoomLocation r2 : p2.getRoomLocations()) {
144                        dist = Math.max(dist, getDistanceInMinutes(r1, r2));
145                    }
146                }
147                return dist;
148            } else {
149                if (p2.getRoomLocation() == null)
150                    return 0;
151                int dist = 0;
152                for (RoomLocation r1 : p1.getRoomLocations()) {
153                    dist = Math.max(dist, getDistanceInMinutes(r1, p2.getRoomLocation()));
154                }
155                return dist;
156            }
157        } else if (p2.isMultiRoom()) {
158            if (p1.getRoomLocation() == null)
159                return 0;
160            int dist = 0;
161            for (RoomLocation r2 : p2.getRoomLocations()) {
162                dist = Math.max(dist, getDistanceInMinutes(p1.getRoomLocation(), r2));
163            }
164            return dist;
165        } else {
166            if (p1.getRoomLocation() == null || p2.getRoomLocation() == null)
167                return 0;
168            return getDistanceInMinutes(p1.getRoomLocation(), p2.getRoomLocation());
169        }
170    }
171    
172    /**
173     * Return true if the given two sections are in distance conflict. This
174     * means that the sections are back-to-back and that they are placed in
175     * locations that are two far.
176     * 
177     * @param s1
178     *            a section
179     * @param s2
180     *            a section
181     * @return true, if the given sections are in a distance conflict
182     */
183    public boolean inConflict(Section s1, Section s2) {
184        if (s1.getPlacement() == null || s2.getPlacement() == null)
185            return false;
186        TimeLocation t1 = s1.getTime();
187        TimeLocation t2 = s2.getTime();
188        if (!t1.shareDays(t2) || !t1.shareWeeks(t2))
189            return false;
190        int a1 = t1.getStartSlot(), a2 = t2.getStartSlot();
191        if (getDistanceMetric().doComputeDistanceConflictsBetweenNonBTBClasses()) {
192            if (a1 + t1.getNrSlotsPerMeeting() <= a2) {
193                int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
194                if (dist > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a2 - a1 - t1.getLength()))
195                    return true;
196            } else if (a2 + t2.getNrSlotsPerMeeting() <= a1) {
197                int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
198                if (dist > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (a1 - a2 - t2.getLength()))
199                    return true;
200            }
201        } else {
202            if (a1 + t1.getNrSlotsPerMeeting() == a2) {
203                int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
204                if (dist > t1.getBreakTime())
205                    return true;
206            } else if (a2 + t2.getNrSlotsPerMeeting() == a1) {
207                int dist = getDistanceInMinutes(s1.getPlacement(), s2.getPlacement());
208                if (dist > t2.getBreakTime())
209                    return true;
210            }
211        }
212        return false;
213    }
214
215    /**
216     * Return number of distance conflict of a (course) enrollment. It is the
217     * number of pairs of assignments of the enrollment that are in a distance
218     * conflict.
219     * 
220     * @param e1
221     *            an enrollment
222     * @return number of distance conflicts
223     */
224    public int nrConflicts(Enrollment e1) {
225        if (!e1.isCourseRequest())
226            return 0;
227        int cnt = 0;
228        for (Section s1 : e1.getSections()) {
229            for (Section s2 : e1.getSections()) {
230                if (s1.getId() < s2.getId() && inConflict(s1, s2))
231                    cnt ++;
232            }
233        }
234        return cnt;
235    }
236
237    /**
238     * Return number of distance conflicts that are between two enrollments. It
239     * is the number of pairs of assignments of these enrollments that are in a
240     * distance conflict.
241     * 
242     * @param e1
243     *            an enrollment
244     * @param e2
245     *            an enrollment
246     * @return number of distance conflict between given enrollments
247     */
248    public int nrConflicts(Enrollment e1, Enrollment e2) {
249        if (!e1.isCourseRequest() || !e2.isCourseRequest() || !e1.getStudent().equals(e2.getStudent()))
250            return 0;
251        int cnt = 0;
252        for (Section s1 : e1.getSections()) {
253            for (Section s2 : e2.getSections()) {
254                if (inConflict(s1, s2))
255                    cnt ++;
256            }
257        }
258        return cnt;
259    }
260
261    /**
262     * Return a set of distance conflicts ({@link Conflict} objects) of a
263     * (course) enrollment.
264     * 
265     * @param e1
266     *            an enrollment
267     * @return list of distance conflicts that are between assignment of the
268     *         given enrollment
269     */
270    public Set<Conflict> conflicts(Enrollment e1) {
271        Set<Conflict> ret = new HashSet<Conflict>();
272        if (!e1.isCourseRequest())
273            return ret;
274        for (Section s1 : e1.getSections()) {
275            for (Section s2 : e1.getSections()) {
276                if (s1.getId() < s2.getId() && inConflict(s1, s2))
277                    ret.add(new Conflict(e1.getStudent(), e1, s1, e1, s2));
278            }
279        }
280        return ret;
281    }
282
283    /**
284     * Return a set of distance conflicts ({@link Conflict} objects) between
285     * given (course) enrollments.
286     * 
287     * @param e1
288     *            an enrollment
289     * @param e2
290     *            an enrollment
291     * @return list of distance conflicts that are between assignment of the
292     *         given enrollments
293     */
294    public Set<Conflict> conflicts(Enrollment e1, Enrollment e2) {
295        Set<Conflict> ret = new HashSet<Conflict>();
296        if (!e1.isCourseRequest() || !e2.isCourseRequest() || !e1.getStudent().equals(e2.getStudent()))
297            return ret;
298        for (Section s1 : e1.getSections()) {
299            for (Section s2 : e2.getSections()) {
300                if (inConflict(s1, s2))
301                    ret.add(new Conflict(e1.getStudent(), e1, s1, e2, s2));
302            }
303        }
304        return ret;
305    }
306
307    /**
308     * Total sum of all conflict of the given enrollment and other enrollments
309     * that are assignmed to the same student.
310     */
311    public int nrAllConflicts(Enrollment enrollment) {
312        if (!enrollment.isCourseRequest())
313            return 0;
314        int cnt = nrConflicts(enrollment);
315        for (Request request : enrollment.getStudent().getRequests()) {
316            if (request.equals(enrollment.getRequest()) || request.getAssignment() == null
317                    || request.equals(iOldVariable))
318                continue;
319            cnt += nrConflicts(enrollment, request.getAssignment());
320        }
321        return cnt;
322    }
323
324    /**
325     * The set of all conflicts ({@link Conflict} objects) of the given
326     * enrollment and other enrollments that are assignmed to the same student.
327     */
328    public Set<Conflict> allConflicts(Enrollment enrollment) {
329        Set<Conflict> ret = conflicts(enrollment);
330        if (!enrollment.isCourseRequest())
331            return ret;
332        for (Request request : enrollment.getStudent().getRequests()) {
333            if (request.equals(enrollment.getRequest()) || request.getAssignment() == null)
334                continue;
335            ret.addAll(conflicts(enrollment, request.getAssignment()));
336        }
337        return ret;
338    }
339
340    /**
341     * Called when a value is assigned to a variable. Internal number of
342     * distance conflicts is updated, see
343     * {@link DistanceConflict#getTotalNrConflicts()}.
344     */
345    public void assigned(long iteration, Enrollment value) {
346        StudentSectioningModel m = (StudentSectioningModel)value.variable().getModel();
347        for (Conflict c: allConflicts(value)) {
348            if (iAllConflicts.add(c))
349                m.add(c);
350        }
351        if (sDebug) {
352            sLog.debug("A:" + value.variable() + " := " + value);
353            int inc = nrConflicts(value);
354            if (inc != 0) {
355                sLog.debug("-- DC+" + inc + " A: " + value.variable() + " := " + value);
356                for (Iterator<Conflict> i = allConflicts(value).iterator(); i.hasNext();)
357                    sLog.debug("  -- " + i.next());
358            }
359        }
360    }
361
362    /**
363     * Called when a value is unassigned from a variable. Internal number of
364     * distance conflicts is updated, see
365     * {@link DistanceConflict#getTotalNrConflicts()}.
366     */
367    public void unassigned(long iteration, Enrollment value) {
368        if (value.variable().equals(iOldVariable))
369            return;
370        StudentSectioningModel m = (StudentSectioningModel)value.variable().getModel();
371        for (Conflict c: allConflicts(value)) {
372            if (iAllConflicts.remove(c))
373                m.remove(c);
374        }
375        if (sDebug) {
376            sLog.debug("U:" + value.variable() + " := " + value);
377            int dec = nrAllConflicts(value);
378            if (dec != 0) {
379                sLog.debug("-- DC+" + dec + " U: " + value.variable() + " := " + value);
380                Set<Conflict> confs = allConflicts(value);
381                for (Iterator<Conflict> i = confs.iterator(); i.hasNext();)
382                    sLog.debug("  -- " + i.next());
383            }
384        }
385    }
386
387    /** Checks the counter counting all conflicts */
388    public void checkAllConflicts() {
389        Set<Conflict> allConfs = computeAllConflicts();
390        if (iAllConflicts.size() != allConfs.size()) {
391            sLog.error("Different number of conflicts " + iAllConflicts.size() + "!=" + allConfs.size());
392            for (Iterator<Conflict> i = allConfs.iterator(); i.hasNext();) {
393                Conflict c = i.next();
394                if (!iAllConflicts.contains(c))
395                    sLog.debug("  +add+ " + c);
396            }
397            for (Iterator<Conflict> i = iAllConflicts.iterator(); i.hasNext();) {
398                Conflict c = i.next();
399                if (!allConfs.contains(c))
400                    sLog.debug("  -rem- " + c);
401            }
402            iAllConflicts = allConfs;
403        }
404    }
405    /** Actual number of all distance conflicts */
406    public int getTotalNrConflicts() {
407        return iAllConflicts.size();
408    }
409
410    /**
411     * Compute the actual number of all distance conflicts. Should be equal to
412     * {@link DistanceConflict#getTotalNrConflicts()}.
413     */
414    public int countTotalNrConflicts() {
415        int total = 0;
416        for (Request r1 : getModel().variables()) {
417            if (r1.getAssignment() == null || !(r1 instanceof CourseRequest))
418                continue;
419            total += nrConflicts(r1.getAssignment());
420            for (Request r2 : r1.getStudent().getRequests()) {
421                if (r2.getAssignment() == null || r1.getId() >= r2.getId() || !(r2 instanceof CourseRequest))
422                    continue;
423                total += nrConflicts(r1.getAssignment(), r2.getAssignment());
424            }
425        }
426        return total;
427    }
428
429    /**
430     * Compute a set of all distance conflicts ({@link Conflict} objects).
431     */
432    public Set<Conflict> computeAllConflicts() {
433        Set<Conflict> ret = new HashSet<Conflict>();
434        for (Request r1 : getModel().variables()) {
435            if (r1.getAssignment() == null || !(r1 instanceof CourseRequest))
436                continue;
437            ret.addAll(conflicts(r1.getAssignment()));
438            for (Request r2 : r1.getStudent().getRequests()) {
439                if (r2.getAssignment() == null || r1.getId() >= r2.getId() || !(r2 instanceof CourseRequest))
440                    continue;
441                ret.addAll(conflicts(r1.getAssignment(), r2.getAssignment()));
442            }
443        }
444        return ret;
445    }
446    
447    /**
448     * Return a set of all distance conflicts ({@link Conflict} objects).
449     */
450    public Set<Conflict> getAllConflicts() {
451        return iAllConflicts;
452    }
453
454    /**
455     * Called before a value is assigned to a variable.
456     */
457    @Override
458    public void beforeAssigned(long iteration, Enrollment value) {
459        if (value != null) {
460            if (value.variable().getAssignment() != null) {
461                unassigned(iteration, value.variable().getAssignment());
462                iUnassignedValue = value.variable().getAssignment();
463            }
464            iOldVariable = value.variable();
465        }
466    }
467
468    /**
469     * Called after a value is assigned to a variable.
470     */
471    @Override
472    public void afterAssigned(long iteration, Enrollment value) {
473        iOldVariable = null;
474        iUnassignedValue = null;
475        if (value != null)
476            assigned(iteration, value);
477    }
478
479    /**
480     * Called after a value is unassigned from a variable.
481     */
482    @Override
483    public void afterUnassigned(long iteration, Enrollment value) {
484        if (value != null && !value.equals(iUnassignedValue))
485            unassigned(iteration, value);
486    }
487
488    /** A representation of a distance conflict */
489    public static class Conflict {
490        private Student iStudent;
491        private Section iS1, iS2;
492        private Enrollment iE1, iE2;
493        private int iHashCode;
494
495        /**
496         * Constructor
497         * 
498         * @param student
499         *            related student
500         * @param s1
501         *            first conflicting section
502         * @param s2
503         *            second conflicting section
504         */
505        public Conflict(Student student, Enrollment e1, Section s1, Enrollment e2, Section s2) {
506            iStudent = student;
507            if (s1.getId() < s2.getId()) {
508                iS1 = s1;
509                iS2 = s2;
510                iE1 = e1;
511                iE2 = e2;
512            } else {
513                iS1 = s2;
514                iS2 = s1;
515                iE1 = e2;
516                iE2 = e1;
517            }
518            iHashCode = (iStudent.getId() + ":" + iS1.getId() + ":" + iS2.getId()).hashCode();
519        }
520
521        /** Related student */
522        public Student getStudent() {
523            return iStudent;
524        }
525
526        /** First section */
527        public Section getS1() {
528            return iS1;
529        }
530
531        /** Second section */
532        public Section getS2() {
533            return iS2;
534        }
535        
536        /** First request */
537        public Request getR1() {
538            return iE1.getRequest();
539        }
540        
541        /** Second request */
542        public Request getR2() {
543            return iE2.getRequest();
544        }
545        
546        /** First enrollment */
547        public Enrollment getE1() {
548            return iE1;
549        }
550
551        /** Second enrollment */
552        public Enrollment getE2() {
553            return iE2;
554        }
555
556        @Override
557        public int hashCode() {
558            return iHashCode;
559        }
560
561        /** The distance between conflicting sections */
562        public double getDistance(DistanceMetric dm) {
563            return Placement.getDistanceInMeters(dm, getS1().getPlacement(), getS2().getPlacement());
564        }
565
566        @Override
567        public boolean equals(Object o) {
568            if (o == null || !(o instanceof Conflict)) return false;
569            Conflict c = (Conflict) o;
570            return getStudent().equals(c.getStudent()) && getS1().equals(c.getS1()) && getS2().equals(c.getS2());
571        }
572
573        @Override
574        public String toString() {
575            return getStudent() + ": " + getS1() + " -- " + getS2();
576        }
577    }
578}