    001package net.sf.cpsolver.studentsct.extension;
    002
    003import java.util.HashSet;
    004import java.util.Set;
    005
    006import org.apache.log4j.Logger;
    007
    008import net.sf.cpsolver.ifs.extension.Extension;
    009import net.sf.cpsolver.ifs.solver.Solver;
    010import net.sf.cpsolver.ifs.util.DataProperties;
    011import net.sf.cpsolver.studentsct.StudentSectioningModel;
    012import net.sf.cpsolver.studentsct.model.Assignment;
    013import net.sf.cpsolver.studentsct.model.Enrollment;
    014import net.sf.cpsolver.studentsct.model.FreeTimeRequest;
    015import net.sf.cpsolver.studentsct.model.Request;
    016import net.sf.cpsolver.studentsct.model.Section;
    017import net.sf.cpsolver.studentsct.model.Student;
    018
    019/**
    020 * This extension computes time overlaps. Only sections that allow overlaps
    021 * (see {@link Assignment#isAllowOverlap()}) can overlap. This class counts
    022 * how many overlapping slots there are so that this number can be minimized.
    023 *
    024 * <br>
    025 * <br>
    026 *
    027 * @version StudentSct 1.2 (Student Sectioning)<br>
    028 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    029 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    030 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    031 * <br>
    032 *          This library is free software; you can redistribute it and/or modify
    033 *          it under the terms of the GNU Lesser General Public License as
    034 *          published by the Free Software Foundation; either version 3 of the
    035 *          License, or (at your option) any later version. <br>
    036 * <br>
    037 *          This library is distributed in the hope that it will be useful, but
    038 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    039 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    040 *          Lesser General Public License for more details. <br>
    041 * <br>
    042 *          You should have received a copy of the GNU Lesser General Public
    043 *          License along with this library; if not see
    044 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    045 */
    046
    047public class TimeOverlapsCounter extends Extension<Request, Enrollment> {
    048    private static Logger sLog = Logger.getLogger(TimeOverlapsCounter.class);
    049    private int iTotalNrConflicts = 0;
    050    private Set<Conflict> iAllConflicts = new HashSet<Conflict>();
    051    /** Debug flag */
    052    public static boolean sDebug = false;
    053    private Request iOldVariable = null;
    054    private Enrollment iUnassignedValue = null;
    055
    056    /**
    057     * Constructor. Beside of other things, this constructor also uses
    058     * {@link StudentSectioningModel#setTimeOverlaps(TimeOverlapsCounter)} to
    059     * set the this instance to the model.
    060     *
    061     * @param solver
    062     *            constraint solver
    063     * @param properties
    064     *            configuration
    065     */
    066    public TimeOverlapsCounter(Solver<Request, Enrollment> solver, DataProperties properties) {
    067        super(solver, properties);
    068        if (solver != null)
    069            ((StudentSectioningModel) solver.currentSolution().getModel()).setTimeOverlaps(this);
    070    }
    071
    072    /**
    073     * Initialize extension
    074     */
    075    @Override
    076    public boolean init(Solver<Request, Enrollment> solver) {
    077        iTotalNrConflicts = countTotalNrConflicts();
    078        if (sDebug)
    079            iAllConflicts = computeAllConflicts();
    080        StudentSectioningModel m = (StudentSectioningModel)solver.currentSolution().getModel();
    081        for (Conflict c: computeAllConflicts())
    082            m.add(c);
    083        return true;
    084    }
    085
    086    @Override
    087    public String toString() {
    088        return "TimeOverlaps";
    089    }
    090
    091    /**
    092     * Return true if the given two assignments are overlapping.
    093     *
    094     * @param a1
    095     *            an assignment
    096     * @param a2
    097     *            an assignment
    098     * @return true, if the given sections are in an overlapping conflict
    099     */
    100    public boolean inConflict(Assignment a1, Assignment a2) {
    101        if (a1.getTime() == null || a2.getTime() == null) return false;
    102        if (a1 instanceof Section && a2 instanceof Section && ((Section)a1).isToIgnoreStudentConflictsWith(a2.getId())) return false;
    103        return a1.getTime().hasIntersection(a2.getTime());
    104    }
    105
    106    /**
    107     * If the two sections are overlapping, return the number of slots of the overlap.
    108     *
    109     * @param a1
    110     *            an assignment
    111     * @param a2
    112     *            an assignment
    113     * @return the number of overlapping slots against the number of slots of the smallest section
    114     */
    115    public int share(Assignment a1, Assignment a2) {
    116        if (!inConflict(a1, a2)) return 0;
    117        return a1.getTime().nrSharedDays(a2.getTime()) * a1.getTime().nrSharedHours(a2.getTime());
    118    }
    119
    120
    121    /**
    122     * Return number of time overlapping conflicts that are between two enrollments. It
    123     * is the total share between pairs of assignments of these enrollments that are in a
    124     * time overlap.
    125     *
    126     * @param e1
    127     *            an enrollment
    128     * @param e2
    129     *            an enrollment
    130     * @return number of time overlapping conflict between given enrollments
    131     */
    132    public int nrConflicts(Enrollment e1, Enrollment e2) {
    133        if (!e1.getStudent().equals(e2.getStudent())) return 0;
    134        if (e1.getRequest() instanceof FreeTimeRequest && e2.getRequest() instanceof FreeTimeRequest) return 0;
    135        int cnt = 0;
    136        for (Assignment s1 : e1.getAssignments()) {
    137            for (Assignment s2 : e2.getAssignments()) {
    138                if (inConflict(s1, s2))
    139                    cnt += share(s1, s2);
    140            }
    141        }
    142        return cnt;
    143    }
    144
    145    /**
    146     * Return a set of time overlapping conflicts ({@link Conflict} objects) between
    147     * given (course) enrollments.
    148     *
    149     * @param e1
    150     *            an enrollment
    151     * @param e2
    152     *            an enrollment
    153     * @return list of time overlapping conflicts that are between assignment of the
    154     *         given enrollments
    155     */
    156    public Set<Conflict> conflicts(Enrollment e1, Enrollment e2) {
    157        Set<Conflict> ret = new HashSet<Conflict>();
    158        if (!e1.getStudent().equals(e2.getStudent())) return ret;
    159        if (e1.getRequest() instanceof FreeTimeRequest && e2.getRequest() instanceof FreeTimeRequest) return ret;
    160        for (Assignment s1 : e1.getAssignments()) {
    161            for (Assignment s2 : e2.getAssignments()) {
    162                if (inConflict(s1, s2))
    163                    ret.add(new Conflict(e1.getStudent(), share(s1, s2), e1, s1, e2, s2));
    164            }
    165        }
    166        return ret;
    167    }
    168
    169    /**
    170     * Total sum of all conflict of the given enrollment and other enrollments
    171     * that are assigned to the same student.
    172     */
    173    public int nrAllConflicts(Enrollment enrollment) {
    174        if (enrollment.getRequest() instanceof FreeTimeRequest) return 0;
    175        int cnt = 0;
    176        for (Request request : enrollment.getStudent().getRequests()) {
    177            if (request.equals(enrollment.getRequest())) continue;
    178            if (request instanceof FreeTimeRequest) {
    179                FreeTimeRequest ft = (FreeTimeRequest)request;
    180                cnt += nrConflicts(enrollment, ft.createEnrollment());
    181            } else if (request.getAssignment() != null && !request.equals(iOldVariable)) {
    182                cnt += nrConflicts(enrollment, request.getAssignment());
    183            }
    184        }
    185        return cnt;
    186    }
    187
    188    /**
    189     * Total sum of all free time conflict of the given enrollment.
    190     */
    191    public int nrFreeTimeConflicts(Enrollment enrollment) {
    192        if (enrollment.getRequest() instanceof FreeTimeRequest) return 0;
    193        int cnt = 0;
    194        for (Request request : enrollment.getStudent().getRequests()) {
    195            if (request instanceof FreeTimeRequest) {
    196                FreeTimeRequest ft = (FreeTimeRequest)request;
    197                for (Assignment section: enrollment.getAssignments())
    198                    cnt += share(section, ft);
    199            }
    200        }
    201        return cnt;
    202    }
    203
    204    /**
    205     * Return a set of free time conflict of the given enrollment.
    206     */
    207    public Set<Conflict> freeTimeConflicts(Enrollment enrollment) {
    208        Set<Conflict> ret = new HashSet<Conflict>();
    209        if (enrollment.getRequest() instanceof FreeTimeRequest) return ret;
    210        for (Request request : enrollment.getStudent().getRequests()) {
    211            if (request instanceof FreeTimeRequest) {
    212                FreeTimeRequest ft = (FreeTimeRequest)request;
    213                for (Assignment section: enrollment.getAssignments()) {
    214                    if (inConflict(section, ft))
    215                        ret.add(new Conflict(enrollment.getStudent(), share(section, ft), enrollment, section, ft.createEnrollment(), ft));
    216                }
    217            }
    218        }
    219        return ret;
    220    }
    221
    222    /**
    223     * The set of all conflicts ({@link Conflict} objects) of the given
    224     * enrollment and other enrollments that are assigned to the same student.
    225     */
    226    public Set<Conflict> allConflicts(Enrollment enrollment) {
    227        Set<Conflict> ret = new HashSet<Conflict>();
    228        if (enrollment.getRequest() instanceof FreeTimeRequest) return ret;
    229        for (Request request : enrollment.getStudent().getRequests()) {
    230            if (request.equals(enrollment.getRequest())) continue;
    231            if (request instanceof FreeTimeRequest) {
    232                FreeTimeRequest ft = (FreeTimeRequest)request;
    233                ret.addAll(conflicts(enrollment, ft.createEnrollment()));
    234                continue;
    235            } else if (request.getAssignment() != null && !request.equals(iOldVariable)) {
    236                ret.addAll(conflicts(enrollment, request.getAssignment()));
    237            }
    238        }
    239        return ret;
    240    }
    241
    242    /**
    243     * Called when a value is assigned to a variable. Internal number of
    244     * time overlapping conflicts is updated, see
    245     * {@link TimeOverlapsCounter#getTotalNrConflicts()}.
    246     */
    247    public void assigned(long iteration, Enrollment value) {
    248        StudentSectioningModel m = (StudentSectioningModel)value.variable().getModel();
    249        for (Conflict c: allConflicts(value)) {
    250            iTotalNrConflicts += c.getShare();
    251            m.add(c);
    252        }
    253        if (sDebug) {
    254            sLog.debug("A:" + value.variable() + " := " + value);
    255            int inc = nrAllConflicts(value);
    256            if (inc != 0) {
    257                sLog.debug("-- TOC+" + inc + " A: " + value.variable() + " := " + value);
    258                for (Conflict c: allConflicts(value)) {
    259                    sLog.debug("  -- " + c);
    260                    iAllConflicts.add(c);
    261                    inc -= c.getShare();
    262                }
    263                if (inc != 0) {
    264                    sLog.error("Different number of conflicts for the assigned value (difference: " + inc + ")!");
    265                }
    266            }
    267        }
    268    }
    269
    270    /**
    271     * Called when a value is unassigned from a variable. Internal number of
    272     * time overlapping conflicts is updated, see
    273     * {@link TimeOverlapsCounter#getTotalNrConflicts()}.
    274     */
    275    public void unassigned(long iteration, Enrollment value) {
    276        StudentSectioningModel m = (StudentSectioningModel)value.variable().getModel();
    277        for (Conflict c: allConflicts(value)) {
    278            iTotalNrConflicts -= c.getShare();
    279            m.remove(c);
    280        }
    281        if (sDebug) {
    282            sLog.debug("U:" + value.variable() + " := " + value);
    283            int dec = nrAllConflicts(value);
    284            if (dec != 0) {
    285                sLog.debug("-- TOC-" + dec + " U: " + value.variable() + " := " + value);
    286                for (Conflict c: allConflicts(value)) {
    287                    sLog.debug("  -- " + c);
    288                    iAllConflicts.remove(c);
    289                    dec -= c.getShare();
    290                }
    291                if (dec != 0) {
    292                    sLog.error("Different number of conflicts for the unassigned value (difference: " + dec + ")!");
    293                }
    294            }
    295        }
    296    }
    297
    298    /** Actual number of all time overlapping conflicts */
    299    public int getTotalNrConflicts() {
    300        return iTotalNrConflicts;
    301    }
    302
    303    public void checkTotalNrConflicts() {
    304        int total = countTotalNrConflicts();
    305        if (total != iTotalNrConflicts) {
    306            sLog.error("Number of conflicts does not match (actual: " + total + ", count: " + iTotalNrConflicts + ")!");
    307            iTotalNrConflicts = total;
    308            if (sDebug) {
    309                Set<Conflict> conflicts = computeAllConflicts();
    310                for (Conflict c: conflicts) {
    311                    if (!iAllConflicts.contains(c))
    312                        sLog.debug("  +add+ " + c);
    313                }
    314                for (Conflict c: iAllConflicts) {
    315                    if (!conflicts.contains(c))
    316                        sLog.debug("  -rem- " + c);
    317                }
    318                for (Conflict c: conflicts) {
    319                    for (Conflict d: iAllConflicts) {
    320                        if (c.equals(d) && c.getShare() != d.getShare()) {
    321                            sLog.debug("  -dif- " + c + " (other: " + d.getShare() + ")");
    322                        }
    323                    }
    324                }
    325                iAllConflicts = conflicts;
    326                // getSolver().stopSolver(false);
    327            }
    328        }
    329    }
    330
    331    /**
    332     * Compute the actual number of all time overlapping conflicts. Should be equal to
    333     * {@link TimeOverlapsCounter#getTotalNrConflicts()}.
    334     */
    335    public int countTotalNrConflicts() {
    336        int total = 0;
    337        for (Request r1 : getModel().variables()) {
    338            if (r1.getAssignment() == null || r1 instanceof FreeTimeRequest || r1.equals(iOldVariable))
    339                continue;
    340            for (Request r2 : r1.getStudent().getRequests()) {
    341                if (r2 instanceof FreeTimeRequest) {
    342                    FreeTimeRequest ft = (FreeTimeRequest)r2;
    343                    total += nrConflicts(r1.getAssignment(), ft.createEnrollment());
    344                } else if (r2.getAssignment() != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) {
    345                    total += nrConflicts(r1.getAssignment(), r2.getAssignment());
    346                }
    347            }
    348        }
    349        return total;
    350    }
    351
    352    /**
    353     * Compute a set of all time overlapping conflicts ({@link Conflict} objects).
    354     */
    355    public Set<Conflict> computeAllConflicts() {
    356        Set<Conflict> ret = new HashSet<Conflict>();
    357        for (Request r1 : getModel().variables()) {
    358            if (r1.getAssignment() == null || r1 instanceof FreeTimeRequest || r1.equals(iOldVariable))
    359                continue;
    360            for (Request r2 : r1.getStudent().getRequests()) {
    361                if (r2 instanceof FreeTimeRequest) {
    362                    FreeTimeRequest ft = (FreeTimeRequest)r2;
    363                    ret.addAll(conflicts(r1.getAssignment(), ft.createEnrollment()));
    364                } else if (r2.getAssignment() != null && r1.getId() < r2.getId() && !r2.equals(iOldVariable)) {
    365                    ret.addAll(conflicts(r1.getAssignment(), r2.getAssignment()));
    366                }
    367            }
    368        }
    369        return ret;
    370    }
    371
    372    /**
    373     * Return a set of all time overlapping conflicts ({@link Conflict} objects).
    374     */
    375    public Set<Conflict> getAllConflicts() {
    376        return iAllConflicts;
    377    }
    378
    379    /**
    380     * Called before a value is assigned to a variable.
    381     */
    382    @Override
    383    public void beforeAssigned(long iteration, Enrollment value) {
    384        if (value != null) {
    385            if (value.variable().getAssignment() != null) {
    386                iUnassignedValue = value.variable().getAssignment();
    387                unassigned(iteration, value.variable().getAssignment());
    388            }
    389            iOldVariable = value.variable();
    390        }
    391    }
    392
    393    /**
    394     * Called after a value is assigned to a variable.
    395     */
    396    @Override
    397    public void afterAssigned(long iteration, Enrollment value) {
    398        iOldVariable = null;
    399        iUnassignedValue = null;
    400        if (value != null) {
    401            assigned(iteration, value);
    402        }
    403    }
    404
    405    /**
    406     * Called after a value is unassigned from a variable.
    407     */
    408    @Override
    409    public void afterUnassigned(long iteration, Enrollment value) {
    410        if (value != null && !value.equals(iUnassignedValue)) {
    411            unassigned(iteration, value);
    412        }
    413    }
    414
    415    /** A representation of a time overlapping conflict */
    416    public static class Conflict {
    417        private int iShare;
    418        private Student iStudent;
    419        private Assignment iA1, iA2;
    420        private Enrollment iE1, iE2;
    421        private int iHashCode;
    422
    423        /**
    424         * Constructor
    425         *
    426         * @param student
    427         *            related student
    428         * @param a1
    429         *            first conflicting section
    430         * @param a2
    431         *            second conflicting section
    432         */
    433        public Conflict(Student student, int share, Enrollment e1, Assignment a1, Enrollment e2, Assignment a2) {
    434            iStudent = student;
    435            if (a1.compareById(a2) < 0 ) {
    436                iA1 = a1;
    437                iA2 = a2;
    438                iE1 = e1;
    439                iE2 = e2;
    440            } else {
    441                iA1 = a2;
    442                iA2 = a1;
    443                iE1 = e2;
    444                iE2 = e1;
    445            }
    446            iHashCode = (iStudent.getId() + ":" + iA1.getId() + ":" + iA2.getId()).hashCode();
    447            iShare = share;
    448        }
    449
    450        /** Related student */
    451        public Student getStudent() {
    452            return iStudent;
    453        }
    454
    455        /** First section */
    456        public Assignment getS1() {
    457            return iA1;
    458        }
    459
    460        /** Second section */
    461        public Assignment getS2() {
    462            return iA2;
    463        }
    464
    465        /** First request */
    466        public Request getR1() {
    467            return iE1.getRequest();
    468        }
    469
    470        /** Second request */
    471        public Request getR2() {
    472            return iE2.getRequest();
    473        }
    474
    475        /** First enrollment */
    476        public Enrollment getE1() {
    477            return iE1;
    478        }
    479
    480        /** Second enrollment */
    481        public Enrollment getE2() {
    482            return iE2;
    483        }
    484
    485        @Override
    486        public int hashCode() {
    487            return iHashCode;
    488        }
    489
    490        /** The number of overlapping slots against the number of slots of the smallest section */
    491        public int getShare() {
    492            return iShare;
    493        }
    494
    495        @Override
    496        public boolean equals(Object o) {
    497            if (o == null || !(o instanceof Conflict)) return false;
    498            Conflict c = (Conflict) o;
    499            return getStudent().equals(c.getStudent()) && getS1().equals(c.getS1()) && getS2().equals(c.getS2());
    500        }
    501
    502        @Override
    503        public String toString() {
    504            return getStudent() + ": (s:" + getShare() + ") " + getS1() + " -- " + getS2();
    505        }
    506    }
    507}