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