    001package net.sf.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 net.sf.cpsolver.ifs.model.Constraint;
    012import net.sf.cpsolver.studentsct.model.Course;
    013import net.sf.cpsolver.studentsct.model.CourseRequest;
    014import net.sf.cpsolver.studentsct.model.Enrollment;
    015import net.sf.cpsolver.studentsct.model.Offering;
    016import net.sf.cpsolver.studentsct.model.Request;
    017import net.sf.cpsolver.studentsct.model.Section;
    018import net.sf.cpsolver.studentsct.model.Student;
    019import 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 Tomáš Müller<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 */
    047public 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}