001 package net.sf.cpsolver.studentsct.constraint;
002
003 import java.util.ArrayList;
004 import java.util.Collection;
005 import java.util.HashMap;
006 import java.util.HashSet;
007 import java.util.List;
008 import java.util.Map;
009 import java.util.Set;
010
011 import net.sf.cpsolver.ifs.model.Constraint;
012 import net.sf.cpsolver.studentsct.model.Course;
013 import net.sf.cpsolver.studentsct.model.CourseRequest;
014 import net.sf.cpsolver.studentsct.model.Enrollment;
015 import net.sf.cpsolver.studentsct.model.Offering;
016 import net.sf.cpsolver.studentsct.model.Request;
017 import net.sf.cpsolver.studentsct.model.Section;
018 import net.sf.cpsolver.studentsct.model.Student;
019 import 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 Tomas Muller<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 */
047 public 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 }