001    package net.sf.cpsolver.coursett.model;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.HashSet;
006    import java.util.HashMap;
007    import java.util.Iterator;
008    import java.util.List;
009    
010    import net.sf.cpsolver.ifs.util.Progress;
011    
012    /**
013     * Student initial sectioning (before a solver is started). <br>
014     * <br>
015     * Many course offerings consist of multiple classes, with students enrolled in
016     * the course divided among them. These classes are often linked by a set of
017     * constraints, namely:
018     * <ul>
019     * <li>Each class has a limit stating the maximum number of students who can be
020     * enrolled in it.
021     * <li>A student must be enrolled in exactly one class for each subpart of a
022     * course.
023     * <li>If two subparts of a course have a parent�child relationship, a student
024     * enrolled in the parent class must also be enrolled in one of the child
025     * classes.
026     * </ul>
027     * Moreover, some of the classes of an offering may be required or prohibited
028     * for certain students, based on reservations that can be set on an offering, a
029     * configuration, or a class. <br>
030     * Before implementing the solver, an initial sectioning of students into
031     * classes is processed. This sectioning is based on Carter�s homogeneous
032     * sectioning and is intended to minimize future student conflicts. However, it
033     * is still possible to improve on the number of student conflicts in the
034     * solution. This can be accomplished by moving students between alternative
035     * classes of the same course during or after the search (see
036     * {@link FinalSectioning}).
037     * 
038     * @version CourseTT 1.2 (University Course Timetabling)<br>
039     *          Copyright (C) 2006 - 2010 Tomas Muller<br>
040     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
041     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
042     * <br>
043     *          This library is free software; you can redistribute it and/or modify
044     *          it under the terms of the GNU Lesser General Public License as
045     *          published by the Free Software Foundation; either version 3 of the
046     *          License, or (at your option) any later version. <br>
047     * <br>
048     *          This library is distributed in the hope that it will be useful, but
049     *          WITHOUT ANY WARRANTY; without even the implied warranty of
050     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
051     *          Lesser General Public License for more details. <br>
052     * <br>
053     *          You should have received a copy of the GNU Lesser General Public
054     *          License along with this library; if not see
055     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
056     */
057    public class InitialSectioning {
058        Collection<Student> iStudents = null;
059        Group[] iGroups = null;
060        Long iOfferingId = null;
061        Progress iProgress = null;
062    
063        public InitialSectioning(Progress progress, Long offeringId, Collection<?> lectureOrConfigurations,
064                Collection<Student> students) {
065            iOfferingId = offeringId;
066            iStudents = new HashSet<Student>(students);
067            iProgress = progress;
068    
069            iGroups = new Group[lectureOrConfigurations.size()];
070    
071            int idx = 0;
072            double total = 0;
073            for (Iterator<?> i = lectureOrConfigurations.iterator(); i.hasNext(); idx++) {
074                Object lectureOrConfiguration = i.next();
075                if (lectureOrConfiguration instanceof Lecture) {
076                    Lecture lecture = (Lecture) lectureOrConfiguration;
077                    iGroups[idx] = new Group(lecture);
078                } else {
079                    Configuration configuration = (Configuration) lectureOrConfiguration;
080                    iGroups[idx] = new Group(configuration);
081                }
082                total += iGroups[idx].getMaxSize();
083            }
084    
085            if (total == 0) {
086                for (idx = 0; idx < iGroups.length; idx++) {
087                    iGroups[idx].setMaxSize(1);
088                    total++;
089                }
090            }
091    
092            double studentsWeight = 0;
093            for (Student s : iStudents) {
094                studentsWeight += s.getOfferingWeight(iOfferingId);
095            }
096    
097            double factor = studentsWeight / total;
098            for (idx = 0; idx < iGroups.length; idx++) {
099                iGroups[idx].setMaxSize(factor * iGroups[idx].getMaxSize());
100                iGroups[idx].setMinSize(Math.min(iGroups[idx].getMinSize(), 0.9 * iGroups[idx].getMaxSize()));
101            }
102    
103            progress.trace("Initial sectioning:");
104            progress.trace("  going to section " + iStudents.size() + " into " + total + " seats");
105            for (idx = 0; idx < iGroups.length; idx++)
106                progress.trace("    " + (idx + 1) + ". group can accomodate <" + iGroups[idx].getMinSize() + ","
107                        + iGroups[idx].getMaxSize() + "> students");
108        }
109    
110        public void addStudent(Student student) {
111            iStudents.add(student);
112        }
113    
114        private boolean moveAwayOneStudent(Group group) {
115            Group newGroup = null;
116            Student movingStudent = null;
117            double curDist = 0, newDist = 0;
118    
119            for (Student student : group.getStudents()) {
120                if (group.isEnrolled(student))
121                    continue;
122                double cd = group.getDistance(student);
123                for (int x = 0; x < iGroups.length; x++) {
124                    if (group.equals(iGroups[x]))
125                        continue;
126                    if (iGroups[x].size() > iGroups[x].getMaxSize())
127                        continue;
128                    if (!iGroups[x].canEnroll(student))
129                        continue;
130                    double nd = iGroups[x].getDistance(student);
131                    if (newGroup == null || newDist - curDist < nd - cd) {
132                        newGroup = iGroups[x];
133                        movingStudent = student;
134                        curDist = cd;
135                        newDist = nd;
136                        if (newDist - curDist < 0.01)
137                            break;
138                    }
139                }
140            }
141    
142            if (newGroup != null) {
143                group.removeStudent(movingStudent);
144                newGroup.addStudent(movingStudent);
145                return true;
146            }
147    
148            return false;
149        }
150    
151        public boolean moveIntoOneStudent(Group group) {
152            Group oldGroup = null;
153            Student movingStudent = null;
154            double curDist = 0, newDist = 0;
155    
156            for (int x = 0; x < iGroups.length; x++) {
157                if (group.equals(iGroups[x]))
158                    continue;
159                if (iGroups[x].size() <= iGroups[x].getMinSize())
160                    continue;
161                for (Student student : iGroups[x].getStudents()) {
162                    if (!group.canEnroll(student))
163                        continue;
164                    if (iGroups[x].isEnrolled(student))
165                        continue;
166                    double cd = iGroups[x].getDistance(student);
167                    double nd = group.getDistance(student);
168                    if (oldGroup == null || newDist - curDist < nd - cd) {
169                        oldGroup = iGroups[x];
170                        movingStudent = student;
171                        curDist = cd;
172                        newDist = nd;
173                        if (newDist - curDist < 0.01)
174                            break;
175                    }
176                }
177            }
178    
179            if (oldGroup != null) {
180                oldGroup.removeStudent(movingStudent);
181                group.addStudent(movingStudent);
182                return true;
183            }
184    
185            return false;
186        }
187    
188        public Group[] getGroups() {
189            double minDist = 1.0 / iGroups.length;
190    
191            for (Iterator<Student> i = iStudents.iterator(); i.hasNext();) {
192                Student student = i.next();
193                Group group = null;
194                for (int idx = 0; idx < iGroups.length; idx++) {
195                    if (iGroups[idx].isEnrolled(student)) {
196                        group = iGroups[idx];
197                        break;
198                    }
199                }
200                if (group != null) {
201                    group.addStudent(student);
202                    i.remove();
203                }
204            }
205    
206            for (Student student : iStudents) {
207                double studentWeight = student.getOfferingWeight(iOfferingId);
208    
209                Group group = null;
210                double dist = 0.0;
211                for (int idx = 0; idx < iGroups.length; idx++) {
212                    Group g = iGroups[idx];
213                    if (!g.canEnroll(student))
214                        continue;
215                    if (g.size() + studentWeight > g.getMaxSize())
216                        continue;
217                    double d = g.getDistance(student);
218                    if (group == null || d < dist) {
219                        group = g;
220                        dist = d;
221                        if (d < minDist)
222                            break;
223                    }
224                }
225    
226                if (group != null) {
227                    group.addStudent(student);
228                    continue;
229                }
230    
231                // disobey max size, but prefer sections with smallest excess
232                int excess = 0;
233                for (int idx = 0; idx < iGroups.length; idx++) {
234                    Group g = iGroups[idx];
235                    if (!g.canEnroll(student))
236                        continue;
237                    double d = g.getDistance(student);
238                    int ex = (int)Math.round(g.size() + studentWeight - g.getMaxSize());
239                    if (group == null || ex < excess || (ex == excess && d < dist)) {
240                        group = g;
241                        dist = d;
242                        excess = ex;
243                    }
244                }
245    
246                if (group != null) {
247                    group.addStudent(student);
248                    continue;
249                }
250    
251                // disobey max size & can enroll
252                for (int idx = 0; idx < iGroups.length; idx++) {
253                    Group g = iGroups[idx];
254                    double d = g.getDistance(student);
255                    if (group == null || d < dist) {
256                        group = g;
257                        dist = d;
258                    }
259                }
260    
261                iProgress.debug("Unable to find a valid section for student "
262                        + student.getId()
263                        + ", enrolling to "
264                        + (group.getLecture() != null ? group.getLecture().getName() : group.getConfiguration()
265                                .getConfigId().toString()));
266    
267                group.addStudent(student);
268            }
269    
270            for (int idx = 0; idx < iGroups.length; idx++) {
271                Group group = iGroups[idx];
272    
273                while (group.size() > group.getMaxSize()) {
274                    if (!moveAwayOneStudent(group))
275                        break;
276                }
277    
278                while (group.size() > group.getMaxSize()) {
279    
280                    Group newGroup = null;
281                    Student movingStudent = null;
282    
283                    for (Student student : group.getStudents()) {
284                        if (group.isEnrolled(student))
285                            continue;
286                        for (int x = 0; x < iGroups.length; x++) {
287                            if (idx == x)
288                                continue;
289                            if (!iGroups[x].canEnroll(student))
290                                continue;
291                            while (iGroups[x].size() + student.getOfferingWeight(iOfferingId) > iGroups[x].getMaxSize()) {
292                                if (!moveAwayOneStudent(iGroups[x]))
293                                    break;
294                            }
295                            if (iGroups[x].size() + student.getOfferingWeight(iOfferingId) > iGroups[x].getMaxSize())
296                                continue;
297                            newGroup = iGroups[x];
298                            movingStudent = student;
299                            break;
300                        }
301                        if (newGroup != null)
302                            break;
303                    }
304    
305                    if (newGroup != null) {
306                        group.removeStudent(movingStudent);
307                        newGroup.addStudent(movingStudent);
308                    } else {
309                        break;
310                    }
311                }
312    
313                while (group.size() < group.getMinSize()) {
314                    if (!moveIntoOneStudent(group))
315                        break;
316                }
317            }
318    
319            return iGroups;
320        }
321    
322        public class Group {
323            private ArrayList<Student> iStudents = new ArrayList<Student>();
324            private Lecture iLecture = null;
325            private Configuration iConfiguration = null;
326            private Double iDist = null;
327            private double iMinSize = 0, iMaxSize = 0;
328            private HashMap<Student, Double> iDistCache = new HashMap<Student, Double>();
329            private double iSize = 0.0;
330    
331            public Group(Lecture lecture) {
332                iLecture = lecture;
333                iMinSize = lecture.minClassLimit();
334                iMaxSize = lecture.maxAchievableClassLimit();
335            }
336    
337            public Group(Configuration configuration) {
338                iConfiguration = configuration;
339                iMinSize = iMaxSize = iConfiguration.getLimit();
340            }
341    
342            public Configuration getConfiguration() {
343                return iConfiguration;
344            }
345    
346            public Lecture getLecture() {
347                return iLecture;
348            }
349    
350            public double getMinSize() {
351                return iMinSize;
352            }
353    
354            public double getMaxSize() {
355                return iMaxSize;
356            }
357    
358            public void setMinSize(double minSize) {
359                iMinSize = minSize;
360            }
361    
362            public void setMaxSize(double maxSize) {
363                iMaxSize = maxSize;
364            }
365    
366            public double getDistance() {
367                if (iDist == null) {
368                    double dist = 0.0;
369                    double prob = 10.0 / iStudents.size();
370                    int cnt = 0;
371                    for (Student s1 : iStudents) {
372                        if (Math.random() < prob) {
373                            for (Student s2 : iStudents) {
374                                if (s1.getId().compareTo(s2.getId()) <= 0)
375                                    continue;
376                                if (Math.random() < prob) {
377                                    dist += s1.getDistance(s2);
378                                    cnt++;
379                                }
380                            }
381                        }
382                    }
383                    iDist = new Double(dist / cnt);
384                }
385                return iDist.doubleValue();
386            }
387    
388            public double getDistance(Student student) {
389                Double cachedDist = iDistCache.get(student);
390                if (cachedDist != null)
391                    return cachedDist.doubleValue();
392                double dist = 0.0;
393                double prob = 10.0 / iStudents.size();
394                int cnt = 0;
395                for (Student s : iStudents) {
396                    if (prob >= 1.0 || Math.random() < prob) {
397                        dist += s.getDistance(student);
398                        cnt++;
399                    }
400                }
401                iDistCache.put(student, new Double(dist / cnt));
402                return dist / cnt;
403            }
404    
405            public void addStudent(Student student) {
406                iStudents.add(student);
407                iSize += student.getOfferingWeight(iOfferingId);
408                iDist = null;
409                iDistCache.clear();
410            }
411    
412            public void removeStudent(Student student) {
413                iStudents.remove(student);
414                iSize -= student.getOfferingWeight(iOfferingId);
415                iDist = null;
416                iDistCache.clear();
417            }
418    
419            public List<Student> getStudents() {
420                return iStudents;
421            }
422    
423            public double size() {
424                return iSize;
425            }
426    
427            @Override
428            public String toString() {
429                return "{" + size() + "-" + getDistance() + "/" + getStudents() + "}";
430            }
431    
432            public boolean canEnroll(Student student) {
433                if (getLecture() != null) {
434                    return student.canEnroll(getLecture());
435                } else {
436                    for (Long subpartId: getConfiguration().getTopSubpartIds()) {
437                        boolean canEnrollThisSubpart = false;
438                        for (Lecture lecture : getConfiguration().getTopLectures(subpartId)) {
439                            if (student.canEnroll(lecture)) {
440                                canEnrollThisSubpart = true;
441                                break;
442                            }
443                        }
444                        if (!canEnrollThisSubpart)
445                            return false;
446                    }
447                    return true;
448                }
449            }
450    
451            public boolean isEnrolled(Student student) {
452                if (getLecture() != null) {
453                    return student.getLectures().contains(getLecture());
454                } else {
455                    for (Lecture lect : student.getLectures()) {
456                        if (lect.getConfiguration().equals(getConfiguration()))
457                            return true;
458                    }
459                    return false;
460                }
461    
462            }
463        }
464    
465        public static void initialSectioningCfg(Progress p, Long offeringId, String courseName, Collection<Student> students,
466                List<Configuration> configurations) {
467            if (students == null || students.isEmpty())
468                return;
469            if (configurations == null || configurations.isEmpty())
470                return;
471            if (configurations.size() == 1) {
472                Configuration cfg = configurations.get(0);
473                for (Student st : students) {
474                    st.addConfiguration(cfg);
475                }
476                for (Long subpartId: cfg.getTopSubpartIds()) {
477                    initialSectioning(p, offeringId, courseName, students, cfg.getTopLectures(subpartId));
478                }
479            } else {
480                p.trace("sectioning " + students.size() + " students of course " + courseName + " into "
481                        + configurations.size() + " configurations");
482                InitialSectioning sect = new InitialSectioning(p, offeringId, configurations, students);
483                Group[] studentsPerSection = sect.getGroups();
484                for (int i = 0; i < configurations.size(); i++) {
485                    Group group = studentsPerSection[i];
486                    p.trace((i + 1) + ". configuration got " + group.getStudents().size() + " students (weighted="
487                            + group.size() + ", cfgLimit=" + group.getConfiguration().getLimit() + ")");
488                    for (Student st : group.getStudents()) {
489                        st.addConfiguration(group.getConfiguration());
490                    }
491                    for (Long subpartId: group.getConfiguration().getTopSubpartIds()) {
492                        initialSectioning(p, offeringId, courseName, group.getStudents(), group.getConfiguration()
493                                .getTopLectures(subpartId));
494                    }
495                }
496            }
497        }
498    
499        private static String getClassLabel(Lecture lecture) {
500            return "<A href='classDetail.do?cid=" + lecture.getClassId() + "'>" + lecture.getName() + "</A>";
501        }
502    
503        private static void initialSectioning(Progress p, Long offeringId, String parentName, Collection<Student> students,
504                Collection<Lecture> lectures) {
505            if (lectures == null || lectures.isEmpty())
506                return;
507            if (students == null || students.isEmpty())
508                return;
509            for (Lecture lecture : lectures) {
510                if (lecture.classLimit() == 0 && !lecture.isCommitted())
511                    p.warn("Class " + getClassLabel(lecture) + " has zero class limit.");
512            }
513    
514            p.trace("sectioning " + students.size() + " students of course " + parentName + " into " + lectures.size()
515                    + " sections");
516            if (lectures.size() == 1) {
517                Lecture lect = lectures.iterator().next();
518                for (Student st : students) {
519                    if (!st.canEnroll(lect)) {
520                        p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect));
521                    }
522                    lect.addStudent(st);
523                    st.addLecture(lect);
524                }
525                if (lect.hasAnyChildren()) {
526                    for (Long subpartId: lect.getChildrenSubpartIds()) {
527                        List<Lecture> children = lect.getChildren(subpartId);
528                        initialSectioning(p, offeringId, lect.getName(), students, children);
529                    }
530                }
531            } else {
532                InitialSectioning sect = new InitialSectioning(p, offeringId, lectures, students);
533                Group[] studentsPerSection = sect.getGroups();
534                for (int i = 0; i < studentsPerSection.length; i++) {
535                    Group group = studentsPerSection[i];
536                    Lecture lect = group.getLecture();
537                    if (group.getStudents().isEmpty()) {
538                        p.trace("Lecture " + getClassLabel(lect) + " got no students (cl=" + lect.classLimit() + ")");
539                        continue;
540                    }
541                    p.trace("Lecture " + getClassLabel(lect) + " got " + group.getStudents().size()
542                            + " students (weighted=" + group.size() + ", classLimit=" + lect.classLimit() + ")");
543                    List<Student> studentsThisSection = group.getStudents();
544                    for (Student st : studentsThisSection) {
545                        if (!st.canEnroll(lect)) {
546                            p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect));
547                        }
548                        lect.addStudent(st);
549                        st.addLecture(lect);
550                    }
551                    if (lect.hasAnyChildren()) {
552                        for (Long subpartId: lect.getChildrenSubpartIds()) {
553                            List<Lecture> children = lect.getChildren(subpartId);
554                            initialSectioning(p, offeringId, lect.getName(), studentsThisSection, children);
555                        }
556                    }
557                }
558            }
559        }
560    
561    }