    001package net.sf.cpsolver.studentsct.heuristics.studentord;
    002
    003import java.util.ArrayList;
    004import java.util.Collections;
    005import java.util.Comparator;
    006import java.util.HashSet;
    007import java.util.HashMap;
    008import java.util.List;
    009
    010import net.sf.cpsolver.ifs.util.DataProperties;
    011import net.sf.cpsolver.studentsct.model.Config;
    012import net.sf.cpsolver.studentsct.model.Course;
    013import net.sf.cpsolver.studentsct.model.CourseRequest;
    014import net.sf.cpsolver.studentsct.model.Request;
    015import net.sf.cpsolver.studentsct.model.Section;
    016import net.sf.cpsolver.studentsct.model.Student;
    017import net.sf.cpsolver.studentsct.model.Subpart;
    018
    019/**
    020 * Return the given set of students in an order of average number of choices of
    021 * each student (students with more choices first).
    022 *
    023 * @version StudentSct 1.2 (Student Sectioning)<br>
    024 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    025 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    026 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    027 * <br>
    028 *          This library is free software; you can redistribute it and/or modify
    029 *          it under the terms of the GNU Lesser General Public License as
    030 *          published by the Free Software Foundation; either version 3 of the
    031 *          License, or (at your option) any later version. <br>
    032 * <br>
    033 *          This library is distributed in the hope that it will be useful, but
    034 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    035 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    036 *          Lesser General Public License for more details. <br>
    037 * <br>
    038 *          You should have received a copy of the GNU Lesser General Public
    039 *          License along with this library; if not see
    040 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    041 */
    042public class StudentChoiceOrder implements StudentOrder, Comparator<Student> {
    043    private boolean iReverse = false;
    044    private boolean iFast = true;
    045    private HashMap<Config, Integer> iCache = new HashMap<Config, Integer>();
    046
    047    public StudentChoiceOrder(DataProperties config) {
    048        iReverse = config.getPropertyBoolean("StudentChoiceOrder.Reverse", iReverse);
    049        iFast = config.getPropertyBoolean("StudentChoiceOrder.Fast", iFast);
    050    }
    051
    052    /** Is order reversed */
    053    public boolean isReverse() {
    054        return iReverse;
    055    }
    056
    057    /** Set reverse order */
    058    public void setReverse(boolean reverse) {
    059        iReverse = reverse;
    060    }
    061
    062    /** Order the given list of students */
    063    @Override
    064    public List<Student> order(List<Student> students) {
    065        List<Student> ret = new ArrayList<Student>(students);
    066        Collections.sort(ret, this);
    067        return ret;
    068    }
    069
    070    @Override
    071    public int compare(Student s1, Student s2) {
    072        try {
    073            int cmp = -Double.compare(avgNrChoices(s1), avgNrChoices(s2));
    074            if (cmp != 0)
    075                return (iReverse ? -1 : 1) * cmp;
    076        } catch (Exception e) {
    077            e.printStackTrace();
    078        }
    079        return (iReverse ? -1 : 1) * Double.compare(s1.getId(), s2.getId());
    080    }
    081
    082    private int nrChoices(Config config, int idx, HashSet<Section> sections) {
    083        if (iFast) {
    084            int nrChoices = 1;
    085            for (Subpart subpart: config.getSubparts()) {
    086                if (subpart.getChildren().isEmpty())
    087                    nrChoices *= subpart.getSections().size();
    088            }
    089            return nrChoices;
    090        }
    091        if (config.getSubparts().size() == idx) {
    092            return 1;
    093        } else {
    094            Subpart subpart = config.getSubparts().get(idx);
    095            int choicesThisSubpart = 0;
    096            for (Section section : subpart.getSections()) {
    097                if (section.getParent() != null && !sections.contains(section.getParent()))
    098                    continue;
    099                if (section.isOverlapping(sections))
    100                    continue;
    101                sections.add(section);
    102                choicesThisSubpart += nrChoices(config, idx + 1, sections);
    103                sections.remove(section);
    104            }
    105            return choicesThisSubpart;
    106        }
    107    }
    108
    109    /** Average number of choices for each student */
    110    public double avgNrChoices(Student student) {
    111        int nrRequests = 0;
    112        int nrChoices = 0;
    113        for (Request request : student.getRequests()) {
    114            if (request instanceof CourseRequest) {
    115                CourseRequest cr = (CourseRequest) request;
    116                for (Course course : cr.getCourses()) {
    117                    for (Config config : course.getOffering().getConfigs()) {
    118                        Integer nrChoicesThisCfg = iCache.get(config);
    119                        if (nrChoicesThisCfg == null) {
    120                            nrChoicesThisCfg = new Integer(nrChoices(config, 0, new HashSet<Section>()));
    121                            iCache.put(config, nrChoicesThisCfg);
    122                        }
    123                        nrChoices += nrChoicesThisCfg.intValue();
    124                    }
    125                }
    126                nrRequests++;
    127            }
    128        }
    129        return (nrRequests == 0 ? 0.0 : ((double) nrChoices) / nrRequests);
    130    }
    131}