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    /**
071     * Constructor
072     * @param id reservation unique id
073     * @param offering instructional offering on which the reservation is set
074     */
075    public Reservation(long id, Offering offering) {
076        iId = id;
077        iOffering = offering;
078        iOffering.getReservations().add(this);
079        iOffering.clearReservationCache();
080    }
081    
082    /**
083     * Reservation  id
084     * @return reservation unique id
085     */
086    public long getId() { return iId; }
087    
088    /**
089     * Reservation limit
090     * @return reservation limit, -1 for unlimited
091     */
092    public abstract double getReservationLimit();
093    
094    
095    /** Reservation priority (e.g., individual reservations first) 
096     * @return reservation priority
097     **/
098    public abstract int getPriority();
099    
100    /**
101     * Returns true if the student is applicable for the reservation
102     * @param student a student 
103     * @return true if student can use the reservation to get into the course / configuration / section
104     */
105    public abstract boolean isApplicable(Student student);
106
107    /**
108     * Instructional offering on which the reservation is set.
109     * @return instructional offering
110     */
111    public Offering getOffering() { return iOffering; }
112    
113    /**
114     * One or more configurations on which the reservation is set (optional).
115     * @return instructional offering configurations
116     */
117    public Set<Config> getConfigs() { return iConfigs; }
118    
119    /**
120     * Add a configuration (of the offering {@link Reservation#getOffering()}) to this reservation
121     * @param config instructional offering configuration
122     */
123    public void addConfig(Config config) {
124        iConfigs.add(config);
125        clearLimitCapCache();
126    }
127    
128    /**
129     * One or more sections on which the reservation is set (optional).
130     * @return class restrictions
131     */
132    public Map<Subpart, Set<Section>> getSections() { return iSections; }
133    
134    /**
135     * One or more sections on which the reservation is set (optional).
136     * @param subpart scheduling subpart
137     * @return class restrictions for the given scheduling subpart
138     */
139    public Set<Section> getSections(Subpart subpart) {
140        return iSections.get(subpart);
141    }
142    
143    /**
144     * Add a section (of the offering {@link Reservation#getOffering()}) to this reservation.
145     * This will also add all parent sections and the appropriate configuration to the offering.
146     * @param section a class restriction
147     */
148    public void addSection(Section section) {
149        addConfig(section.getSubpart().getConfig());
150        while (section != null) {
151            Set<Section> sections = iSections.get(section.getSubpart());
152            if (sections == null) {
153                sections = new HashSet<Section>();
154                iSections.put(section.getSubpart(), sections);
155            }
156            sections.add(section);
157            section = section.getParent();
158        }
159        clearLimitCapCache();
160    }
161    
162    /**
163     * Return true if the given enrollment meets the reservation.
164     * @param enrollment given enrollment
165     * @return true if the given enrollment meets the reservation
166     */
167    public boolean isIncluded(Enrollment enrollment) {
168        // Free time request are never included
169        if (enrollment.getConfig() == null) return false;
170        
171        // Check the offering
172        if (!iOffering.equals(enrollment.getConfig().getOffering())) return false;
173        
174        // If there are configurations, check the configuration
175        if (!iConfigs.isEmpty() && !iConfigs.contains(enrollment.getConfig())) return false;
176        
177        // Check all the sections of the enrollment
178        for (Section section: enrollment.getSections()) {
179            Set<Section> sections = iSections.get(section.getSubpart());
180            if (sections != null && !sections.contains(section))
181                return false;
182        }
183        
184        return true;
185    }
186    
187    /**
188     * True if the enrollment can be done using this reservation
189     * @param assignment current assignment
190     * @param enrollment given enrollment
191     * @return true if the given enrollment can be assigned
192     */
193    public boolean canEnroll(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
194        // Check if student can use this reservation
195        if (!isApplicable(enrollment.getStudent())) return false;
196        
197        // Check if the enrollment meets the reservation
198        if (!isIncluded(enrollment)) return false;
199
200        // Check the limit
201        return getLimit() < 0 || getContext(assignment).getUsedSpace() + enrollment.getRequest().getWeight() <= getLimit();
202    }
203    
204    /**
205     * True if can go over the course / config / section limit. Only to be used in the online sectioning. 
206     * @return can assign over class / configuration / course limit
207      */
208    public abstract boolean canAssignOverLimit();
209    
210    /**
211     * If true, student must use the reservation (if applicable)
212     * @return must this reservation be used
213     */
214    public abstract boolean mustBeUsed();
215    
216    /**
217     * Reservation restrictivity (estimated percentage of enrollments that include this reservation, 1.0 reservation on the whole offering)
218     * @return computed restrictivity
219     */
220    public double getRestrictivity() {
221        if (iCachedRestrictivity == null) {
222            if (getConfigs().isEmpty()) return 1.0;
223            int nrChoices = 0, nrMatchingChoices = 0;
224            for (Config config: getOffering().getConfigs()) {
225                int x[] = nrChoices(config, 0, new HashSet<Section>(), getConfigs().contains(config));
226                nrChoices += x[0];
227                nrMatchingChoices += x[1];
228            }
229            iCachedRestrictivity = ((double)nrMatchingChoices) / nrChoices;
230        }
231        return iCachedRestrictivity;
232    }
233    private Double iCachedRestrictivity = null;
234    
235    
236    /** Number of choices and number of chaing choices in the given sub enrollment */
237    private int[] nrChoices(Config config, int idx, HashSet<Section> sections, boolean matching) {
238        if (config.getSubparts().size() == idx) {
239            return new int[]{1, matching ? 1 : 0};
240        } else {
241            Subpart subpart = config.getSubparts().get(idx);
242            Set<Section> matchingSections = getSections(subpart);
243            int choicesThisSubpart = 0;
244            int matchingChoicesThisSubpart = 0;
245            for (Section section : subpart.getSections()) {
246                if (section.getParent() != null && !sections.contains(section.getParent()))
247                    continue;
248                if (section.isOverlapping(sections))
249                    continue;
250                sections.add(section);
251                boolean m = matching && (matchingSections == null || matchingSections.contains(section));
252                int[] x = nrChoices(config, 1 + idx, sections, m);
253                choicesThisSubpart += x[0];
254                matchingChoicesThisSubpart += x[1];
255                sections.remove(section);
256            }
257            return new int[] {choicesThisSubpart, matchingChoicesThisSubpart};
258        }
259    }
260    
261    /**
262     * Priority first, than restrictivity (more restrictive first), than availability (more available first), than id 
263     */
264    @Override
265    public int compareTo(Assignment<Request, Enrollment> assignment, Reservation r) {
266        if (getPriority() != r.getPriority()) {
267            return (getPriority() < r.getPriority() ? -1 : 1);
268        }
269        int cmp = Double.compare(getRestrictivity(), r.getRestrictivity());
270        if (cmp != 0) return cmp;
271        cmp = - Double.compare(getContext(assignment).getReservedAvailableSpace(assignment, null), r.getContext(assignment).getReservedAvailableSpace(assignment, null));
272        if (cmp != 0) return cmp;
273        return new Long(getId()).compareTo(r.getId());
274    }
275    
276    /**
277     * Priority first, than restrictivity (more restrictive first), than id 
278     */
279    @Override
280    public int compareTo(Reservation r) {
281        if (getPriority() != r.getPriority()) {
282            return (getPriority() < r.getPriority() ? -1 : 1);
283        }
284        int cmp = Double.compare(getRestrictivity(), r.getRestrictivity());
285        if (cmp != 0) return cmp;
286        return new Long(getId()).compareTo(r.getId());
287    }
288    
289    /**
290     * Return minimum of two limits where -1 counts as unlimited (any limit is smaller)
291     */
292    private static double min(double l1, double l2) {
293        return (l1 < 0 ? l2 : l2 < 0 ? l1 : Math.min(l1, l2));
294    }
295    
296    /**
297     * Add two limits where -1 counts as unlimited (unlimited plus anything is unlimited)
298     */
299    private static double add(double l1, double l2) {
300        return (l1 < 0 ? -1 : l2 < 0 ? -1 : l1 + l2);
301    }
302    
303
304    /** Limit cap cache */
305    private Double iLimitCap = null;
306
307    /**
308     * Compute limit cap (maximum number of students that can get into the offering using this reservation)
309     * @return reservation limit cap
310     */
311    public double getLimitCap() {
312        if (iLimitCap == null) iLimitCap = getLimitCapNoCache();
313        return iLimitCap;
314    }
315
316    /**
317     * Compute limit cap (maximum number of students that can get into the offering using this reservation)
318     */
319    private double getLimitCapNoCache() {
320        if (getConfigs().isEmpty()) return -1; // no config -> can be unlimited
321        
322        if (canAssignOverLimit()) return -1; // can assign over limit -> no cap
323        
324        // config cap
325        double cap = 0;
326        for (Config config: iConfigs)
327            cap = add(cap, config.getLimit());
328        
329        for (Set<Section> sections: getSections().values()) {
330            // subpart cap
331            double subpartCap = 0;
332            for (Section section: sections)
333                subpartCap = add(subpartCap, section.getLimit());
334            
335            // minimize
336            cap = min(cap, subpartCap);
337        }
338        
339        return cap;
340    }
341    
342    /**
343     * Clear limit cap cache
344     */
345    private void clearLimitCapCache() {
346        iLimitCap = null;
347    }
348    
349    /**
350     * Reservation limit capped the limit cap (see {@link Reservation#getLimitCap()})
351     * @return reservation limit, -1 if unlimited
352     */
353    public double getLimit() {
354        return min(getLimitCap(), getReservationLimit());
355    }
356    
357    /**
358     * True if holding this reservation allows a student to have attend overlapping class. 
359     * @return does this reservation allow for overlaps
360     */
361    public boolean isAllowOverlap() {
362        return false;
363    }
364    
365    /**
366     * Set reservation expiration. If a reservation is expired, it works as ordinary reservation
367     * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students
368     * of getting into the offering / config / section.  
369     * @param expired is this reservation expired
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     * @return is this reservation expired
380     */
381    public boolean isExpired() {
382        return iExpired;
383    }
384    
385    @Override
386    public Model<Request, Enrollment> getModel() {
387        return getOffering().getModel();
388    }
389    
390    /**
391     * Available reserved space
392     * @param assignment current assignment
393     * @param excludeRequest excluding given request (if not null)
394     * @return available reserved space
395     **/
396    public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) {
397        return getContext(assignment).getReservedAvailableSpace(assignment, excludeRequest);
398    }
399    
400    /** Enrollments assigned using this reservation 
401     * @param assignment current assignment
402     * @return assigned enrollments of this reservation
403     **/
404    public Set<Enrollment> getEnrollments(Assignment<Request, Enrollment> assignment) {
405        return getContext(assignment).getEnrollments();
406    }
407
408    @Override
409    public ReservationContext createAssignmentContext(Assignment<Request, Enrollment> assignment) {
410        return new ReservationContext(assignment);
411    }
412    
413    public class ReservationContext implements AssignmentConstraintContext<Request, Enrollment> {
414        /** Enrollments included in this reservation */
415        private Set<Enrollment> iEnrollments = new HashSet<Enrollment>();
416        
417        /** Used part of the limit */
418        private double iUsed = 0;
419
420        public ReservationContext(Assignment<Request, Enrollment> assignment) {
421            for (Course course: getOffering().getCourses())
422                for (CourseRequest request: course.getRequests()) {
423                    Enrollment enrollment = assignment.getValue(request);
424                    if (enrollment != null && Reservation.this.equals(enrollment.getReservation()))
425                        assigned(assignment, enrollment);
426                }
427        }
428
429        /** Notify reservation about an unassignment */
430        @Override
431        public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
432            if (iEnrollments.add(enrollment))
433                iUsed += enrollment.getRequest().getWeight();
434        }
435
436        /** Notify reservation about an assignment */
437        @Override
438        public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
439            if (iEnrollments.remove(enrollment))
440                iUsed -= enrollment.getRequest().getWeight();
441        }
442        
443        /** Enrollments assigned using this reservation 
444         * @return assigned enrollments of this reservation
445         **/
446        public Set<Enrollment> getEnrollments() {
447            return iEnrollments;
448        }
449        
450        /** Used space 
451         * @return spaced used of this reservation
452         **/
453        public double getUsedSpace() {
454            return iUsed;
455        }
456        
457        /**
458         * Available reserved space
459         * @param assignment current assignment
460         * @param excludeRequest excluding given request (if not null)
461         * @return available reserved space
462         **/
463        public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) {
464            // Unlimited
465            if (getLimit() < 0) return Double.MAX_VALUE;
466            
467            double reserved = getLimit() - getContext(assignment).getUsedSpace();
468            if (excludeRequest != null && assignment.getValue(excludeRequest) != null && iEnrollments.contains(assignment.getValue(excludeRequest)))
469                reserved += excludeRequest.getWeight();
470            
471            return reserved;
472        }
473    }
474}