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}