    001package net.sf.cpsolver.coursett.custom;
    002
    003import java.util.ArrayList;
    004import java.util.Collection;
    005import java.util.Comparator;
    006import java.util.Iterator;
    007import java.util.Set;
    008import java.util.TreeSet;
    009
    010import net.sf.cpsolver.coursett.model.Configuration;
    011import net.sf.cpsolver.coursett.model.DefaultStudentSectioning;
    012import net.sf.cpsolver.coursett.model.InitialSectioning;
    013import net.sf.cpsolver.coursett.model.InitialSectioning.Group;
    014import net.sf.cpsolver.coursett.model.Lecture;
    015import net.sf.cpsolver.coursett.model.Student;
    016import net.sf.cpsolver.coursett.model.StudentSectioning;
    017import net.sf.cpsolver.coursett.model.TimetableModel;
    018import net.sf.cpsolver.ifs.util.Progress;
    019
    020/**
    021 * Deterministic implementation of the initial student sectioning. This class assign students to groups in
    022 * a deterministic way. Students are ordered by their academic information (curriculum) and unique ids and
    023 * assigned in this order to the first available group (configuration or lecture). See {@link StudentSectioning}
    024 * and {@link DefaultStudentSectioning} for more details about sectioning students during course timetabling.
    025 * <br><br>
    026 * This deterministic sectioning can be enabled by setting the following parameter:<ul>
    027 * <code>StudentSectioning.Class=net.sf.cpsolver.coursett.custom.DeterministicStudentSectioning</code>
    028 * </ul>
    029 *
    030 * @version CourseTT 1.2 (University Course Timetabling)<br>
    031 *          Copyright (C) 2014 Tomáš Müller<br>
    032 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    033 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    034 *          This customization has been implemented for <a href='http://www.agh.pl'>AGH, Poland</a>.<br>
    035 * <br>
    036 *          This library is free software; you can redistribute it and/or modify
    037 *          it under the terms of the GNU Lesser General Public License as
    038 *          published by the Free Software Foundation; either version 3 of the
    039 *          License, or (at your option) any later version. <br>
    040 * <br>
    041 *          This library is distributed in the hope that it will be useful, but
    042 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    043 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    044 *          Lesser General Public License for more details. <br>
    045 * <br>
    046 *          You should have received a copy of the GNU Lesser General Public
    047 *          License along with this library; if not see
    048 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    049 */
    050public class DeterministicStudentSectioning extends DefaultStudentSectioning {
    051    public DeterministicStudentSectioning(TimetableModel model) {
    052        super(model);
    053    }
    054
    055    @Override
    056    protected Group[] studentsToConfigurations(Long offeringId, Collection<Student> students, Collection<Configuration> configurations) {
    057        DeterministicInitialSectioning sect = new DeterministicInitialSectioning(getProgress(), offeringId, configurations, students);
    058        return sect.getGroups();
    059    }
    060
    061    @Override
    062    protected Group[] studentsToLectures(Long offeringId, Collection<Student> students, Collection<Lecture> lectures) {
    063        Set<Lecture> sortedLectures = new TreeSet<Lecture>(new Comparator<Lecture>() {
    064            @Override
    065            public int compare(Lecture l1, Lecture l2) {
    066                return l1.getClassId().compareTo(l2.getClassId());
    067            }
    068        });
    069        sortedLectures.addAll(lectures);
    070        DeterministicInitialSectioning sect = new DeterministicInitialSectioning(getProgress(), offeringId, sortedLectures, students);
    071        return sect.getGroups();
    072    }
    073
    074    /**
    075     * No re-sectioning (final sectioning) during deterministic student sectioning.
    076     */
    077    @Override
    078    public boolean hasFinalSectioning() {
    079        return false;
    080    }
    081
    082    /**
    083     * No re-sectioning (final sectioning) during deterministic student sectioning.
    084     */
    085    @Override
    086    public void switchStudents(TimetableModel model) {
    087    }
    088
    089    /**
    090     * No re-sectioning (final sectioning) during deterministic student sectioning.
    091     */
    092    @Override
    093    public void resection(Lecture lecture, boolean recursive, boolean configAsWell) {
    094    }
    095
    096    /**
    097     * Assign students to groups in a deterministic way, i.e., first student to first available group etc.
    098     * @author Tomáš Müller
    099     */
    100    public class DeterministicInitialSectioning extends InitialSectioning implements Comparator<Student> {
    101
    102        public DeterministicInitialSectioning(Progress progress, Long offeringId, Collection<?> lectureOrConfigurations, Collection<Student> students) {
    103            super(progress, offeringId, lectureOrConfigurations, students);
    104
    105            // Sort students by their curriculum information first
    106            iStudents = new TreeSet<Student>(this); iStudents.addAll(students);
    107        }
    108
    109        @Override
    110        protected void tweakSizes(double total) {
    111            double studentsWeight = 0;
    112            for (Student s : iStudents) {
    113                studentsWeight += s.getOfferingWeight(iOfferingId);
    114            }
    115
    116            // if there is not enough space for the given students
    117            if (studentsWeight > total) {
    118                if (total == 0) {
    119                    // all limits are zero -> spread students equally
    120                    for (int idx = 0; idx < iGroups.length; idx++)
    121                        iGroups[idx].setMaxSize(total / iGroups.length);
    122                } else {
    123                    // enlarge sections proportionally
    124                    double factor = studentsWeight / total;
    125                    for (int idx = 0; idx < iGroups.length; idx++) {
    126                        iGroups[idx].setMaxSize(factor * iGroups[idx].getMaxSize());
    127                        iGroups[idx].setMinSize(Math.min(iGroups[idx].getMinSize(), 0.9 * iGroups[idx].getMaxSize()));
    128                   }
    129                }
    130            }
    131        }
    132
    133        @Override
    134        public Group[] getGroups() {
    135            // Assign already enrolled students first
    136            students: for (Iterator<Student> i = iStudents.iterator(); i.hasNext();) {
    137                Student student = i.next();
    138                for (int idx = 0; idx < iGroups.length; idx++) {
    139                    if (iGroups[idx].isEnrolled(student)) {
    140                        iGroups[idx].addStudent(student);
    141                        i.remove();
    142                        continue students;
    143                    }
    144                }
    145            }
    146
    147            // For all other (not enrolled) students
    148            students: for (Student student : iStudents) {
    149                double studentWeight = student.getOfferingWeight(iOfferingId);
    150
    151                // enroll into first available group with enough space
    152                for (int idx = 0; idx < iGroups.length; idx++) {
    153                    Group g = iGroups[idx];
    154                    if (!g.canEnroll(student) || g.size() >= g.getMaxSize()) continue;
    155                    // group found -> enroll and continue with the next student
    156                    g.addStudent(student);
    157                    continue students;
    158                }
    159
    160                // disobey max size, but prefer sections with smallest excess
    161                Group group = null; int excess = 0;
    162                for (int idx = 0; idx < iGroups.length; idx++) {
    163                    Group g = iGroups[idx];
    164                    if (!g.canEnroll(student)) continue;
    165                    int ex = (int)Math.round(g.size() + studentWeight - g.getMaxSize());
    166                    if (group == null || ex < excess) {
    167                        group = g;
    168                        excess = ex;
    169                    }
    170                }
    171
    172                if (group != null) {
    173                    group.addStudent(student);
    174                    continue;
    175                }
    176
    177                // put the student into the first group
    178                getProgress().debug("Unable to find a valid section for student " + student.getId() + ", enrolling to " + (iGroups[0].getLecture() != null ? iGroups[0].getLecture().getName() : iGroups[0].getConfiguration().getConfigId().toString()));
    179                iGroups[0].addStudent(student);
    180            }
    181
    182            // try to move students away from groups with an excess of more than a student
    183            for (int idx = 0; idx < iGroups.length; idx++) {
    184                Group group = iGroups[idx];
    185                if (group.size() > group.getMaxSize()) {
    186                    // for each student of a group that is not enrolled in it
    187                    for (Student student : new ArrayList<Student>(group.getStudents())) {
    188                        if (group.isEnrolled(student)) continue;
    189                        // excess of a fraction of a student is allowed
    190                        if (group.size() - student.getOfferingWeight(iOfferingId) < group.getMaxSize()) continue;
    191                        // look for an available group with enough space
    192                        for (int x = 0; x < iGroups.length; x++) {
    193                            if (idx == x) continue;
    194                            if (!iGroups[x].canEnroll(student) || iGroups[x].size() >= iGroups[x].getMaxSize()) continue;
    195                            // group found, move the student away
    196                            group.removeStudent(student);
    197                            iGroups[x].addStudent(student);
    198                            break;
    199                        }
    200                        if (group.size() <= group.getMaxSize()) break;
    201                    }
    202                }
    203            }
    204
    205            return iGroups;
    206        }
    207
    208        /**
    209         * Sort students by their curriculum information and id
    210         */
    211        @Override
    212        public int compare(Student s1, Student s2) {
    213            int cmp = (s1.getCurriculum() == null ? "" : s1.getCurriculum()).compareToIgnoreCase(s2.getCurriculum() == null ? "" : s2.getCurriculum());
    214            if (cmp != 0) return cmp;
    215            cmp = (s1.getAcademicArea() == null ? "" : s1.getAcademicArea()).compareToIgnoreCase(s2.getAcademicArea() == null ? "" : s2.getAcademicArea());
    216            if (cmp != 0) return cmp;
    217            cmp = (s1.getMajor() == null ? "" : s1.getMajor()).compareToIgnoreCase(s2.getMajor() == null ? "" : s2.getMajor());
    218            if (cmp != 0) return cmp;
    219            cmp = (s1.getAcademicClassification() == null ? "" : s1.getAcademicClassification()).compareToIgnoreCase(s2.getAcademicClassification() == null ? "" : s2.getAcademicClassification());
    220            if (cmp != 0) return cmp;
    221            return s1.getId().compareTo(s2.getId());
    222        }
    223    }
    224}