001 package net.sf.cpsolver.studentsct.model;
002
003 import java.text.DecimalFormat;
004 import java.util.Collection;
005 import java.util.Collections;
006 import java.util.Enumeration;
007 import java.util.HashSet;
008 import java.util.Iterator;
009 import java.util.Set;
010 import java.util.TreeSet;
011 import java.util.Vector;
012
013 import net.sf.cpsolver.ifs.util.ToolBox;
014 import net.sf.cpsolver.studentsct.constraint.SectionLimit;
015
016 /**
017 * Representation of a request of a student for one or more course. A student requests one of the given courses,
018 * preferably the first one.
019 * <br><br>
020 *
021 * @version
022 * StudentSct 1.1 (Student Sectioning)<br>
023 * Copyright (C) 2007 Tomáš Müller<br>
024 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
025 * Lazenska 391, 76314 Zlin, Czech Republic<br>
026 * <br>
027 * This library is free software; you can redistribute it and/or
028 * modify it under the terms of the GNU Lesser General Public
029 * License as published by the Free Software Foundation; either
030 * version 2.1 of the License, or (at your option) any later version.
031 * <br><br>
032 * This library is distributed in the hope that it will be useful,
033 * but WITHOUT ANY WARRANTY; without even the implied warranty of
034 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
035 * Lesser General Public License for more details.
036 * <br><br>
037 * You should have received a copy of the GNU Lesser General Public
038 * License along with this library; if not, write to the Free Software
039 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
040 */
041 public class CourseRequest extends Request {
042 private static DecimalFormat sDF = new DecimalFormat("0.000");
043 private Vector iCourses = null;
044 private Set iWaitlistedChoices = new HashSet();
045 private Set iSelectedChoices = new HashSet();
046 private boolean iWaitlist = false;
047 private Double iCachedBound = null, iCachedMinPenalty = null, iCachedMaxPenalty = null;
048 /** Enrollment value: value * sAltValue ^ index, where index is zero for the first course, one for the second course etc. */
049 public static double sAltValue = 0.5;
050 public static boolean sSameTimePrecise = false;
051
052 /** Constructor
053 * @param id request unique id
054 * @param priority request priority
055 * @param alternative true if the request is alternative (alternative request can be assigned instead of a non-alternative course requests, if it is left unassigned)
056 * @param student appropriate student
057 * @param courses list of requested courses (in the correct order -- first is the requested course, second is the first alternative, etc.)
058 * @param waitlist true if the student can be put on a waitlist (no alternative course request will be given instead)
059 */
060 public CourseRequest(long id, int priority, boolean alternative, Student student, Vector courses, boolean waitlist) {
061 super(id, priority, alternative, student);
062 iCourses = courses;
063 iWaitlist = waitlist;
064 }
065
066 /**
067 * List of requested courses (in the correct order -- first is the requested course, second is the first alternative, etc.)
068 */
069 public Vector getCourses() {
070 return iCourses;
071 }
072
073 /**
074 * Create enrollment for the given list of sections. The list of sections needs to be correct, i.e., a section for each subpart of a
075 * configuration of one of the requested courses.
076 */
077 public Enrollment createEnrollment(Set sections) {
078 if (sections==null || sections.isEmpty()) return null;
079 Config config = ((Section)sections.iterator().next()).getSubpart().getConfig();
080 return new Enrollment(this, Math.pow(sAltValue, iCourses.indexOf(config.getOffering().getCourse(getStudent()))), config, sections);
081 }
082
083 /**
084 * Return all possible enrollments.
085 */
086 public Vector computeEnrollments() {
087 Vector ret = new Vector();
088 int idx = 0;
089 for (Enumeration e=iCourses.elements();e.hasMoreElements();idx++) {
090 Course course = (Course)e.nextElement();
091 for (Enumeration f=course.getOffering().getConfigs().elements();f.hasMoreElements();) {
092 Config config = (Config)f.nextElement();
093 computeEnrollments(ret, Math.pow(sAltValue, idx), 0, config, new HashSet(), 0, false, false, false, false, -1);
094 }
095 }
096 return ret;
097 }
098
099 /**
100 * Return a subset of all enrollments -- randomly select only up to limitEachConfig enrollments of each config.
101 */
102 public Vector computeRandomEnrollments(int limitEachConfig) {
103 Vector ret = new Vector();
104 int idx = 0;
105 for (Enumeration e=iCourses.elements();e.hasMoreElements();idx++) {
106 Course course = (Course)e.nextElement();
107 for (Enumeration f=course.getOffering().getConfigs().elements();f.hasMoreElements();) {
108 Config config = (Config)f.nextElement();
109 computeEnrollments(ret, Math.pow(sAltValue, idx), 0, config, new HashSet(), 0, false, false, false, true, (limitEachConfig<=0?limitEachConfig:ret.size()+limitEachConfig));
110 }
111 }
112 return ret;
113 }
114
115 /** Return true if the both sets of sections contain sections of the same subparts, and each pair of sections of the same subpart is offered at the same time. */
116 private boolean sameTimes(Set sections1, Set sections2) {
117 for (Iterator i1=sections1.iterator();i1.hasNext();) {
118 Section s1 = (Section)i1.next();
119 Section s2 = null;
120 for (Iterator i2=sections2.iterator();i2.hasNext();) {
121 Section s = (Section)i2.next();
122 if (s.getSubpart().equals(s1.getSubpart())) {
123 s2 = s; break;
124 }
125 }
126 if (s2==null) return false;
127 if (!ToolBox.equals(s1.getTime(), s2.getTime())) return false;
128 }
129 return true;
130 }
131
132 /**
133 * Recursive computation of enrollments
134 * @param enrollments list of enrollments to be returned
135 * @param value value of the selected sections
136 * @param penalty penalty of the selected sections
137 * @param config selected configurations
138 * @param sections sections selected so far
139 * @param idx index of the subparts (a section of 0..idx-1 subparts has been already selected)
140 * @param avaiableOnly only use available sections
141 * @param skipSameTime for each possible times, pick only one section
142 * @param selectedOnly select only sections that are selected ({@link CourseRequest#isSelected(Section)} is true)
143 * @param random pick sections in a random order (useful when limit is used)
144 * @param limit when above zero, limit the number of selected enrollments to this limit
145 */
146 private void computeEnrollments(Collection enrollments, double value, double penalty, Config config, HashSet sections, int idx, boolean avaiableOnly, boolean skipSameTime, boolean selectedOnly, boolean random, int limit) {
147 if (limit>0 && enrollments.size()>=limit) return;
148 if (config.getSubparts().size()==idx) {
149 if (skipSameTime && sSameTimePrecise) {
150 boolean waitListedOrSelected = false;
151 if (!getSelectedChoices().isEmpty() || !getWaitlistedChoices().isEmpty()) {
152 for (Iterator i=sections.iterator();i.hasNext();) {
153 Section section = (Section)i.next();
154 if (isWaitlisted(section) || isSelected(section)) { waitListedOrSelected = true; break; }
155 }
156 }
157 if (!waitListedOrSelected) {
158 for (Iterator i=enrollments.iterator();i.hasNext();) {
159 Enrollment enrollment = (Enrollment)i.next();
160 if (sameTimes(enrollment.getAssignments(), sections)) return;
161 }
162 }
163 }
164 enrollments.add(new Enrollment(this, value, config, new HashSet(sections)));
165 } else {
166 Subpart subpart = (Subpart)config.getSubparts().elementAt(idx);
167 HashSet times = (skipSameTime?new HashSet():null);
168 Vector sectionsThisSubpart = subpart.getSections();
169 if (random) {
170 sectionsThisSubpart = new Vector(subpart.getSections());
171 Collections.shuffle(sectionsThisSubpart);
172 } else if (skipSameTime) {
173 sectionsThisSubpart = new Vector(subpart.getSections());
174 Collections.sort(sectionsThisSubpart);
175 }
176 boolean hasChildren = !subpart.getChildren().isEmpty();
177 for (Enumeration e=sectionsThisSubpart.elements();e.hasMoreElements();) {
178 Section section = (Section)e.nextElement();
179 if (section.getParent()!=null && !sections.contains(section.getParent())) continue;
180 if (section.isOverlapping(sections)) continue;
181 if (avaiableOnly && section.getLimit()>=0 && SectionLimit.getEnrollmentWeight(section,this)>section.getLimit()) continue;
182 if (selectedOnly && !isSelected(section)) continue;
183 if (skipSameTime && section.getTime()!=null && !hasChildren && !times.add(section.getTime()) && !isSelected(section) && !isWaitlisted(section)) continue;
184 sections.add(section);
185 computeEnrollments(enrollments, value, penalty+section.getPenalty(), config, sections, idx+1, avaiableOnly, skipSameTime, selectedOnly, random, limit);
186 sections.remove(section);
187 }
188 }
189 }
190
191 /** Return all enrollments that are available */
192 public Vector getAvaiableEnrollments() {
193 Vector ret = new Vector();
194 int idx = 0;
195 for (Enumeration e=iCourses.elements();e.hasMoreElements();idx++) {
196 Course course = (Course)e.nextElement();
197 for (Enumeration f=course.getOffering().getConfigs().elements();f.hasMoreElements();) {
198 Config config = (Config)f.nextElement();
199 computeEnrollments(ret, Math.pow(sAltValue, idx), 0, config, new HashSet(), 0, true, false, false, false, -1);
200 }
201 }
202 return ret;
203 }
204
205 /** Return all enrollments that are selected ({@link CourseRequest#isSelected(Section)} is true)
206 * @param availableOnly pick only available sections
207 */
208 public Vector getSelectedEnrollments(boolean availableOnly) {
209 if (getSelectedChoices().isEmpty()) return null;
210 Choice firstChoice = (Choice)getSelectedChoices().iterator().next();
211 Vector enrollments = new Vector();
212 for (Enumeration e=iCourses.elements();e.hasMoreElements();) {
213 Course course = (Course)e.nextElement();
214 if (!course.getOffering().equals(firstChoice.getOffering())) continue;
215 for (Enumeration f=course.getOffering().getConfigs().elements();f.hasMoreElements();) {
216 Config config = (Config)f.nextElement();
217 computeEnrollments(enrollments, 1.0, 0, config, new HashSet(), 0, availableOnly, false, true, false, -1);
218 }
219 }
220 return enrollments;
221 }
222
223 /** Return all enrollments that are available, pick only the first section of the sections with the same time (of each subpart, {@link Section} comparator is used) */
224 public TreeSet getAvaiableEnrollmentsSkipSameTime() {
225 TreeSet avaiableEnrollmentsSkipSameTime = new TreeSet();
226 if (getInitialAssignment()!=null)
227 avaiableEnrollmentsSkipSameTime.add(getInitialAssignment());
228 int idx = 0;
229 for (Enumeration e=iCourses.elements();e.hasMoreElements();idx++) {
230 Course course = (Course)e.nextElement();
231 for (Enumeration f=course.getOffering().getConfigs().elements();f.hasMoreElements();) {
232 Config config = (Config)f.nextElement();
233 computeEnrollments(avaiableEnrollmentsSkipSameTime, Math.pow(sAltValue, idx), 0, config, new HashSet(), 0, true, true, false, false, -1);
234 }
235 }
236 return avaiableEnrollmentsSkipSameTime;
237 }
238
239 /**
240 * Return all possible enrollments.
241 */
242 public Vector getEnrollmentsSkipSameTime() {
243 Vector ret = new Vector();
244 int idx = 0;
245 for (Enumeration e=iCourses.elements();e.hasMoreElements();idx++) {
246 Course course = (Course)e.nextElement();
247 for (Enumeration f=course.getOffering().getConfigs().elements();f.hasMoreElements();) {
248 Config config = (Config)f.nextElement();
249 computeEnrollments(ret, Math.pow(sAltValue, idx), 0, config, new HashSet(), 0, false, true, false, false, -1);
250 }
251 }
252 return ret;
253 }
254
255
256 /** Wait-listed choices */
257 public Set getWaitlistedChoices() {
258 return iWaitlistedChoices;
259 }
260
261 /** Return true when the given section is wait-listed (i.e., its choice is among wait-listed choices) */
262 public boolean isWaitlisted(Section section) {
263 return iWaitlistedChoices.contains(section.getChoice());
264 }
265
266 /** Selected choices */
267 public Set getSelectedChoices() {
268 return iSelectedChoices;
269 }
270
271 /** Return true when the given section is selected (i.e., its choice is among selected choices) */
272 public boolean isSelected(Section section) {
273 return iSelectedChoices.contains(section.getChoice());
274 }
275
276 /** Request name: A for alternative, 1 + priority, (w) when waitlist, list of course names */
277 public String getName() {
278 String ret = (isAlternative()?"A":"")+(1+getPriority()+(isAlternative()?-getStudent().nrRequests():0))+". "+(isWaitlist()?"(w) ":"");
279 int idx = 0;
280 for (Enumeration e=iCourses.elements();e.hasMoreElements();idx++) {
281 Course course = (Course)e.nextElement();
282 if (idx==0)
283 ret+=course.getName();
284 else
285 ret+=", "+idx+". alt "+course.getName();
286 }
287 return ret;
288 }
289
290 /** True if the student can be put on a wait-list (no alternative course request will be given instead) */
291 public boolean isWaitlist() {
292 return iWaitlist;
293 }
294
295 public String toString() {
296 return getName()+(getWeight()!=1.0?" (W:"+sDF.format(getWeight())+")":"");
297 }
298
299 /** Return course of the requested courses with the given id */
300 public Course getCourse(long courseId) {
301 for (Enumeration e=getCourses().elements();e.hasMoreElements();) {
302 Course course = (Course)e.nextElement();
303 if (course.getId()==courseId) return course;
304 }
305 return null;
306 }
307
308 /** Return configuration of the requested courses with the given id */
309 public Config getConfig(long configId) {
310 for (Enumeration e=getCourses().elements();e.hasMoreElements();) {
311 Course course = (Course)e.nextElement();
312 for (Enumeration f=course.getOffering().getConfigs().elements();f.hasMoreElements();) {
313 Config config = (Config)f.nextElement();
314 if (config.getId()==configId) return config;
315 }
316 }
317 return null;
318 }
319
320 /** Return subpart of the requested courses with the given id */
321 public Subpart getSubpart(long subpartId) {
322 for (Enumeration e=getCourses().elements();e.hasMoreElements();) {
323 Course course = (Course)e.nextElement();
324 for (Enumeration f=course.getOffering().getConfigs().elements();f.hasMoreElements();) {
325 Config config = (Config)f.nextElement();
326 for (Enumeration i=config.getSubparts().elements();i.hasMoreElements();) {
327 Subpart subpart = (Subpart)i.nextElement();
328 if (subpart.getId()==subpartId)
329 return subpart;
330 }
331 }
332 }
333 return null;
334 }
335
336 /** Return section of the requested courses with the given id */
337 public Section getSection(long sectionId) {
338 for (Enumeration e=getCourses().elements();e.hasMoreElements();) {
339 Course course = (Course)e.nextElement();
340 for (Enumeration f=course.getOffering().getConfigs().elements();f.hasMoreElements();) {
341 Config config = (Config)f.nextElement();
342 for (Enumeration i=config.getSubparts().elements();i.hasMoreElements();) {
343 Subpart subpart = (Subpart)i.nextElement();
344 for (Enumeration g=subpart.getSections().elements();g.hasMoreElements();) {
345 Section section = (Section)g.nextElement();
346 if (section.getId()==sectionId) return section;
347 }
348 }
349 }
350 }
351 return null;
352 }
353
354 /** Minimal penalty (minimum of {@link Offering#getMinPenalty()} among requested courses) */
355 public double getMinPenalty() {
356 if (iCachedMinPenalty==null) {
357 double min = Double.MAX_VALUE;
358 for (Enumeration e=getCourses().elements();e.hasMoreElements();) {
359 Course course = (Course)e.nextElement();
360 min = Math.min(min, course.getOffering().getMinPenalty());
361 }
362 iCachedMinPenalty = new Double(min);
363 }
364 return iCachedMinPenalty.doubleValue();
365 }
366
367 /** Maximal penalty (maximum of {@link Offering#getMaxPenalty()} among requested courses) */
368 public double getMaxPenalty() {
369 if (iCachedMaxPenalty==null) {
370 double max = Double.MIN_VALUE;
371 for (Enumeration e=getCourses().elements();e.hasMoreElements();) {
372 Course course = (Course)e.nextElement();
373 max = Math.max(max, course.getOffering().getMaxPenalty());
374 }
375 iCachedMaxPenalty = new Double(max);
376 }
377 return iCachedMaxPenalty.doubleValue();
378 }
379
380 /** Clear cached min/max penalties and cached bound */
381 public void clearCache() {
382 iCachedMaxPenalty = null;
383 iCachedMinPenalty = null;
384 iCachedBound = null;
385 }
386
387 /** Estimated bound for this request -- it estimates the smallest value among all possible enrollments */
388 public double getBound() {
389 if (iCachedBound==null) {
390 iCachedBound = new Double(
391 - Math.pow(Enrollment.sPriorityWeight,getPriority()) *
392 (isAlternative()?Enrollment.sAlterativeWeight:1.0) *
393 Math.pow(Enrollment.sInitialWeight,(getInitialAssignment()==null?0:1)) *
394 Math.pow(Enrollment.sSelectedWeight,(iSelectedChoices.isEmpty()?0:1)) *
395 Math.pow(Enrollment.sWaitlistedWeight,(iWaitlistedChoices.isEmpty()?0:1)) *
396 //Math.max(Enrollment.sMinWeight,getWeight()) *
397 (getStudent().isDummy()?Student.sDummyStudentWeight:1.0) *
398 Enrollment.normalizePenalty(getMinPenalty())
399 );
400 }
401 return iCachedBound.doubleValue();
402 }
403 }