001package org.cpsolver.studentsct.constraint; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.HashMap; 006import java.util.HashSet; 007import java.util.List; 008import java.util.Map; 009import java.util.Set; 010 011import org.cpsolver.ifs.assignment.Assignment; 012import org.cpsolver.ifs.model.Constraint; 013import org.cpsolver.studentsct.model.Course; 014import org.cpsolver.studentsct.model.CourseRequest; 015import org.cpsolver.studentsct.model.Enrollment; 016import org.cpsolver.studentsct.model.Offering; 017import org.cpsolver.studentsct.model.Request; 018import org.cpsolver.studentsct.model.Section; 019import org.cpsolver.studentsct.model.Student; 020import org.cpsolver.studentsct.model.Subpart; 021 022 023/** 024 * Linked sections are sections (of different courses) that should be attended by the 025 * same students. If there are multiple sections of the same subpart, one or can be 026 * chosen randomly. For instance, if section A1 (of a course A) and section B1 (of a course 027 * B) are linked, a student requesting both courses must attend A1 if and only if he 028 * also attends B1. 029 * 030 * @version StudentSct 1.3 (Student Sectioning)<br> 031 * Copyright (C) 2007 - 2014 Tomas Muller<br> 032 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 033 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 034 * <br> 035 * This library is free software; you can redistribute it and/or modify 036 * it under the terms of the GNU Lesser General Public License as 037 * published by the Free Software Foundation; either version 3 of the 038 * License, or (at your option) any later version. <br> 039 * <br> 040 * This library is distributed in the hope that it will be useful, but 041 * WITHOUT ANY WARRANTY; without even the implied warranty of 042 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 043 * Lesser General Public License for more details. <br> 044 * <br> 045 * You should have received a copy of the GNU Lesser General Public 046 * License along with this library; if not see 047 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 048 */ 049public class LinkedSections { 050 private Map<Offering, Map<Subpart, Set<Section>>> iSections = new HashMap<Offering, Map<Subpart,Set<Section>>>(); 051 private boolean iMustBeUsed; 052 053 /** 054 * Constructor 055 * @param sections sections that are to be linked 056 */ 057 public LinkedSections(Section... sections) { 058 for (Section section: sections) 059 addSection(section); 060 061 } 062 063 /** 064 * Constructor 065 * @param sections sections that are to be linked 066 */ 067 public LinkedSections(Collection<Section> sections) { 068 for (Section section: sections) 069 addSection(section); 070 } 071 072 /** 073 * Add a section to this link 074 * @param section 075 */ 076 private void addSection(Section section) { 077 Map<Subpart, Set<Section>> subparts = iSections.get(section.getSubpart().getConfig().getOffering()); 078 if (subparts == null) { 079 subparts = new HashMap<Subpart, Set<Section>>(); 080 iSections.put(section.getSubpart().getConfig().getOffering(), subparts); 081 } 082 Set<Section> sections = subparts.get(section.getSubpart()); 083 if (sections == null) { 084 sections = new HashSet<Section>(); 085 subparts.put(section.getSubpart(), sections); 086 } 087 sections.add(section); 088 089 } 090 091 /** 092 * Return offerings of this link 093 * @return offerings of this link 094 */ 095 public Set<Offering> getOfferings() { return iSections.keySet(); } 096 097 /** 098 * Return subpart (or subparts) of an offering of this link 099 * @param offering an offering of this link 100 * @return subpart (or subparts) of this offering in this link 101 */ 102 public Set<Subpart> getSubparts(Offering offering) { return iSections.get(offering).keySet(); } 103 104 /** 105 * Return section (or sections) of a subpart of this link 106 * @param subpart subpart of this link 107 * @return section (or sections) of this subpart in this link 108 */ 109 public Set<Section> getSections(Subpart subpart) { return iSections.get(subpart.getConfig().getOffering()).get(subpart); } 110 111 /** 112 * Create linked-section constraints for a given student 113 */ 114 private LinkedSectionsConstraint createConstraint(Student student) { 115 List<Request> requests = new ArrayList<Request>(); 116 int nrOfferings = 0; 117 requests: for (Request request: student.getRequests()) { 118 if (request instanceof CourseRequest) { 119 for (Course course: ((CourseRequest)request).getCourses()) { 120 Map<Subpart, Set<Section>> subpartsThisOffering = iSections.get(course.getOffering()); 121 if (subpartsThisOffering != null) { 122 requests.add(request); 123 nrOfferings++; 124 continue requests; 125 } 126 } 127 } 128 } 129 if (nrOfferings <= 1) return null; 130 LinkedSectionsConstraint constraint = new LinkedSectionsConstraint(student, requests); 131 student.getRequests().get(0).getModel().addConstraint(constraint); 132 return constraint; 133 } 134 135 /** 136 * Create linked-section constraints for this link. A constraint is created for each 137 * student that has two or more offerings of this link. 138 */ 139 public void createConstraints() { 140 Set<Student> students = new HashSet<Student>(); 141 for (Offering offering: iSections.keySet()) 142 for (Course course: offering.getCourses()) 143 for (Request request: course.getRequests()) 144 if (students.add(request.getStudent())) { 145 if (createConstraint(request.getStudent()) != null) 146 request.getStudent().getLinkedSections().add(this); 147 } 148 } 149 150 /** 151 * Compute conflicting enrollments. If the given enrollment contains sections of this link 152 * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment 153 * of this student is in a conflict, if it does not contain the appropriate sections from 154 * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}. 155 * 156 * @param assignment current assignment 157 * @param enrollment given enrollment 158 * @param conflicts found conflicts are given to this interface, see {@link ConflictHandler#onConflict(Enrollment)} 159 */ 160 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, ConflictHandler conflicts) { 161 computeConflicts(enrollment, new CurrentAssignment(assignment), conflicts); 162 } 163 164 /** 165 * Compute conflicting enrollments. If the given enrollment contains sections of this link 166 * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment 167 * of this student is in a conflict, if it does not contain the appropriate sections from 168 * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}. 169 * 170 * @param enrollment given enrollment 171 * @param assignment custom assignment 172 * @param conflicts found conflicts are given to this interface, see {@link ConflictHandler#onConflict(Enrollment)} 173 */ 174 public void computeConflicts(Enrollment enrollment, EnrollmentAssignment assignment, ConflictHandler conflicts) { 175 if (enrollment == null || enrollment.getCourse() == null) return; 176 Map<Subpart, Set<Section>> subparts = iSections.get(enrollment.getCourse().getOffering()); 177 if (subparts == null || subparts.isEmpty()) return; 178 boolean match = false, partial = false; 179 for (Section section: enrollment.getSections()) { 180 Set<Section> sections = subparts.get(section.getSubpart()); 181 if (sections != null) { 182 if (sections.contains(section)) 183 match = true; 184 else 185 partial = true; 186 } 187 } 188 boolean full = match && !partial; 189 if (isMustBeUsed()) { 190 if (!full) { // not full match -> conflict if there is no other linked section constraint with a full match 191 // check if there is some other constraint taking care of this case 192 boolean hasOtherMatch = false; 193 for (LinkedSections other: enrollment.getStudent().getLinkedSections()) { 194 if (other.hasFullMatch(enrollment) && nrSharedOfferings(other) > 1) { hasOtherMatch = true; break; } 195 } 196 // no other match -> problem 197 if (!hasOtherMatch && !conflicts.onConflict(enrollment)) return; 198 } 199 } 200 if (full) { // full match -> check other enrollments 201 for (int i = 0; i < enrollment.getStudent().getRequests().size(); i++) { 202 Request request = enrollment.getStudent().getRequests().get(i); 203 if (request.equals(enrollment.getRequest())) continue; // given enrollment 204 Enrollment otherEnrollment = assignment.getEnrollment(request, i); 205 if (otherEnrollment == null || otherEnrollment.getCourse() == null) continue; // not assigned or not course request 206 Map<Subpart, Set<Section>> otherSubparts = iSections.get(otherEnrollment.getCourse().getOffering()); 207 if (otherSubparts == null || otherSubparts.isEmpty()) continue; // offering is not in the link 208 boolean otherMatch = false, otherPartial = false; 209 for (Section section: otherEnrollment.getSections()) { 210 Set<Section> otherSections = otherSubparts.get(section.getSubpart()); 211 if (otherSections != null) { 212 if (otherSections.contains(section)) 213 otherMatch = true; 214 else 215 otherPartial = true; 216 } 217 } 218 boolean otherFull = otherMatch && !otherPartial; 219 // not full match -> conflict 220 if (!otherFull && !conflicts.onConflict(otherEnrollment)) return; 221 } 222 } else { // no or only partial match -> there should be no match in other offerings too 223 for (int i = 0; i < enrollment.getStudent().getRequests().size(); i++) { 224 Request request = enrollment.getStudent().getRequests().get(i); 225 if (request.equals(enrollment.getRequest())) continue; // given enrollment 226 Enrollment otherEnrollment = assignment.getEnrollment(request, i); 227 if (otherEnrollment == null || otherEnrollment.getCourse() == null) continue; // not assigned or not course request 228 Map<Subpart, Set<Section>> otherSubparts = iSections.get(otherEnrollment.getCourse().getOffering()); 229 if (otherSubparts == null || otherSubparts.isEmpty()) continue; // offering is not in the link 230 boolean otherMatch = false, otherPartial = false; 231 for (Section section: otherEnrollment.getSections()) { 232 Set<Section> otherSections = otherSubparts.get(section.getSubpart()); 233 if (otherSections != null) { 234 if (otherSections.contains(section)) 235 otherMatch = true; 236 else 237 otherPartial = true; 238 } 239 } 240 boolean otherFull = otherMatch && !otherPartial; 241 // full match -> conflict 242 if (otherFull && !conflicts.onConflict(otherEnrollment)) return; 243 } 244 } 245 } 246 247 /** 248 * Check if the given enrollment fully matches this constraint 249 * @param enrollment an enrollment 250 * @return true, if there is a full match 251 */ 252 protected boolean hasFullMatch(Enrollment enrollment) { 253 if (enrollment == null || enrollment.getCourse() == null) return false; // not assigned or not course request 254 Map<Subpart, Set<Section>> subparts = iSections.get(enrollment.getCourse().getOffering()); 255 if (subparts == null || subparts.isEmpty()) return false; // offering is not in the link 256 boolean match = false, partial = false; 257 for (Section section: enrollment.getSections()) { 258 Set<Section> sections = subparts.get(section.getSubpart()); 259 if (sections != null) { 260 if (sections.contains(section)) 261 match = true; 262 else 263 partial = true; 264 } 265 } 266 return match && !partial; 267 } 268 269 /** 270 * Number of offerings that are shared with some other linked sections constraint 271 * @param other the other constraint 272 * @return number of offerings in common 273 */ 274 protected int nrSharedOfferings(LinkedSections other) { 275 int shared = 0; 276 for (Offering offering: other.getOfferings()) 277 if (iSections.containsKey(offering)) shared ++; 278 return shared; 279 } 280 281 /** 282 * Check for conflicts. If the given enrollment contains sections of this link 283 * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment 284 * of this student is in a conflict, if it does not contain the appropriate sections from 285 * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}. 286 * 287 * @param assignment current assignment 288 * @param enrollment given enrollment 289 * @return conflicting enrollment 290 */ 291 public Enrollment inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 292 return inConflict(enrollment, new CurrentAssignment(assignment)); 293 } 294 295 /** 296 * Check for conflicts. If the given enrollment contains sections of this link 297 * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment 298 * of this student is in a conflict, if it does not contain the appropriate sections from 299 * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}. 300 * 301 * @param enrollment given enrollment 302 * @param assignment custom assignment 303 * @return conflicting enrollment 304 */ 305 public Enrollment inConflict(Enrollment enrollment, EnrollmentAssignment assignment) { 306 final Toggle<Enrollment> ret = new Toggle<Enrollment>(null); 307 computeConflicts(enrollment, assignment, new ConflictHandler() { 308 @Override 309 public boolean onConflict(Enrollment conflict) { 310 ret.set(conflict); 311 return false; 312 } 313 }); 314 return ret.get(); 315 } 316 317 /** 318 * Interface to be able to provide a custom assignment to {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)} 319 */ 320 public static interface EnrollmentAssignment { 321 /** 322 * Return enrollment of the given request 323 * @param request given request 324 * @param index index of the request 325 * @return an enrollment 326 */ 327 public Enrollment getEnrollment(Request request, int index); 328 } 329 330 /** 331 * Helper interface to process conflicts in {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)} 332 */ 333 public static interface ConflictHandler { 334 /** 335 * Called when there is a conflict, if false the computation of other conflicts is stopped. 336 * @param conflict a conflicting enrollment 337 * @return stop the computation when false 338 */ 339 public boolean onConflict(Enrollment conflict); 340 } 341 342 /** 343 * Current assignment -- default for {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)} 344 */ 345 public static class CurrentAssignment implements EnrollmentAssignment { 346 protected Assignment<Request, Enrollment> iAssignment; 347 348 public CurrentAssignment(Assignment<Request, Enrollment> assignment) { 349 iAssignment = assignment; 350 } 351 352 /** 353 * Return {@link Request#getAssignment(Assignment)} 354 */ 355 @Override 356 public Enrollment getEnrollment(Request request, int index) { 357 return iAssignment.getValue(request); 358 } 359 } 360 361 /** 362 * Return whether this constraint must be used 363 * @return if true, a pair of linked sections must be used when a student requests both courses 364 */ 365 public boolean isMustBeUsed() { return iMustBeUsed; } 366 367 /** 368 * Set whether this constraint must be used 369 * @param mustBeUsed if true, a pair of linked sections must be used when a student requests both courses 370 */ 371 public void setMustBeUsed(boolean mustBeUsed) { iMustBeUsed = mustBeUsed; } 372 373 @Override 374 public String toString() { 375 return "LinkedSections" + iSections.keySet(); 376 } 377 378 private static class Toggle<T> { 379 private T iValue; 380 Toggle(T value) { set(value); } 381 void set(T value) { iValue = value; } 382 T get() { return iValue; } 383 } 384 385 /** 386 * Linked sections constraint -- to be created for each student that requests two 387 * or more offerings of this link 388 */ 389 public class LinkedSectionsConstraint extends Constraint<Request, Enrollment> { 390 private Student iStudent; 391 392 /** 393 * Constructor 394 * @param student a student 395 * @param requests sub-set of student requests {@link Student#getRequests()} that contains offerings of this link 396 */ 397 protected LinkedSectionsConstraint(Student student, Collection<Request> requests) { 398 iStudent = student; 399 for (Request request: requests) 400 addVariable(request); 401 } 402 403 /** 404 * Return student 405 * @return student 406 */ 407 public Student getStudent() { return iStudent; } 408 409 /** 410 * Return linked section 411 * @return linked sections constraint 412 */ 413 public LinkedSections getLinkedSections() { return LinkedSections.this; } 414 415 /** 416 * Compute conflicts using {@link LinkedSections#computeConflicts(Assignment, Enrollment, ConflictHandler)} 417 */ 418 @Override 419 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment value, final Set<Enrollment> conflicts) { 420 getLinkedSections().computeConflicts(assignment, value, new ConflictHandler() { 421 @Override 422 public boolean onConflict(Enrollment conflict) { 423 conflicts.add(conflict); 424 return true; 425 } 426 }); 427 } 428 429 /** 430 * Check consistency using {@link LinkedSections#inConflict(Enrollment, EnrollmentAssignment)} 431 */ 432 @Override 433 public boolean isConsistent(Enrollment enrollment, final Enrollment other) { 434 return getLinkedSections().inConflict(enrollment, new LinkedSections.EnrollmentAssignment() { 435 @Override 436 public Enrollment getEnrollment(Request request, int indext) { 437 return (request.equals(other.getRequest()) ? other : null); 438 } 439 }) == null; 440 } 441 442 /** 443 * Check for conflict using {@link LinkedSections#inConflict(Assignment, Enrollment)} 444 */ 445 @Override 446 public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment value) { 447 return getLinkedSections().inConflict(assignment, value) != null; 448 } 449 450 @Override 451 public String toString() { 452 return getLinkedSections().toString(); 453 } 454 } 455}