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 // config cap 389 double cap = 0; 390 for (Config config: iConfigs) 391 cap = add(cap, config.getLimit()); 392 393 for (Set<Section> sections: getSections().values()) { 394 // subpart cap 395 double subpartCap = 0; 396 for (Section section: sections) 397 subpartCap = add(subpartCap, section.getLimit()); 398 399 // minimize 400 cap = min(cap, subpartCap); 401 } 402 403 return cap; 404 } 405 406 /** 407 * Clear limit cap cache 408 */ 409 private void clearLimitCapCache() { 410 iLimitCap = null; 411 } 412 413 /** 414 * Reservation limit capped the limit cap (see {@link Reservation#getLimitCap()}) 415 * @return reservation limit, -1 if unlimited 416 */ 417 public double getLimit() { 418 return min(getLimitCap(), getReservationLimit()); 419 } 420 421 /** 422 * True if holding this reservation allows a student to have attend overlapping class. 423 * @return does this reservation allow for overlaps 424 */ 425 public boolean isAllowOverlap() { 426 return iAllowOverlap; 427 } 428 429 /** 430 * Set to true if holding this reservation allows a student to have attend overlapping class. 431 * @param allowOverlap does this reservation allow for overlaps 432 */ 433 public void setAllowOverlap(boolean allowOverlap) { 434 iAllowOverlap = allowOverlap; 435 } 436 437 /** 438 * True if holding this reservation allows a student to attend a disabled class. 439 * @return does this reservation allow for disabled sections 440 */ 441 public boolean isAllowDisabled() { 442 return iAllowDisabled; 443 } 444 445 /** 446 * Set to true if holding this reservation allows a student to attend a disabled class 447 * @param allowDisabled does this reservation allow for disabled sections 448 */ 449 public void setAllowDisabled(boolean allowDisabled) { 450 iAllowDisabled = allowDisabled; 451 } 452 453 /** 454 * Set reservation expiration. If a reservation is expired, it works as ordinary reservation 455 * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students 456 * of getting into the offering / config / section. 457 * @param expired is this reservation expired 458 */ 459 public void setExpired(boolean expired) { 460 iExpired = expired; 461 } 462 463 /** 464 * True if the reservation is expired. If a reservation is expired, it works as ordinary reservation 465 * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students 466 * of getting into the offering / config / section. 467 * @return is this reservation expired 468 */ 469 public boolean isExpired() { 470 return iExpired; 471 } 472 473 @Override 474 public Model<Request, Enrollment> getModel() { 475 return getOffering().getModel(); 476 } 477 478 /** 479 * Available reserved space 480 * @param assignment current assignment 481 * @param excludeRequest excluding given request (if not null) 482 * @return available reserved space 483 **/ 484 public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) { 485 return getContext(assignment).getReservedAvailableSpace(assignment, excludeRequest); 486 } 487 488 /** Enrollments assigned using this reservation 489 * @param assignment current assignment 490 * @return assigned enrollments of this reservation 491 **/ 492 public Set<Enrollment> getEnrollments(Assignment<Request, Enrollment> assignment) { 493 return getContext(assignment).getEnrollments(); 494 } 495 496 @Override 497 public ReservationContext createAssignmentContext(Assignment<Request, Enrollment> assignment) { 498 return new ReservationContext(assignment); 499 } 500 501 502 @Override 503 public ReservationContext inheritAssignmentContext(Assignment<Request, Enrollment> assignment, ReservationContext parentContext) { 504 return new ReservationContext(parentContext); 505 } 506 507 508 public class ReservationContext implements AssignmentConstraintContext<Request, Enrollment> { 509 /** Enrollments included in this reservation */ 510 private Set<Enrollment> iEnrollments = new HashSet<Enrollment>(); 511 512 /** Used part of the limit */ 513 private double iUsed = 0; 514 private boolean iReadOnly = false; 515 516 public ReservationContext(Assignment<Request, Enrollment> assignment) { 517 for (Course course: getOffering().getCourses()) 518 for (CourseRequest request: course.getRequests()) { 519 Enrollment enrollment = assignment.getValue(request); 520 if (enrollment != null && Reservation.this.equals(enrollment.getReservation())) 521 assigned(assignment, enrollment); 522 } 523 } 524 525 public ReservationContext(ReservationContext parent) { 526 iUsed = parent.iUsed; 527 iEnrollments = parent.iEnrollments; 528 iReadOnly = true; 529 } 530 531 /** Notify reservation about an unassignment */ 532 @Override 533 public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 534 if (iReadOnly) { 535 iEnrollments = new HashSet<Enrollment>(iEnrollments); 536 iReadOnly = false; 537 } 538 if (iEnrollments.add(enrollment)) 539 iUsed += enrollment.getRequest().getWeight(); 540 } 541 542 /** Notify reservation about an assignment */ 543 @Override 544 public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) { 545 if (iReadOnly) { 546 iEnrollments = new HashSet<Enrollment>(iEnrollments); 547 iReadOnly = false; 548 } 549 if (iEnrollments.remove(enrollment)) 550 iUsed -= enrollment.getRequest().getWeight(); 551 } 552 553 /** Enrollments assigned using this reservation 554 * @return assigned enrollments of this reservation 555 **/ 556 public Set<Enrollment> getEnrollments() { 557 return iEnrollments; 558 } 559 560 /** Used space 561 * @return spaced used of this reservation 562 **/ 563 public double getUsedSpace() { 564 return iUsed; 565 } 566 567 /** 568 * Available reserved space 569 * @param assignment current assignment 570 * @param excludeRequest excluding given request (if not null) 571 * @return available reserved space 572 **/ 573 public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) { 574 // Unlimited 575 if (getLimit() < 0) return Double.MAX_VALUE; 576 577 double reserved = getLimit() - getContext(assignment).getUsedSpace(); 578 if (excludeRequest != null && assignment.getValue(excludeRequest) != null && iEnrollments.contains(assignment.getValue(excludeRequest))) 579 reserved += excludeRequest.getWeight(); 580 581 return reserved; 582 } 583 } 584}