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