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