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}