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