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;
010import java.util.TreeSet;
011
012import org.cpsolver.ifs.assignment.Assignment;
013import org.cpsolver.ifs.model.Constraint;
014import org.cpsolver.studentsct.model.Course;
015import org.cpsolver.studentsct.model.CourseRequest;
016import org.cpsolver.studentsct.model.Enrollment;
017import org.cpsolver.studentsct.model.Offering;
018import org.cpsolver.studentsct.model.Request;
019import org.cpsolver.studentsct.model.Section;
020import org.cpsolver.studentsct.model.Student;
021import org.cpsolver.studentsct.model.Subpart;
022
023
024/**
025 * Linked sections are sections (of different courses) that should be attended by the
026 * same students. If there are multiple sections of the same subpart, one or can be
027 * chosen randomly. For instance, if section A1 (of a course A) and section B1 (of a course
028 * B) are linked, a student requesting both courses must attend A1 if and only if he
029 * also attends B1. 
030 * 
031 * @version StudentSct 1.3 (Student Sectioning)<br>
032 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
033 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
034 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
035 * <br>
036 *          This library is free software; you can redistribute it and/or modify
037 *          it under the terms of the GNU Lesser General Public License as
038 *          published by the Free Software Foundation; either version 3 of the
039 *          License, or (at your option) any later version. <br>
040 * <br>
041 *          This library is distributed in the hope that it will be useful, but
042 *          WITHOUT ANY WARRANTY; without even the implied warranty of
043 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
044 *          Lesser General Public License for more details. <br>
045 * <br>
046 *          You should have received a copy of the GNU Lesser General Public
047 *          License along with this library; if not see
048 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
049 */
050public class LinkedSections {
051    private Map<Offering, Map<Subpart, Set<Section>>> iSections = new HashMap<Offering, Map<Subpart,Set<Section>>>();
052    private boolean iMustBeUsed;
053    
054    /**
055     * Constructor
056     * @param sections sections that are to be linked
057     */
058    public LinkedSections(Section... sections) {
059        for (Section section: sections)
060            addSection(section);
061        
062    }
063    
064    /**
065     * Constructor
066     * @param sections sections that are to be linked
067     */
068    public LinkedSections(Collection<Section> sections) {
069        for (Section section: sections)
070            addSection(section);
071    }
072
073    /**
074     * Add a section to this link
075     * @param section
076     */
077    private void addSection(Section section) {
078        Map<Subpart, Set<Section>> subparts = iSections.get(section.getSubpart().getConfig().getOffering());
079        if (subparts == null) {
080            subparts = new HashMap<Subpart, Set<Section>>();
081            iSections.put(section.getSubpart().getConfig().getOffering(), subparts);
082        }
083        Set<Section> sections = subparts.get(section.getSubpart());
084        if (sections == null) {
085            sections = new HashSet<Section>();
086            subparts.put(section.getSubpart(), sections);
087        }
088        sections.add(section);
089
090    }
091    
092    /**
093     * Return offerings of this link
094     * @return offerings of this link
095     */
096    public Set<Offering> getOfferings() { return iSections.keySet(); }
097    
098    /**
099     * Return subpart (or subparts) of an offering of this link
100     * @param offering an offering of this link
101     * @return subpart (or subparts) of this offering in this link
102     */
103    public Set<Subpart> getSubparts(Offering offering) { return iSections.get(offering).keySet(); }
104    
105    /**
106     * Return section (or sections) of a subpart of this link
107     * @param subpart subpart of this link
108     * @return section (or sections) of this subpart in this link
109     */
110    public Set<Section> getSections(Subpart subpart) { return iSections.get(subpart.getConfig().getOffering()).get(subpart); }
111    
112    /**
113     * Create linked-section constraints for a given student
114     */
115    private LinkedSectionsConstraint createConstraint(Student student) {
116        List<Request> requests = new ArrayList<Request>();
117        int nrOfferings = 0;
118        requests: for (Request request: student.getRequests()) {
119            if (request instanceof CourseRequest) {
120                for (Course course: ((CourseRequest)request).getCourses()) {
121                    Map<Subpart, Set<Section>> subpartsThisOffering = iSections.get(course.getOffering());
122                    if (subpartsThisOffering != null) {
123                        requests.add(request);
124                        nrOfferings++;
125                        continue requests;
126                    }
127                }
128            }
129        }
130        if (nrOfferings <= 1) return null;
131        LinkedSectionsConstraint constraint = new LinkedSectionsConstraint(student, requests);
132        student.getRequests().get(0).getModel().addConstraint(constraint);
133        return constraint;
134    }
135    
136    /**
137     * Create linked-section constraints for this link. A constraint is created for each
138     * student that has two or more offerings of this link.
139     */
140    public void createConstraints() {
141        Set<Student> students = new HashSet<Student>();
142        for (Offering offering: iSections.keySet())
143            for (Course course: offering.getCourses())
144                for (Request request: course.getRequests())
145                    if (students.add(request.getStudent())) {
146                        if (createConstraint(request.getStudent()) != null)
147                            request.getStudent().getLinkedSections().add(this);
148                    }
149    }
150    
151    /**
152     * Compute conflicting enrollments. If the given enrollment contains sections of this link
153     * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment
154     * of this student is in a conflict, if it does not contain the appropriate sections from
155     * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}.
156     * 
157     * @param assignment current assignment
158     * @param enrollment given enrollment 
159     * @param conflicts found conflicts are given to this interface, see {@link ConflictHandler#onConflict(Enrollment)}
160     */
161    public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment enrollment, ConflictHandler conflicts) {
162        computeConflicts(enrollment, new CurrentAssignment(assignment), conflicts);
163    }
164    
165    /**
166     * Compute conflicting enrollments. If the given enrollment contains sections of this link
167     * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment
168     * of this student is in a conflict, if it does not contain the appropriate sections from
169     * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}.
170     * 
171     * @param enrollment given enrollment
172     * @param assignment custom assignment 
173     * @param conflicts found conflicts are given to this interface, see {@link ConflictHandler#onConflict(Enrollment)}
174     */
175    public void computeConflicts(Enrollment enrollment, EnrollmentAssignment assignment, ConflictHandler conflicts) {
176        if (enrollment == null || enrollment.getCourse() == null) return;
177        Map<Subpart, Set<Section>> subparts = iSections.get(enrollment.getCourse().getOffering());
178        if (subparts == null || subparts.isEmpty()) return;
179        boolean match = false, partial = false;
180        for (Section section: enrollment.getSections()) {
181            Set<Section> sections = subparts.get(section.getSubpart());
182            if (sections != null) {
183                if (sections.contains(section))
184                    match = true;
185                else
186                    partial = true;
187            }
188        }
189        boolean full = match && !partial;
190        if (isMustBeUsed()) {
191            if (!full) { // not full match -> conflict if there is no other linked section constraint with a full match
192                // check if there is some other constraint taking care of this case
193                boolean hasOtherMatch = false;
194                for (LinkedSections other: enrollment.getStudent().getLinkedSections()) {
195                    if (other.hasFullMatch(enrollment) && nrSharedOfferings(other) > 1) { hasOtherMatch = true; break; }
196                }
197                // no other match -> problem
198                if (!hasOtherMatch && !conflicts.onConflict(enrollment)) return;
199            }
200        }
201        if (full) { // full match -> check other enrollments
202            for (int i = 0; i < enrollment.getStudent().getRequests().size(); i++) {
203                Request request = enrollment.getStudent().getRequests().get(i);
204                if (request.equals(enrollment.getRequest())) continue; // given enrollment
205                Enrollment otherEnrollment = assignment.getEnrollment(request, i);
206                if (otherEnrollment == null || otherEnrollment.getCourse() == null) continue; // not assigned or not course request
207                Map<Subpart, Set<Section>> otherSubparts = iSections.get(otherEnrollment.getCourse().getOffering());
208                if (otherSubparts == null || otherSubparts.isEmpty()) continue; // offering is not in the link
209                boolean otherMatch = false, otherPartial = false;
210                for (Section section: otherEnrollment.getSections()) {
211                    Set<Section> otherSections = otherSubparts.get(section.getSubpart());
212                    if (otherSections != null) {
213                        if (otherSections.contains(section))
214                            otherMatch = true;
215                        else
216                            otherPartial = true;
217                    }
218                }
219                boolean otherFull = otherMatch && !otherPartial;
220                // not full match -> conflict
221                if (!otherFull && !conflicts.onConflict(otherEnrollment)) return;
222            }
223        } else { // no or only partial match -> there should be no match in other offerings too
224            for (int i = 0; i < enrollment.getStudent().getRequests().size(); i++) {
225                Request request = enrollment.getStudent().getRequests().get(i);
226                if (request.equals(enrollment.getRequest())) continue; // given enrollment
227                Enrollment otherEnrollment = assignment.getEnrollment(request, i);
228                if (otherEnrollment == null || otherEnrollment.getCourse() == null) continue; // not assigned or not course request
229                Map<Subpart, Set<Section>> otherSubparts = iSections.get(otherEnrollment.getCourse().getOffering());
230                if (otherSubparts == null || otherSubparts.isEmpty()) continue; // offering is not in the link
231                boolean otherMatch = false, otherPartial = false;
232                for (Section section: otherEnrollment.getSections()) {
233                    Set<Section> otherSections = otherSubparts.get(section.getSubpart());
234                    if (otherSections != null) {
235                        if (otherSections.contains(section))
236                            otherMatch = true;
237                        else
238                            otherPartial = true;
239                    }
240                }
241                boolean otherFull = otherMatch && !otherPartial;
242                // full match -> conflict
243                if (otherFull && !conflicts.onConflict(otherEnrollment)) return;
244            }
245        }
246    }
247    
248    /**
249     * Check if the given enrollment fully matches this constraint
250     * @param enrollment an enrollment
251     * @return true, if there is a full match
252     */
253    protected boolean hasFullMatch(Enrollment enrollment) {
254        if (enrollment == null || enrollment.getCourse() == null) return false; // not assigned or not course request
255        Map<Subpart, Set<Section>> subparts = iSections.get(enrollment.getCourse().getOffering());
256        if (subparts == null || subparts.isEmpty()) return false; // offering is not in the link
257        boolean match = false, partial = false;
258        for (Section section: enrollment.getSections()) {
259            Set<Section> sections = subparts.get(section.getSubpart());
260            if (sections != null) {
261                if (sections.contains(section))
262                    match = true;
263                else
264                    partial = true;
265            }
266        }
267        return match && !partial;
268    }
269    
270    /**
271     * Number of offerings that are shared with some other linked sections constraint
272     * @param other the other constraint
273     * @return number of offerings in common
274     */
275    protected int nrSharedOfferings(LinkedSections other) {
276        int shared = 0;
277        for (Offering offering: other.getOfferings())
278            if (iSections.containsKey(offering)) shared ++;
279        return shared;
280    }
281    
282    /**
283     * Check for conflicts. If the given enrollment contains sections of this link
284     * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment
285     * of this student is in a conflict, if it does not contain the appropriate sections from
286     * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}.
287     * 
288     * @param assignment current assignment
289     * @param enrollment given enrollment 
290     * @return conflicting enrollment
291     */
292    public Enrollment inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
293        return inConflict(enrollment, new CurrentAssignment(assignment));
294    }
295    
296    /**
297     * Check for conflicts. If the given enrollment contains sections of this link
298     * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment
299     * of this student is in a conflict, if it does not contain the appropriate sections from
300     * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}.
301     * 
302     * @param enrollment given enrollment
303     * @param assignment custom assignment 
304     * @return conflicting enrollment
305     */
306    public Enrollment inConflict(Enrollment enrollment, EnrollmentAssignment assignment) {
307        final Toggle<Enrollment> ret = new Toggle<Enrollment>(null);
308        computeConflicts(enrollment, assignment, new ConflictHandler() {
309            @Override
310            public boolean onConflict(Enrollment conflict) {
311                ret.set(conflict);
312                return false;
313            }
314        });
315        return ret.get();
316    }
317    
318    /**
319     * Interface to be able to provide a custom assignment to {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)}
320     */
321    public static interface EnrollmentAssignment {
322        /**
323         * Return enrollment of the given request
324         * @param request given request
325         * @param index index of the request
326         * @return an enrollment
327         */
328        public Enrollment getEnrollment(Request request, int index);
329    }
330    
331    /**
332     * Helper interface to process conflicts in {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)}
333     */
334    public static interface ConflictHandler {
335        /**
336         * Called when there is a conflict, if false the computation of other conflicts is stopped.
337         * @param conflict a conflicting enrollment
338         * @return stop the computation when false
339         */
340        public boolean onConflict(Enrollment conflict);
341    }
342    
343    /**
344     * Current assignment -- default for {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)}
345     */
346    public static class CurrentAssignment implements EnrollmentAssignment {
347        protected Assignment<Request, Enrollment> iAssignment;
348        
349        public CurrentAssignment(Assignment<Request, Enrollment> assignment) {
350            iAssignment = assignment;
351        }
352        
353        /**
354         * Return {@link Request#getAssignment(Assignment)}
355         */
356        @Override
357        public Enrollment getEnrollment(Request request, int index) {
358            return iAssignment.getValue(request);
359        }
360    }
361    
362    /**
363     * Return whether this constraint must be used
364     * @return if true, a pair of linked sections must be used when a student requests both courses
365     */
366    public boolean isMustBeUsed() { return iMustBeUsed; }
367
368    /**
369     * Set whether this constraint must be used
370     * @param mustBeUsed if true,  a pair of linked sections must be used when a student requests both courses
371     */
372    public void setMustBeUsed(boolean mustBeUsed) { iMustBeUsed = mustBeUsed; }
373    
374    @Override
375    public String toString() {
376        String sections = "";
377        for (Map.Entry<Offering, Map<Subpart, Set<Section>>> e: iSections.entrySet()) {
378            sections += (sections.isEmpty() ? "" : "; ") + e.getKey().getName();
379            Set<String> ids = new TreeSet<String>();
380            for (Map.Entry<Subpart, Set<Section>> f: e.getValue().entrySet()) {
381                for (Section s: f.getValue())
382                    ids.add(s.getName());
383                sections += ":" + ids;
384            }
385        }
386        return "LinkedSections{" + sections + "}";
387    }
388    
389    private static class Toggle<T> {
390        private T iValue;
391        Toggle(T value) { set(value); }
392        void set(T value) { iValue = value; }
393        T get() { return iValue; }
394    }
395    
396    /**
397     * Linked sections constraint -- to be created for each student that requests two
398     * or more offerings of this link
399     */
400    public class LinkedSectionsConstraint extends Constraint<Request, Enrollment> {
401        private Student iStudent;
402        
403        /**
404         * Constructor
405         * @param student a student
406         * @param requests sub-set of student requests {@link Student#getRequests()} that contains offerings of this link
407         */
408        protected LinkedSectionsConstraint(Student student, Collection<Request> requests) {
409            iStudent = student;
410            for (Request request: requests)
411                addVariable(request);
412        }
413        
414        /**
415         * Return student
416         * @return student
417         */
418        public Student getStudent() { return iStudent; }
419
420        /**
421         * Return linked section
422         * @return linked sections constraint
423         */
424        public LinkedSections getLinkedSections() { return LinkedSections.this; }
425
426        /**
427         * Compute conflicts using {@link LinkedSections#computeConflicts(Assignment, Enrollment, ConflictHandler)}
428         */
429        @Override
430        public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment value, final Set<Enrollment> conflicts) {
431            getLinkedSections().computeConflicts(assignment, value, new ConflictHandler() {
432                @Override
433                public boolean onConflict(Enrollment conflict) {
434                    conflicts.add(conflict);
435                    return true;
436                }
437            });
438        }
439        
440        /**
441         * Check consistency using {@link LinkedSections#inConflict(Enrollment, EnrollmentAssignment)}
442         */
443        @Override
444        public boolean isConsistent(Enrollment enrollment, final Enrollment other) {
445            return getLinkedSections().inConflict(enrollment, new LinkedSections.EnrollmentAssignment() {
446                @Override
447                public Enrollment getEnrollment(Request request, int indext) {
448                    return (request.equals(other.getRequest()) ? other : null);
449                }
450            }) == null;
451        }
452        
453        /**
454         * Check for conflict using {@link LinkedSections#inConflict(Assignment, Enrollment)}
455         */
456        @Override
457        public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment value) {
458            return getLinkedSections().inConflict(assignment, value) != null;
459        }
460        
461        @Override
462        public String toString() {
463            return getLinkedSections().toString();
464        }
465    }
466}