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 * Set to true if the student must use the reservation (if applicable) 274 * @param mustBeUsed must this reservation be used 275 */ 276 public void setMustBeUsed(boolean mustBeUsed) { 277 iMustBeUsed = mustBeUsed; 278 } 279 280 /** 281 * Reservation restrictivity (estimated percentage of enrollments that include this reservation, 1.0 reservation on the whole offering) 282 * @return computed restrictivity 283 */ 284 public double getRestrictivity() { 285 if (iCachedRestrictivity == null) { 286 if (getConfigs().isEmpty()) return 1.0; 287 int nrChoices = 0, nrMatchingChoices = 0; 288 for (Config config: getOffering().getConfigs()) { 289 int x[] = nrChoices(config, 0, new HashSet<Section>(), getConfigs().contains(config)); 290 nrChoices += x[0]; 291 nrMatchingChoices += x[1]; 292 } 293 iCachedRestrictivity = ((double)nrMatchingChoices) / nrChoices; 294 } 295 return iCachedRestrictivity; 296 } 297 private Double iCachedRestrictivity = null; 298 299 300 /** Number of choices and number of chaing choices in the given sub enrollment */ 301 private int[] nrChoices(Config config, int idx, HashSet<Section> sections, boolean matching) { 302 if (config.getSubparts().size() == idx) { 303 return new int[]{1, matching ? 1 : 0}; 304 } else { 305 Subpart subpart = config.getSubparts().get(idx); 306 Set<Section> matchingSections = getSections(subpart); 307 int choicesThisSubpart = 0; 308 int matchingChoicesThisSubpart = 0; 309 for (Section section : subpart.getSections()) { 310 if (section.getParent() != null && !sections.contains(section.getParent())) 311 continue; 312 if (section.isOverlapping(sections)) 313 continue; 314 sections.add(section); 315 boolean m = matching && (matchingSections == null || matchingSections.contains(section)); 316 int[] x = nrChoices(config, 1 + idx, sections, m); 317 choicesThisSubpart += x[0]; 318 matchingChoicesThisSubpart += x[1]; 319 sections.remove(section); 320 } 321 return new int[] {choicesThisSubpart, matchingChoicesThisSubpart}; 322 } 323 } 324 325 /** 326 * Priority first, than restrictivity (more restrictive first), than availability (more available first), than id 327 */ 328 @Override 329 public int compareTo(Assignment<Request, Enrollment> assignment, Reservation r) { 330 if (getPriority() != r.getPriority()) { 331 return (getPriority() < r.getPriority() ? -1 : 1); 332 } 333 int cmp = Double.compare(getRestrictivity(), r.getRestrictivity()); 334 if (cmp != 0) return cmp; 335 cmp = - Double.compare(getContext(assignment).getReservedAvailableSpace(assignment, null), r.getContext(assignment).getReservedAvailableSpace(assignment, null)); 336 if (cmp != 0) return cmp; 337 return new Long(getId()).compareTo(r.getId()); 338 } 339 340 /** 341 * Priority first, than restrictivity (more restrictive first), than id 342 */ 343 @Override 344 public int compareTo(Reservation r) { 345 if (getPriority() != r.getPriority()) { 346 return (getPriority() < r.getPriority() ? -1 : 1); 347 } 348 int cmp = Double.compare(getRestrictivity(), r.getRestrictivity()); 349 if (cmp != 0) return cmp; 350 return new Long(getId()).compareTo(r.getId()); 351 } 352 353 /** 354 * Return minimum of two limits where -1 counts as unlimited (any limit is smaller) 355 */ 356 private static double min(double l1, double l2) { 357 return (l1 < 0 ? l2 : l2 < 0 ? l1 : Math.min(l1, l2)); 358 } 359 360 /** 361 * Add two limits where -1 counts as unlimited (unlimited plus anything is unlimited) 362 */ 363 private static double add(double l1, double l2) { 364 return (l1 < 0 ? -1 : l2 < 0 ? -1 : l1 + l2); 365 } 366 367 368 /** Limit cap cache */ 369 private Double iLimitCap = null; 370 371 /** 372 * Compute limit cap (maximum number of students that can get into the offering using this reservation) 373 * @return reservation limit cap 374 */ 375 public double getLimitCap() { 376 if (iLimitCap == null) iLimitCap = getLimitCapNoCache(); 377 return iLimitCap; 378 } 379 380 /** 381 * Compute limit cap (maximum number of students that can get into the offering using this reservation) 382 */ 383 private double getLimitCapNoCache() { 384 if (getConfigs().isEmpty()) return -1; // no config -> can be unlimited 385 386 if (canAssignOverLimit()) return -1; // can assign over limit -> no cap 387 388 double cap = 0; 389 // for each config 390 for (Config config: iConfigs) { 391 // config cap 392 double configCap = config.getLimit(); 393 394 for (Map.Entry<Subpart, Set<Section>> entry: getSections().entrySet()) { 395 if (!config.equals(entry.getKey().getConfig())) continue; 396 Set<Section> sections = entry.getValue(); 397 398 // subpart cap 399 double subpartCap = 0; 400 for (Section section: sections) 401 subpartCap = add(subpartCap, section.getLimit()); 402 403 // minimize 404 configCap = min(configCap, subpartCap); 405 } 406 407 // add config cap 408 cap = add(cap, configCap); 409 } 410 411 return cap; 412 } 413 414 /** 415 * Clear limit cap cache 416 */ 417 private void clearLimitCapCache() { 418 iLimitCap = null; 419 } 420 421 /** 422 * Reservation limit capped the limit cap (see {@link Reservation#getLimitCap()}) 423 * @return reservation limit, -1 if unlimited 424 */ 425 public double getLimit() { 426 return min(getLimitCap(), getReservationLimit()); 427 } 428 429 /** 430 * True if holding this reservation allows a student to have attend overlapping class. 431 * @return does this reservation allow for overlaps 432 */ 433 public boolean isAllowOverlap() { 434 return iAllowOverlap; 435 } 436 437 /** 438 * Set to true if holding this reservation allows a student to have attend overlapping class. 439 * @param allowOverlap does this reservation allow for overlaps 440 */ 441 public void setAllowOverlap(boolean allowOverlap) { 442 iAllowOverlap = allowOverlap; 443 } 444 445 /** 446 * True if holding this reservation allows a student to attend a disabled class. 447 * @return does this reservation allow for disabled sections 448 */ 449 public boolean isAllowDisabled() { 450 return iAllowDisabled; 451 } 452 453 /** 454 * Set to true if holding this reservation allows a student to attend a disabled class 455 * @param allowDisabled does this reservation allow for disabled sections 456 */ 457 public void setAllowDisabled(boolean allowDisabled) { 458 iAllowDisabled = allowDisabled; 459 } 460 461 /** 462 * Set reservation expiration. If a reservation is expired, it works as ordinary reservation 463 * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students 464 * of getting into the offering / config / section. 465 * @param expired is this reservation expired 466 */ 467 public void setExpired(boolean expired) { 468 iExpired = expired; 469 } 470 471 /** 472 * True if the reservation is expired. If a reservation is expired, it works as ordinary reservation 473 * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students 474 * of getting into the offering / config / section. 475 * @return is this reservation expired 476 */ 477 public boolean isExpired() { 478 return iExpired; 479 } 480 481 @Override 482 public Model<Request, Enrollment> getModel() { 483 return getOffering().getModel(); 484 } 485 486 /** 487 * Available reserved space 488 * @param assignment current assignment 489 * @param excludeRequest excluding given request (if not null) 490 * @return available reserved space 491 **/ 492 public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) { 493 return getContext(assignment).getReservedAvailableSpace(assignment, excludeRequest); 494 } 495 496 /** Enrollments assigned using this reservation 497 * @param assignment current assignment 498 * @return assigned enrollments of this reservation 499 **/ 500 public Set<Enrollment> getEnrollments(Assignment<Request, Enrollment> assignment) { 501 return getContext(assignment).getEnrollments(); 502 } 503 504 @Override 505 public ReservationContext createAssignmentContext(Assignment<Request, Enrollment> assignment) { 506 return new ReservationContext(assignment); 507 } 508 509 510 @Override 511 public ReservationContext inheritAssignmentContext(Assignment<Request, Enrollment> assignment, ReservationContext parentContext) { 512 return new ReservationContext(parentContext); 513 } 514 515 516 public class ReservationContext implements AssignmentConstraintContext<Request, Enrollment> { 517 /** Enrollments included in this reservation */ 518 private Set<Enrollment> iEnrollments = new HashSet<Enrollment>(); 519 520 /** Used part of the limit */ 521 private double iUsed = 0; 522 private boolean iReadOnly = false; 523 524 public ReservationContext(Assignment<Request, Enrollment> assignment) { 525 for (Course course: getOffering().getCourses()) 526 for (CourseRequest request: course.getRequests()) { 527 Enrollment enrollment = assignment.getValue(request); 528 if (enrollment != null && Reservation.this.equals(enrollment.getReservation())) 529 assigned(assignment, enrollment); 530 } 531 } 532 533 public ReservationContext(ReservationContext parent) { 534 iUsed = parent.iUsed; 535 iEnrollments = parent.iEnrollments; 536 iReadOnly = true; 537 } 538 539 /** Notify reservation about an unassignment */ 540 @Override 541 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 542 if (iReadOnly) { 543 iEnrollments = new HashSet<Enrollment>(iEnrollments); 544 iReadOnly = false; 545 } 546 if (iEnrollments.add(enrollment)) 547 iUsed += enrollment.getRequest().getWeight(); 548 } 549 550 /** Notify reservation about an assignment */ 551 @Override 552 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 553 if (iReadOnly) { 554 iEnrollments = new HashSet<Enrollment>(iEnrollments); 555 iReadOnly = false; 556 } 557 if (iEnrollments.remove(enrollment)) 558 iUsed -= enrollment.getRequest().getWeight(); 559 } 560 561 /** Enrollments assigned using this reservation 562 * @return assigned enrollments of this reservation 563 **/ 564 public Set<Enrollment> getEnrollments() { 565 return iEnrollments; 566 } 567 568 /** Used space 569 * @return spaced used of this reservation 570 **/ 571 public double getUsedSpace() { 572 return iUsed; 573 } 574 575 /** 576 * Available reserved space 577 * @param assignment current assignment 578 * @param excludeRequest excluding given request (if not null) 579 * @return available reserved space 580 **/ 581 public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) { 582 // Unlimited 583 if (getLimit() < 0) return Double.MAX_VALUE; 584 585 double reserved = getLimit() - getContext(assignment).getUsedSpace(); 586 if (excludeRequest != null && assignment.getValue(excludeRequest) != null && iEnrollments.contains(assignment.getValue(excludeRequest))) 587 reserved += excludeRequest.getWeight(); 588 589 return reserved; 590 } 591 } 592}