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}