001 package net.sf.cpsolver.studentsct.model; 002 003 import java.text.DecimalFormat; 004 import java.util.ArrayList; 005 import java.util.HashMap; 006 import java.util.HashSet; 007 import java.util.List; 008 import java.util.Map; 009 import java.util.Set; 010 011 import net.sf.cpsolver.coursett.model.Placement; 012 import net.sf.cpsolver.coursett.model.RoomLocation; 013 import net.sf.cpsolver.coursett.model.TimeLocation; 014 import net.sf.cpsolver.studentsct.reservation.Reservation; 015 016 /** 017 * Representation of a class. Each section contains id, name, scheduling 018 * subpart, time/room placement, and a limit. Optionally, parent-child relation 019 * between sections can be defined. <br> 020 * <br> 021 * Each student requesting a course needs to be enrolled in a class of each 022 * subpart of a selected configuration. In the case of parent-child relation 023 * between classes, if a student is enrolled in a section that has a parent 024 * section defined, he/she has to be enrolled in the parent section as well. If 025 * there is a parent-child relation between two sections, the same relation is 026 * defined on their subparts as well, i.e., if section A is a parent section B, 027 * subpart of section A isa parent of subpart of section B. <br> 028 * <br> 029 * 030 * @version StudentSct 1.2 (Student Sectioning)<br> 031 * Copyright (C) 2007 - 2010 Tomas Muller<br> 032 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 033 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 034 * <br> 035 * This library is free software; you can redistribute it and/or modify 036 * it under the terms of the GNU Lesser General Public License as 037 * published by the Free Software Foundation; either version 3 of the 038 * License, or (at your option) any later version. <br> 039 * <br> 040 * This library is distributed in the hope that it will be useful, but 041 * WITHOUT ANY WARRANTY; without even the implied warranty of 042 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 043 * Lesser General Public License for more details. <br> 044 * <br> 045 * You should have received a copy of the GNU Lesser General Public 046 * License along with this library; if not see 047 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 048 */ 049 public class Section implements Assignment, Comparable<Section> { 050 private static DecimalFormat sDF = new DecimalFormat("0.000"); 051 private long iId = -1; 052 private String iName = null; 053 private Map<Long, String> iNameByCourse = null; 054 private Subpart iSubpart = null; 055 private Section iParent = null; 056 private Placement iPlacement = null; 057 private int iLimit = 0; 058 private Set<Enrollment> iEnrollments = new HashSet<Enrollment>(); 059 private Choice iChoice = null; 060 private double iPenalty = 0.0; 061 private double iEnrollmentWeight = 0.0; 062 private double iMaxEnrollmentWeight = 0.0; 063 private double iMinEnrollmentWeight = 0.0; 064 private double iSpaceExpected = 0.0; 065 private double iSpaceHeld = 0.0; 066 private String iNote = null; 067 068 /** 069 * Constructor 070 * 071 * @param id 072 * section unique id 073 * @param limit 074 * section limit, i.e., the maximal number of students that can 075 * be enrolled in this section at the same time 076 * @param name 077 * section name 078 * @param subpart 079 * subpart of this section 080 * @param placement 081 * time/room placement 082 * @param instructorIds 083 * instructor(s) id -- needed for {@link Section#getChoice()} 084 * @param instructorNames 085 * instructor(s) name -- needed for {@link Section#getChoice()} 086 * @param parent 087 * parent section -- if there is a parent section defined, a 088 * student that is enrolled in this section has to be enrolled in 089 * the parent section as well. Also, the same relation needs to 090 * be defined between subpart of this section and the subpart of 091 * the parent section 092 */ 093 public Section(long id, int limit, String name, Subpart subpart, Placement placement, String instructorIds, 094 String instructorNames, Section parent) { 095 iId = id; 096 iLimit = limit; 097 iName = name; 098 iSubpart = subpart; 099 iSubpart.getSections().add(this); 100 iPlacement = placement; 101 iParent = parent; 102 iChoice = new Choice(getSubpart().getConfig().getOffering(), getSubpart().getInstructionalType(), getTime(), 103 instructorIds, instructorNames); 104 } 105 106 /** Section id */ 107 @Override 108 public long getId() { 109 return iId; 110 } 111 112 /** 113 * Section limit. This is defines the maximal number of students that can be 114 * enrolled into this section at the same time. It is -1 in the case of an 115 * unlimited section 116 */ 117 public int getLimit() { 118 return iLimit; 119 } 120 121 /** Set section limit */ 122 public void setLimit(int limit) { 123 iLimit = limit; 124 } 125 126 /** Section name */ 127 public String getName() { 128 return iName; 129 } 130 131 /** Set section name */ 132 public void setName(String name) { 133 iName = name; 134 } 135 136 /** Scheduling subpart to which this section belongs */ 137 public Subpart getSubpart() { 138 return iSubpart; 139 } 140 141 /** 142 * Parent section of this section (can be null). If there is a parent 143 * section defined, a student that is enrolled in this section has to be 144 * enrolled in the parent section as well. Also, the same relation needs to 145 * be defined between subpart of this section and the subpart of the parent 146 * section. 147 */ 148 public Section getParent() { 149 return iParent; 150 } 151 152 /** 153 * Time/room placement of the section. This can be null, for arranged 154 * sections. 155 */ 156 public Placement getPlacement() { 157 return iPlacement; 158 } 159 160 /** 161 * Set time/room placement of the section. This can be null, for arranged 162 * sections. 163 */ 164 public void setPlacement(Placement placement) { 165 iPlacement = placement; 166 } 167 168 /** Time placement of the section. */ 169 @Override 170 public TimeLocation getTime() { 171 return (iPlacement == null ? null : iPlacement.getTimeLocation()); 172 } 173 174 /** Number of rooms in which the section meet. */ 175 @Override 176 public int getNrRooms() { 177 return (iPlacement == null ? 0 : iPlacement.getNrRooms()); 178 } 179 180 /** 181 * Room placement -- list of 182 * {@link net.sf.cpsolver.coursett.model.RoomLocation} 183 */ 184 @Override 185 public List<RoomLocation> getRooms() { 186 if (iPlacement == null) 187 return null; 188 if (iPlacement.getRoomLocations() == null && iPlacement.getRoomLocation() != null) { 189 List<RoomLocation> ret = new ArrayList<RoomLocation>(1); 190 ret.add(iPlacement.getRoomLocation()); 191 return ret; 192 } 193 return iPlacement.getRoomLocations(); 194 } 195 196 /** 197 * True, if this section overlaps with the given assignment in time and 198 * space 199 */ 200 @Override 201 public boolean isOverlapping(Assignment assignment) { 202 if (isAllowOverlap() || assignment.isAllowOverlap()) return false; 203 if (getTime() == null || assignment.getTime() == null) 204 return false; 205 return getTime().hasIntersection(assignment.getTime()); 206 } 207 208 /** 209 * True, if this section overlaps with one of the given set of assignments 210 * in time and space 211 */ 212 @Override 213 public boolean isOverlapping(Set<? extends Assignment> assignments) { 214 if (isAllowOverlap()) return false; 215 if (getTime() == null || assignments == null) 216 return false; 217 for (Assignment assignment : assignments) { 218 if (assignment.isAllowOverlap()) 219 continue; 220 if (assignment.getTime() == null) 221 continue; 222 if (getTime().hasIntersection(assignment.getTime())) 223 return true; 224 } 225 return false; 226 } 227 228 /** Called when an enrollment with this section is assigned to a request */ 229 @Override 230 public void assigned(Enrollment enrollment) { 231 if (iEnrollments.isEmpty()) { 232 iMinEnrollmentWeight = iMaxEnrollmentWeight = enrollment.getRequest().getWeight(); 233 } else { 234 iMaxEnrollmentWeight = Math.max(iMaxEnrollmentWeight, enrollment.getRequest().getWeight()); 235 iMinEnrollmentWeight = Math.min(iMinEnrollmentWeight, enrollment.getRequest().getWeight()); 236 } 237 iEnrollments.add(enrollment); 238 iEnrollmentWeight += enrollment.getRequest().getWeight(); 239 } 240 241 /** Called when an enrollment with this section is unassigned from a request */ 242 @Override 243 public void unassigned(Enrollment enrollment) { 244 iEnrollments.remove(enrollment); 245 iEnrollmentWeight -= enrollment.getRequest().getWeight(); 246 if (iEnrollments.isEmpty()) { 247 iMinEnrollmentWeight = iMaxEnrollmentWeight = 0; 248 } else if (iMinEnrollmentWeight != iMaxEnrollmentWeight) { 249 if (iMinEnrollmentWeight == enrollment.getRequest().getWeight()) { 250 double newMinEnrollmentWeight = Double.MAX_VALUE; 251 for (Enrollment e : iEnrollments) { 252 if (e.getRequest().getWeight() == iMinEnrollmentWeight) { 253 newMinEnrollmentWeight = iMinEnrollmentWeight; 254 break; 255 } else { 256 newMinEnrollmentWeight = Math.min(newMinEnrollmentWeight, e.getRequest().getWeight()); 257 } 258 } 259 iMinEnrollmentWeight = newMinEnrollmentWeight; 260 } 261 if (iMaxEnrollmentWeight == enrollment.getRequest().getWeight()) { 262 double newMaxEnrollmentWeight = Double.MIN_VALUE; 263 for (Enrollment e : iEnrollments) { 264 if (e.getRequest().getWeight() == iMaxEnrollmentWeight) { 265 newMaxEnrollmentWeight = iMaxEnrollmentWeight; 266 break; 267 } else { 268 newMaxEnrollmentWeight = Math.max(newMaxEnrollmentWeight, e.getRequest().getWeight()); 269 } 270 } 271 iMaxEnrollmentWeight = newMaxEnrollmentWeight; 272 } 273 } 274 } 275 276 /** Set of assigned enrollments */ 277 @Override 278 public Set<Enrollment> getEnrollments() { 279 return iEnrollments; 280 } 281 282 /** 283 * Enrollment weight -- weight of all requests which have an enrollment that 284 * contains this section, excluding the given one. See 285 * {@link Request#getWeight()}. 286 */ 287 public double getEnrollmentWeight(Request excludeRequest) { 288 double weight = iEnrollmentWeight; 289 if (excludeRequest != null && excludeRequest.getAssignment() != null 290 && iEnrollments.contains(excludeRequest.getAssignment())) 291 weight -= excludeRequest.getWeight(); 292 return weight; 293 } 294 295 /** 296 * Maximal weight of a single enrollment in the section 297 */ 298 public double getMaxEnrollmentWeight() { 299 return iMaxEnrollmentWeight; 300 } 301 302 /** 303 * Minimal weight of a single enrollment in the section 304 */ 305 public double getMinEnrollmentWeight() { 306 return iMinEnrollmentWeight; 307 } 308 309 /** Long name: subpart name + time long name + room names + instructor names */ 310 public String getLongName() { 311 return getSubpart().getName() + " " + getName() + " " + (getTime() == null ? "" : " " + getTime().getLongName()) 312 + (getNrRooms() == 0 ? "" : " " + getPlacement().getRoomName(",")) 313 + (getChoice().getInstructorNames() == null ? "" : " " + getChoice().getInstructorNames()); 314 } 315 316 @Override 317 public String toString() { 318 return getSubpart().getConfig().getOffering().getName() + " " + getSubpart().getName() + " " + getName() 319 + (getTime() == null ? "" : " " + getTime().getLongName()) 320 + (getNrRooms() == 0 ? "" : " " + getPlacement().getRoomName(",")) 321 + (getChoice().getInstructorNames() == null ? "" : " " + getChoice().getInstructorNames()) + " (L:" 322 + (getLimit() < 0 ? "unlimited" : "" + getLimit()) 323 + (getPenalty() == 0.0 ? "" : ",P:" + sDF.format(getPenalty())) + ")"; 324 } 325 326 /** A (student) choice representing this section. */ 327 public Choice getChoice() { 328 return iChoice; 329 } 330 331 /** 332 * Return penalty which is added to an enrollment that contains this 333 * section. 334 */ 335 public double getPenalty() { 336 return iPenalty; 337 } 338 339 /** Set penalty which is added to an enrollment that contains this section. */ 340 public void setPenalty(double penalty) { 341 iPenalty = penalty; 342 } 343 344 /** 345 * Compare two sections, prefer sections with lower penalty and more open 346 * space 347 */ 348 @Override 349 public int compareTo(Section s) { 350 int cmp = Double.compare(getPenalty(), s.getPenalty()); 351 if (cmp != 0) 352 return cmp; 353 cmp = Double.compare(getLimit() - getEnrollmentWeight(null), s.getLimit() - s.getEnrollmentWeight(null)); 354 if (cmp != 0) 355 return cmp; 356 return Double.compare(getId(), s.getId()); 357 } 358 359 /** 360 * Return the amount of space of this section that is held for incoming 361 * students. This attribute is computed during the batch sectioning (it is 362 * the overall weight of dummy students enrolled in this section) and it is 363 * being updated with each incomming student during the online sectioning. 364 */ 365 public double getSpaceHeld() { 366 return iSpaceHeld; 367 } 368 369 /** 370 * Set the amount of space of this section that is held for incoming 371 * students. See {@link Section#getSpaceHeld()} for more info. 372 */ 373 public void setSpaceHeld(double spaceHeld) { 374 iSpaceHeld = spaceHeld; 375 } 376 377 /** 378 * Return the amount of space of this section that is expected to be taken 379 * by incoming students. This attribute is computed during the batch 380 * sectioning (for each dummy student that can attend this section (without 381 * any conflict with other enrollments of that student), 1 / x where x is 382 * the number of such sections of this subpart is added to this value). 383 * Also, this value is being updated with each incomming student during the 384 * online sectioning. 385 */ 386 public double getSpaceExpected() { 387 return iSpaceExpected; 388 } 389 390 /** 391 * Set the amount of space of this section that is expected to be taken by 392 * incoming students. See {@link Section#getSpaceExpected()} for more info. 393 */ 394 public void setSpaceExpected(double spaceExpected) { 395 iSpaceExpected = spaceExpected; 396 } 397 398 /** 399 * Online sectioning penalty. 400 */ 401 public double getOnlineSectioningPenalty() { 402 if (getLimit() <= 0) 403 return 0.0; 404 405 double available = getLimit() - getEnrollmentWeight(null); 406 407 double penalty = (getSpaceExpected() - available) / getLimit(); 408 409 return Math.max(-1.0, Math.min(1.0, penalty)); 410 } 411 412 /** 413 * Return true if overlaps are allowed, but the number of overlapping slots should be minimized. 414 * This can be changed on the subpart, using {@link Subpart#setAllowOverlap(boolean)}. 415 **/ 416 @Override 417 public boolean isAllowOverlap() { 418 return iSubpart.isAllowOverlap(); 419 } 420 421 /** Sections first, then by {@link FreeTimeRequest#getId()} */ 422 @Override 423 public int compareById(Assignment a) { 424 if (a instanceof Section) { 425 return new Long(getId()).compareTo(((Section)a).getId()); 426 } else { 427 return -1; 428 } 429 } 430 431 /** 432 * Available space in the section that is not reserved by any section reservation 433 * @param excludeRequest excluding given request (if not null) 434 **/ 435 public double getUnreservedSpace(Request excludeRequest) { 436 // section is unlimited -> there is unreserved space unless there is an unlimited reservation too 437 // (in which case there is no unreserved space) 438 if (getLimit() < 0) { 439 // exclude reservations that are not directly set on this section 440 for (Reservation r: getSectionReservations()) { 441 // ignore expired reservations 442 if (r.isExpired()) continue; 443 // there is an unlimited reservation -> no unreserved space 444 if (r.getLimit() < 0) return 0.0; 445 } 446 return Double.MAX_VALUE; 447 } 448 449 double available = getLimit() - getEnrollmentWeight(excludeRequest); 450 // exclude reservations that are not directly set on this section 451 for (Reservation r: getSectionReservations()) { 452 // ignore expired reservations 453 if (r.isExpired()) continue; 454 // unlimited reservation -> all the space is reserved 455 if (r.getLimit() < 0.0) return 0.0; 456 // compute space that can be potentially taken by this reservation 457 double reserved = r.getReservedAvailableSpace(excludeRequest); 458 // deduct the space from available space 459 available -= Math.max(0.0, reserved); 460 } 461 462 return available; 463 } 464 465 /** 466 * Total space in the section that cannot be used by any section reservation 467 **/ 468 public double getTotalUnreservedSpace() { 469 if (iTotalUnreservedSpace == null) 470 iTotalUnreservedSpace = getTotalUnreservedSpaceNoCache(); 471 return iTotalUnreservedSpace; 472 } 473 private Double iTotalUnreservedSpace = null; 474 private double getTotalUnreservedSpaceNoCache() { 475 // section is unlimited -> there is unreserved space unless there is an unlimited reservation too 476 // (in which case there is no unreserved space) 477 if (getLimit() < 0) { 478 // exclude reservations that are not directly set on this section 479 for (Reservation r: getSectionReservations()) { 480 // ignore expired reservations 481 if (r.isExpired()) continue; 482 // there is an unlimited reservation -> no unreserved space 483 if (r.getLimit() < 0) return 0.0; 484 } 485 return Double.MAX_VALUE; 486 } 487 488 // we need to check all reservations linked with this section 489 double available = getLimit(), reserved = 0, exclusive = 0; 490 Set<Section> sections = new HashSet<Section>(); 491 reservations: for (Reservation r: getSectionReservations()) { 492 // ignore expired reservations 493 if (r.isExpired()) continue; 494 // unlimited reservation -> no unreserved space 495 if (r.getLimit() < 0) return 0.0; 496 for (Section s: r.getSections(getSubpart())) { 497 if (s.equals(this)) continue; 498 if (s.getLimit() < 0) continue reservations; 499 if (sections.add(s)) 500 available += s.getLimit(); 501 } 502 reserved += r.getLimit(); 503 if (r.getSections(getSubpart()).size() == 1) 504 exclusive += r.getLimit(); 505 } 506 507 return Math.min(available - reserved, getLimit() - exclusive); 508 } 509 510 511 /** 512 * Get reservations for this section 513 */ 514 public List<Reservation> getReservations() { 515 if (iReservations == null) { 516 iReservations = new ArrayList<Reservation>(); 517 for (Reservation r: getSubpart().getConfig().getOffering().getReservations()) { 518 if (r.getSections(getSubpart()) == null || r.getSections(getSubpart()).contains(this)) 519 iReservations.add(r); 520 } 521 } 522 return iReservations; 523 } 524 private List<Reservation> iReservations = null; 525 526 /** 527 * Get reservations that require this section 528 */ 529 public List<Reservation> getSectionReservations() { 530 if (iSectionReservations == null) { 531 iSectionReservations = new ArrayList<Reservation>(); 532 for (Reservation r: getSubpart().getSectionReservations()) { 533 if (r.getSections(getSubpart()).contains(this)) 534 iSectionReservations.add(r); 535 } 536 } 537 return iSectionReservations; 538 } 539 private List<Reservation> iSectionReservations = null; 540 541 /** 542 * Clear reservation information that was cached on this section 543 */ 544 public void clearReservationCache() { 545 iReservations = null; 546 iSectionReservations = null; 547 iTotalUnreservedSpace = null; 548 } 549 550 /** 551 * Return course-dependent section name 552 */ 553 public String getName(long courseId) { 554 if (iNameByCourse == null) return getName(); 555 String name = iNameByCourse.get(courseId); 556 return (name == null ? getName() : name); 557 } 558 559 /** 560 * Set course-dependent section name 561 */ 562 public void setName(long courseId, String name) { 563 if (iNameByCourse == null) iNameByCourse = new HashMap<Long, String>(); 564 iNameByCourse.put(courseId, name); 565 } 566 567 /** 568 * Return course-dependent section names 569 */ 570 public Map<Long, String> getNameByCourse() { return iNameByCourse; } 571 572 @Override 573 public boolean equals(Object o) { 574 if (o == null || !(o instanceof Section)) return false; 575 return getId() == ((Section)o).getId(); 576 } 577 578 @Override 579 public int hashCode() { 580 return (int) (iId ^ (iId >>> 32)); 581 } 582 583 /** 584 * Section note 585 */ 586 public String getNote() { return iNote; } 587 588 /** 589 * Section note 590 */ 591 public void setNote(String note) { iNote = note; } 592 }