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}