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