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}