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 List<Section> match = new ArrayList<Section>(); 179 for (Section section: enrollment.getSections()) { 180 Set<Section> sections = subparts.get(section.getSubpart()); 181 if (sections != null && sections.contains(section)) 182 match.add(section); 183 } 184 if (isMustBeUsed()) { 185 if (match.size() < subparts.size()) { // partial or no match -> conflict if there is no other linked section constraint with a full match 186 // check if there is some other constraint taking care of this case 187 boolean hasOtherMatch = false; 188 for (LinkedSections other: enrollment.getStudent().getLinkedSections()) { 189 if (other.hasFullMatch(enrollment) && nrSharedOfferings(other) > 1) { hasOtherMatch = true; break; } 190 } 191 // no other match -> problem 192 if (!hasOtherMatch && !conflicts.onConflict(enrollment)) return; 193 } 194 } 195 if (match.size() == subparts.size()) { // full match -> check other enrollments 196 for (int i = 0; i < enrollment.getStudent().getRequests().size(); i++) { 197 Request request = enrollment.getStudent().getRequests().get(i); 198 if (request.equals(enrollment.getRequest())) continue; // given enrollment 199 Enrollment otherEnrollment = assignment.getEnrollment(request, i); 200 if (otherEnrollment == null || otherEnrollment.getCourse() == null) continue; // not assigned or not course request 201 Map<Subpart, Set<Section>> otherSubparts = iSections.get(otherEnrollment.getCourse().getOffering()); 202 if (otherSubparts == null || otherSubparts.isEmpty()) continue; // offering is not in the link 203 List<Section> otherMatch = new ArrayList<Section>(); 204 for (Section section: otherEnrollment.getSections()) { 205 Set<Section> otherSections = otherSubparts.get(section.getSubpart()); 206 if (otherSections != null && otherSections.contains(section)) 207 otherMatch.add(section); 208 } 209 // no or partial patch -> conflict 210 if (otherMatch.size() != otherSubparts.size() && !conflicts.onConflict(otherEnrollment)) return; 211 } 212 } else { // no or only partial match -> there should be no match in other offerings too 213 for (int i = 0; i < enrollment.getStudent().getRequests().size(); i++) { 214 Request request = enrollment.getStudent().getRequests().get(i); 215 if (request.equals(enrollment.getRequest())) continue; // given enrollment 216 Enrollment otherEnrollment = assignment.getEnrollment(request, i); 217 if (otherEnrollment == null || otherEnrollment.getCourse() == null) continue; // not assigned or not course request 218 Map<Subpart, Set<Section>> otherSubparts = iSections.get(otherEnrollment.getCourse().getOffering()); 219 if (otherSubparts == null || otherSubparts.isEmpty()) continue; // offering is not in the link 220 List<Section> otherMatch = new ArrayList<Section>(); 221 for (Section section: otherEnrollment.getSections()) { 222 Set<Section> otherSections = otherSubparts.get(section.getSubpart()); 223 if (otherSections != null && otherSections.contains(section)) 224 otherMatch.add(section); 225 } 226 // full patch -> conflict 227 if (otherMatch.size() == otherSubparts.size() && !conflicts.onConflict(otherEnrollment)) return; 228 } 229 } 230 } 231 232 /** 233 * Check if the given enrollment fully matches this constraint 234 * @param enrollment an enrollment 235 * @return true, if there is a full match 236 */ 237 protected boolean hasFullMatch(Enrollment enrollment) { 238 if (enrollment == null || enrollment.getCourse() == null) return false; 239 Map<Subpart, Set<Section>> subparts = iSections.get(enrollment.getCourse().getOffering()); 240 if (subparts == null || subparts.isEmpty()) return false; 241 int match = 0; 242 for (Section section: enrollment.getSections()) { 243 Set<Section> sections = subparts.get(section.getSubpart()); 244 if (sections != null && sections.contains(section)) 245 match ++; 246 } 247 return match == subparts.size(); 248 } 249 250 /** 251 * Number of offerings that are shared with some other linked sections constraint 252 * @param other the other constraint 253 * @return number of offerings in common 254 */ 255 protected int nrSharedOfferings(LinkedSections other) { 256 int shared = 0; 257 for (Offering offering: other.getOfferings()) 258 if (iSections.containsKey(offering)) shared ++; 259 return shared; 260 } 261 262 /** 263 * Check for conflicts. If the given enrollment contains sections of this link 264 * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment 265 * of this student is in a conflict, if it does not contain the appropriate sections from 266 * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}. 267 * 268 * @param assignment current assignment 269 * @param enrollment given enrollment 270 * @return conflicting enrollment 271 */ 272 public Enrollment inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 273 return inConflict(enrollment, new CurrentAssignment(assignment)); 274 } 275 276 /** 277 * Check for conflicts. If the given enrollment contains sections of this link 278 * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment 279 * of this student is in a conflict, if it does not contain the appropriate sections from 280 * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}. 281 * 282 * @param enrollment given enrollment 283 * @param assignment custom assignment 284 * @return conflicting enrollment 285 */ 286 public Enrollment inConflict(Enrollment enrollment, EnrollmentAssignment assignment) { 287 final Toggle<Enrollment> ret = new Toggle<Enrollment>(null); 288 computeConflicts(enrollment, assignment, new ConflictHandler() { 289 @Override 290 public boolean onConflict(Enrollment conflict) { 291 ret.set(conflict); 292 return false; 293 } 294 }); 295 return ret.get(); 296 } 297 298 /** 299 * Interface to be able to provide a custom assignment to {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)} 300 */ 301 public static interface EnrollmentAssignment { 302 /** 303 * Return enrollment of the given request 304 * @param request given request 305 * @param index index of the request 306 * @return an enrollment 307 */ 308 public Enrollment getEnrollment(Request request, int index); 309 } 310 311 /** 312 * Helper interface to process conflicts in {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)} 313 */ 314 public static interface ConflictHandler { 315 /** 316 * Called when there is a conflict, if false the computation of other conflicts is stopped. 317 * @param conflict a conflicting enrollment 318 * @return stop the computation when false 319 */ 320 public boolean onConflict(Enrollment conflict); 321 } 322 323 /** 324 * Current assignment -- default for {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)} 325 */ 326 public static class CurrentAssignment implements EnrollmentAssignment { 327 protected Assignment<Request, Enrollment> iAssignment; 328 329 public CurrentAssignment(Assignment<Request, Enrollment> assignment) { 330 iAssignment = assignment; 331 } 332 333 /** 334 * Return {@link Request#getAssignment(Assignment)} 335 */ 336 @Override 337 public Enrollment getEnrollment(Request request, int index) { 338 return iAssignment.getValue(request); 339 } 340 } 341 342 /** 343 * Return whether this constraint must be used 344 * @return if true, a pair of linked sections must be used when a student requests both courses 345 */ 346 public boolean isMustBeUsed() { return iMustBeUsed; } 347 348 /** 349 * Set whether this constraint must be used 350 * @param mustBeUsed if true, a pair of linked sections must be used when a student requests both courses 351 */ 352 public void setMustBeUsed(boolean mustBeUsed) { iMustBeUsed = mustBeUsed; } 353 354 @Override 355 public String toString() { 356 return "LinkedSections" + iSections.keySet(); 357 } 358 359 private static class Toggle<T> { 360 private T iValue; 361 Toggle(T value) { set(value); } 362 void set(T value) { iValue = value; } 363 T get() { return iValue; } 364 } 365 366 /** 367 * Linked sections constraint -- to be created for each student that requests two 368 * or more offerings of this link 369 */ 370 public class LinkedSectionsConstraint extends Constraint<Request, Enrollment> { 371 private Student iStudent; 372 373 /** 374 * Constructor 375 * @param student a student 376 * @param requests sub-set of student requests {@link Student#getRequests()} that contains offerings of this link 377 */ 378 protected LinkedSectionsConstraint(Student student, Collection<Request> requests) { 379 iStudent = student; 380 for (Request request: requests) 381 addVariable(request); 382 } 383 384 /** 385 * Return student 386 * @return student 387 */ 388 public Student getStudent() { return iStudent; } 389 390 /** 391 * Return linked section 392 * @return linked sections constraint 393 */ 394 public LinkedSections getLinkedSections() { return LinkedSections.this; } 395 396 /** 397 * Compute conflicts using {@link LinkedSections#computeConflicts(Assignment, Enrollment, ConflictHandler)} 398 */ 399 @Override 400 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment value, final Set<Enrollment> conflicts) { 401 getLinkedSections().computeConflicts(assignment, value, new ConflictHandler() { 402 @Override 403 public boolean onConflict(Enrollment conflict) { 404 conflicts.add(conflict); 405 return true; 406 } 407 }); 408 } 409 410 /** 411 * Check consistency using {@link LinkedSections#inConflict(Enrollment, EnrollmentAssignment)} 412 */ 413 @Override 414 public boolean isConsistent(Enrollment enrollment, final Enrollment other) { 415 return getLinkedSections().inConflict(enrollment, new LinkedSections.EnrollmentAssignment() { 416 @Override 417 public Enrollment getEnrollment(Request request, int indext) { 418 return (request.equals(other.getRequest()) ? other : null); 419 } 420 }) == null; 421 } 422 423 /** 424 * Check for conflict using {@link LinkedSections#inConflict(Assignment, Enrollment)} 425 */ 426 @Override 427 public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment value) { 428 return getLinkedSections().inConflict(assignment, value) != null; 429 } 430 431 @Override 432 public String toString() { 433 return getLinkedSections().toString(); 434 } 435 } 436}