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