001    package net.sf.cpsolver.coursett.custom;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.Comparator;
006    import java.util.Iterator;
007    import java.util.Set;
008    import java.util.TreeSet;
009    
010    import net.sf.cpsolver.coursett.model.Configuration;
011    import net.sf.cpsolver.coursett.model.DefaultStudentSectioning;
012    import net.sf.cpsolver.coursett.model.InitialSectioning;
013    import net.sf.cpsolver.coursett.model.InitialSectioning.Group;
014    import net.sf.cpsolver.coursett.model.Lecture;
015    import net.sf.cpsolver.coursett.model.Student;
016    import net.sf.cpsolver.coursett.model.StudentSectioning;
017    import net.sf.cpsolver.coursett.model.TimetableModel;
018    import 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 Tomas Muller<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     */
050    public 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 Tomas Muller
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    }