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}