001 package net.sf.cpsolver.studentsct.reservation;
002
003 import java.util.HashMap;
004 import java.util.HashSet;
005 import java.util.Map;
006 import java.util.Set;
007
008 import net.sf.cpsolver.studentsct.model.Config;
009 import net.sf.cpsolver.studentsct.model.Enrollment;
010 import net.sf.cpsolver.studentsct.model.Offering;
011 import net.sf.cpsolver.studentsct.model.Request;
012 import net.sf.cpsolver.studentsct.model.Section;
013 import net.sf.cpsolver.studentsct.model.Student;
014 import 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 Tomas Muller<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 */
046 public 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 // config cap
326 double cap = 0;
327 for (Config config: iConfigs)
328 cap = add(cap, config.getLimit());
329
330 for (Set<Section> sections: getSections().values()) {
331 // subpart cap
332 double subpartCap = 0;
333 for (Section section: sections)
334 subpartCap = add(subpartCap, section.getLimit());
335
336 // minimize
337 cap = min(cap, subpartCap);
338 }
339
340 return cap;
341 }
342
343 /**
344 * Clear limit cap cache
345 */
346 private void clearLimitCapCache() {
347 iLimitCap = null;
348 }
349
350 /**
351 * Reservation limit capped the limit cap (see {@link Reservation#getLimitCap()})
352 */
353 public double getLimit() {
354 return min(getLimitCap(), getReservationLimit());
355 }
356
357 /**
358 * True if holding this reservation allows a student to have attend overlapping class.
359 */
360 public boolean isAllowOverlap() {
361 return false;
362 }
363
364 /**
365 * Set reservation expiration. If a reservation is expired, it works as ordinary reservation
366 * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students
367 * of getting into the offering / config / section.
368 */
369 public void setExpired(boolean expired) {
370 iExpired = expired;
371 }
372
373 /**
374 * True if the reservation is expired. If a reservation is expired, it works as ordinary reservation
375 * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students
376 * of getting into the offering / config / section.
377 */
378 public boolean isExpired() {
379 return iExpired;
380 }
381 }