001package net.sf.cpsolver.coursett.model;
002
003import java.util.ArrayList;
004import java.util.Collection;
005import java.util.HashSet;
006import java.util.HashMap;
007import java.util.Iterator;
008import java.util.List;
009
010import 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 Tomáš Müller<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 */
057public 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}