    001package net.sf.cpsolver.coursett.criteria;
    002
    003import java.util.Collection;
    004import java.util.HashSet;
    005import java.util.Set;
    006
    007import net.sf.cpsolver.coursett.Constants;
    008import net.sf.cpsolver.coursett.constraint.JenrlConstraint;
    009import net.sf.cpsolver.coursett.model.Lecture;
    010import net.sf.cpsolver.coursett.model.Placement;
    011import net.sf.cpsolver.coursett.model.Student;
    012import net.sf.cpsolver.coursett.model.TimeLocation;
    013import net.sf.cpsolver.coursett.model.TimetableModel;
    014import net.sf.cpsolver.ifs.solver.Solver;
    015import net.sf.cpsolver.ifs.util.DistanceMetric;
    016
    017/**
    018 * Student conflicts. This criterion counts student conflicts between classes. A conflict
    019 * occurs when two classes that are attended by the same student (or students) are overlapping
    020 * in time or place back-to-back in rooms that are too far a part. The combinations of classes
    021 * that share students are maintained by {@link JenrlConstraint}.
    022 * <br>
    023 *
    024 * @version CourseTT 1.2 (University Course Timetabling)<br>
    025 *          Copyright (C) 2006 - 2011 Tomáš Müller<br>
    026 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    027 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    028 * <br>
    029 *          This library is free software; you can redistribute it and/or modify
    030 *          it under the terms of the GNU Lesser General Public License as
    031 *          published by the Free Software Foundation; either version 3 of the
    032 *          License, or (at your option) any later version. <br>
    033 * <br>
    034 *          This library is distributed in the hope that it will be useful, but
    035 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    036 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    037 *          Lesser General Public License for more details. <br>
    038 * <br>
    039 *          You should have received a copy of the GNU Lesser General Public
    040 *          License along with this library; if not see
    041 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    042 */
    043public class StudentConflict extends TimetablingCriterion {
    044    protected boolean iIncludeConflicts = false;
    045
    046    public StudentConflict() {
    047        iValueUpdateType = ValueUpdateType.BeforeUnassignedBeforeAssigned;
    048    }
    049
    050    @Override
    051    public boolean init(Solver<Lecture, Placement> solver) {
    052        iIncludeConflicts = solver.getProperties().getPropertyBoolean("StudentConflict.IncludeConflicts", false);
    053        return super.init(solver);
    054    }
    055
    056    @Override
    057    public String getPlacementSelectionWeightName() {
    058        return null;
    059    }
    060
    061    @Override
    062    public double getValue() {
    063        return super.getValue();
    064    }
    065
    066    public DistanceMetric getMetrics() {
    067        return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric());
    068    }
    069
    070    public static boolean overlaps(Placement p1, Placement p2) {
    071        return p1 != null && p2 != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation()) && (!p1.variable().isCommitted() || !p2.variable().isCommitted());
    072    }
    073
    074    protected double jointEnrollment(JenrlConstraint jenrl) {
    075        return jenrl.jenrl();
    076    }
    077
    078    public static boolean distance(DistanceMetric m, Placement p1, Placement p2) {
    079        if (m == null && p1 != null) m = ((TimetableModel)p1.variable().getModel()).getDistanceMetric();
    080        if (m == null && p2 != null) m = ((TimetableModel)p2.variable().getModel()).getDistanceMetric();
    081        if (p1 == null || p2 == null || m == null) return false;
    082        if (p1.variable().isCommitted() && p2.variable().isCommitted()) return false;
    083        TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation();
    084        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
    085        if (m.doComputeDistanceConflictsBetweenNonBTBClasses()) {
    086            if (t1.getStartSlot() + t1.getLength() <= t2.getStartSlot()) {
    087                return Placement.getDistanceInMinutes(m, p1, p2) > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t2.getStartSlot() - t1.getStartSlot() - t1.getLength());
    088            } else if (t2.getStartSlot() + t2.getLength() <= t1.getStartSlot()) {
    089                return Placement.getDistanceInMinutes(m, p1, p2) > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t1.getStartSlot() - t2.getStartSlot() - t2.getLength());
    090            }
    091        } else {
    092            if (t1.getStartSlot() + t1.getLength() == t2.getStartSlot()) {
    093                return Placement.getDistanceInMinutes(m, p1, p2) > t1.getBreakTime();
    094            } else if (t2.getStartSlot() + t2.getLength() == t1.getStartSlot()) {
    095                return Placement.getDistanceInMinutes(m, p1, p2) > t2.getBreakTime();
    096            }
    097        }
    098        return false;
    099    }
    100
    101    public static boolean ignore(Placement p1, Placement p2) {
    102        return p1 != null && p2 != null && p1.variable().isToIgnoreStudentConflictsWith(p2.variable());
    103    }
    104
    105    public static boolean ignore(Lecture l1, Lecture l2) {
    106        return l1 != null && l2 != null && l1.isToIgnoreStudentConflictsWith(l2);
    107    }
    108
    109    public static boolean committed(Placement p1, Placement p2) {
    110        return p1 != null && p2 != null && committed(p1.variable(), p2.variable());
    111    }
    112
    113    public static boolean committed(Lecture l1, Lecture l2) {
    114        return l1 != null && l2 != null && (l1.isCommitted() || l2.isCommitted()) && (!l1.isCommitted() || !l2.isCommitted());
    115    }
    116
    117    public static boolean applicable(Placement p1, Placement p2) {
    118        return p1 != null && p2 != null && applicable(p1.variable(), p2.variable());
    119    }
    120
    121    public static boolean applicable(Lecture l1, Lecture l2) {
    122        return l1 != null && l2 != null && (!l1.isCommitted() || !l2.isCommitted());
    123    }
    124
    125    public static boolean hard(Placement p1, Placement p2) {
    126        return p1 != null && p2 != null && hard(p1.variable(), p2.variable());
    127    }
    128
    129    public static boolean hard(Lecture l1, Lecture l2) {
    130        return l1 != null && l2 != null && l1.isSingleSection() && l2.isSingleSection() && (!l1.isCommitted() || !l2.isCommitted());
    131    }
    132
    133    public boolean isApplicable(Lecture l1, Lecture l2) {
    134        return !ignore(l1, l2) && applicable(l1, l2) && !committed(l1, l2); // exclude committed and outside student conflicts
    135    }
    136
    137    public boolean inConflict(Placement p1, Placement p2) {
    138        return !ignore(p1, p2) && (overlaps(p1, p2) || distance(getMetrics(), p1, p2)) && isApplicable(p1.variable(), p2.variable());
    139    }
    140
    141    @Override
    142    public double getValue(Placement value, Set<Placement> conflicts) {
    143        double ret = 0.0;
    144        for (JenrlConstraint jenrl: value.variable().jenrlConstraints()) {
    145            Placement another = jenrl.another(value.variable()).getAssignment();
    146            if (another == null) continue;
    147            if (conflicts != null && conflicts.contains(another)) continue;
    148            if (inConflict(value, another))
    149                ret += jointEnrollment(jenrl);
    150        }
    151        if (iIncludeConflicts && conflicts != null)
    152            for (Placement conflict: conflicts) {
    153                for (JenrlConstraint jenrl: conflict.variable().jenrlConstraints()) {
    154                    Placement another = jenrl.another(conflict.variable()).getAssignment();
    155                    if (another == null || another.variable().equals(value.variable())) continue;
    156                    if (conflicts != null && conflicts.contains(another)) continue;
    157                    if (inConflict(conflict, another))
    158                        ret -= jointEnrollment(jenrl);
    159                }
    160            }
    161        return ret;
    162    }
    163
    164    @Override
    165    public double getValue(Collection<Lecture> variables) {
    166        double ret = 0.0;
    167        Set<JenrlConstraint> constraints = new HashSet<JenrlConstraint>();
    168        for (Lecture lect: variables) {
    169            if (lect.getAssignment() == null) continue;
    170            for (JenrlConstraint jenrl: lect.jenrlConstraints()) {
    171                if (!constraints.add(jenrl)) continue;
    172                if (!jenrl.another(lect).isCommitted() && !variables.contains(jenrl.another(lect))) continue;
    173                if (inConflict(lect.getAssignment(), jenrl.another(lect).getAssignment()))
    174                    ret += jointEnrollment(jenrl);
    175            }
    176        }
    177        return ret;
    178    }
    179
    180    @Override
    181    public double[] getBounds() {
    182        double[] bounds = { 0.0, 0.0 };
    183        for (JenrlConstraint jenrl: ((TimetableModel)getModel()).getJenrlConstraints())
    184            if (isApplicable(jenrl.first(), jenrl.second()))
    185                bounds[0] += jointEnrollment(jenrl);
    186        return bounds;
    187    }
    188
    189    @Override
    190    public double[] getBounds(Collection<Lecture> variables) {
    191        double[] bounds = { 0.0, 0.0 };
    192        Set<JenrlConstraint> constraints = new HashSet<JenrlConstraint>();
    193        for (Lecture lect: variables) {
    194            if (lect.getAssignment() == null) continue;
    195            for (JenrlConstraint jenrl: lect.jenrlConstraints()) {
    196                if (isApplicable(jenrl.first(), jenrl.second()) && constraints.add(jenrl) && (jenrl.another(lect).isCommitted() || variables.contains(jenrl.another(lect))))
    197                    bounds[0] += jointEnrollment(jenrl);
    198            }
    199        }
    200        return bounds;
    201    }
    202
    203    public void incJenrl(JenrlConstraint jenrl, double studentWeight, Double conflictPriority, Student student) {
    204        if (inConflict(jenrl.first().getAssignment(), jenrl.second().getAssignment()))
    205            iValue += studentWeight;
    206    }
    207
    208    @Override
    209    public void bestRestored() {
    210        super.bestRestored();
    211        iValue = getValue(getModel().variables());
    212    }
    213}