    001package net.sf.cpsolver.studentsct.model;
    002
    003import java.text.DecimalFormat;
    004import java.util.ArrayList;
    005import java.util.HashMap;
    006import java.util.HashSet;
    007import java.util.List;
    008import java.util.Map;
    009import java.util.Set;
    010
    011import net.sf.cpsolver.coursett.model.Placement;
    012import net.sf.cpsolver.coursett.model.RoomLocation;
    013import net.sf.cpsolver.coursett.model.TimeLocation;
    014import 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 Tomáš Müller<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 */
    049public 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}