001package net.sf.cpsolver.studentsct.reservation; 002 003import java.util.HashMap; 004import java.util.HashSet; 005import java.util.Map; 006import java.util.Set; 007 008import net.sf.cpsolver.studentsct.model.Config; 009import net.sf.cpsolver.studentsct.model.Enrollment; 010import net.sf.cpsolver.studentsct.model.Offering; 011import net.sf.cpsolver.studentsct.model.Request; 012import net.sf.cpsolver.studentsct.model.Section; 013import net.sf.cpsolver.studentsct.model.Student; 014import net.sf.cpsolver.studentsct.model.Subpart; 015 016 017/** 018 * Abstract reservation. This abstract class allow some section, courses, 019 * and other parts to be reserved to particular group of students. A reservation 020 * can be unlimited (any number of students of that particular group can attend 021 * a course, section, etc.) or with a limit (only given number of seats is 022 * reserved to the students of the particular group). 023 * 024 * <br> 025 * <br> 026 * 027 * @version StudentSct 1.2 (Student Sectioning)<br> 028 * Copyright (C) 2007 - 2010 Tomáš Müller<br> 029 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 030 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 031 * <br> 032 * This library is free software; you can redistribute it and/or modify 033 * it under the terms of the GNU Lesser General Public License as 034 * published by the Free Software Foundation; either version 3 of the 035 * License, or (at your option) any later version. <br> 036 * <br> 037 * This library is distributed in the hope that it will be useful, but 038 * WITHOUT ANY WARRANTY; without even the implied warranty of 039 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 040 * Lesser General Public License for more details. <br> 041 * <br> 042 * You should have received a copy of the GNU Lesser General Public 043 * License along with this library; if not see 044 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 045 */ 046public abstract class Reservation implements Comparable<Reservation> { 047 /** Reservation unique id */ 048 private long iId = 0; 049 050 /** Is reservation expired? */ 051 private boolean iExpired; 052 053 /** Instructional offering on which the reservation is set, required */ 054 private Offering iOffering; 055 056 /** One or more configurations, if applicable */ 057 private Set<Config> iConfigs = new HashSet<Config>(); 058 059 /** One or more sections, if applicable */ 060 private Map<Subpart, Set<Section>> iSections = new HashMap<Subpart, Set<Section>>(); 061 062 /** Enrollments included in this reservation */ 063 private Set<Enrollment> iEnrollments = new HashSet<Enrollment>(); 064 065 /** Used part of the limit */ 066 private double iUsed = 0; 067 068 /** 069 * Constructor 070 * @param id reservation unique id 071 * @param offering instructional offering on which the reservation is set 072 */ 073 public Reservation(long id, Offering offering) { 074 iId = id; 075 iOffering = offering; 076 iOffering.getReservations().add(this); 077 iOffering.clearReservationCache(); 078 } 079 080 /** 081 * Reservation id 082 */ 083 public long getId() { return iId; } 084 085 /** 086 * Reservation limit 087 */ 088 public abstract double getReservationLimit(); 089 090 091 /** Reservation priority (e.g., individual reservations first) */ 092 public abstract int getPriority(); 093 094 /** 095 * Returns true if the student is applicable for the reservation 096 * @param student a student 097 * @return true if student can use the reservation to get into the course / configuration / section 098 */ 099 public abstract boolean isApplicable(Student student); 100 101 /** 102 * Instructional offering on which the reservation is set. 103 */ 104 public Offering getOffering() { return iOffering; } 105 106 /** 107 * One or more configurations on which the reservation is set (optional). 108 */ 109 public Set<Config> getConfigs() { return iConfigs; } 110 111 /** 112 * Add a configuration (of the offering {@link Reservation#getOffering()}) to this reservation 113 */ 114 public void addConfig(Config config) { 115 iConfigs.add(config); 116 clearLimitCapCache(); 117 } 118 119 /** 120 * One or more sections on which the reservation is set (optional). 121 */ 122 public Map<Subpart, Set<Section>> getSections() { return iSections; } 123 124 /** 125 * One or more sections on which the reservation is set (optional). 126 */ 127 public Set<Section> getSections(Subpart subpart) { 128 return iSections.get(subpart); 129 } 130 131 /** 132 * Add a section (of the offering {@link Reservation#getOffering()}) to this reservation. 133 * This will also add all parent sections and the appropriate configuration to the offering. 134 */ 135 public void addSection(Section section) { 136 addConfig(section.getSubpart().getConfig()); 137 while (section != null) { 138 Set<Section> sections = iSections.get(section.getSubpart()); 139 if (sections == null) { 140 sections = new HashSet<Section>(); 141 iSections.put(section.getSubpart(), sections); 142 } 143 sections.add(section); 144 section = section.getParent(); 145 } 146 clearLimitCapCache(); 147 } 148 149 /** 150 * Return true if the given enrollment meets the reservation. 151 */ 152 public boolean isIncluded(Enrollment enrollment) { 153 // Free time request are never included 154 if (enrollment.getConfig() == null) return false; 155 156 // Check the offering 157 if (!iOffering.equals(enrollment.getConfig().getOffering())) return false; 158 159 // If there are configurations, check the configuration 160 if (!iConfigs.isEmpty() && !iConfigs.contains(enrollment.getConfig())) return false; 161 162 // Check all the sections of the enrollment 163 for (Section section: enrollment.getSections()) { 164 Set<Section> sections = iSections.get(section.getSubpart()); 165 if (sections != null && !sections.contains(section)) 166 return false; 167 } 168 169 return true; 170 } 171 172 /** 173 * True if the enrollment can be done using this configuration 174 */ 175 public boolean canEnroll(Enrollment enrollment) { 176 // Check if student can use this reservation 177 if (!isApplicable(enrollment.getStudent())) return false; 178 179 // Check if the enrollment meets the reservation 180 if (!isIncluded(enrollment)) return false; 181 182 // Check the limit 183 return getLimit() < 0 || getUsedSpace() + enrollment.getRequest().getWeight() <= getLimit(); 184 } 185 186 /** Notify reservation about an unassignment */ 187 public void assigned(Enrollment enrollment) { 188 iEnrollments.add(enrollment); 189 iUsed += enrollment.getRequest().getWeight(); 190 } 191 192 /** Notify reservation about an assignment */ 193 public void unassigned(Enrollment enrollment) { 194 iEnrollments.remove(enrollment); 195 iUsed -= enrollment.getRequest().getWeight(); 196 } 197 198 /** Enrollments assigned using this reservation */ 199 public Set<Enrollment> getEnrollments() { 200 return iEnrollments; 201 } 202 203 /** Used space */ 204 public double getUsedSpace() { 205 return iUsed; 206 } 207 208 /** 209 * Available reserved space 210 * @param excludeRequest excluding given request (if not null) 211 **/ 212 public double getReservedAvailableSpace(Request excludeRequest) { 213 // Unlimited 214 if (getLimit() < 0) return Double.MAX_VALUE; 215 216 double reserved = getLimit() - getUsedSpace(); 217 if (excludeRequest != null && excludeRequest.getAssignment() != null && 218 iEnrollments.contains(excludeRequest.getAssignment())) 219 reserved += excludeRequest.getWeight(); 220 221 return reserved; 222 } 223 224 /** 225 * True if can go over the course / config / section limit. Only to be used in the online sectioning. 226 */ 227 public abstract boolean canAssignOverLimit(); 228 229 /** 230 * If true, student must use the reservation (if applicable) 231 */ 232 public abstract boolean mustBeUsed(); 233 234 /** 235 * Reservation restrictivity (estimated percentage of enrollments that include this reservation, 1.0 reservation on the whole offering) 236 */ 237 public double getRestrictivity() { 238 if (iCachedRestrictivity == null) { 239 if (getConfigs().isEmpty()) return 1.0; 240 int nrChoices = 0, nrMatchingChoices = 0; 241 for (Config config: getOffering().getConfigs()) { 242 int x[] = nrChoices(config, 0, new HashSet<Section>(), getConfigs().contains(config)); 243 nrChoices += x[0]; 244 nrMatchingChoices += x[1]; 245 } 246 iCachedRestrictivity = ((double)nrMatchingChoices) / nrChoices; 247 } 248 return iCachedRestrictivity; 249 } 250 private Double iCachedRestrictivity = null; 251 252 253 /** Number of choices and number of chaing choices in the given sub enrollment */ 254 private int[] nrChoices(Config config, int idx, HashSet<Section> sections, boolean matching) { 255 if (config.getSubparts().size() == idx) { 256 return new int[]{1, matching ? 1 : 0}; 257 } else { 258 Subpart subpart = config.getSubparts().get(idx); 259 Set<Section> matchingSections = getSections(subpart); 260 int choicesThisSubpart = 0; 261 int matchingChoicesThisSubpart = 0; 262 for (Section section : subpart.getSections()) { 263 if (section.getParent() != null && !sections.contains(section.getParent())) 264 continue; 265 if (section.isOverlapping(sections)) 266 continue; 267 sections.add(section); 268 boolean m = matching && (matchingSections == null || matchingSections.contains(section)); 269 int[] x = nrChoices(config, 1 + idx, sections, m); 270 choicesThisSubpart += x[0]; 271 matchingChoicesThisSubpart += x[1]; 272 sections.remove(section); 273 } 274 return new int[] {choicesThisSubpart, matchingChoicesThisSubpart}; 275 } 276 } 277 278 /** 279 * Priority first, than restrictivity (more restrictive first), than availability (more available first), than id 280 */ 281 @Override 282 public int compareTo(Reservation r) { 283 if (getPriority() != r.getPriority()) { 284 return (getPriority() < r.getPriority() ? -1 : 1); 285 } 286 int cmp = Double.compare(getRestrictivity(), r.getRestrictivity()); 287 if (cmp != 0) return cmp; 288 cmp = - Double.compare(getReservedAvailableSpace(null), r.getReservedAvailableSpace(null)); 289 if (cmp != 0) return cmp; 290 return new Long(getId()).compareTo(r.getId()); 291 } 292 293 /** 294 * Return minimum of two limits where -1 counts as unlimited (any limit is smaller) 295 */ 296 private static double min(double l1, double l2) { 297 return (l1 < 0 ? l2 : l2 < 0 ? l1 : Math.min(l1, l2)); 298 } 299 300 /** 301 * Add two limits where -1 counts as unlimited (unlimited plus anything is unlimited) 302 */ 303 private static double add(double l1, double l2) { 304 return (l1 < 0 ? -1 : l2 < 0 ? -1 : l1 + l2); 305 } 306 307 308 /** Limit cap cache */ 309 private Double iLimitCap = null; 310 311 /** 312 * Compute limit cap (maximum number of students that can get into the offering using this reservation) 313 */ 314 public double getLimitCap() { 315 if (iLimitCap == null) iLimitCap = getLimitCapNoCache(); 316 return iLimitCap; 317 } 318 319 /** 320 * Compute limit cap (maximum number of students that can get into the offering using this reservation) 321 */ 322 private double getLimitCapNoCache() { 323 if (getConfigs().isEmpty()) return -1; // no config -> can be unlimited 324 325 if (canAssignOverLimit()) return -1; // can assign over limit -> no cap 326 327 // config cap 328 double cap = 0; 329 for (Config config: iConfigs) 330 cap = add(cap, config.getLimit()); 331 332 for (Set<Section> sections: getSections().values()) { 333 // subpart cap 334 double subpartCap = 0; 335 for (Section section: sections) 336 subpartCap = add(subpartCap, section.getLimit()); 337 338 // minimize 339 cap = min(cap, subpartCap); 340 } 341 342 return cap; 343 } 344 345 /** 346 * Clear limit cap cache 347 */ 348 private void clearLimitCapCache() { 349 iLimitCap = null; 350 } 351 352 /** 353 * Reservation limit capped the limit cap (see {@link Reservation#getLimitCap()}) 354 */ 355 public double getLimit() { 356 return min(getLimitCap(), getReservationLimit()); 357 } 358 359 /** 360 * True if holding this reservation allows a student to have attend overlapping class. 361 */ 362 public boolean isAllowOverlap() { 363 return false; 364 } 365 366 /** 367 * Set reservation expiration. If a reservation is expired, it works as ordinary reservation 368 * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students 369 * of getting into the offering / config / section. 370 */ 371 public void setExpired(boolean expired) { 372 iExpired = expired; 373 } 374 375 /** 376 * True if the reservation is expired. If a reservation is expired, it works as ordinary reservation 377 * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students 378 * of getting into the offering / config / section. 379 */ 380 public boolean isExpired() { 381 return iExpired; 382 } 383}