    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}