    001package org.cpsolver.coursett.criteria;
    002
    003import java.util.Collection;
    004import java.util.HashSet;
    005import java.util.Set;
    006
    007import org.cpsolver.coursett.Constants;
    008import org.cpsolver.coursett.constraint.JenrlConstraint;
    009import org.cpsolver.coursett.model.Lecture;
    010import org.cpsolver.coursett.model.Placement;
    011import org.cpsolver.coursett.model.Student;
    012import org.cpsolver.coursett.model.TimeLocation;
    013import org.cpsolver.coursett.model.TimetableModel;
    014import org.cpsolver.ifs.assignment.Assignment;
    015import org.cpsolver.ifs.util.DataProperties;
    016import org.cpsolver.ifs.util.DistanceMetric;
    017
    018
    019/**
    020 * Student conflicts. This criterion counts student conflicts between classes. A conflict
    021 * occurs when two classes that are attended by the same student (or students) are overlapping
    022 * in time or place back-to-back in rooms that are too far a part. The combinations of classes
    023 * that share students are maintained by {@link JenrlConstraint}.
    024 * <br>
    025 *
    026 * @author  Tomáš Müller
    027 * @version CourseTT 1.3 (University Course Timetabling)<br>
    028 *          Copyright (C) 2006 - 2014 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 */
    046public class StudentConflict extends TimetablingCriterion {
    047    protected boolean iIncludeConflicts = false;
    048
    049    public StudentConflict() {
    050        setValueUpdateType(ValueUpdateType.BeforeUnassignedBeforeAssigned);
    051    }
    052
    053    @Override
    054    public void configure(DataProperties properties) {
    055        super.configure(properties);
    056        iIncludeConflicts = properties.getPropertyBoolean("StudentConflict.IncludeConflicts", false);
    057    }
    058
    059    @Override
    060    public String getPlacementSelectionWeightName() {
    061        return null;
    062    }
    063
    064    public DistanceMetric getMetrics() {
    065        return (getModel() == null ? null : ((TimetableModel)getModel()).getDistanceMetric());
    066    }
    067
    068    public static boolean overlaps(Placement p1, Placement p2) {
    069        return p1 != null && p2 != null && p1.getTimeLocation().hasIntersection(p2.getTimeLocation()) && (!p1.variable().isCommitted() || !p2.variable().isCommitted());
    070    }
    071
    072    protected double jointEnrollment(JenrlConstraint jenrl, Placement p1, Placement p2) {
    073        return jointEnrollment(jenrl);
    074    }
    075
    076    protected double jointEnrollment(JenrlConstraint jenrl) {
    077        return jenrl.jenrl();
    078    }
    079
    080    public static boolean distance(DistanceMetric m, Placement p1, Placement p2) {
    081        if (m == null && p1 != null) m = ((TimetableModel)p1.variable().getModel()).getDistanceMetric();
    082        if (m == null && p2 != null) m = ((TimetableModel)p2.variable().getModel()).getDistanceMetric();
    083        if (p1 == null || p2 == null || m == null) return false;
    084        if (p1.variable().isCommitted() && p2.variable().isCommitted()) return false;
    085        TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation();
    086        if (!t1.shareDays(t2) || !t1.shareWeeks(t2)) return false;
    087        if (m.doComputeDistanceConflictsBetweenNonBTBClasses()) {
    088            if (t1.getStartSlot() + t1.getLength() <= t2.getStartSlot()) {
    089                return Placement.getDistanceInMinutes(m, p1, p2) > t1.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t2.getStartSlot() - t1.getStartSlot() - t1.getLength());
    090            } else if (t2.getStartSlot() + t2.getLength() <= t1.getStartSlot()) {
    091                return Placement.getDistanceInMinutes(m, p1, p2) > t2.getBreakTime() + Constants.SLOT_LENGTH_MIN * (t1.getStartSlot() - t2.getStartSlot() - t2.getLength());
    092            }
    093        } else {
    094            if (t1.getStartSlot() + t1.getLength() == t2.getStartSlot()) {
    095                return Placement.getDistanceInMinutes(m, p1, p2) > t1.getBreakTime();
    096            } else if (t2.getStartSlot() + t2.getLength() == t1.getStartSlot()) {
    097                return Placement.getDistanceInMinutes(m, p1, p2) > t2.getBreakTime();
    098            }
    099        }
    100        return false;
    101    }
    102
    103    public static int slots(Placement p1, Placement p2) {
    104        if (p1 == null || p2 == null) return 0;
    105        TimeLocation t1 = p1.getTimeLocation(), t2 = p2.getTimeLocation();
    106        if (t1 == null || t2 == null || !t1.shareDays(t2) || !t1.shareWeeks(t2)) return 0;
    107        return Math.max(t1.getStartSlot() + t1.getLength(), t2.getStartSlot() + t2.getLength()) - Math.min(t1.getStartSlot(), t2.getStartSlot());
    108    }
    109
    110    public static boolean workday(int slotsLimit, Placement p1, Placement p2) {
    111        if (slotsLimit <= 0) return false;
    112        return p1 != null && p2 != null && slots(p1, p2) > slotsLimit;
    113    }
    114
    115    public static boolean ignore(Lecture l1, Lecture l2) {
    116        return l1 != null && l2 != null && l1.isToIgnoreStudentConflictsWith(l2);
    117    }
    118
    119    public static boolean committed(Lecture l1, Lecture l2) {
    120        return l1 != null && l2 != null && (l1.isCommitted() || l2.isCommitted()) && (!l1.isCommitted() || !l2.isCommitted());
    121    }
    122
    123    public static boolean uncommitted(Lecture l1, Lecture l2) {
    124        return l1 != null && l2 != null && !l1.isCommitted() && !l2.isCommitted();
    125    }
    126
    127    public static boolean applicable(Lecture l1, Lecture l2) {
    128        return l1 != null && l2 != null && (!l1.isCommitted() || !l2.isCommitted());
    129    }
    130
    131    public static boolean hard(Lecture l1, Lecture l2) {
    132        return l1 != null && l2 != null && l1.isSingleSection() && l2.isSingleSection() && (!l1.isCommitted() || !l2.isCommitted());
    133    }
    134
    135    public boolean isApplicable(Lecture l1, Lecture l2) {
    136        return l1 != null && l2 != null && !ignore(l1, l2) && uncommitted(l1, l2); // exclude committed and outside student conflicts
    137    }
    138
    139    public boolean isApplicable(Student student, Lecture l1, Lecture l2) {
    140        return isApplicable(l1, l2);
    141    }
    142
    143    public boolean inConflict(Placement p1, Placement p2) {
    144        return overlaps(p1, p2) || distance(getMetrics(), p1, p2);
    145    }
    146
    147    @Override
    148    public double getValue(Assignment<Lecture, Placement> assignment, Placement value, Set<Placement> conflicts) {
    149        double ret = 0.0;
    150        for (JenrlConstraint jenrl: value.variable().jenrlConstraints()) {
    151            Lecture other = jenrl.another(value.variable());
    152            if (!isApplicable(value.variable(), other)) continue;
    153            Placement another = assignment.getValue(other);
    154            if (another == null) continue;
    155            if (conflicts != null && conflicts.contains(another)) continue;
    156            if (inConflict(value, another))
    157                ret += jointEnrollment(jenrl, value, another);
    158        }
    159        if (iIncludeConflicts && conflicts != null)
    160            for (Placement conflict: conflicts) {
    161                for (JenrlConstraint jenrl: conflict.variable().jenrlConstraints()) {
    162                    Lecture other = jenrl.another(conflict.variable());
    163                    if (!isApplicable(conflict.variable(), other)) continue;
    164                    Placement another = assignment.getValue(other);
    165                    if (another == null || another.variable().equals(value.variable())) continue;
    166                    if (conflicts != null && conflicts.contains(another)) continue;
    167                    if (inConflict(conflict, another))
    168                        ret -= jointEnrollment(jenrl, conflict, another);
    169                }
    170            }
    171        return ret;
    172    }
    173
    174    @Override
    175    public double getValue(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) {
    176        double ret = 0.0;
    177        Set<JenrlConstraint> constraints = new HashSet<JenrlConstraint>();
    178        for (Lecture lect: variables) {
    179            Placement plac = assignment.getValue(lect);
    180            if (plac == null) continue;
    181            for (JenrlConstraint jenrl: lect.jenrlConstraints()) {
    182                if (!constraints.add(jenrl)) continue;
    183                Lecture other = jenrl.another(lect);
    184                if (!other.isCommitted() && !variables.contains(other)) continue;
    185                if (!isApplicable(lect, other)) continue;
    186                if (inConflict(plac, assignment.getValue(other)))
    187                    ret += jointEnrollment(jenrl, plac, assignment.getValue(other));
    188            }
    189        }
    190        return ret;
    191    }
    192
    193    @Override
    194    public double[] getBounds(Assignment<Lecture, Placement> assignment) {
    195        double[] bounds = { 0.0, 0.0 };
    196        for (JenrlConstraint jenrl: ((TimetableModel)getModel()).getJenrlConstraints())
    197            if (isApplicable(jenrl.first(), jenrl.second()))
    198                bounds[0] += jointEnrollment(jenrl);
    199        return bounds;
    200    }
    201
    202    @Override
    203    public double[] getBounds(Assignment<Lecture, Placement> assignment, Collection<Lecture> variables) {
    204        double[] bounds = { 0.0, 0.0 };
    205        Set<JenrlConstraint> constraints = new HashSet<JenrlConstraint>();
    206        for (Lecture lect: variables) {
    207            if (assignment.getValue(lect) == null) continue;
    208            for (JenrlConstraint jenrl: lect.jenrlConstraints()) {
    209                if (isApplicable(jenrl.first(), jenrl.second()) && constraints.add(jenrl) && (jenrl.another(lect).isCommitted() || variables.contains(jenrl.another(lect))))
    210                    bounds[0] += jointEnrollment(jenrl);
    211            }
    212        }
    213        return bounds;
    214    }
    215
    216    public void incJenrl(Assignment<Lecture, Placement> assignment, JenrlConstraint jenrl, double studentWeight, Double conflictPriority, Student student) {
    217        if (isApplicable(jenrl.first(), jenrl.second()) && inConflict(assignment.getValue(jenrl.first()), assignment.getValue(jenrl.second())))
    218            super.inc(assignment, studentWeight);
    219    }
    220
    221    @Override
    222    public void bestRestored(Assignment<Lecture, Placement> assignment) {
    223        super.bestRestored(assignment);
    224        getContext(assignment).setTotal(getValue(assignment, getModel().variables()));
    225    }
    226}