    001package org.cpsolver.coursett.model;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.List;
    006import java.util.Locale;
    007import java.util.Map;
    008
    009import org.cpsolver.coursett.model.InitialSectioning.Group;
    010import org.cpsolver.coursett.sectioning.StudentSwapSectioning;
    011import org.cpsolver.ifs.assignment.Assignment;
    012import org.cpsolver.ifs.model.InfoProvider;
    013import org.cpsolver.ifs.solution.Solution;
    014import org.cpsolver.ifs.termination.TerminationCondition;
    015import org.cpsolver.ifs.util.Progress;
    016
    017
    018/**
    019 * Default implementation of the student sectioning functions needed within the course timetabling solver
    020 * consisting of {@link InitialSectioning} and {@link FinalSectioning}.
    021 * <br>
    022 * <br>
    023 * Many course offerings consist of multiple classes, with students enrolled in
    024 * the course divided among them. These classes are often linked by a set of
    025 * constraints, namely:
    026 * <ul>
    027 * <li>Each class has a limit stating the maximum number of students who can be
    028 * enrolled in it.
    029 * <li>A student must be enrolled in exactly one class for each subpart of a
    030 * course.
    031 * <li>If two subparts of a course have a parent-child relationship, a student
    032 * enrolled in the parent class must also be enrolled in one of the child
    033 * classes.
    034 * </ul>
    035 * Moreover, some of the classes of an offering may be required or prohibited
    036 * for certain students, based on reservations that can be set on an offering, a
    037 * configuration, or a class. <br>
    038 * While the data are loaded into the solver, an initial sectioning of students into
    039 * classes is processed (see {@link InitialSectioning}). However, it
    040 * is still possible to improve on the number of student conflicts in the
    041 * solution. This can be accomplished by moving students between alternative
    042 * classes of the same course during or after the search (see
    043 * {@link FinalSectioning}).
    044 *
    045 * @author  Tomáš Müller
    046 * @version CourseTT 1.3 (University Course Timetabling)<br>
    047 *          Copyright (C) 2014 Tomáš Müller<br>
    048 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    049 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    050 * <br>
    051 *          This library is free software; you can redistribute it and/or modify
    052 *          it under the terms of the GNU Lesser General Public License as
    053 *          published by the Free Software Foundation; either version 3 of the
    054 *          License, or (at your option) any later version. <br>
    055 * <br>
    056 *          This library is distributed in the hope that it will be useful, but
    057 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    058 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    059 *          Lesser General Public License for more details. <br>
    060 * <br>
    061 *          You should have received a copy of the GNU Lesser General Public
    062 *          License along with this library; if not see
    063 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    064 */
    065public class DefaultStudentSectioning implements StudentSectioning, InfoProvider<Lecture, Placement> {
    066    protected TimetableModel iModel = null;
    067    private Progress iProgress = null;
    068    protected FinalSectioning iFinalSectioning = null;
    069    protected boolean iMustFollowReservations = false;
    070    protected static java.text.DecimalFormat sDF2 = new java.text.DecimalFormat("0.00", new java.text.DecimalFormatSymbols(Locale.US));
    071
    072    /**
    073     * Constructor
    074     * @param model problem model
    075     */
    076    public DefaultStudentSectioning(TimetableModel model) {
    077        iModel = model;
    078        iFinalSectioning = new FinalSectioning(model);
    079        iMustFollowReservations = model.getProperties().getPropertyBoolean("StudentSectioning.MustFollowReservations", false);
    080    }
    081
    082    public Progress getProgress() {
    083        if (iProgress == null) iProgress = Progress.getInstance(iModel);
    084        return iProgress;
    085    }
    086
    087    /**
    088     * Enroll students into the given offering during the initial data load using {@link InitialSectioning}.
    089     * @param offeringId instructional offering id
    090     * @param courseName course name
    091     * @param students list of students to be sectioned
    092     * @param configurations list of configurations the students are to be sectioned into
    093     */
    094    @Override
    095    public void initialSectioning(Assignment<Lecture, Placement> assignment, Long offeringId, String courseName, Collection<Student> students, Collection<Configuration> configurations) {
    096        if (students == null || students.isEmpty())
    097            return;
    098        if (configurations == null || configurations.isEmpty())
    099            return;
    100        if (configurations.size() == 1) {
    101            if (isMustFollowReservations()) {
    102                Collection<Student> availableStudents = new ArrayList<Student>(students.size());
    103                Configuration cfg = configurations.iterator().next();
    104                for (Student st : students) {
    105                    if (st.canEnroll(cfg)) {
    106                        availableStudents.add(st);
    107                        st.addConfiguration(cfg);
    108                    } else {
    109                        getProgress().debug("Unable to enroll student " + st.getId() + " in " + courseName);
    110                    }
    111                    for (Long subpartId: cfg.getTopSubpartIds()) {
    112                        initialSectioningLectures(assignment, offeringId, courseName, availableStudents, cfg.getTopLectures(subpartId));
    113                    }
    114                }
    115            } else {
    116                Configuration cfg = configurations.iterator().next();
    117                for (Student st : students) {
    118                    st.addConfiguration(cfg);
    119                }
    120                for (Long subpartId: cfg.getTopSubpartIds()) {
    121                    initialSectioningLectures(assignment, offeringId, courseName, students, cfg.getTopLectures(subpartId));
    122                }
    123            }
    124        } else {
    125            getProgress().trace("sectioning " + students.size() + " students of course " + courseName + " into " + configurations.size() + " configurations");
    126            Group[] studentsPerSection = studentsToConfigurations(offeringId, students, configurations);
    127            for (int i = 0; i < configurations.size(); i++) {
    128                Group group = studentsPerSection[i];
    129                getProgress().trace((i + 1) + ". configuration got " + group.getStudents().size() + " students (weighted=" + group.size() + ", cfgLimit=" + group.getConfiguration().getLimit() + ")");
    130                for (Student st : group.getStudents()) {
    131                    st.addConfiguration(group.getConfiguration());
    132                }
    133                for (Long subpartId: group.getConfiguration().getTopSubpartIds()) {
    134                    initialSectioningLectures(assignment, offeringId, courseName, group.getStudents(), group.getConfiguration().getTopLectures(subpartId));
    135                }
    136            }
    137            if (isMustFollowReservations()) {
    138                for (Student st : students) {
    139                    boolean hasConfig = false;
    140                    for (Configuration cfg: configurations)
    141                        if (st.getConfigurations().contains(cfg)) {
    142                            hasConfig = true;
    143                            break;
    144                        }
    145                    if (!hasConfig)
    146                        getProgress().debug("Unable to enroll student " + st.getId() + " in " + courseName);
    147                }
    148            }
    149        }
    150    }
    151
    152    /**
    153     * Class label
    154     * @param lecture a class
    155     * @return class label including a link to be printed in the log
    156     */
    157    protected String getClassLabel(Lecture lecture) {
    158        return "<A href='classDetail.do?cid=" + lecture.getClassId() + "'>" + lecture.getName() + "</A>";
    159    }
    160
    161    /**
    162     * Enroll students into the given classes during the initial data load using {@link InitialSectioning}.
    163     * @param assignment current assignment
    164     * @param offeringId instructional offering id
    165     * @param courseName course name
    166     * @param students list of students to be sectioned
    167     * @param lectures list of lectures the students are to be sectioned into
    168     */
    169    protected void initialSectioningLectures(Assignment<Lecture, Placement> assignment, Long offeringId, String courseName, Collection<Student> students, Collection<Lecture> lectures) {
    170        if (lectures == null || lectures.isEmpty())
    171            return;
    172        if (students == null || students.isEmpty())
    173            return;
    174        for (Lecture lecture : lectures) {
    175            if (lecture.classLimit(assignment) == 0 && !lecture.isCommitted())
    176                getProgress().warn("Class " + getClassLabel(lecture) + " has zero class limit.");
    177        }
    178
    179        getProgress().trace("sectioning " + students.size() + " students of course " + courseName + " into " + lectures.size() + " sections");
    180        if (lectures.size() == 1) {
    181            Collection<Student> availableStudents = (isMustFollowReservations() ? new ArrayList<Student>(students.size()) : students);
    182            Lecture lect = lectures.iterator().next();
    183            for (Student st : students) {
    184                if (!st.canEnroll(lect)) {
    185                    getProgress().debug("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect));
    186                    if (isMustFollowReservations()) continue;
    187                }
    188                lect.addStudent(assignment, st);
    189                st.addLecture(lect);
    190                if (isMustFollowReservations()) availableStudents.add(st);
    191            }
    192            if (lect.hasAnyChildren()) {
    193                for (Long subpartId: lect.getChildrenSubpartIds()) {
    194                    List<Lecture> children = lect.getChildren(subpartId);
    195                    initialSectioningLectures(assignment, offeringId, lect.getName(), availableStudents, children);
    196                }
    197            }
    198        } else {
    199            Group[] studentsPerSection = studentsToLectures(offeringId, students, lectures);
    200            for (int i = 0; i < studentsPerSection.length; i++) {
    201                Group group = studentsPerSection[i];
    202                Lecture lect = group.getLecture();
    203                if (group.getStudents().isEmpty()) {
    204                    getProgress().trace("Lecture " + getClassLabel(lect) + " got no students (cl=" + lect.classLimit(assignment) + ")");
    205                    continue;
    206                }
    207                getProgress().trace("Lecture " + getClassLabel(lect) + " got " + group.getStudents().size() + " students (weighted=" + group.size() + ", classLimit=" + lect.classLimit(assignment) + ")");
    208                List<Student> studentsThisSection = group.getStudents();
    209                for (Student st : studentsThisSection) {
    210                    if (!st.canEnroll(lect)) {
    211                        if (isMustFollowReservations()) {
    212                            // should not really happen
    213                            getProgress().info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect));
    214                            continue;
    215                        } else {
    216                            getProgress().debug("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect));
    217                        }
    218                    }
    219                    lect.addStudent(assignment, st);
    220                    st.addLecture(lect);
    221                }
    222                if (lect.hasAnyChildren()) {
    223                    for (Long subpartId: lect.getChildrenSubpartIds()) {
    224                        List<Lecture> children = lect.getChildren(subpartId);
    225                        initialSectioningLectures(assignment, offeringId, lect.getName(), studentsThisSection, children);
    226                    }
    227                }
    228            }
    229            if (isMustFollowReservations()) {
    230                for (Student st : students) {
    231                    boolean hasLecture = false;
    232                    for (Lecture lect: lectures)
    233                        if (st.getLectures().contains(lect)) {
    234                            hasLecture = true;
    235                            break;
    236                        }
    237                    if (!hasLecture)
    238                        getProgress().debug("Unable to enroll student " + st.getId() + " in " + courseName);
    239                }
    240            }
    241        }
    242    }
    243
    244    /**
    245     * Section students into configurations. This method calls the actual initial sectioning {@link InitialSectioning#getGroups()}.
    246     * @param offeringId instructional offering id
    247     * @param students list of students to be sectioned
    248     * @param configurations list of configurations the students are to be sectioned into
    249     * @return list of {@link Group}
    250     */
    251    protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) {
    252        InitialSectioning sect = new InitialSectioning(getProgress(), offeringId, configurations, students);
    253        sect.setMustFollowReservations(isMustFollowReservations());
    254        return sect.getGroups();
    255    }
    256
    257    /**
    258     * Section students into lectures. This method calls the actual initial sectioning {@link InitialSectioning#getGroups()}.
    259     * @param offeringId instructional offering id
    260     * @param students list of students to be sectioned
    261     * @param lectures list of lectures the students are to be sectioned into
    262     * @return list of {@link Group}
    263     */
    264    protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) {
    265        InitialSectioning sect = new InitialSectioning(getProgress(), offeringId, lectures, students);
    266        sect.setMustFollowReservations(isMustFollowReservations());
    267        return sect.getGroups();
    268    }
    269
    270    /**
    271     * Return true if final student sectioning is implemented.
    272     */
    273    @Override
    274    public boolean hasFinalSectioning() {
    275        return true;
    276    }
    277
    278    /**
    279     * Run student final sectioning (switching students between sections of the same
    280     * class in order to minimize overall number of student conflicts).
    281     */
    282    @Override
    283    public void switchStudents(Solution<Lecture, Placement> solution, TerminationCondition<Lecture, Placement> termination) {
    284        iFinalSectioning.execute(solution, termination);
    285    }
    286
    287    /**
    288     * Perform sectioning on the given lecture
    289     * @param lecture given lecture
    290     * @param recursive recursively resection lectures affected by a student swap
    291     * @param configAsWell resection students between configurations as well
    292     **/
    293    @Override
    294    public void resection(Assignment<Lecture, Placement> assignment, Lecture lecture, boolean recursive, boolean configAsWell) {
    295        iFinalSectioning.resection(assignment, lecture, recursive, configAsWell);
    296    }
    297
    298    @Override
    299    public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info) {
    300        if (!iModel.getStudentGroups().isEmpty())
    301            info.put("Student groups", sDF2.format(100.0 * StudentSwapSectioning.group(iModel) / iModel.getStudentGroups().size()) + "%");
    302    }
    303
    304    @Override
    305    public void getInfo(Assignment<Lecture, Placement> assignment, Map<String, String> info, Collection<Lecture> variables) {
    306        if (!iModel.getStudentGroups().isEmpty())
    307            info.put("Student groups", sDF2.format(StudentSwapSectioning.gp(iModel, variables)) + "%");
    308    }
    309
    310    /**
    311     * Must reservations be followed? When true, a student cannot be placed in a section where {@link Student#canEnroll(Lecture)} is false.
    312     * Defaults to false.
    313     */
    314    public boolean isMustFollowReservations() { return iMustFollowReservations; }
    315    /**
    316     * Must reservations be followed? When true, a student cannot be placed in a section where {@link Student#canEnroll(Lecture)} is false.
    317     * Defaults to false.
    318     */
    319    public void setMustFollowReservations(boolean mustFollow) { iMustFollowReservations = mustFollow; }
    320}