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 /** Does this reservation allow for disabled sections */ 086 private boolean iAllowDisabled = false; 087 088 /** 089 * Constructor 090 * @param id reservation unique id 091 * @param offering instructional offering on which the reservation is set 092 * @param priority reservation priority 093 * @param mustBeUsed must this reservation be used 094 * @param canAssignOverLimit can assign over class / configuration / course limit 095 * @param allowOverlap does this reservation allow for overlaps 096 */ 097 public Reservation(long id, Offering offering, int priority, boolean mustBeUsed, boolean canAssignOverLimit, boolean allowOverlap) { 098 iId = id; 099 iOffering = offering; 100 iOffering.getReservations().add(this); 101 iOffering.clearReservationCache(); 102 iPriority = priority; 103 iMustBeUsed = mustBeUsed; 104 iCanAssignOverLimit = canAssignOverLimit; 105 iAllowOverlap = allowOverlap; 106 } 107 108 /** 109 * Reservation id 110 * @return reservation unique id 111 */ 112 public long getId() { return iId; } 113 114 /** 115 * Reservation limit 116 * @return reservation limit, -1 for unlimited 117 */ 118 public abstract double getReservationLimit(); 119 120 121 /** Reservation priority (e.g., individual reservations first) 122 * @return reservation priority 123 **/ 124 public int getPriority() { 125 return iPriority; 126 } 127 128 /** 129 * Set reservation priority (e.g., individual reservations first) 130 * @param priority reservation priority 131 */ 132 public void setPriority(int priority) { 133 iPriority = priority; 134 } 135 136 /** 137 * Returns true if the student is applicable for the reservation 138 * @param student a student 139 * @return true if student can use the reservation to get into the course / configuration / section 140 */ 141 public abstract boolean isApplicable(Student student); 142 143 /** 144 * Instructional offering on which the reservation is set. 145 * @return instructional offering 146 */ 147 public Offering getOffering() { return iOffering; } 148 149 /** 150 * One or more configurations on which the reservation is set (optional). 151 * @return instructional offering configurations 152 */ 153 public Set<Config> getConfigs() { return iConfigs; } 154 155 /** 156 * Add a configuration (of the offering {@link Reservation#getOffering()}) to this reservation 157 * @param config instructional offering configuration 158 */ 159 public void addConfig(Config config) { 160 iConfigs.add(config); 161 clearLimitCapCache(); 162 } 163 164 /** 165 * One or more sections on which the reservation is set (optional). 166 * @return class restrictions 167 */ 168 public Map<Subpart, Set<Section>> getSections() { return iSections; } 169 170 /** 171 * One or more sections on which the reservation is set (optional). 172 * @param subpart scheduling subpart 173 * @return class restrictions for the given scheduling subpart 174 */ 175 public Set<Section> getSections(Subpart subpart) { 176 return iSections.get(subpart); 177 } 178 179 /** 180 * Add a section (of the offering {@link Reservation#getOffering()}) to this reservation. 181 * This will also add all parent sections and the appropriate configuration to the offering. 182 * @param section a class restriction 183 */ 184 public void addSection(Section section) { 185 addConfig(section.getSubpart().getConfig()); 186 while (section != null) { 187 Set<Section> sections = iSections.get(section.getSubpart()); 188 if (sections == null) { 189 sections = new HashSet<Section>(); 190 iSections.put(section.getSubpart(), sections); 191 } 192 sections.add(section); 193 section = section.getParent(); 194 } 195 clearLimitCapCache(); 196 } 197 198 /** 199 * Return true if the given enrollment meets the reservation. 200 * @param enrollment given enrollment 201 * @return true if the given enrollment meets the reservation 202 */ 203 public boolean isIncluded(Enrollment enrollment) { 204 // Free time request are never included 205 if (enrollment.getConfig() == null) return false; 206 207 // Check the offering 208 if (!iOffering.equals(enrollment.getConfig().getOffering())) return false; 209 210 // If there are configurations, check the configuration 211 if (!iConfigs.isEmpty() && !iConfigs.contains(enrollment.getConfig())) return false; 212 213 // Check all the sections of the enrollment 214 for (Section section: enrollment.getSections()) { 215 Set<Section> sections = iSections.get(section.getSubpart()); 216 if (sections != null && !sections.contains(section)) 217 return false; 218 } 219 220 return true; 221 } 222 223 /** 224 * True if the enrollment can be done using this reservation 225 * @param assignment current assignment 226 * @param enrollment given enrollment 227 * @return true if the given enrollment can be assigned 228 */ 229 public boolean canEnroll(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 230 // Check if student can use this reservation 231 if (!isApplicable(enrollment.getStudent())) return false; 232 233 // Check if the enrollment meets the reservation 234 if (!isIncluded(enrollment)) return false; 235 236 // Check the limit 237 return getLimit() < 0 || getContext(assignment).getUsedSpace() + enrollment.getRequest().getWeight() <= getLimit(); 238 } 239 240 /** 241 * True if can go over the course / config / section limit. Only to be used in the online sectioning. 242 * @return can assign over class / configuration / course limit 243 */ 244 public boolean canAssignOverLimit() { 245 return iCanAssignOverLimit; 246 } 247 248 /** 249 * True if the batch solver can assign the reservation over the course / config / section limit. 250 * @return {@link Reservation#canAssignOverLimit()} and {@link StudentSectioningModel#getReservationCanAssignOverTheLimit()} 251 */ 252 public boolean canBatchAssignOverLimit() { 253 return canAssignOverLimit() && (iOffering.getModel() == null || ((StudentSectioningModel)iOffering.getModel()).getReservationCanAssignOverTheLimit()); 254 } 255 256 /** 257 * Set to true if a student meeting this reservation can go over the course / config / section limit. 258 * @param canAssignOverLimit can assign over class / configuration / course limit 259 */ 260 public void setCanAssignOverLimit(boolean canAssignOverLimit) { 261 iCanAssignOverLimit = canAssignOverLimit; 262 } 263 264 /** 265 * If true, student must use the reservation (if applicable). Expired reservations do not need to be used. 266 * @return must this reservation be used 267 */ 268 public boolean mustBeUsed() { 269 return iMustBeUsed && !isExpired(); 270 } 271 272 /** 273 * If true, student must use the reservation (if applicable). Expiration date is ignored. 274 * @return must this reservation be used 275 */ 276 public boolean mustBeUsedIgnoreExpiration() { 277 return iMustBeUsed; 278 } 279 280 /** 281 * Set to true if the student must use the reservation (if applicable) 282 * @param mustBeUsed must this reservation be used 283 */ 284 public void setMustBeUsed(boolean mustBeUsed) { 285 iMustBeUsed = mustBeUsed; 286 } 287 288 /** 289 * Reservation restrictivity (estimated percentage of enrollments that include this reservation, 1.0 reservation on the whole offering) 290 * @return computed restrictivity 291 */ 292 public double getRestrictivity() { 293 if (iCachedRestrictivity == null) { 294 if (getConfigs().isEmpty()) return 1.0; 295 int nrChoices = 0, nrMatchingChoices = 0; 296 for (Config config: getOffering().getConfigs()) { 297 int x[] = nrChoices(config, 0, new HashSet<Section>(), getConfigs().contains(config)); 298 nrChoices += x[0]; 299 nrMatchingChoices += x[1]; 300 } 301 iCachedRestrictivity = ((double)nrMatchingChoices) / nrChoices; 302 } 303 return iCachedRestrictivity; 304 } 305 private Double iCachedRestrictivity = null; 306 307 308 /** Number of choices and number of chaing choices in the given sub enrollment */ 309 private int[] nrChoices(Config config, int idx, HashSet<Section> sections, boolean matching) { 310 if (config.getSubparts().size() == idx) { 311 return new int[]{1, matching ? 1 : 0}; 312 } else { 313 Subpart subpart = config.getSubparts().get(idx); 314 Set<Section> matchingSections = getSections(subpart); 315 int choicesThisSubpart = 0; 316 int matchingChoicesThisSubpart = 0; 317 for (Section section : subpart.getSections()) { 318 if (section.getParent() != null && !sections.contains(section.getParent())) 319 continue; 320 if (section.isOverlapping(sections)) 321 continue; 322 sections.add(section); 323 boolean m = matching && (matchingSections == null || matchingSections.contains(section)); 324 int[] x = nrChoices(config, 1 + idx, sections, m); 325 choicesThisSubpart += x[0]; 326 matchingChoicesThisSubpart += x[1]; 327 sections.remove(section); 328 } 329 return new int[] {choicesThisSubpart, matchingChoicesThisSubpart}; 330 } 331 } 332 333 /** 334 * Priority first, than restrictivity (more restrictive first), than availability (more available first), than id 335 */ 336 @Override 337 public int compareTo(Assignment<Request, Enrollment> assignment, Reservation r) { 338 if (getPriority() != r.getPriority()) { 339 return (getPriority() < r.getPriority() ? -1 : 1); 340 } 341 int cmp = Double.compare(getRestrictivity(), r.getRestrictivity()); 342 if (cmp != 0) return cmp; 343 cmp = - Double.compare(getContext(assignment).getReservedAvailableSpace(assignment, null), r.getContext(assignment).getReservedAvailableSpace(assignment, null)); 344 if (cmp != 0) return cmp; 345 return new Long(getId()).compareTo(r.getId()); 346 } 347 348 /** 349 * Priority first, than restrictivity (more restrictive first), than id 350 */ 351 @Override 352 public int compareTo(Reservation r) { 353 if (getPriority() != r.getPriority()) { 354 return (getPriority() < r.getPriority() ? -1 : 1); 355 } 356 int cmp = Double.compare(getRestrictivity(), r.getRestrictivity()); 357 if (cmp != 0) return cmp; 358 return new Long(getId()).compareTo(r.getId()); 359 } 360 361 /** 362 * Return minimum of two limits where -1 counts as unlimited (any limit is smaller) 363 */ 364 private static double min(double l1, double l2) { 365 return (l1 < 0 ? l2 : l2 < 0 ? l1 : Math.min(l1, l2)); 366 } 367 368 /** 369 * Add two limits where -1 counts as unlimited (unlimited plus anything is unlimited) 370 */ 371 private static double add(double l1, double l2) { 372 return (l1 < 0 ? -1 : l2 < 0 ? -1 : l1 + l2); 373 } 374 375 376 /** Limit cap cache */ 377 private Double iLimitCap = null; 378 379 /** 380 * Compute limit cap (maximum number of students that can get into the offering using this reservation) 381 * @return reservation limit cap 382 */ 383 public double getLimitCap() { 384 if (iLimitCap == null) iLimitCap = getLimitCapNoCache(); 385 return iLimitCap; 386 } 387 388 /** 389 * Compute limit cap (maximum number of students that can get into the offering using this reservation) 390 */ 391 private double getLimitCapNoCache() { 392 if (getConfigs().isEmpty()) return -1; // no config -> can be unlimited 393 394 if (canAssignOverLimit()) return -1; // can assign over limit -> no cap 395 396 double cap = 0; 397 // for each config 398 for (Config config: iConfigs) { 399 // config cap 400 double configCap = config.getLimit(); 401 402 for (Map.Entry<Subpart, Set<Section>> entry: getSections().entrySet()) { 403 if (!config.equals(entry.getKey().getConfig())) continue; 404 Set<Section> sections = entry.getValue(); 405 406 // subpart cap 407 double subpartCap = 0; 408 for (Section section: sections) 409 subpartCap = add(subpartCap, section.getLimit()); 410 411 // minimize 412 configCap = min(configCap, subpartCap); 413 } 414 415 // add config cap 416 cap = add(cap, configCap); 417 } 418 419 return cap; 420 } 421 422 /** 423 * Clear limit cap cache 424 */ 425 private void clearLimitCapCache() { 426 iLimitCap = null; 427 } 428 429 /** 430 * Reservation limit capped the limit cap (see {@link Reservation#getLimitCap()}) 431 * @return reservation limit, -1 if unlimited 432 */ 433 public double getLimit() { 434 return min(getLimitCap(), getReservationLimit()); 435 } 436 437 /** 438 * True if holding this reservation allows a student to have attend overlapping class. 439 * @return does this reservation allow for overlaps 440 */ 441 public boolean isAllowOverlap() { 442 return iAllowOverlap; 443 } 444 445 /** 446 * Set to true if holding this reservation allows a student to have attend overlapping class. 447 * @param allowOverlap does this reservation allow for overlaps 448 */ 449 public void setAllowOverlap(boolean allowOverlap) { 450 iAllowOverlap = allowOverlap; 451 } 452 453 /** 454 * True if holding this reservation allows a student to attend a disabled class. 455 * @return does this reservation allow for disabled sections 456 */ 457 public boolean isAllowDisabled() { 458 return iAllowDisabled; 459 } 460 461 /** 462 * Set to true if holding this reservation allows a student to attend a disabled class 463 * @param allowDisabled does this reservation allow for disabled sections 464 */ 465 public void setAllowDisabled(boolean allowDisabled) { 466 iAllowDisabled = allowDisabled; 467 } 468 469 /** 470 * Set reservation expiration. If a reservation is expired, it works as ordinary reservation 471 * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students 472 * of getting into the offering / config / section. 473 * @param expired is this reservation expired 474 */ 475 public void setExpired(boolean expired) { 476 iExpired = expired; 477 } 478 479 /** 480 * True if the reservation is expired. If a reservation is expired, it works as ordinary reservation 481 * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students 482 * of getting into the offering / config / section. 483 * @return is this reservation expired 484 */ 485 public boolean isExpired() { 486 return iExpired; 487 } 488 489 @Override 490 public Model<Request, Enrollment> getModel() { 491 return getOffering().getModel(); 492 } 493 494 /** 495 * Available reserved space 496 * @param assignment current assignment 497 * @param excludeRequest excluding given request (if not null) 498 * @return available reserved space 499 **/ 500 public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) { 501 return getContext(assignment).getReservedAvailableSpace(assignment, excludeRequest); 502 } 503 504 /** Enrollments assigned using this reservation 505 * @param assignment current assignment 506 * @return assigned enrollments of this reservation 507 **/ 508 public Set<Enrollment> getEnrollments(Assignment<Request, Enrollment> assignment) { 509 return getContext(assignment).getEnrollments(); 510 } 511 512 @Override 513 public ReservationContext createAssignmentContext(Assignment<Request, Enrollment> assignment) { 514 return new ReservationContext(assignment); 515 } 516 517 518 @Override 519 public ReservationContext inheritAssignmentContext(Assignment<Request, Enrollment> assignment, ReservationContext parentContext) { 520 return new ReservationContext(parentContext); 521 } 522 523 524 public class ReservationContext implements AssignmentConstraintContext<Request, Enrollment> { 525 /** Enrollments included in this reservation */ 526 private Set<Enrollment> iEnrollments = new HashSet<Enrollment>(); 527 528 /** Used part of the limit */ 529 private double iUsed = 0; 530 private boolean iReadOnly = false; 531 532 public ReservationContext(Assignment<Request, Enrollment> assignment) { 533 for (Course course: getOffering().getCourses()) 534 for (CourseRequest request: course.getRequests()) { 535 Enrollment enrollment = assignment.getValue(request); 536 if (enrollment != null && Reservation.this.equals(enrollment.getReservation())) 537 assigned(assignment, enrollment); 538 } 539 } 540 541 public ReservationContext(ReservationContext parent) { 542 iUsed = parent.iUsed; 543 iEnrollments = parent.iEnrollments; 544 iReadOnly = true; 545 } 546 547 /** Notify reservation about an unassignment */ 548 @Override 549 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 550 if (iReadOnly) { 551 iEnrollments = new HashSet<Enrollment>(iEnrollments); 552 iReadOnly = false; 553 } 554 if (iEnrollments.add(enrollment)) 555 iUsed += enrollment.getRequest().getWeight(); 556 } 557 558 /** Notify reservation about an assignment */ 559 @Override 560 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 561 if (iReadOnly) { 562 iEnrollments = new HashSet<Enrollment>(iEnrollments); 563 iReadOnly = false; 564 } 565 if (iEnrollments.remove(enrollment)) 566 iUsed -= enrollment.getRequest().getWeight(); 567 } 568 569 /** Enrollments assigned using this reservation 570 * @return assigned enrollments of this reservation 571 **/ 572 public Set<Enrollment> getEnrollments() { 573 return iEnrollments; 574 } 575 576 /** Used space 577 * @return spaced used of this reservation 578 **/ 579 public double getUsedSpace() { 580 return iUsed; 581 } 582 583 /** 584 * Available reserved space 585 * @param assignment current assignment 586 * @param excludeRequest excluding given request (if not null) 587 * @return available reserved space 588 **/ 589 public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) { 590 // Unlimited 591 if (getLimit() < 0) return Double.MAX_VALUE; 592 593 double reserved = getLimit() - getContext(assignment).getUsedSpace(); 594 if (excludeRequest != null && assignment.getValue(excludeRequest) != null && iEnrollments.contains(assignment.getValue(excludeRequest))) 595 reserved += excludeRequest.getWeight(); 596 597 return reserved; 598 } 599 } 600}