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