001    package net.sf.cpsolver.studentsct.extension;
002    
003    import java.util.HashMap;
004    import java.util.HashSet;
005    import java.util.Iterator;
006    import java.util.Map;
007    import java.util.Set;
008    
009    import org.apache.log4j.Logger;
010    
011    import net.sf.cpsolver.coursett.Constants;
012    import net.sf.cpsolver.coursett.model.Placement;
013    import net.sf.cpsolver.coursett.model.RoomLocation;
014    import net.sf.cpsolver.coursett.model.TimeLocation;
015    import net.sf.cpsolver.ifs.extension.Extension;
016    import net.sf.cpsolver.ifs.model.ModelListener;
017    import net.sf.cpsolver.ifs.solver.Solver;
018    import net.sf.cpsolver.ifs.util.DataProperties;
019    import net.sf.cpsolver.ifs.util.DistanceMetric;
020    import net.sf.cpsolver.studentsct.StudentSectioningModel;
021    import net.sf.cpsolver.studentsct.model.CourseRequest;
022    import net.sf.cpsolver.studentsct.model.Enrollment;
023    import net.sf.cpsolver.studentsct.model.Request;
024    import net.sf.cpsolver.studentsct.model.Section;
025    import 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 Tomas Muller<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    
060    public 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    }