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}