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