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 052 /** 053 * Constructor 054 * @param sections sections that are to be linked 055 */ 056 public LinkedSections(Section... sections) { 057 for (Section section: sections) 058 addSection(section); 059 060 } 061 062 /** 063 * Constructor 064 * @param sections sections that are to be linked 065 */ 066 public LinkedSections(Collection<Section> sections) { 067 for (Section section: sections) 068 addSection(section); 069 } 070 071 /** 072 * Add a section to this link 073 * @param section 074 */ 075 private void addSection(Section section) { 076 Map<Subpart, Set<Section>> subparts = iSections.get(section.getSubpart().getConfig().getOffering()); 077 if (subparts == null) { 078 subparts = new HashMap<Subpart, Set<Section>>(); 079 iSections.put(section.getSubpart().getConfig().getOffering(), subparts); 080 } 081 Set<Section> sections = subparts.get(section.getSubpart()); 082 if (sections == null) { 083 sections = new HashSet<Section>(); 084 subparts.put(section.getSubpart(), sections); 085 } 086 sections.add(section); 087 088 } 089 090 /** 091 * Return offerings of this link 092 * @return offerings of this link 093 */ 094 public Set<Offering> getOfferings() { return iSections.keySet(); } 095 096 /** 097 * Return subpart (or subparts) of an offering of this link 098 * @param offering an offering of this link 099 * @return subpart (or subparts) of this offering in this link 100 */ 101 public Set<Subpart> getSubparts(Offering offering) { return iSections.get(offering).keySet(); } 102 103 /** 104 * Return section (or sections) of a subpart of this link 105 * @param subpart subpart of this link 106 * @return section (or sections) of this subpart in this link 107 */ 108 public Set<Section> getSections(Subpart subpart) { return iSections.get(subpart.getConfig().getOffering()).get(subpart); } 109 110 /** 111 * Create linked-section constraints for a given student 112 */ 113 private LinkedSectionsConstraint createConstraint(Student student) { 114 List<Request> requests = new ArrayList<Request>(); 115 int nrOfferings = 0; 116 requests: for (Request request: student.getRequests()) { 117 if (request instanceof CourseRequest) { 118 for (Course course: ((CourseRequest)request).getCourses()) { 119 Map<Subpart, Set<Section>> subpartsThisOffering = iSections.get(course.getOffering()); 120 if (subpartsThisOffering != null) { 121 requests.add(request); 122 nrOfferings++; 123 continue requests; 124 } 125 } 126 } 127 } 128 if (nrOfferings <= 1) return null; 129 LinkedSectionsConstraint constraint = new LinkedSectionsConstraint(student, requests); 130 student.getRequests().get(0).getModel().addConstraint(constraint); 131 return constraint; 132 } 133 134 /** 135 * Create linked-section constraints for this link. A constraint is created for each 136 * student that has two or more offerings of this link. 137 */ 138 public void createConstraints() { 139 Set<Student> students = new HashSet<Student>(); 140 for (Offering offering: iSections.keySet()) 141 for (Course course: offering.getCourses()) 142 for (Request request: course.getRequests()) 143 if (students.add(request.getStudent())) { 144 if (createConstraint(request.getStudent()) != null) 145 request.getStudent().getLinkedSections().add(this); 146 } 147 } 148 149 /** 150 * Compute conflicting enrollments. If the given enrollment contains sections of this link 151 * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment 152 * of this student is in a conflict, if it does not contain the appropriate sections from 153 * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}. 154 * 155 * @param assignment current assignment 156 * @param enrollment given enrollment 157 * @param conflicts found conflicts are given to this interface, see {@link ConflictHandler#onConflict(Enrollment)} 158 */ 159 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, ConflictHandler conflicts) { 160 computeConflicts(enrollment, new CurrentAssignment(assignment), conflicts); 161 } 162 163 /** 164 * Compute conflicting enrollments. If the given enrollment contains sections of this link 165 * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment 166 * of this student is in a conflict, if it does not contain the appropriate sections from 167 * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}. 168 * 169 * @param enrollment given enrollment 170 * @param assignment custom assignment 171 * @param conflicts found conflicts are given to this interface, see {@link ConflictHandler#onConflict(Enrollment)} 172 */ 173 public void computeConflicts(Enrollment enrollment, EnrollmentAssignment assignment, ConflictHandler conflicts) { 174 if (enrollment == null || enrollment.getCourse() == null) return; 175 Map<Subpart, Set<Section>> subparts = iSections.get(enrollment.getCourse().getOffering()); 176 if (subparts == null || subparts.isEmpty()) return; 177 List<Section> match = new ArrayList<Section>(); 178 for (Section section: enrollment.getSections()) { 179 Set<Section> sections = subparts.get(section.getSubpart()); 180 if (sections != null && sections.contains(section)) 181 match.add(section); 182 } 183 if (match.size() == subparts.size()) { // full match -> check other enrollments 184 for (int i = 0; i < enrollment.getStudent().getRequests().size(); i++) { 185 Request request = enrollment.getStudent().getRequests().get(i); 186 if (request.equals(enrollment.getRequest())) continue; // given enrollment 187 Enrollment otherEnrollment = assignment.getEnrollment(request, i); 188 if (otherEnrollment == null || otherEnrollment.getCourse() == null) continue; // not assigned or not course request 189 Map<Subpart, Set<Section>> otherSubparts = iSections.get(otherEnrollment.getCourse().getOffering()); 190 if (otherSubparts == null || otherSubparts.isEmpty()) continue; // offering is not in the link 191 List<Section> otherMatch = new ArrayList<Section>(); 192 for (Section section: otherEnrollment.getSections()) { 193 Set<Section> otherSections = otherSubparts.get(section.getSubpart()); 194 if (otherSections != null && otherSections.contains(section)) 195 otherMatch.add(section); 196 } 197 // no or partial patch -> conflict 198 if (otherMatch.size() != otherSubparts.size() && !conflicts.onConflict(otherEnrollment)) return; 199 } 200 } else { // no or only partial match -> there should be no match in other offerings too 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 List<Section> otherMatch = new ArrayList<Section>(); 209 for (Section section: otherEnrollment.getSections()) { 210 Set<Section> otherSections = otherSubparts.get(section.getSubpart()); 211 if (otherSections != null && otherSections.contains(section)) 212 otherMatch.add(section); 213 } 214 // full patch -> conflict 215 if (otherMatch.size() == otherSubparts.size() && !conflicts.onConflict(otherEnrollment)) return; 216 } 217 } 218 } 219 220 /** 221 * Check for conflicts. If the given enrollment contains sections of this link 222 * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment 223 * of this student is in a conflict, if it does not contain the appropriate sections from 224 * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}. 225 * 226 * @param assignment current assignment 227 * @param enrollment given enrollment 228 * @return conflicting enrollment 229 */ 230 public Enrollment inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 231 return inConflict(enrollment, new CurrentAssignment(assignment)); 232 } 233 234 /** 235 * Check for conflicts. If the given enrollment contains sections of this link 236 * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment 237 * of this student is in a conflict, if it does not contain the appropriate sections from 238 * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}. 239 * 240 * @param enrollment given enrollment 241 * @param assignment custom assignment 242 * @return conflicting enrollment 243 */ 244 public Enrollment inConflict(Enrollment enrollment, EnrollmentAssignment assignment) { 245 final Toggle<Enrollment> ret = new Toggle<Enrollment>(null); 246 computeConflicts(enrollment, assignment, new ConflictHandler() { 247 @Override 248 public boolean onConflict(Enrollment conflict) { 249 ret.set(conflict); 250 return false; 251 } 252 }); 253 return ret.get(); 254 } 255 256 /** 257 * Interface to be able to provide a custom assignment to {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)} 258 */ 259 public static interface EnrollmentAssignment { 260 /** 261 * Return enrollment of the given request 262 * @param request given request 263 * @param index index of the request 264 * @return an enrollment 265 */ 266 public Enrollment getEnrollment(Request request, int index); 267 } 268 269 /** 270 * Helper interface to process conflicts in {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)} 271 */ 272 public static interface ConflictHandler { 273 /** 274 * Called when there is a conflict, if false the computation of other conflicts is stopped. 275 * @param conflict a conflicting enrollment 276 * @return stop the computation when false 277 */ 278 public boolean onConflict(Enrollment conflict); 279 } 280 281 /** 282 * Current assignment -- default for {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)} 283 */ 284 public static class CurrentAssignment implements EnrollmentAssignment { 285 protected Assignment<Request, Enrollment> iAssignment; 286 287 public CurrentAssignment(Assignment<Request, Enrollment> assignment) { 288 iAssignment = assignment; 289 } 290 291 /** 292 * Return {@link Request#getAssignment(Assignment)} 293 */ 294 @Override 295 public Enrollment getEnrollment(Request request, int index) { 296 return iAssignment.getValue(request); 297 } 298 } 299 300 @Override 301 public String toString() { 302 return "LinkedSections" + iSections.keySet(); 303 } 304 305 private static class Toggle<T> { 306 private T iValue; 307 Toggle(T value) { set(value); } 308 void set(T value) { iValue = value; } 309 T get() { return iValue; } 310 } 311 312 /** 313 * Linked sections constraint -- to be created for each student that requests two 314 * or more offerings of this link 315 */ 316 public class LinkedSectionsConstraint extends Constraint<Request, Enrollment> { 317 private Student iStudent; 318 319 /** 320 * Constructor 321 * @param student a student 322 * @param requests sub-set of student requests {@link Student#getRequests()} that contains offerings of this link 323 */ 324 protected LinkedSectionsConstraint(Student student, Collection<Request> requests) { 325 iStudent = student; 326 for (Request request: requests) 327 addVariable(request); 328 } 329 330 /** 331 * Return student 332 * @return student 333 */ 334 public Student getStudent() { return iStudent; } 335 336 /** 337 * Return linked section 338 * @return linked sections constraint 339 */ 340 public LinkedSections getLinkedSections() { return LinkedSections.this; } 341 342 /** 343 * Compute conflicts using {@link LinkedSections#computeConflicts(Assignment, Enrollment, ConflictHandler)} 344 */ 345 @Override 346 public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment value, final Set<Enrollment> conflicts) { 347 getLinkedSections().computeConflicts(assignment, value, new ConflictHandler() { 348 @Override 349 public boolean onConflict(Enrollment conflict) { 350 conflicts.add(conflict); 351 return true; 352 } 353 }); 354 } 355 356 /** 357 * Check consistency using {@link LinkedSections#inConflict(Enrollment, EnrollmentAssignment)} 358 */ 359 @Override 360 public boolean isConsistent(Enrollment enrollment, final Enrollment other) { 361 return getLinkedSections().inConflict(enrollment, new LinkedSections.EnrollmentAssignment() { 362 @Override 363 public Enrollment getEnrollment(Request request, int indext) { 364 return (request.equals(other.getRequest()) ? other : null); 365 } 366 }) == null; 367 } 368 369 /** 370 * Check for conflict using {@link LinkedSections#inConflict(Assignment, Enrollment)} 371 */ 372 @Override 373 public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment value) { 374 return getLinkedSections().inConflict(assignment, value) != null; 375 } 376 377 @Override 378 public String toString() { 379 return getLinkedSections().toString(); 380 } 381 } 382}