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 Tomáš Müller<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        if (enrollment.getReservation() != null && enrollment.getReservation().canBreakLinkedSections()) return;
178        Map<Subpart, Set<Section>> subparts = iSections.get(enrollment.getCourse().getOffering());
179        if (subparts == null || subparts.isEmpty()) return;
180        boolean match = false, partial = false;
181        for (Section section: enrollment.getSections()) {
182            Set<Section> sections = subparts.get(section.getSubpart());
183            if (sections != null) {
184                if (sections.contains(section))
185                    match = true;
186                else
187                    partial = true;
188            }
189        }
190        boolean full = match && !partial;
191        if (isMustBeUsed()) {
192            if (!full) { // not full match -> conflict if there is no other linked section constraint with a full match
193                // check if there is some other constraint taking care of this case
194                boolean hasOtherMatch = false;
195                for (LinkedSections other: enrollment.getStudent().getLinkedSections()) {
196                    if (other.hasFullMatch(enrollment) && nrSharedOfferings(other) > 1) { hasOtherMatch = true; break; }
197                }
198                // no other match -> problem
199                if (!hasOtherMatch && !conflicts.onConflict(enrollment)) return;
200            }
201        }
202        if (full) { // full match -> check other enrollments
203            for (int i = 0; i < enrollment.getStudent().getRequests().size(); i++) {
204                Request request = enrollment.getStudent().getRequests().get(i);
205                if (request.equals(enrollment.getRequest())) continue; // given enrollment
206                Enrollment otherEnrollment = assignment.getEnrollment(request, i);
207                if (otherEnrollment == null || otherEnrollment.getCourse() == null) continue; // not assigned or not course request
208                if (otherEnrollment.getReservation() != null && otherEnrollment.getReservation().canBreakLinkedSections()) continue;
209                Map<Subpart, Set<Section>> otherSubparts = iSections.get(otherEnrollment.getCourse().getOffering());
210                if (otherSubparts == null || otherSubparts.isEmpty()) continue; // offering is not in the link
211                boolean otherMatch = false, otherPartial = false;
212                for (Section section: otherEnrollment.getSections()) {
213                    Set<Section> otherSections = otherSubparts.get(section.getSubpart());
214                    if (otherSections != null) {
215                        if (otherSections.contains(section))
216                            otherMatch = true;
217                        else
218                            otherPartial = true;
219                    }
220                }
221                boolean otherFull = otherMatch && !otherPartial;
222                // not full match -> conflict
223                if (!otherFull && !conflicts.onConflict(otherEnrollment)) return;
224            }
225        } else { // no or only partial match -> there should be no match in other offerings too
226            for (int i = 0; i < enrollment.getStudent().getRequests().size(); i++) {
227                Request request = enrollment.getStudent().getRequests().get(i);
228                if (request.equals(enrollment.getRequest())) continue; // given enrollment
229                Enrollment otherEnrollment = assignment.getEnrollment(request, i);
230                if (otherEnrollment == null || otherEnrollment.getCourse() == null) continue; // not assigned or not course request
231                if (otherEnrollment.getReservation() != null && otherEnrollment.getReservation().canBreakLinkedSections()) continue;
232                Map<Subpart, Set<Section>> otherSubparts = iSections.get(otherEnrollment.getCourse().getOffering());
233                if (otherSubparts == null || otherSubparts.isEmpty()) continue; // offering is not in the link
234                boolean otherMatch = false, otherPartial = false;
235                for (Section section: otherEnrollment.getSections()) {
236                    Set<Section> otherSections = otherSubparts.get(section.getSubpart());
237                    if (otherSections != null) {
238                        if (otherSections.contains(section))
239                            otherMatch = true;
240                        else
241                            otherPartial = true;
242                    }
243                }
244                boolean otherFull = otherMatch && !otherPartial;
245                // full match -> conflict
246                if (otherFull && !conflicts.onConflict(otherEnrollment)) return;
247            }
248        }
249    }
250    
251    /**
252     * Check if the given enrollment fully matches this constraint
253     * @param enrollment an enrollment
254     * @return true, if there is a full match
255     */
256    protected boolean hasFullMatch(Enrollment enrollment) {
257        if (enrollment == null || enrollment.getCourse() == null) return false; // not assigned or not course request
258        Map<Subpart, Set<Section>> subparts = iSections.get(enrollment.getCourse().getOffering());
259        if (subparts == null || subparts.isEmpty()) return false; // offering is not in the link
260        boolean match = false, partial = false;
261        for (Section section: enrollment.getSections()) {
262            Set<Section> sections = subparts.get(section.getSubpart());
263            if (sections != null) {
264                if (sections.contains(section))
265                    match = true;
266                else
267                    partial = true;
268            }
269        }
270        return match && !partial;
271    }
272    
273    /**
274     * Number of offerings that are shared with some other linked sections constraint
275     * @param other the other constraint
276     * @return number of offerings in common
277     */
278    protected int nrSharedOfferings(LinkedSections other) {
279        int shared = 0;
280        for (Offering offering: other.getOfferings())
281            if (iSections.containsKey(offering)) shared ++;
282        return shared;
283    }
284    
285    /**
286     * Check for conflicts. If the given enrollment contains sections of this link
287     * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment
288     * of this student is in a conflict, if it does not contain the appropriate sections from
289     * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}.
290     * 
291     * @param assignment current assignment
292     * @param enrollment given enrollment 
293     * @return conflicting enrollment
294     */
295    public Enrollment inConflict(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
296        return inConflict(enrollment, new CurrentAssignment(assignment));
297    }
298    
299    /**
300     * Check for conflicts. If the given enrollment contains sections of this link
301     * (one for each subpart in {@link LinkedSections#getSubparts(Offering)}), another assignment
302     * of this student is in a conflict, if it does not contain the appropriate sections from
303     * {@link LinkedSections#getSubparts(Offering)} and {@link LinkedSections#getSections(Subpart)}.
304     * 
305     * @param enrollment given enrollment
306     * @param assignment custom assignment 
307     * @return conflicting enrollment
308     */
309    public Enrollment inConflict(Enrollment enrollment, EnrollmentAssignment assignment) {
310        final Toggle<Enrollment> ret = new Toggle<Enrollment>(null);
311        computeConflicts(enrollment, assignment, new ConflictHandler() {
312            @Override
313            public boolean onConflict(Enrollment conflict) {
314                ret.set(conflict);
315                return false;
316            }
317        });
318        return ret.get();
319    }
320    
321    /**
322     * Interface to be able to provide a custom assignment to {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)}
323     */
324    public static interface EnrollmentAssignment {
325        /**
326         * Return enrollment of the given request
327         * @param request given request
328         * @param index index of the request
329         * @return an enrollment
330         */
331        public Enrollment getEnrollment(Request request, int index);
332    }
333    
334    /**
335     * Helper interface to process conflicts in {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)}
336     */
337    public static interface ConflictHandler {
338        /**
339         * Called when there is a conflict, if false the computation of other conflicts is stopped.
340         * @param conflict a conflicting enrollment
341         * @return stop the computation when false
342         */
343        public boolean onConflict(Enrollment conflict);
344    }
345    
346    /**
347     * Current assignment -- default for {@link LinkedSections#computeConflicts(Enrollment, EnrollmentAssignment, ConflictHandler)}
348     */
349    public static class CurrentAssignment implements EnrollmentAssignment {
350        protected Assignment<Request, Enrollment> iAssignment;
351        
352        public CurrentAssignment(Assignment<Request, Enrollment> assignment) {
353            iAssignment = assignment;
354        }
355        
356        /**
357         * Return {@link Request#getAssignment(Assignment)}
358         */
359        @Override
360        public Enrollment getEnrollment(Request request, int index) {
361            return iAssignment.getValue(request);
362        }
363    }
364    
365    /**
366     * Return whether this constraint must be used
367     * @return if true, a pair of linked sections must be used when a student requests both courses
368     */
369    public boolean isMustBeUsed() { return iMustBeUsed; }
370
371    /**
372     * Set whether this constraint must be used
373     * @param mustBeUsed if true,  a pair of linked sections must be used when a student requests both courses
374     */
375    public void setMustBeUsed(boolean mustBeUsed) { iMustBeUsed = mustBeUsed; }
376    
377    @Override
378    public String toString() {
379        String sections = "";
380        for (Map.Entry<Offering, Map<Subpart, Set<Section>>> e: iSections.entrySet()) {
381            sections += (sections.isEmpty() ? "" : "; ") + e.getKey().getName();
382            Set<String> ids = new TreeSet<String>();
383            for (Map.Entry<Subpart, Set<Section>> f: e.getValue().entrySet()) {
384                for (Section s: f.getValue())
385                    ids.add(s.getName());
386                sections += ":" + ids;
387            }
388        }
389        return "LinkedSections{" + sections + "}";
390    }
391    
392    private static class Toggle<T> {
393        private T iValue;
394        Toggle(T value) { set(value); }
395        void set(T value) { iValue = value; }
396        T get() { return iValue; }
397    }
398    
399    /**
400     * Linked sections constraint -- to be created for each student that requests two
401     * or more offerings of this link
402     */
403    public class LinkedSectionsConstraint extends Constraint<Request, Enrollment> {
404        private Student iStudent;
405        
406        /**
407         * Constructor
408         * @param student a student
409         * @param requests sub-set of student requests {@link Student#getRequests()} that contains offerings of this link
410         */
411        protected LinkedSectionsConstraint(Student student, Collection<Request> requests) {
412            iStudent = student;
413            for (Request request: requests)
414                addVariable(request);
415        }
416        
417        /**
418         * Return student
419         * @return student
420         */
421        public Student getStudent() { return iStudent; }
422
423        /**
424         * Return linked section
425         * @return linked sections constraint
426         */
427        public LinkedSections getLinkedSections() { return LinkedSections.this; }
428
429        /**
430         * Compute conflicts using {@link LinkedSections#computeConflicts(Assignment, Enrollment, ConflictHandler)}
431         */
432        @Override
433        public void computeConflicts(Assignment<Request, Enrollment> assignment, Enrollment value, final Set<Enrollment> conflicts) {
434            getLinkedSections().computeConflicts(assignment, value, new ConflictHandler() {
435                @Override
436                public boolean onConflict(Enrollment conflict) {
437                    conflicts.add(conflict);
438                    return true;
439                }
440            });
441        }
442        
443        /**
444         * Check consistency using {@link LinkedSections#inConflict(Enrollment, EnrollmentAssignment)}
445         */
446        @Override
447        public boolean isConsistent(Enrollment enrollment, final Enrollment other) {
448            return getLinkedSections().inConflict(enrollment, new LinkedSections.EnrollmentAssignment() {
449                @Override
450                public Enrollment getEnrollment(Request request, int indext) {
451                    return (request.equals(other.getRequest()) ? other : null);
452                }
453            }) == null;
454        }
455        
456        /**
457         * Check for conflict using {@link LinkedSections#inConflict(Assignment, Enrollment)}
458         */
459        @Override
460        public boolean inConflict(Assignment<Request, Enrollment> assignment, Enrollment value) {
461            return getLinkedSections().inConflict(assignment, value) != null;
462        }
463        
464        @Override
465        public String toString() {
466            return getLinkedSections().toString();
467        }
468    }
469}