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