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