    001package net.sf.cpsolver.studentsct.reservation;
    002
    003import java.util.HashMap;
    004import java.util.HashSet;
    005import java.util.Map;
    006import java.util.Set;
    007
    008import net.sf.cpsolver.studentsct.model.Config;
    009import net.sf.cpsolver.studentsct.model.Enrollment;
    010import net.sf.cpsolver.studentsct.model.Offering;
    011import net.sf.cpsolver.studentsct.model.Request;
    012import net.sf.cpsolver.studentsct.model.Section;
    013import net.sf.cpsolver.studentsct.model.Student;
    014import net.sf.cpsolver.studentsct.model.Subpart;
    015
    016
    017/**
    018 * Abstract reservation. This abstract class allow some section, courses,
    019 * and other parts to be reserved to particular group of students. A reservation
    020 * can be unlimited (any number of students of that particular group can attend
    021 * a course, section, etc.) or with a limit (only given number of seats is
    022 * reserved to the students of the particular group).
    023 *
    024 * <br>
    025 * <br>
    026 *
    027 * @version StudentSct 1.2 (Student Sectioning)<br>
    028 *          Copyright (C) 2007 - 2010 Tomáš Müller<br>
    029 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    030 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    031 * <br>
    032 *          This library is free software; you can redistribute it and/or modify
    033 *          it under the terms of the GNU Lesser General Public License as
    034 *          published by the Free Software Foundation; either version 3 of the
    035 *          License, or (at your option) any later version. <br>
    036 * <br>
    037 *          This library is distributed in the hope that it will be useful, but
    038 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    039 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    040 *          Lesser General Public License for more details. <br>
    041 * <br>
    042 *          You should have received a copy of the GNU Lesser General Public
    043 *          License along with this library; if not see
    044 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    045 */
    046public abstract class Reservation implements Comparable<Reservation> {
    047    /** Reservation unique id */
    048    private long iId = 0;
    049
    050    /** Is reservation expired? */
    051    private boolean iExpired;
    052
    053    /** Instructional offering on which the reservation is set, required */
    054    private Offering iOffering;
    055
    056    /** One or more configurations, if applicable */
    057    private Set<Config> iConfigs = new HashSet<Config>();
    058
    059    /** One or more sections, if applicable */
    060    private Map<Subpart, Set<Section>> iSections = new HashMap<Subpart, Set<Section>>();
    061
    062    /** Enrollments included in this reservation */
    063    private Set<Enrollment> iEnrollments = new HashSet<Enrollment>();
    064
    065    /** Used part of the limit */
    066    private double iUsed = 0;
    067
    068    /**
    069     * Constructor
    070     * @param id reservation unique id
    071     * @param offering instructional offering on which the reservation is set
    072     */
    073    public Reservation(long id, Offering offering) {
    074        iId = id;
    075        iOffering = offering;
    076        iOffering.getReservations().add(this);
    077        iOffering.clearReservationCache();
    078    }
    079
    080    /**
    081     * Reservation  id
    082     */
    083    public long getId() { return iId; }
    084
    085    /**
    086     * Reservation limit
    087     */
    088    public abstract double getReservationLimit();
    089
    090
    091    /** Reservation priority (e.g., individual reservations first) */
    092    public abstract int getPriority();
    093
    094    /**
    095     * Returns true if the student is applicable for the reservation
    096     * @param student a student
    097     * @return true if student can use the reservation to get into the course / configuration / section
    098     */
    099    public abstract boolean isApplicable(Student student);
    100
    101    /**
    102     * Instructional offering on which the reservation is set.
    103     */
    104    public Offering getOffering() { return iOffering; }
    105
    106    /**
    107     * One or more configurations on which the reservation is set (optional).
    108     */
    109    public Set<Config> getConfigs() { return iConfigs; }
    110
    111    /**
    112     * Add a configuration (of the offering {@link Reservation#getOffering()}) to this reservation
    113     */
    114    public void addConfig(Config config) {
    115        iConfigs.add(config);
    116        clearLimitCapCache();
    117    }
    118
    119    /**
    120     * One or more sections on which the reservation is set (optional).
    121     */
    122    public Map<Subpart, Set<Section>> getSections() { return iSections; }
    123
    124    /**
    125     * One or more sections on which the reservation is set (optional).
    126     */
    127    public Set<Section> getSections(Subpart subpart) {
    128        return iSections.get(subpart);
    129    }
    130
    131    /**
    132     * Add a section (of the offering {@link Reservation#getOffering()}) to this reservation.
    133     * This will also add all parent sections and the appropriate configuration to the offering.
    134     */
    135    public void addSection(Section section) {
    136        addConfig(section.getSubpart().getConfig());
    137        while (section != null) {
    138            Set<Section> sections = iSections.get(section.getSubpart());
    139            if (sections == null) {
    140                sections = new HashSet<Section>();
    141                iSections.put(section.getSubpart(), sections);
    142            }
    143            sections.add(section);
    144            section = section.getParent();
    145        }
    146        clearLimitCapCache();
    147    }
    148
    149    /**
    150     * Return true if the given enrollment meets the reservation.
    151     */
    152    public boolean isIncluded(Enrollment enrollment) {
    153        // Free time request are never included
    154        if (enrollment.getConfig() == null) return false;
    155
    156        // Check the offering
    157        if (!iOffering.equals(enrollment.getConfig().getOffering())) return false;
    158
    159        // If there are configurations, check the configuration
    160        if (!iConfigs.isEmpty() && !iConfigs.contains(enrollment.getConfig())) return false;
    161
    162        // Check all the sections of the enrollment
    163        for (Section section: enrollment.getSections()) {
    164            Set<Section> sections = iSections.get(section.getSubpart());
    165            if (sections != null && !sections.contains(section))
    166                return false;
    167        }
    168
    169        return true;
    170    }
    171
    172    /**
    173     * True if the enrollment can be done using this configuration
    174     */
    175    public boolean canEnroll(Enrollment enrollment) {
    176        // Check if student can use this reservation
    177        if (!isApplicable(enrollment.getStudent())) return false;
    178
    179        // Check if the enrollment meets the reservation
    180        if (!isIncluded(enrollment)) return false;
    181
    182        // Check the limit
    183        return getLimit() < 0 || getUsedSpace() + enrollment.getRequest().getWeight() <= getLimit();
    184    }
    185
    186    /** Notify reservation about an unassignment */
    187    public void assigned(Enrollment enrollment) {
    188        iEnrollments.add(enrollment);
    189        iUsed += enrollment.getRequest().getWeight();
    190    }
    191
    192    /** Notify reservation about an assignment */
    193    public void unassigned(Enrollment enrollment) {
    194        iEnrollments.remove(enrollment);
    195        iUsed -= enrollment.getRequest().getWeight();
    196    }
    197
    198    /** Enrollments assigned using this reservation */
    199    public Set<Enrollment> getEnrollments() {
    200        return iEnrollments;
    201    }
    202
    203    /** Used space */
    204    public double getUsedSpace() {
    205        return iUsed;
    206    }
    207
    208    /**
    209     * Available reserved space
    210     * @param excludeRequest excluding given request (if not null)
    211     **/
    212    public double getReservedAvailableSpace(Request excludeRequest) {
    213        // Unlimited
    214        if (getLimit() < 0) return Double.MAX_VALUE;
    215
    216        double reserved = getLimit() - getUsedSpace();
    217        if (excludeRequest != null && excludeRequest.getAssignment() != null &&
    218            iEnrollments.contains(excludeRequest.getAssignment()))
    219            reserved += excludeRequest.getWeight();
    220
    221        return reserved;
    222    }
    223
    224    /**
    225     * True if can go over the course / config / section limit. Only to be used in the online sectioning.
    226      */
    227    public abstract boolean canAssignOverLimit();
    228
    229    /**
    230     * If true, student must use the reservation (if applicable)
    231     */
    232    public abstract boolean mustBeUsed();
    233
    234    /**
    235     * Reservation restrictivity (estimated percentage of enrollments that include this reservation, 1.0 reservation on the whole offering)
    236     */
    237    public double getRestrictivity() {
    238        if (iCachedRestrictivity == null) {
    239            if (getConfigs().isEmpty()) return 1.0;
    240            int nrChoices = 0, nrMatchingChoices = 0;
    241            for (Config config: getOffering().getConfigs()) {
    242                int x[] = nrChoices(config, 0, new HashSet<Section>(), getConfigs().contains(config));
    243                nrChoices += x[0];
    244                nrMatchingChoices += x[1];
    245            }
    246            iCachedRestrictivity = ((double)nrMatchingChoices) / nrChoices;
    247        }
    248        return iCachedRestrictivity;
    249    }
    250    private Double iCachedRestrictivity = null;
    251
    252
    253    /** Number of choices and number of chaing choices in the given sub enrollment */
    254    private int[] nrChoices(Config config, int idx, HashSet<Section> sections, boolean matching) {
    255        if (config.getSubparts().size() == idx) {
    256            return new int[]{1, matching ? 1 : 0};
    257        } else {
    258            Subpart subpart = config.getSubparts().get(idx);
    259            Set<Section> matchingSections = getSections(subpart);
    260            int choicesThisSubpart = 0;
    261            int matchingChoicesThisSubpart = 0;
    262            for (Section section : subpart.getSections()) {
    263                if (section.getParent() != null && !sections.contains(section.getParent()))
    264                    continue;
    265                if (section.isOverlapping(sections))
    266                    continue;
    267                sections.add(section);
    268                boolean m = matching && (matchingSections == null || matchingSections.contains(section));
    269                int[] x = nrChoices(config, 1 + idx, sections, m);
    270                choicesThisSubpart += x[0];
    271                matchingChoicesThisSubpart += x[1];
    272                sections.remove(section);
    273            }
    274            return new int[] {choicesThisSubpart, matchingChoicesThisSubpart};
    275        }
    276    }
    277
    278    /**
    279     * Priority first, than restrictivity (more restrictive first), than availability (more available first), than id
    280     */
    281    @Override
    282    public int compareTo(Reservation r) {
    283        if (getPriority() != r.getPriority()) {
    284            return (getPriority() < r.getPriority() ? -1 : 1);
    285        }
    286        int cmp = Double.compare(getRestrictivity(), r.getRestrictivity());
    287        if (cmp != 0) return cmp;
    288        cmp = - Double.compare(getReservedAvailableSpace(null), r.getReservedAvailableSpace(null));
    289        if (cmp != 0) return cmp;
    290        return new Long(getId()).compareTo(r.getId());
    291    }
    292
    293    /**
    294     * Return minimum of two limits where -1 counts as unlimited (any limit is smaller)
    295     */
    296    private static double min(double l1, double l2) {
    297        return (l1 < 0 ? l2 : l2 < 0 ? l1 : Math.min(l1, l2));
    298    }
    299
    300    /**
    301     * Add two limits where -1 counts as unlimited (unlimited plus anything is unlimited)
    302     */
    303    private static double add(double l1, double l2) {
    304        return (l1 < 0 ? -1 : l2 < 0 ? -1 : l1 + l2);
    305    }
    306
    307
    308    /** Limit cap cache */
    309    private Double iLimitCap = null;
    310
    311    /**
    312     * Compute limit cap (maximum number of students that can get into the offering using this reservation)
    313     */
    314    public double getLimitCap() {
    315        if (iLimitCap == null) iLimitCap = getLimitCapNoCache();
    316        return iLimitCap;
    317    }
    318
    319    /**
    320     * Compute limit cap (maximum number of students that can get into the offering using this reservation)
    321     */
    322    private double getLimitCapNoCache() {
    323        if (getConfigs().isEmpty()) return -1; // no config -> can be unlimited
    324
    325        if (canAssignOverLimit()) return -1; // can assign over limit -> no cap
    326
    327        // config cap
    328        double cap = 0;
    329        for (Config config: iConfigs)
    330            cap = add(cap, config.getLimit());
    331
    332        for (Set<Section> sections: getSections().values()) {
    333            // subpart cap
    334            double subpartCap = 0;
    335            for (Section section: sections)
    336                subpartCap = add(subpartCap, section.getLimit());
    337
    338            // minimize
    339            cap = min(cap, subpartCap);
    340        }
    341
    342        return cap;
    343    }
    344
    345    /**
    346     * Clear limit cap cache
    347     */
    348    private void clearLimitCapCache() {
    349        iLimitCap = null;
    350    }
    351
    352    /**
    353     * Reservation limit capped the limit cap (see {@link Reservation#getLimitCap()})
    354     */
    355    public double getLimit() {
    356        return min(getLimitCap(), getReservationLimit());
    357    }
    358
    359    /**
    360     * True if holding this reservation allows a student to have attend overlapping class.
    361     */
    362    public boolean isAllowOverlap() {
    363        return false;
    364    }
    365
    366    /**
    367     * Set reservation expiration. If a reservation is expired, it works as ordinary reservation
    368     * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students
    369     * of getting into the offering / config / section.
    370     */
    371    public void setExpired(boolean expired) {
    372        iExpired = expired;
    373    }
    374
    375    /**
    376     * True if the reservation is expired. If a reservation is expired, it works as ordinary reservation
    377     * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students
    378     * of getting into the offering / config / section.
    379     */
    380    public boolean isExpired() {
    381        return iExpired;
    382    }
    383}