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}