001 package net.sf.cpsolver.studentsct.heuristics.studentord; 002 003 import java.util.Collections; 004 import java.util.Comparator; 005 import java.util.Enumeration; 006 import java.util.HashSet; 007 import java.util.Hashtable; 008 import java.util.Vector; 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 021 * of choices of each student (students with more choices first). 022 * 023 * @version 024 * StudentSct 1.1 (Student Sectioning)<br> 025 * Copyright (C) 2007 Tomáš Müller<br> 026 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 027 * Lazenska 391, 76314 Zlin, Czech Republic<br> 028 * <br> 029 * This library is free software; you can redistribute it and/or 030 * modify it under the terms of the GNU Lesser General Public 031 * License as published by the Free Software Foundation; either 032 * version 2.1 of the License, or (at your option) any later version. 033 * <br><br> 034 * This library is distributed in the hope that it will be useful, 035 * but 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. 038 * <br><br> 039 * You should have received a copy of the GNU Lesser General Public 040 * License along with this library; if not, write to the Free Software 041 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 042 */ 043 public class StudentChoiceOrder implements StudentOrder, Comparator { 044 private boolean iReverse = false; 045 private Hashtable iCache = new Hashtable(); 046 047 public StudentChoiceOrder(DataProperties config) { 048 iReverse = config.getPropertyBoolean("StudentChoiceOrder.Reverse", iReverse); 049 } 050 051 /** Is order reversed */ 052 public boolean isReverse() { 053 return iReverse; 054 } 055 056 /** Set reverse order */ 057 public void setReverse(boolean reverse) { 058 iReverse = reverse; 059 } 060 061 /** Order the given list of students */ 062 public Vector order(Vector students) { 063 Vector ret = new Vector(students); 064 Collections.sort(ret, this); 065 return ret; 066 } 067 068 public int compare(Object o1, Object o2) { 069 Student s1 = (Student)o1; 070 Student s2 = (Student)o2; 071 try { 072 int cmp = -Double.compare(avgNrChoices(s1),avgNrChoices(s2)); 073 if (cmp!=0) 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 sections) { 081 if (config.getSubparts().size()==idx) { 082 return 1; 083 } else { 084 Subpart subpart = (Subpart)config.getSubparts().elementAt(idx); 085 int choicesThisSubpart = 0; 086 for (Enumeration e=subpart.getSections().elements();e.hasMoreElements();) { 087 Section section = (Section)e.nextElement(); 088 if (section.getParent()!=null && !sections.contains(section.getParent())) continue; 089 if (section.isOverlapping(sections)) continue; 090 sections.add(section); 091 choicesThisSubpart += nrChoices(config, idx+1, sections); 092 sections.remove(section); 093 } 094 return choicesThisSubpart; 095 } 096 } 097 098 /** Average number of choices for each student */ 099 public double avgNrChoices(Student student) { 100 int nrRequests = 0; 101 int nrChoices = 0; 102 for (Enumeration e=student.getRequests().elements();e.hasMoreElements();) { 103 Request request = (Request)e.nextElement(); 104 if (request instanceof CourseRequest) { 105 CourseRequest cr = (CourseRequest)request; 106 for (Enumeration f=cr.getCourses().elements();f.hasMoreElements();) { 107 Course course = (Course)f.nextElement(); 108 for (Enumeration g=course.getOffering().getConfigs().elements();g.hasMoreElements();) { 109 Config config = (Config)g.nextElement(); 110 Integer nrChoicesThisCfg = (Integer)iCache.get(config); 111 if (nrChoicesThisCfg==null) { 112 nrChoicesThisCfg = new Integer(nrChoices(config, 0, new HashSet())); 113 iCache.put(config, nrChoicesThisCfg); 114 } 115 nrChoices += nrChoicesThisCfg.intValue(); 116 } 117 } 118 nrRequests ++; 119 } 120 } 121 return (nrRequests==0?0.0:((double)nrChoices)/nrRequests); 122 } 123 }