    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}