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