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 }