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        protected Collection<Student> iStudents = null;
059        protected Group[] iGroups = null;
060        protected Long iOfferingId = null;
061        protected 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            tweakSizes(total);
086    
087            progress.trace("Initial sectioning:");
088            progress.trace("  going to section " + iStudents.size() + " into " + total + " seats");
089            for (idx = 0; idx < iGroups.length; idx++)
090                progress.trace("    " + (idx + 1) + ". group can accomodate <" + iGroups[idx].getMinSize() + ","
091                        + iGroups[idx].getMaxSize() + "> students");
092        }
093        
094        protected void tweakSizes(double total) {
095            if (total == 0) {
096                for (int idx = 0; idx < iGroups.length; idx++) {
097                    iGroups[idx].setMaxSize(1);
098                    total++;
099                }
100            }
101    
102            double studentsWeight = 0;
103            for (Student s : iStudents) {
104                studentsWeight += s.getOfferingWeight(iOfferingId);
105            }
106    
107            double factor = studentsWeight / total;
108            for (int idx = 0; idx < iGroups.length; idx++) {
109                iGroups[idx].setMaxSize(factor * iGroups[idx].getMaxSize());
110                iGroups[idx].setMinSize(Math.min(iGroups[idx].getMinSize(), 0.9 * iGroups[idx].getMaxSize()));
111            }
112        }
113    
114        public void addStudent(Student student) {
115            iStudents.add(student);
116        }
117    
118        private boolean moveAwayOneStudent(Group group) {
119            Group newGroup = null;
120            Student movingStudent = null;
121            double curDist = 0, newDist = 0;
122    
123            for (Student student : group.getStudents()) {
124                if (group.isEnrolled(student))
125                    continue;
126                double cd = group.getDistance(student);
127                for (int x = 0; x < iGroups.length; x++) {
128                    if (group.equals(iGroups[x]))
129                        continue;
130                    if (iGroups[x].size() > iGroups[x].getMaxSize())
131                        continue;
132                    if (!iGroups[x].canEnroll(student))
133                        continue;
134                    double nd = iGroups[x].getDistance(student);
135                    if (newGroup == null || newDist - curDist < nd - cd) {
136                        newGroup = iGroups[x];
137                        movingStudent = student;
138                        curDist = cd;
139                        newDist = nd;
140                        if (newDist - curDist < 0.01)
141                            break;
142                    }
143                }
144            }
145    
146            if (newGroup != null) {
147                group.removeStudent(movingStudent);
148                newGroup.addStudent(movingStudent);
149                return true;
150            }
151    
152            return false;
153        }
154    
155        public boolean moveIntoOneStudent(Group group) {
156            Group oldGroup = null;
157            Student movingStudent = null;
158            double curDist = 0, newDist = 0;
159    
160            for (int x = 0; x < iGroups.length; x++) {
161                if (group.equals(iGroups[x]))
162                    continue;
163                if (iGroups[x].size() <= iGroups[x].getMinSize())
164                    continue;
165                for (Student student : iGroups[x].getStudents()) {
166                    if (!group.canEnroll(student))
167                        continue;
168                    if (iGroups[x].isEnrolled(student))
169                        continue;
170                    double cd = iGroups[x].getDistance(student);
171                    double nd = group.getDistance(student);
172                    if (oldGroup == null || newDist - curDist < nd - cd) {
173                        oldGroup = iGroups[x];
174                        movingStudent = student;
175                        curDist = cd;
176                        newDist = nd;
177                        if (newDist - curDist < 0.01)
178                            break;
179                    }
180                }
181            }
182    
183            if (oldGroup != null) {
184                oldGroup.removeStudent(movingStudent);
185                group.addStudent(movingStudent);
186                return true;
187            }
188    
189            return false;
190        }
191    
192        public Group[] getGroups() {
193            double minDist = 1.0 / iGroups.length;
194    
195            for (Iterator<Student> i = iStudents.iterator(); i.hasNext();) {
196                Student student = i.next();
197                Group group = null;
198                for (int idx = 0; idx < iGroups.length; idx++) {
199                    if (iGroups[idx].isEnrolled(student)) {
200                        group = iGroups[idx];
201                        break;
202                    }
203                }
204                if (group != null) {
205                    group.addStudent(student);
206                    i.remove();
207                }
208            }
209    
210            for (Student student : iStudents) {
211                double studentWeight = student.getOfferingWeight(iOfferingId);
212    
213                Group group = null;
214                double dist = 0.0;
215                for (int idx = 0; idx < iGroups.length; idx++) {
216                    Group g = iGroups[idx];
217                    if (!g.canEnroll(student))
218                        continue;
219                    if (g.size() + studentWeight > g.getMaxSize())
220                        continue;
221                    double d = g.getDistance(student);
222                    if (group == null || d < dist) {
223                        group = g;
224                        dist = d;
225                        if (d < minDist)
226                            break;
227                    }
228                }
229    
230                if (group != null) {
231                    group.addStudent(student);
232                    continue;
233                }
234    
235                // disobey max size, but prefer sections with smallest excess
236                int excess = 0;
237                for (int idx = 0; idx < iGroups.length; idx++) {
238                    Group g = iGroups[idx];
239                    if (!g.canEnroll(student))
240                        continue;
241                    double d = g.getDistance(student);
242                    int ex = (int)Math.round(g.size() + studentWeight - g.getMaxSize());
243                    if (group == null || ex < excess || (ex == excess && d < dist)) {
244                        group = g;
245                        dist = d;
246                        excess = ex;
247                    }
248                }
249    
250                if (group != null) {
251                    group.addStudent(student);
252                    continue;
253                }
254    
255                // disobey max size & can enroll
256                for (int idx = 0; idx < iGroups.length; idx++) {
257                    Group g = iGroups[idx];
258                    double d = g.getDistance(student);
259                    if (group == null || d < dist) {
260                        group = g;
261                        dist = d;
262                    }
263                }
264    
265                iProgress.debug("Unable to find a valid section for student "
266                        + student.getId()
267                        + ", enrolling to "
268                        + (group.getLecture() != null ? group.getLecture().getName() : group.getConfiguration()
269                                .getConfigId().toString()));
270    
271                group.addStudent(student);
272            }
273    
274            for (int idx = 0; idx < iGroups.length; idx++) {
275                Group group = iGroups[idx];
276    
277                while (group.size() > group.getMaxSize()) {
278                    if (!moveAwayOneStudent(group))
279                        break;
280                }
281    
282                while (group.size() > group.getMaxSize()) {
283    
284                    Group newGroup = null;
285                    Student movingStudent = null;
286    
287                    for (Student student : group.getStudents()) {
288                        if (group.isEnrolled(student))
289                            continue;
290                        for (int x = 0; x < iGroups.length; x++) {
291                            if (idx == x)
292                                continue;
293                            if (!iGroups[x].canEnroll(student))
294                                continue;
295                            while (iGroups[x].size() + student.getOfferingWeight(iOfferingId) > iGroups[x].getMaxSize()) {
296                                if (!moveAwayOneStudent(iGroups[x]))
297                                    break;
298                            }
299                            if (iGroups[x].size() + student.getOfferingWeight(iOfferingId) > iGroups[x].getMaxSize())
300                                continue;
301                            newGroup = iGroups[x];
302                            movingStudent = student;
303                            break;
304                        }
305                        if (newGroup != null)
306                            break;
307                    }
308    
309                    if (newGroup != null) {
310                        group.removeStudent(movingStudent);
311                        newGroup.addStudent(movingStudent);
312                    } else {
313                        break;
314                    }
315                }
316    
317                while (group.size() < group.getMinSize()) {
318                    if (!moveIntoOneStudent(group))
319                        break;
320                }
321            }
322    
323            return iGroups;
324        }
325    
326        public class Group {
327            private ArrayList<Student> iStudents = new ArrayList<Student>();
328            private Lecture iLecture = null;
329            private Configuration iConfiguration = null;
330            private Double iDist = null;
331            private double iMinSize = 0, iMaxSize = 0;
332            private HashMap<Student, Double> iDistCache = new HashMap<Student, Double>();
333            private double iSize = 0.0;
334    
335            public Group(Lecture lecture) {
336                iLecture = lecture;
337                iMinSize = lecture.minClassLimit();
338                iMaxSize = lecture.maxAchievableClassLimit();
339            }
340    
341            public Group(Configuration configuration) {
342                iConfiguration = configuration;
343                iMinSize = iMaxSize = iConfiguration.getLimit();
344            }
345    
346            public Configuration getConfiguration() {
347                return iConfiguration;
348            }
349    
350            public Lecture getLecture() {
351                return iLecture;
352            }
353    
354            public double getMinSize() {
355                return iMinSize;
356            }
357    
358            public double getMaxSize() {
359                return iMaxSize;
360            }
361    
362            public void setMinSize(double minSize) {
363                iMinSize = minSize;
364            }
365    
366            public void setMaxSize(double maxSize) {
367                iMaxSize = maxSize;
368            }
369    
370            public double getDistance() {
371                if (iDist == null) {
372                    double dist = 0.0;
373                    double prob = 10.0 / iStudents.size();
374                    int cnt = 0;
375                    for (Student s1 : iStudents) {
376                        if (Math.random() < prob) {
377                            for (Student s2 : iStudents) {
378                                if (s1.getId().compareTo(s2.getId()) <= 0)
379                                    continue;
380                                if (Math.random() < prob) {
381                                    dist += s1.getDistance(s2);
382                                    cnt++;
383                                }
384                            }
385                        }
386                    }
387                    iDist = new Double(dist / cnt);
388                }
389                return iDist.doubleValue();
390            }
391    
392            public double getDistance(Student student) {
393                Double cachedDist = iDistCache.get(student);
394                if (cachedDist != null)
395                    return cachedDist.doubleValue();
396                double dist = 0.0;
397                double prob = 10.0 / iStudents.size();
398                int cnt = 0;
399                for (Student s : iStudents) {
400                    if (prob >= 1.0 || Math.random() < prob) {
401                        dist += s.getDistance(student);
402                        cnt++;
403                    }
404                }
405                iDistCache.put(student, new Double(dist / cnt));
406                return dist / cnt;
407            }
408    
409            public void addStudent(Student student) {
410                iStudents.add(student);
411                iSize += student.getOfferingWeight(iOfferingId);
412                iDist = null;
413                iDistCache.clear();
414            }
415    
416            public void removeStudent(Student student) {
417                iStudents.remove(student);
418                iSize -= student.getOfferingWeight(iOfferingId);
419                iDist = null;
420                iDistCache.clear();
421            }
422    
423            public List<Student> getStudents() {
424                return iStudents;
425            }
426    
427            public double size() {
428                return iSize;
429            }
430    
431            @Override
432            public String toString() {
433                return "{" + size() + "-" + getDistance() + "/" + getStudents() + "}";
434            }
435    
436            public boolean canEnroll(Student student) {
437                if (getLecture() != null) {
438                    return student.canEnroll(getLecture());
439                } else {
440                    for (Long subpartId: getConfiguration().getTopSubpartIds()) {
441                        boolean canEnrollThisSubpart = false;
442                        for (Lecture lecture : getConfiguration().getTopLectures(subpartId)) {
443                            if (student.canEnroll(lecture)) {
444                                canEnrollThisSubpart = true;
445                                break;
446                            }
447                        }
448                        if (!canEnrollThisSubpart)
449                            return false;
450                    }
451                    return true;
452                }
453            }
454    
455            public boolean isEnrolled(Student student) {
456                if (getLecture() != null) {
457                    return student.getLectures().contains(getLecture());
458                } else {
459                    for (Lecture lect : student.getLectures()) {
460                        if (lect.getConfiguration().equals(getConfiguration()))
461                            return true;
462                    }
463                    return false;
464                }
465    
466            }
467        }
468    
469        public static void initialSectioningCfg(Progress p, Long offeringId, String courseName, Collection<Student> students,
470                List<Configuration> configurations) {
471            if (students == null || students.isEmpty())
472                return;
473            if (configurations == null || configurations.isEmpty())
474                return;
475            if (configurations.size() == 1) {
476                Configuration cfg = configurations.get(0);
477                for (Student st : students) {
478                    st.addConfiguration(cfg);
479                }
480                for (Long subpartId: cfg.getTopSubpartIds()) {
481                    initialSectioning(p, offeringId, courseName, students, cfg.getTopLectures(subpartId));
482                }
483            } else {
484                p.trace("sectioning " + students.size() + " students of course " + courseName + " into "
485                        + configurations.size() + " configurations");
486                InitialSectioning sect = new InitialSectioning(p, offeringId, configurations, students);
487                Group[] studentsPerSection = sect.getGroups();
488                for (int i = 0; i < configurations.size(); i++) {
489                    Group group = studentsPerSection[i];
490                    p.trace((i + 1) + ". configuration got " + group.getStudents().size() + " students (weighted="
491                            + group.size() + ", cfgLimit=" + group.getConfiguration().getLimit() + ")");
492                    for (Student st : group.getStudents()) {
493                        st.addConfiguration(group.getConfiguration());
494                    }
495                    for (Long subpartId: group.getConfiguration().getTopSubpartIds()) {
496                        initialSectioning(p, offeringId, courseName, group.getStudents(), group.getConfiguration()
497                                .getTopLectures(subpartId));
498                    }
499                }
500            }
501        }
502    
503        private static String getClassLabel(Lecture lecture) {
504            return "<A href='classDetail.do?cid=" + lecture.getClassId() + "'>" + lecture.getName() + "</A>";
505        }
506    
507        private static void initialSectioning(Progress p, Long offeringId, String parentName, Collection<Student> students,
508                Collection<Lecture> lectures) {
509            if (lectures == null || lectures.isEmpty())
510                return;
511            if (students == null || students.isEmpty())
512                return;
513            for (Lecture lecture : lectures) {
514                if (lecture.classLimit() == 0 && !lecture.isCommitted())
515                    p.warn("Class " + getClassLabel(lecture) + " has zero class limit.");
516            }
517    
518            p.trace("sectioning " + students.size() + " students of course " + parentName + " into " + lectures.size()
519                    + " sections");
520            if (lectures.size() == 1) {
521                Lecture lect = lectures.iterator().next();
522                for (Student st : students) {
523                    if (!st.canEnroll(lect)) {
524                        p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect));
525                    }
526                    lect.addStudent(st);
527                    st.addLecture(lect);
528                }
529                if (lect.hasAnyChildren()) {
530                    for (Long subpartId: lect.getChildrenSubpartIds()) {
531                        List<Lecture> children = lect.getChildren(subpartId);
532                        initialSectioning(p, offeringId, lect.getName(), students, children);
533                    }
534                }
535            } else {
536                InitialSectioning sect = new InitialSectioning(p, offeringId, lectures, students);
537                Group[] studentsPerSection = sect.getGroups();
538                for (int i = 0; i < studentsPerSection.length; i++) {
539                    Group group = studentsPerSection[i];
540                    Lecture lect = group.getLecture();
541                    if (group.getStudents().isEmpty()) {
542                        p.trace("Lecture " + getClassLabel(lect) + " got no students (cl=" + lect.classLimit() + ")");
543                        continue;
544                    }
545                    p.trace("Lecture " + getClassLabel(lect) + " got " + group.getStudents().size()
546                            + " students (weighted=" + group.size() + ", classLimit=" + lect.classLimit() + ")");
547                    List<Student> studentsThisSection = group.getStudents();
548                    for (Student st : studentsThisSection) {
549                        if (!st.canEnroll(lect)) {
550                            p.info("Unable to enroll student " + st.getId() + " in class " + getClassLabel(lect));
551                        }
552                        lect.addStudent(st);
553                        st.addLecture(lect);
554                    }
555                    if (lect.hasAnyChildren()) {
556                        for (Long subpartId: lect.getChildrenSubpartIds()) {
557                            List<Lecture> children = lect.getChildren(subpartId);
558                            initialSectioning(p, offeringId, lect.getName(), studentsThisSection, children);
559                        }
560                    }
561                }
562            }
563        }
564    
565    }