001    package net.sf.cpsolver.studentsct.heuristics.studentord;
002    
003    import java.util.ArrayList;
004    import java.util.Collections;
005    import java.util.Comparator;
006    import java.util.HashSet;
007    import java.util.HashMap;
008    import java.util.List;
009    
010    import net.sf.cpsolver.ifs.util.DataProperties;
011    import net.sf.cpsolver.studentsct.model.Config;
012    import net.sf.cpsolver.studentsct.model.Course;
013    import net.sf.cpsolver.studentsct.model.CourseRequest;
014    import net.sf.cpsolver.studentsct.model.Request;
015    import net.sf.cpsolver.studentsct.model.Section;
016    import net.sf.cpsolver.studentsct.model.Student;
017    import 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 Tomas Muller<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     */
042    public class StudentChoiceOrder implements StudentOrder, Comparator<Student> {
043        private boolean iReverse = false;
044        private HashMap<Config, Integer> iCache = new HashMap<Config, Integer>();
045    
046        public StudentChoiceOrder(DataProperties config) {
047            iReverse = config.getPropertyBoolean("StudentChoiceOrder.Reverse", iReverse);
048        }
049    
050        /** Is order reversed */
051        public boolean isReverse() {
052            return iReverse;
053        }
054    
055        /** Set reverse order */
056        public void setReverse(boolean reverse) {
057            iReverse = reverse;
058        }
059    
060        /** Order the given list of students */
061        @Override
062        public List<Student> order(List<Student> students) {
063            List<Student> ret = new ArrayList<Student>(students);
064            Collections.sort(ret, this);
065            return ret;
066        }
067    
068        @Override
069        public int compare(Student s1, Student s2) {
070            try {
071                int cmp = -Double.compare(avgNrChoices(s1), avgNrChoices(s2));
072                if (cmp != 0)
073                    return (iReverse ? -1 : 1) * cmp;
074            } catch (Exception e) {
075                e.printStackTrace();
076            }
077            return (iReverse ? -1 : 1) * Double.compare(s1.getId(), s2.getId());
078        }
079    
080        private int nrChoices(Config config, int idx, HashSet<Section> sections) {
081            if (config.getSubparts().size() == idx) {
082                return 1;
083            } else {
084                Subpart subpart = config.getSubparts().get(idx);
085                int choicesThisSubpart = 0;
086                for (Section section : subpart.getSections()) {
087                    if (section.getParent() != null && !sections.contains(section.getParent()))
088                        continue;
089                    if (section.isOverlapping(sections))
090                        continue;
091                    sections.add(section);
092                    choicesThisSubpart += nrChoices(config, idx + 1, sections);
093                    sections.remove(section);
094                }
095                return choicesThisSubpart;
096            }
097        }
098    
099        /** Average number of choices for each student */
100        public double avgNrChoices(Student student) {
101            int nrRequests = 0;
102            int nrChoices = 0;
103            for (Request request : student.getRequests()) {
104                if (request instanceof CourseRequest) {
105                    CourseRequest cr = (CourseRequest) request;
106                    for (Course course : cr.getCourses()) {
107                        for (Config config : course.getOffering().getConfigs()) {
108                            Integer nrChoicesThisCfg = iCache.get(config);
109                            if (nrChoicesThisCfg == null) {
110                                nrChoicesThisCfg = new Integer(nrChoices(config, 0, new HashSet<Section>()));
111                                iCache.put(config, nrChoicesThisCfg);
112                            }
113                            nrChoices += nrChoicesThisCfg.intValue();
114                        }
115                    }
116                    nrRequests++;
117                }
118            }
119            return (nrRequests == 0 ? 0.0 : ((double) nrChoices) / nrRequests);
120        }
121    }