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