    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 * @version CourseTT 1.3 (University Course Timetabling)<br>
    024 *          Copyright (C) 2017 Tomáš Müller<br>
    025 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    026 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    027 * <br>
    028 *          This library is free software; you can redistribute it and/or modify
    029 *          it under the terms of the GNU Lesser General Public License as
    030 *          published by the Free Software Foundation; either version 3 of the
    031 *          License, or (at your option) any later version. <br>
    032 * <br>
    033 *          This library is distributed in the hope that it will be useful, but
    034 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    035 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    036 *          Lesser General Public License for more details. <br>
    037 * <br>
    038 *          You should have received a copy of the GNU Lesser General Public
    039 *          License along with this library; if not see
    040 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    041 */
    042public class StudentSwap implements StudentMove {
    043    private TimetableModel iModel;
    044    private Student iFirstStudent, iSecondStudent;
    045    private Set<Lecture> iFirstLectures, iSecondLectures;
    046    private Configuration iFirstConfig, iSecondConfig;
    047    private boolean iAllowed = true;
    048
    049    /**
    050     * Create a swap of two students of an offering.
    051     */
    052    public StudentSwap(TimetableModel model, Assignment<Lecture, Placement> assignment, Student firstStudent, Student secondStudent, Long offeringId) {
    053        iModel = model;
    054        iFirstStudent = firstStudent; iSecondStudent = secondStudent;
    055        iAllowed = initSwap(assignment, offeringId);
    056    }
    057
    058    /**
    059     * Move a student into some other lectures of the offering.
    060     */
    061    public StudentSwap(TimetableModel model, Assignment<Lecture, Placement> assignment, Student student, Collection<Lecture> lectures) {
    062        iModel = model;
    063        iFirstStudent = student; iSecondStudent = null;
    064        iAllowed = initMove(assignment, lectures);
    065    }
    066
    067    /**
    068     * Compute student swap and its validity
    069     */
    070    protected boolean initSwap(Assignment<Lecture, Placement> assignment, Long offeringId) {
    071        double w1 = iFirstStudent.getOfferingWeight(offeringId), w2 = iSecondStudent.getOfferingWeight(offeringId);
    072        iFirstLectures = new HashSet<Lecture>();
    073        for (Lecture lecture: iFirstStudent.getLectures()) {
    074            if (lecture.getConfiguration() == null) return false;
    075            if (lecture.getConfiguration().getOfferingId().equals(offeringId) && !iSecondStudent.getLectures().contains(lecture)) {
    076                iFirstLectures.add(lecture);
    077                if (iFirstConfig == null)
    078                    iFirstConfig = lecture.getConfiguration();
    079                if (!iSecondStudent.canEnroll(lecture) || !iFirstStudent.canUnenroll(lecture)) return false;
    080                if (w2 - w1 > 0.0 && lecture.nrWeightedStudents() - w1 + w2 > sEps + lecture.classLimit(assignment)) return false;
    081            }
    082        }
    083        iSecondLectures = new HashSet<Lecture>();
    084        for (Lecture lecture: iSecondStudent.getLectures()) {
    085            if (lecture.getConfiguration() == null) return false;
    086            if (lecture.getConfiguration().getOfferingId().equals(offeringId) && !iFirstStudent.getLectures().contains(lecture)) {
    087                iSecondLectures.add(lecture);
    088                if (iSecondConfig == null)
    089                    iSecondConfig = lecture.getConfiguration();
    090                if (!iFirstStudent.canEnroll(lecture) || !iSecondStudent.canUnenroll(lecture)) return false;
    091                if (w1 - w2 > 0.0 && lecture.nrWeightedStudents() - w2 + w1 > sEps + lecture.classLimit(assignment)) return false;
    092            }
    093        }
    094        return !iFirstLectures.isEmpty() && !iSecondLectures.isEmpty();
    095    }
    096
    097    /**
    098     * Compute student move and its validity
    099     */
    100    private boolean initMove(Assignment<Lecture, Placement> assignment, Collection<Lecture> lectures) {
    101        double w = 0.0;
    102        iFirstLectures = new HashSet<Lecture>();
    103        iSecondLectures = new HashSet<Lecture>();
    104        for (Lecture lecture: lectures) {
    105            if (lecture.getConfiguration() == null) return false;
    106            if (!iFirstStudent.getLectures().contains(lecture)) {
    107                if (iSecondConfig == null) {
    108                    iSecondConfig = lecture.getConfiguration();
    109                    w = iFirstStudent.getOfferingWeight(iSecondConfig);
    110                }
    111                iSecondLectures.add(lecture);
    112                if (lecture.nrWeightedStudents() + w > sEps + lecture.classLimit(assignment)) return false;
    113            }
    114        }
    115        if (iSecondLectures.isEmpty()) return false;
    116        iFirstLectures = new HashSet<Lecture>();
    117        for (Lecture lecture: iFirstStudent.getLectures()) {
    118            if (lecture.getConfiguration() == null) return false;
    119            if (lecture.getConfiguration().getOfferingId().equals(iSecondConfig.getOfferingId()) && !lectures.contains(lecture)) {
    120                iFirstLectures.add(lecture);
    121                if (iFirstConfig == null) { iFirstConfig = lecture.getConfiguration(); }
    122                if (lecture.getClassLimitConstraint() != null && lecture.nrWeightedStudents() < sEps + lecture.minClassLimit()) return false;
    123            }
    124        }
    125        if (iFirstLectures.isEmpty()) return false;
    126        return true;
    127    }
    128
    129    /**
    130     * Decrement {@link JenrlConstraint} between the given two classes by the given student
    131     */
    132    protected void decJenrl(Assignment<Lecture, Placement> assignment, Student student, Lecture l1, Lecture l2) {
    133        if (l1.equals(l2)) return;
    134        JenrlConstraint jenrl = l1.jenrlConstraint(l2);
    135        if (jenrl != null) {
    136            jenrl.decJenrl(assignment, student);
    137            /*
    138            if (jenrl.getNrStudents() == 0) {
    139                jenrl.getContext(assignment).unassigned(assignment, null);
    140                Object[] vars = jenrl.variables().toArray();
    141                for (int k = 0; k < vars.length; k++)
    142                    jenrl.removeVariable((Lecture) vars[k]);
    143                iModel.removeConstraint(jenrl);
    144            }
    145            */
    146        }
    147    }
    148
    149    /**
    150     * Increment {@link JenrlConstraint} between the given two classes by the given student
    151     */
    152    protected void incJenrl(Assignment<Lecture, Placement> assignment, Student student, Lecture l1, Lecture l2) {
    153        if (l1.equals(l2)) return;
    154        JenrlConstraint jenrl = l1.jenrlConstraint(l2);
    155        if (jenrl == null) {
    156            jenrl = new JenrlConstraint();
    157            jenrl.addVariable(l1);
    158            jenrl.addVariable(l2);
    159            iModel.addConstraint(jenrl);
    160        }
    161        jenrl.incJenrl(assignment, student);
    162    }
    163
    164    /**
    165     * Compute student conflict weigth between two classes.
    166     */
    167    public double getJenrConflictWeight(List<StudentConflict> criteria, Student student, Placement p1, Placement p2) {
    168        if (p1 == null || p2 == null) return 0.0;
    169        if (criteria == null) {
    170            if (JenrlConstraint.isInConflict(p1, p2, iModel.getDistanceMetric(), iModel.getStudentWorkDayLimit()))
    171                return student.getJenrlWeight(p1.variable(), p2.variable());
    172            return 0.0;
    173        }
    174
    175        double weight = 0.0;
    176        for (StudentConflict sc: criteria)
    177            if (sc.isApplicable(student, p1.variable(), p2.variable()) && sc.inConflict(p1, p2))
    178                weight += sc.getWeight() * student.getJenrlWeight(p1.variable(), p2.variable());
    179        return weight;
    180    }
    181
    182    @Override
    183    public double value(Assignment<Lecture, Placement> assignment) {
    184        return value(null, assignment);
    185    }
    186
    187    private double groupValue(Student student, Student other, Lecture lecture) {
    188        if (student.getGroups().isEmpty()) return 0.0;
    189        double ret = 0.0;
    190        for (StudentGroup g: student.getGroups()) {
    191            ret += groupValue(g, student, other, lecture);
    192        }
    193        return ret;
    194    }
    195
    196    private double groupValue(StudentGroup group, Student student, Student other, Lecture lecture) {
    197        int match = 0;
    198        for (Student s: lecture.students()) {
    199            if (s.equals(student) || s.equals(other)) continue;
    200            if (s.getGroups().contains(group)) match ++;
    201        }
    202        if (match > 0) {
    203            double total = group.countStudents(lecture.getConfiguration().getOfferingId());
    204            return 2.0 * match / (total * (total - 1.0)) / group.countOfferings();
    205        } else
    206            return 0.0;
    207    }
    208
    209    private double groupValue(Student student, Student other, Configuration config, Set<Lecture> lectures) {
    210        double ret = 0.0;
    211        for (Lecture lecture: lectures)
    212            ret += groupValue(student, other, lecture);
    213        return ret / config.countSubparts();
    214    }
    215
    216    @Override
    217    public double value(List<StudentConflict> criteria, Assignment<Lecture, Placement> assignment) {
    218        double delta = 0;
    219        for (Lecture l1: iFirstLectures) {
    220            Placement p1 = assignment.getValue(l1);
    221            if (p1 == null) continue;
    222            for (Lecture l2: iFirstStudent.getLectures()) {
    223                Placement p2 = assignment.getValue(l2);
    224                if (l1.equals(l2) || p2 == null) continue;
    225                if (iFirstLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    226                delta -= getJenrConflictWeight(criteria, iFirstStudent, p1, p2);
    227            }
    228            if (iSecondStudent != null) {
    229                for (Lecture l2: iSecondStudent.getLectures()) {
    230                    if (iSecondLectures.contains(l2)) continue;
    231                    Placement p2 = assignment.getValue(l2);
    232                    if (l1.equals(l2) || p2 == null) continue;
    233                    delta += getJenrConflictWeight(criteria, iSecondStudent, p1, p2);
    234                }
    235                for (Lecture l2: iFirstLectures) {
    236                    Placement p2 = assignment.getValue(l2);
    237                    if (l1.equals(l2) || p2 == null) continue;
    238                    if (l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    239                    delta += getJenrConflictWeight(criteria, iSecondStudent, p1, p2);
    240                }
    241            }
    242        }
    243        for (Lecture l1: iSecondLectures) {
    244            Placement p1 = assignment.getValue(l1);
    245            if (p1 == null) continue;
    246            if (iSecondStudent != null) {
    247                for (Lecture l2: iSecondStudent.getLectures()) {
    248                    Placement p2 = assignment.getValue(l2);
    249                    if (l1.equals(l2) || p2 == null) continue;
    250                    if (iSecondLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    251                    delta -= getJenrConflictWeight(criteria, iSecondStudent, p1, p2);
    252                }
    253            }
    254            for (Lecture l2: iFirstStudent.getLectures()) {
    255                if (iFirstLectures.contains(l2)) continue;
    256                Placement p2 = assignment.getValue(l2);
    257                if (l1.equals(l2) || p2 == null) continue;
    258                delta += getJenrConflictWeight(criteria, iFirstStudent, p1, p2);
    259            }
    260            for (Lecture l2: iSecondLectures) {
    261                Placement p2 = assignment.getValue(l2);
    262                if (l1.equals(l2) || p2 == null) continue;
    263                if (l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    264                delta += getJenrConflictWeight(criteria, iFirstStudent, p1, p2);
    265            }
    266        }
    267        return delta;
    268    }
    269
    270    @Override
    271    public void assign(Assignment<Lecture, Placement> assignment, long iteration) {
    272        for (Lecture l1 : iFirstLectures) {
    273            for (Lecture l2: iFirstStudent.getLectures()) {
    274                if (l1.equals(l2)) continue;
    275                if (iFirstLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    276                decJenrl(assignment, iFirstStudent, l1, l2);
    277            }
    278        }
    279        if (iSecondStudent != null) {
    280            for (Lecture l1 : iSecondLectures) {
    281                for (Lecture l2: iSecondStudent.getLectures()) {
    282                    if (l1.equals(l2)) continue;
    283                    if (iSecondLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    284                    decJenrl(assignment, iSecondStudent, l1, l2);
    285                }
    286            }
    287        }
    288        for (Lecture l1 : iFirstLectures) {
    289            l1.removeStudent(assignment, iFirstStudent);
    290            iFirstStudent.removeLecture(l1);
    291            if (iSecondStudent != null) {
    292                l1.addStudent(assignment, iSecondStudent);
    293                iSecondStudent.addLecture(l1);
    294            }
    295        }
    296        for (Lecture l1 : iSecondLectures) {
    297            if (iSecondStudent != null) {
    298                l1.removeStudent(assignment, iSecondStudent);
    299                iSecondStudent.removeLecture(l1);
    300            }
    301            l1.addStudent(assignment, iFirstStudent);
    302            iFirstStudent.addLecture(l1);
    303        }
    304        if (iSecondStudent != null) {
    305            for (Lecture l1 : iFirstLectures) {
    306                for (Lecture l2: iSecondStudent.getLectures()) {
    307                    if (l1.equals(l2)) continue;
    308                    if (iFirstLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    309                    incJenrl(assignment, iSecondStudent, l1, l2);
    310                }
    311            }
    312        }
    313        for (Lecture l1 : iSecondLectures) {
    314            for (Lecture l2: iFirstStudent.getLectures()) {
    315                if (l1.equals(l2)) continue;
    316                if (iSecondLectures.contains(l2) && l1.getClassId().compareTo(l2.getClassId()) >= 0) continue;
    317                incJenrl(assignment, iFirstStudent, l1, l2);
    318            }
    319        }
    320        if (!iFirstConfig.equals(iSecondConfig)) {
    321            iFirstStudent.removeConfiguration(iFirstConfig);
    322            iFirstStudent.addConfiguration(iSecondConfig);
    323            if (iSecondStudent != null) {
    324                iSecondStudent.removeConfiguration(iSecondConfig);
    325                iSecondStudent.addConfiguration(iFirstConfig);
    326            }
    327        }
    328    }
    329
    330    @Override
    331    public boolean isAllowed() {
    332        return iAllowed;
    333    }
    334
    335    @Override
    336    public Map<Lecture, Placement> assignments() {
    337        throw new UnsupportedOperationException();
    338    }
    339
    340    @Override
    341    public double group(List<StudentConflict> criteria, Assignment<Lecture, Placement> assignment) {
    342        double value = groupValue(iFirstStudent, iSecondStudent, iSecondConfig, iSecondLectures) - groupValue(iFirstStudent, iSecondStudent, iFirstConfig, iFirstLectures);
    343        if (iSecondStudent != null)
    344            value += groupValue(iSecondStudent, iFirstStudent, iFirstConfig, iFirstLectures) - groupValue(iSecondStudent, iFirstStudent, iSecondConfig, iSecondLectures);
    345        return value;
    346    }
    347
    348    @Override
    349    public String toString() {
    350        return "StudentSwap{" + iFirstStudent.getId() + " " + iFirstStudent.getGroupNames() + "/" + iFirstLectures + "; " + (iSecondStudent == null ? "NULL" : iSecondStudent.getId() + " " + iSecondStudent.getGroupNames()) + "/" + iSecondLectures + "}";
    351    }
    352}