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 boolean iCriticalOnly = false; 047 private HashMap<Config, Integer> iCache = new HashMap<Config, Integer>(); 048 049 public StudentChoiceOrder(DataProperties config) { 050 iReverse = config.getPropertyBoolean("StudentChoiceOrder.Reverse", iReverse); 051 iFast = config.getPropertyBoolean("StudentChoiceOrder.Fast", iFast); 052 iCriticalOnly = config.getPropertyBoolean("StudentChoiceOrder.CriticalOnly", iCriticalOnly); 053 } 054 055 /** Is order reversed 056 * @return true if the order is reversed 057 **/ 058 public boolean isReverse() { 059 return iReverse; 060 } 061 062 /** Set reverse order 063 * @param reverse true if students are to be in a reversed order 064 **/ 065 public void setReverse(boolean reverse) { 066 iReverse = reverse; 067 } 068 069 public boolean isCriticalOnly() { return iCriticalOnly; } 070 public void setCriticalOnly(boolean critOnly) { iCriticalOnly = critOnly; } 071 072 /** Order the given list of students */ 073 @Override 074 public List<Student> order(List<Student> students) { 075 List<Student> ret = new ArrayList<Student>(students); 076 Collections.sort(ret, this); 077 return ret; 078 } 079 080 @Override 081 public int compare(Student s1, Student s2) { 082 try { 083 int cmp = -Double.compare(avgNrChoices(s1), avgNrChoices(s2)); 084 if (cmp != 0) 085 return (iReverse ? -1 : 1) * cmp; 086 } catch (Exception e) { 087 e.printStackTrace(); 088 } 089 return (iReverse ? -1 : 1) * Double.compare(s1.getId(), s2.getId()); 090 } 091 092 private int nrChoices(Config config, int idx, HashSet<Section> sections) { 093 if (iFast) { 094 int nrChoices = 1; 095 for (Subpart subpart: config.getSubparts()) { 096 if (subpart.getChildren().isEmpty()) 097 nrChoices *= subpart.getSections().size(); 098 } 099 return nrChoices; 100 } 101 if (config.getSubparts().size() == idx) { 102 return 1; 103 } else { 104 Subpart subpart = config.getSubparts().get(idx); 105 int choicesThisSubpart = 0; 106 for (Section section : subpart.getSections()) { 107 if (section.getParent() != null && !sections.contains(section.getParent())) 108 continue; 109 if (section.isOverlapping(sections)) 110 continue; 111 sections.add(section); 112 choicesThisSubpart += nrChoices(config, idx + 1, sections); 113 sections.remove(section); 114 } 115 return choicesThisSubpart; 116 } 117 } 118 119 /** Average number of choices for each student 120 * @param student given student 121 * @return average number of choices of the given student 122 **/ 123 public double avgNrChoices(Student student) { 124 int nrRequests = 0; 125 int nrChoices = 0; 126 for (Request request : student.getRequests()) { 127 if (request instanceof CourseRequest) { 128 CourseRequest cr = (CourseRequest) request; 129 if (iCriticalOnly && (!cr.isCritical() || cr.isAlternative())) continue; 130 for (Course course : cr.getCourses()) { 131 for (Config config : course.getOffering().getConfigs()) { 132 Integer nrChoicesThisCfg = iCache.get(config); 133 if (nrChoicesThisCfg == null) { 134 nrChoicesThisCfg = new Integer(nrChoices(config, 0, new HashSet<Section>())); 135 iCache.put(config, nrChoicesThisCfg); 136 } 137 nrChoices += nrChoicesThisCfg.intValue(); 138 } 139 } 140 nrRequests++; 141 } 142 } 143 return (nrRequests == 0 ? 0.0 : ((double) nrChoices) / nrRequests); 144 } 145}