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.assignment.context.CanInheritContext;
013import org.cpsolver.ifs.model.Model;
014import org.cpsolver.studentsct.StudentSectioningModel;
015import org.cpsolver.studentsct.model.Config;
016import org.cpsolver.studentsct.model.Course;
017import org.cpsolver.studentsct.model.CourseRequest;
018import org.cpsolver.studentsct.model.Enrollment;
019import org.cpsolver.studentsct.model.Offering;
020import org.cpsolver.studentsct.model.Request;
021import org.cpsolver.studentsct.model.Section;
022import org.cpsolver.studentsct.model.Student;
023import org.cpsolver.studentsct.model.Subpart;
024
025
026
027/**
028 * Abstract reservation. This abstract class allow some section, courses,
029 * and other parts to be reserved to particular group of students. A reservation
030 * can be unlimited (any number of students of that particular group can attend
031 * a course, section, etc.) or with a limit (only given number of seats is
032 * reserved to the students of the particular group).
033 * 
034 * <br>
035 * <br>
036 * 
037 * @version StudentSct 1.3 (Student Sectioning)<br>
038 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
039 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
040 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
041 * <br>
042 *          This library is free software; you can redistribute it and/or modify
043 *          it under the terms of the GNU Lesser General Public License as
044 *          published by the Free Software Foundation; either version 3 of the
045 *          License, or (at your option) any later version. <br>
046 * <br>
047 *          This library is distributed in the hope that it will be useful, but
048 *          WITHOUT ANY WARRANTY; without even the implied warranty of
049 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
050 *          Lesser General Public License for more details. <br>
051 * <br>
052 *          You should have received a copy of the GNU Lesser General Public
053 *          License along with this library; if not see
054 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
055 */
056public abstract class Reservation extends AbstractClassWithContext<Request, Enrollment, Reservation.ReservationContext>
057    implements AssignmentComparable<Reservation, Request, Enrollment>, CanInheritContext<Request, Enrollment, Reservation.ReservationContext> {
058    /** Reservation unique id */
059    private long iId = 0;
060    
061    /** Is reservation expired? */
062    private boolean iExpired;
063    
064    /** Instructional offering on which the reservation is set, required */
065    private Offering iOffering;
066
067    /** One or more configurations, if applicable */ 
068    private Set<Config> iConfigs = new HashSet<Config>();
069    
070    /** One or more sections, if applicable */
071    private Map<Subpart, Set<Section>> iSections = new HashMap<Subpart, Set<Section>>();
072    
073    /** Reservation priority */
074    private int iPriority = 100;
075    
076    /** Must this reservation be used */
077    private boolean iMustBeUsed = false;
078    
079    /** Can assign over class / configuration / course limit */
080    private boolean iCanAssignOverLimit = false;
081    
082    /** Does this reservation allow for overlaps */
083    private boolean iAllowOverlap = false;
084    
085    /**
086     * Constructor
087     * @param id reservation unique id
088     * @param offering instructional offering on which the reservation is set
089     * @param priority reservation priority
090     * @param mustBeUsed must this reservation be used
091     * @param canAssignOverLimit can assign over class / configuration / course limit
092     * @param allowOverlap does this reservation allow for overlaps
093     */
094    public Reservation(long id, Offering offering, int priority, boolean mustBeUsed, boolean canAssignOverLimit, boolean allowOverlap) {
095        iId = id;
096        iOffering = offering;
097        iOffering.getReservations().add(this);
098        iOffering.clearReservationCache();
099        iPriority = priority;
100        iMustBeUsed = mustBeUsed;
101        iCanAssignOverLimit = canAssignOverLimit;
102        iAllowOverlap = allowOverlap;
103    }
104    
105    /**
106     * Reservation  id
107     * @return reservation unique id
108     */
109    public long getId() { return iId; }
110    
111    /**
112     * Reservation limit
113     * @return reservation limit, -1 for unlimited
114     */
115    public abstract double getReservationLimit();
116    
117    
118    /** Reservation priority (e.g., individual reservations first) 
119     * @return reservation priority
120     **/
121    public int getPriority() {
122        return iPriority;
123    }
124    
125    /**
126     * Set reservation priority (e.g., individual reservations first) 
127     * @param priority reservation priority
128     */
129    public void setPriority(int priority) {
130        iPriority = priority; 
131    }
132    
133    /**
134     * Returns true if the student is applicable for the reservation
135     * @param student a student 
136     * @return true if student can use the reservation to get into the course / configuration / section
137     */
138    public abstract boolean isApplicable(Student student);
139
140    /**
141     * Instructional offering on which the reservation is set.
142     * @return instructional offering
143     */
144    public Offering getOffering() { return iOffering; }
145    
146    /**
147     * One or more configurations on which the reservation is set (optional).
148     * @return instructional offering configurations
149     */
150    public Set<Config> getConfigs() { return iConfigs; }
151    
152    /**
153     * Add a configuration (of the offering {@link Reservation#getOffering()}) to this reservation
154     * @param config instructional offering configuration
155     */
156    public void addConfig(Config config) {
157        iConfigs.add(config);
158        clearLimitCapCache();
159    }
160    
161    /**
162     * One or more sections on which the reservation is set (optional).
163     * @return class restrictions
164     */
165    public Map<Subpart, Set<Section>> getSections() { return iSections; }
166    
167    /**
168     * One or more sections on which the reservation is set (optional).
169     * @param subpart scheduling subpart
170     * @return class restrictions for the given scheduling subpart
171     */
172    public Set<Section> getSections(Subpart subpart) {
173        return iSections.get(subpart);
174    }
175    
176    /**
177     * Add a section (of the offering {@link Reservation#getOffering()}) to this reservation.
178     * This will also add all parent sections and the appropriate configuration to the offering.
179     * @param section a class restriction
180     */
181    public void addSection(Section section) {
182        addConfig(section.getSubpart().getConfig());
183        while (section != null) {
184            Set<Section> sections = iSections.get(section.getSubpart());
185            if (sections == null) {
186                sections = new HashSet<Section>();
187                iSections.put(section.getSubpart(), sections);
188            }
189            sections.add(section);
190            section = section.getParent();
191        }
192        clearLimitCapCache();
193    }
194    
195    /**
196     * Return true if the given enrollment meets the reservation.
197     * @param enrollment given enrollment
198     * @return true if the given enrollment meets the reservation
199     */
200    public boolean isIncluded(Enrollment enrollment) {
201        // Free time request are never included
202        if (enrollment.getConfig() == null) return false;
203        
204        // Check the offering
205        if (!iOffering.equals(enrollment.getConfig().getOffering())) return false;
206        
207        // If there are configurations, check the configuration
208        if (!iConfigs.isEmpty() && !iConfigs.contains(enrollment.getConfig())) return false;
209        
210        // Check all the sections of the enrollment
211        for (Section section: enrollment.getSections()) {
212            Set<Section> sections = iSections.get(section.getSubpart());
213            if (sections != null && !sections.contains(section))
214                return false;
215        }
216        
217        return true;
218    }
219    
220    /**
221     * True if the enrollment can be done using this reservation
222     * @param assignment current assignment
223     * @param enrollment given enrollment
224     * @return true if the given enrollment can be assigned
225     */
226    public boolean canEnroll(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
227        // Check if student can use this reservation
228        if (!isApplicable(enrollment.getStudent())) return false;
229        
230        // Check if the enrollment meets the reservation
231        if (!isIncluded(enrollment)) return false;
232
233        // Check the limit
234        return getLimit() < 0 || getContext(assignment).getUsedSpace() + enrollment.getRequest().getWeight() <= getLimit();
235    }
236    
237    /**
238     * True if can go over the course / config / section limit. Only to be used in the online sectioning. 
239     * @return can assign over class / configuration / course limit
240      */
241    public boolean canAssignOverLimit() {
242        return iCanAssignOverLimit;
243    }
244    
245    /**
246     * True if the batch solver can assign the reservation over the course / config / section limit.
247     * @return {@link Reservation#canAssignOverLimit()} and {@link StudentSectioningModel#getReservationCanAssignOverTheLimit()}
248     */
249    public boolean canBatchAssignOverLimit() {
250        return canAssignOverLimit() && (iOffering.getModel() == null || ((StudentSectioningModel)iOffering.getModel()).getReservationCanAssignOverTheLimit());
251    }
252    
253    /**
254     * Set to true if a student meeting this reservation can go over the course / config / section limit.
255     * @param canAssignOverLimit can assign over class / configuration / course limit
256     */
257    public void setCanAssignOverLimit(boolean canAssignOverLimit) {
258        iCanAssignOverLimit = canAssignOverLimit;
259    }
260    
261    /**
262     * If true, student must use the reservation (if applicable). Expired reservations do not need to be used. 
263     * @return must this reservation be used
264     */
265    public boolean mustBeUsed() {
266        return iMustBeUsed && !isExpired();
267    }
268    
269    /**
270     * Set to true if the student must use the reservation (if applicable)
271     * @param mustBeUsed must this reservation be used
272     */
273    public void setMustBeUsed(boolean mustBeUsed) {
274        iMustBeUsed = mustBeUsed;
275    }
276    
277    /**
278     * Reservation restrictivity (estimated percentage of enrollments that include this reservation, 1.0 reservation on the whole offering)
279     * @return computed restrictivity
280     */
281    public double getRestrictivity() {
282        if (iCachedRestrictivity == null) {
283            if (getConfigs().isEmpty()) return 1.0;
284            int nrChoices = 0, nrMatchingChoices = 0;
285            for (Config config: getOffering().getConfigs()) {
286                int x[] = nrChoices(config, 0, new HashSet<Section>(), getConfigs().contains(config));
287                nrChoices += x[0];
288                nrMatchingChoices += x[1];
289            }
290            iCachedRestrictivity = ((double)nrMatchingChoices) / nrChoices;
291        }
292        return iCachedRestrictivity;
293    }
294    private Double iCachedRestrictivity = null;
295    
296    
297    /** Number of choices and number of chaing choices in the given sub enrollment */
298    private int[] nrChoices(Config config, int idx, HashSet<Section> sections, boolean matching) {
299        if (config.getSubparts().size() == idx) {
300            return new int[]{1, matching ? 1 : 0};
301        } else {
302            Subpart subpart = config.getSubparts().get(idx);
303            Set<Section> matchingSections = getSections(subpart);
304            int choicesThisSubpart = 0;
305            int matchingChoicesThisSubpart = 0;
306            for (Section section : subpart.getSections()) {
307                if (section.getParent() != null && !sections.contains(section.getParent()))
308                    continue;
309                if (section.isOverlapping(sections))
310                    continue;
311                sections.add(section);
312                boolean m = matching && (matchingSections == null || matchingSections.contains(section));
313                int[] x = nrChoices(config, 1 + idx, sections, m);
314                choicesThisSubpart += x[0];
315                matchingChoicesThisSubpart += x[1];
316                sections.remove(section);
317            }
318            return new int[] {choicesThisSubpart, matchingChoicesThisSubpart};
319        }
320    }
321    
322    /**
323     * Priority first, than restrictivity (more restrictive first), than availability (more available first), than id 
324     */
325    @Override
326    public int compareTo(Assignment<Request, Enrollment> assignment, Reservation r) {
327        if (getPriority() != r.getPriority()) {
328            return (getPriority() < r.getPriority() ? -1 : 1);
329        }
330        int cmp = Double.compare(getRestrictivity(), r.getRestrictivity());
331        if (cmp != 0) return cmp;
332        cmp = - Double.compare(getContext(assignment).getReservedAvailableSpace(assignment, null), r.getContext(assignment).getReservedAvailableSpace(assignment, null));
333        if (cmp != 0) return cmp;
334        return new Long(getId()).compareTo(r.getId());
335    }
336    
337    /**
338     * Priority first, than restrictivity (more restrictive first), than id 
339     */
340    @Override
341    public int compareTo(Reservation r) {
342        if (getPriority() != r.getPriority()) {
343            return (getPriority() < r.getPriority() ? -1 : 1);
344        }
345        int cmp = Double.compare(getRestrictivity(), r.getRestrictivity());
346        if (cmp != 0) return cmp;
347        return new Long(getId()).compareTo(r.getId());
348    }
349    
350    /**
351     * Return minimum of two limits where -1 counts as unlimited (any limit is smaller)
352     */
353    private static double min(double l1, double l2) {
354        return (l1 < 0 ? l2 : l2 < 0 ? l1 : Math.min(l1, l2));
355    }
356    
357    /**
358     * Add two limits where -1 counts as unlimited (unlimited plus anything is unlimited)
359     */
360    private static double add(double l1, double l2) {
361        return (l1 < 0 ? -1 : l2 < 0 ? -1 : l1 + l2);
362    }
363    
364
365    /** Limit cap cache */
366    private Double iLimitCap = null;
367
368    /**
369     * Compute limit cap (maximum number of students that can get into the offering using this reservation)
370     * @return reservation limit cap
371     */
372    public double getLimitCap() {
373        if (iLimitCap == null) iLimitCap = getLimitCapNoCache();
374        return iLimitCap;
375    }
376
377    /**
378     * Compute limit cap (maximum number of students that can get into the offering using this reservation)
379     */
380    private double getLimitCapNoCache() {
381        if (getConfigs().isEmpty()) return -1; // no config -> can be unlimited
382        
383        if (canAssignOverLimit()) return -1; // can assign over limit -> no cap
384        
385        // config cap
386        double cap = 0;
387        for (Config config: iConfigs)
388            cap = add(cap, config.getLimit());
389        
390        for (Set<Section> sections: getSections().values()) {
391            // subpart cap
392            double subpartCap = 0;
393            for (Section section: sections)
394                subpartCap = add(subpartCap, section.getLimit());
395            
396            // minimize
397            cap = min(cap, subpartCap);
398        }
399        
400        return cap;
401    }
402    
403    /**
404     * Clear limit cap cache
405     */
406    private void clearLimitCapCache() {
407        iLimitCap = null;
408    }
409    
410    /**
411     * Reservation limit capped the limit cap (see {@link Reservation#getLimitCap()})
412     * @return reservation limit, -1 if unlimited
413     */
414    public double getLimit() {
415        return min(getLimitCap(), getReservationLimit());
416    }
417    
418    /**
419     * True if holding this reservation allows a student to have attend overlapping class. 
420     * @return does this reservation allow for overlaps
421     */
422    public boolean isAllowOverlap() {
423        return iAllowOverlap;
424    }
425    
426    /**
427     * Set to true if holding this reservation allows a student to have attend overlapping class.
428     * @param allowOverlap does this reservation allow for overlaps
429     */
430    public void setAllowOverlap(boolean allowOverlap) {
431        iAllowOverlap = allowOverlap;
432    }
433    
434    /**
435     * Set reservation expiration. If a reservation is expired, it works as ordinary reservation
436     * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students
437     * of getting into the offering / config / section.  
438     * @param expired is this reservation expired
439     */
440    public void setExpired(boolean expired) {
441        iExpired = expired;
442    }
443    
444    /**
445     * True if the reservation is expired. If a reservation is expired, it works as ordinary reservation
446     * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students
447     * of getting into the offering / config / section.
448     * @return is this reservation expired
449     */
450    public boolean isExpired() {
451        return iExpired;
452    }
453    
454    @Override
455    public Model<Request, Enrollment> getModel() {
456        return getOffering().getModel();
457    }
458    
459    /**
460     * Available reserved space
461     * @param assignment current assignment
462     * @param excludeRequest excluding given request (if not null)
463     * @return available reserved space
464     **/
465    public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) {
466        return getContext(assignment).getReservedAvailableSpace(assignment, excludeRequest);
467    }
468    
469    /** Enrollments assigned using this reservation 
470     * @param assignment current assignment
471     * @return assigned enrollments of this reservation
472     **/
473    public Set<Enrollment> getEnrollments(Assignment<Request, Enrollment> assignment) {
474        return getContext(assignment).getEnrollments();
475    }
476
477    @Override
478    public ReservationContext createAssignmentContext(Assignment<Request, Enrollment> assignment) {
479        return new ReservationContext(assignment);
480    }
481    
482
483    @Override
484    public ReservationContext inheritAssignmentContext(Assignment<Request, Enrollment> assignment, ReservationContext parentContext) {
485        return new ReservationContext(parentContext);
486    }
487
488    
489    public class ReservationContext implements AssignmentConstraintContext<Request, Enrollment> {
490        /** Enrollments included in this reservation */
491        private Set<Enrollment> iEnrollments = new HashSet<Enrollment>();
492        
493        /** Used part of the limit */
494        private double iUsed = 0;
495        private boolean iReadOnly = false;
496
497        public ReservationContext(Assignment<Request, Enrollment> assignment) {
498            for (Course course: getOffering().getCourses())
499                for (CourseRequest request: course.getRequests()) {
500                    Enrollment enrollment = assignment.getValue(request);
501                    if (enrollment != null && Reservation.this.equals(enrollment.getReservation()))
502                        assigned(assignment, enrollment);
503                }
504        }
505        
506        public ReservationContext(ReservationContext parent) {
507            iUsed = parent.iUsed;
508            iEnrollments = parent.iEnrollments;
509            iReadOnly = true;
510        }
511
512        /** Notify reservation about an unassignment */
513        @Override
514        public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
515            if (iReadOnly) {
516                iEnrollments = new HashSet<Enrollment>(iEnrollments);
517                iReadOnly = false;
518            }
519            if (iEnrollments.add(enrollment))
520                iUsed += enrollment.getRequest().getWeight();
521        }
522
523        /** Notify reservation about an assignment */
524        @Override
525        public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
526            if (iReadOnly) {
527                iEnrollments = new HashSet<Enrollment>(iEnrollments);
528                iReadOnly = false;
529            }
530            if (iEnrollments.remove(enrollment))
531                iUsed -= enrollment.getRequest().getWeight();
532        }
533        
534        /** Enrollments assigned using this reservation 
535         * @return assigned enrollments of this reservation
536         **/
537        public Set<Enrollment> getEnrollments() {
538            return iEnrollments;
539        }
540        
541        /** Used space 
542         * @return spaced used of this reservation
543         **/
544        public double getUsedSpace() {
545            return iUsed;
546        }
547        
548        /**
549         * Available reserved space
550         * @param assignment current assignment
551         * @param excludeRequest excluding given request (if not null)
552         * @return available reserved space
553         **/
554        public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) {
555            // Unlimited
556            if (getLimit() < 0) return Double.MAX_VALUE;
557            
558            double reserved = getLimit() - getContext(assignment).getUsedSpace();
559            if (excludeRequest != null && assignment.getValue(excludeRequest) != null && iEnrollments.contains(assignment.getValue(excludeRequest)))
560                reserved += excludeRequest.getWeight();
561            
562            return reserved;
563        }
564    }
565}