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