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    }