    001package org.cpsolver.coursett.sectioning;
    002
    003import java.util.Collection;
    004import java.util.HashSet;
    005import java.util.List;
    006import java.util.Map;
    007import java.util.Set;
    008
    009import org.cpsolver.coursett.constraint.JenrlConstraint;
    010import org.cpsolver.coursett.criteria.StudentConflict;
    011import org.cpsolver.coursett.model.Configuration;
    012import org.cpsolver.coursett.model.Lecture;
    013import org.cpsolver.coursett.model.Placement;
    014import org.cpsolver.coursett.model.Student;
    015import org.cpsolver.coursett.model.StudentGroup;
    016import org.cpsolver.coursett.model.TimetableModel;
    017import org.cpsolver.ifs.assignment.Assignment;
    018
    019/**
    020 * Student swap move. Two students of the same offering are swapped between each other
    021 * or a student is given some other (alternative) enrollment into the given offering.
    022 *
    023 * @author  Tomáš Müller
    024 * @version CourseTT 1.3 (University Course Timetabling)<br>
    025 *          Copyright (C) 2017 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 StudentSwap implements StudentMove {
    044    private TimetableModel iModel;
    045    private Student iFirstStudent, iSecondStudent;
    046    private Set<Lecture> iFirstLectures, iSecondLectures;
    047    private Configuration iFirstConfig, iSecondConfig;
    048    private boolean iAllowed = true;
    049
    050    /**
    051     * Create a swap of two students of an offering.
    052     */
    053    public StudentSwap(TimetableModel model, Assignment<Lecture, Placement> assignment, Student firstStudent, Student secondStudent, Long offeringId) {
    054        iModel = model;
    055        iFirstStudent = firstStudent; iSecondStudent = secondStudent;
    056        iAllowed = initSwap(assignment, offeringId);
    057    }
    058
    059    /**
    060     * Move a student into some other lectures of the offering.
    061     */
    062    public StudentSwap(TimetableModel model, Assignment<Lecture, Placement> assignment, Student student, Collection<Lecture> lectures) {
    063        iModel = model;
    064        iFirstStudent = student; iSecondStudent = null;
    065        iAllowed = initMove(assignment, lectures);
    066    }
    067
    068    /**
    069     * Compute student swap and its validity
    070     */
    071    protected boolean initSwap(Assignment<Lecture, Placement> assignment, Long offeringId) {
    072        double w1 = iFirstStudent.getOfferingWeight(offeringId), w2 = iSecondStudent.getOfferingWeight(offeringId);
    073        iFirstLectures = new HashSet<Lecture>();
    074        for (Lecture lecture: iFirstStudent.getLectures()) {
    075            if (lecture.getConfiguration() == null) return false;
    076            if (lecture.getConfiguration().getOfferingId().equals(offeringId) && !iSecondStudent.getLectures().contains(lecture)) {
    077                iFirstLectures.add(lecture);
    078                if (iFirstConfig == null)
    079                    iFirstConfig = lecture.getConfiguration();
    080                if (!iSecondStudent.canEnroll(lecture) || !iFirstStudent.canUnenroll(lecture)) return false;
    081                if (w2 - w1 > 0.0 && lecture.nrWeightedStudents() - w1 + w2 > sEps + lecture.classLimit(assignment)) return false;
    082            }
    083        }
    084        iSecondLectures = new HashSet<Lecture>();
    085        for (Lecture lecture: iSecondStudent.getLectures()) {
    086            if (lecture.getConfiguration() == null) return false;
    087            if (lecture.getConfiguration().getOfferingId().equals(offeringId) && !iFirstStudent.getLectures().contains(lecture)) {
    088                iSecondLectures.add(lecture);
    089                if (iSecondConfig == null)
    090                    iSecondConfig = lecture.getConfiguration();
    091                if (!iFirstStudent.canEnroll(lecture) || !iSecondStudent.canUnenroll(lecture)) return false;
    092                if (w1 - w2 > 0.0 && lecture.nrWeightedStudents() - w2 + w1 > sEps + lecture.classLimit(assignment)) return false;
    093            }
    094        }
    095        return !iFirstLectures.isEmpty() && !iSecondLectures.isEmpty();
    096    }
    097
    098    /**
    099     * Compute student move and its validity
    100     */
    101    private boolean initMove(Assignment<Lecture, Placement> assignment, Collection<Lecture> lectures) {
    102        double w = 0.0;
    103        iFirstLectures = new HashSet<Lecture>();
    104        iSecondLectures = new HashSet<Lecture>();
    105        for (Lecture lecture: lectures) {
    106            if (lecture.getConfiguration() == null) return false;
    107            if (!iFirstStudent.getLectures().contains(lecture)) {
    108                if (iSecondConfig == null) {
    109                    iSecondConfig = lecture.getConfiguration();
    110                    w = iFirstStudent.getOfferingWeight(iSecondConfig);
    111                }
    112                iSecondLectures.add(lecture);
    113                if (lecture.nrWeightedStudents() + w > sEps + lecture.classLimit(assignment)) return false;
    114            }
    115        }
    116        if (iSecondLectures.isEmpty()) return false;
    117        iFirstLectures = new HashSet<Lecture>();
    118        for (Lecture lecture: iFirstStudent.getLectures()) {
    119            if (lecture.getConfiguration() == null) return false;
    120            if (lecture.getConfiguration().getOfferingId().equals(iSecondConfig.getOfferingId()) && !lectures.contains(lecture)) {
    121                iFirstLectures.add(lecture);
    122                if (iFirstConfig == null) { iFirstConfig = lecture.getConfiguration(); }
    123                if (lecture.getClassLimitConstraint() != null && lecture.nrWeightedStudents() < sEps + lecture.minClassLimit()) return false;
    124            }
    125        }
    126        if (iFirstLectures.isEmpty()) return false;
    127        return true;
    128    }
    129
    130    /**
    131     * Decrement {@link JenrlConstraint} between the given two classes by the given student
    132     */
    133    protected void decJenrl(Assignment<Lecture, Placement> assignment, Student student, Lecture l1, Lecture l2) {
    134        if (l1.equals(l2)) return;
    135        JenrlConstraint jenrl = l1.jenrlConstraint(l2);
    136        if (jenrl != null) {
    137            jenrl.decJenrl(assignment, student);
    138            /*
    139            if (jenrl.getNrStudents() == 0) {
    140                jenrl.getContext(assignment).unassigned(assignment, null);
    141                Object[] vars = jenrl.variables().toArray();
    142                for (int k = 0; k < vars.length; k++)
    143                    jenrl.removeVariable((Lecture) vars[k]);
    144                iModel.removeConstraint(jenrl);
    145            }
    146            */
    147        }
    148    }
    149
    150    /**
    151     * Increment {@link JenrlConstraint} between the given two classes by the given student
    152     */
    153    protected void incJenrl(Assignment<Lecture, Placement> assignment, Student student, Lecture l1, Lecture l2) {
    154        if (l1.equals(l2)) return;
    155        JenrlConstraint jenrl = l1.jenrlConstraint(l2);
    156        if (jenrl == null) {
    157            jenrl = new JenrlConstraint();
    158            jenrl.addVariable(l1);
    159            jenrl.addVariable(l2);
    160            iModel.addConstraint(jenrl);
    161        }
    162        jenrl.incJenrl(assignment, student);
    163    }
    164
    165    /**
    166     * Compute student conflict weigth between two classes.
    167     */
    168    public double getJenrConflictWeight(List<StudentConflict> criteria, Student student, Placement p1, Placement p2) {
    169        if (p1 == null || p2 == null) return 0.0;
    170        if (criteria == null) {
    171            if (JenrlConstraint.isInConflict(p1, p2, iModel.getDistanceMetric(), iModel.getStudentWorkDayLimit()))
    172                return student.getJenrlWeight(p1.variable(), p2.variable());
    173            return 0.0;
    174        }
    175
    176        double weight = 0.0;
    177        for (StudentConflict sc: criteria)
    178            if (sc.isApplicable(student, p1.variable(), p2.variable()) && sc.inConflict(p1, p2))
    179                weight += sc.getWeight() * student.getJenrlWeight(p1.variable(), p2.variable());
    180        return weight;
    181    }
    182
    183    @Override
    184    public double value(Assignment<Lecture, Placement> assignment) {
    185        return value(iModel == null ? null : iModel.getStudentConflictCriteria(), assignment);
    186    }
    187
    188    private double groupValue(Student student, Student other, Lecture lecture) {
    189        if (student.getGroups().isEmpty()) return 0.0;
    190        double ret = 0.0;
    191        for (StudentGroup g: student.getGroups()) {
    192            ret += groupValue(g, student, other, lecture);
    193        }
    194        return ret;
    195    }
    196
    197    private double groupValue(StudentGroup group, Student student, Student other, Lecture lecture) {
    198        int match = 0;
    199        for (Student s: lecture.students()) {
    200            if (s.equals(student) || s.equals(other)) continue;
    201            if (s.getGroups().contains(group)) match ++;
    202        }
    203        if (match > 0) {
    204            double total = group.countStudents(lecture.getConfiguration().getOfferingId());
    205            return 2.0 * match / (total * (total - 1.0)) / group.countOfferings();
    206        } else
    207            return 0.0;
    208    }
    209
    210    private double groupValue(Student student, Student other, Configuration config, Set<Lecture> lectures) {
    211        double ret = 0.0;
    212        for (Lecture lecture: lectures)
    213            ret += groupValue(student, other, lecture);
    214        return ret / config.countSubparts();
    215    }
    216
    217    @Override
    218    public double value(List<StudentConflict> criteria, Assignment<Lecture, Placement> assignment) {
    219        double delta = 0;
    220        for (Lecture l1: iFirstLectures) {
    221            Placement p1 = assignment.getValue(l1);
    222            if (p1 == null) continue;
    223            for (Lecture l2: iFirstStudent.getLectures()) {
    224                Placement p2 = assignment.getValue(l2);
    225                if (l1.equals(l2) || p2 == null) continue;
    226                if (iFirstLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    227                delta -= getJenrConflictWeight(criteria, iFirstStudent, p1, p2);
    228            }
    229            if (iSecondStudent != null) {
    230                for (Lecture l2: iSecondStudent.getLectures()) {
    231                    if (iSecondLectures.contains(l2)) continue;
    232                    Placement p2 = assignment.getValue(l2);
    233                    if (l1.equals(l2) || p2 == null) continue;
    234                    delta += getJenrConflictWeight(criteria, iSecondStudent, p1, p2);
    235                }
    236                for (Lecture l2: iFirstLectures) {
    237                    Placement p2 = assignment.getValue(l2);
    238                    if (l1.equals(l2) || p2 == null) continue;
    239                    if (l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    240                    delta += getJenrConflictWeight(criteria, iSecondStudent, p1, p2);
    241                }
    242            }
    243        }
    244        for (Lecture l1: iSecondLectures) {
    245            Placement p1 = assignment.getValue(l1);
    246            if (p1 == null) continue;
    247            if (iSecondStudent != null) {
    248                for (Lecture l2: iSecondStudent.getLectures()) {
    249                    Placement p2 = assignment.getValue(l2);
    250                    if (l1.equals(l2) || p2 == null) continue;
    251                    if (iSecondLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    252                    delta -= getJenrConflictWeight(criteria, iSecondStudent, p1, p2);
    253                }
    254            }
    255            for (Lecture l2: iFirstStudent.getLectures()) {
    256                if (iFirstLectures.contains(l2)) continue;
    257                Placement p2 = assignment.getValue(l2);
    258                if (l1.equals(l2) || p2 == null) continue;
    259                delta += getJenrConflictWeight(criteria, iFirstStudent, p1, p2);
    260            }
    261            for (Lecture l2: iSecondLectures) {
    262                Placement p2 = assignment.getValue(l2);
    263                if (l1.equals(l2) || p2 == null) continue;
    264                if (l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    265                delta += getJenrConflictWeight(criteria, iFirstStudent, p1, p2);
    266            }
    267        }
    268        return delta;
    269    }
    270
    271    @Override
    272    public void assign(Assignment<Lecture, Placement> assignment, long iteration) {
    273        for (Lecture l1 : iFirstLectures) {
    274            for (Lecture l2: iFirstStudent.getLectures()) {
    275                if (l1.equals(l2)) continue;
    276                if (iFirstLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    277                decJenrl(assignment, iFirstStudent, l1, l2);
    278            }
    279        }
    280        if (iSecondStudent != null) {
    281            for (Lecture l1 : iSecondLectures) {
    282                for (Lecture l2: iSecondStudent.getLectures()) {
    283                    if (l1.equals(l2)) continue;
    284                    if (iSecondLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    285                    decJenrl(assignment, iSecondStudent, l1, l2);
    286                }
    287            }
    288        }
    289        for (Lecture l1 : iFirstLectures) {
    290            l1.removeStudent(assignment, iFirstStudent);
    291            iFirstStudent.removeLecture(l1);
    292            if (iSecondStudent != null) {
    293                l1.addStudent(assignment, iSecondStudent);
    294                iSecondStudent.addLecture(l1);
    295            }
    296        }
    297        for (Lecture l1 : iSecondLectures) {
    298            if (iSecondStudent != null) {
    299                l1.removeStudent(assignment, iSecondStudent);
    300                iSecondStudent.removeLecture(l1);
    301            }
    302            l1.addStudent(assignment, iFirstStudent);
    303            iFirstStudent.addLecture(l1);
    304        }
    305        if (iSecondStudent != null) {
    306            for (Lecture l1 : iFirstLectures) {
    307                for (Lecture l2: iSecondStudent.getLectures()) {
    308                    if (l1.equals(l2)) continue;
    309                    if (iFirstLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    310                    incJenrl(assignment, iSecondStudent, l1, l2);
    311                }
    312            }
    313        }
    314        for (Lecture l1 : iSecondLectures) {
    315            for (Lecture l2: iFirstStudent.getLectures()) {
    316                if (l1.equals(l2)) continue;
    317                if (iSecondLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    318                incJenrl(assignment, iFirstStudent, l1, l2);
    319            }
    320        }
    321        if (!iFirstConfig.equals(iSecondConfig)) {
    322            iFirstStudent.removeConfiguration(iFirstConfig);
    323            iFirstStudent.addConfiguration(iSecondConfig);
    324            if (iSecondStudent != null) {
    325                iSecondStudent.removeConfiguration(iSecondConfig);
    326                iSecondStudent.addConfiguration(iFirstConfig);
    327            }
    328        }
    329    }
    330
    331    @Override
    332    public boolean isAllowed() {
    333        return iAllowed;
    334    }
    335
    336    @Override
    337    public Map<Lecture, Placement> assignments() {
    338        throw new UnsupportedOperationException();
    339    }
    340
    341    @Override
    342    public double group(List<StudentConflict> criteria, Assignment<Lecture, Placement> assignment) {
    343        double value = groupValue(iFirstStudent, iSecondStudent, iSecondConfig, iSecondLectures) - groupValue(iFirstStudent, iSecondStudent, iFirstConfig, iFirstLectures);
    344        if (iSecondStudent != null)
    345            value += groupValue(iSecondStudent, iFirstStudent, iFirstConfig, iFirstLectures) - groupValue(iSecondStudent, iFirstStudent, iSecondConfig, iSecondLectures);
    346        return value;
    347    }
    348
    349    @Override
    350    public String toString() {
    351        return "StudentSwap{" + iFirstStudent.getId() + " " + iFirstStudent.getGroupNames() + "/" + iFirstLectures + "; " + (iSecondStudent == null ? "NULL" : iSecondStudent.getId() + " " + iSecondStudent.getGroupNames()) + "/" + iSecondLectures + "}";
    352    }
    353}