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}