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    /** Does this reservation allow for disabled sections */
086    private boolean iAllowDisabled = false;
087    
088    /**
089     * Constructor
090     * @param id reservation unique id
091     * @param offering instructional offering on which the reservation is set
092     * @param priority reservation priority
093     * @param mustBeUsed must this reservation be used
094     * @param canAssignOverLimit can assign over class / configuration / course limit
095     * @param allowOverlap does this reservation allow for overlaps
096     */
097    public Reservation(long id, Offering offering, int priority, boolean mustBeUsed, boolean canAssignOverLimit, boolean allowOverlap) {
098        iId = id;
099        iOffering = offering;
100        iOffering.getReservations().add(this);
101        iOffering.clearReservationCache();
102        iPriority = priority;
103        iMustBeUsed = mustBeUsed;
104        iCanAssignOverLimit = canAssignOverLimit;
105        iAllowOverlap = allowOverlap;
106    }
107    
108    /**
109     * Reservation  id
110     * @return reservation unique id
111     */
112    public long getId() { return iId; }
113    
114    /**
115     * Reservation limit
116     * @return reservation limit, -1 for unlimited
117     */
118    public abstract double getReservationLimit();
119    
120    
121    /** Reservation priority (e.g., individual reservations first) 
122     * @return reservation priority
123     **/
124    public int getPriority() {
125        return iPriority;
126    }
127    
128    /**
129     * Set reservation priority (e.g., individual reservations first) 
130     * @param priority reservation priority
131     */
132    public void setPriority(int priority) {
133        iPriority = priority; 
134    }
135    
136    /**
137     * Returns true if the student is applicable for the reservation
138     * @param student a student 
139     * @return true if student can use the reservation to get into the course / configuration / section
140     */
141    public abstract boolean isApplicable(Student student);
142
143    /**
144     * Instructional offering on which the reservation is set.
145     * @return instructional offering
146     */
147    public Offering getOffering() { return iOffering; }
148    
149    /**
150     * One or more configurations on which the reservation is set (optional).
151     * @return instructional offering configurations
152     */
153    public Set<Config> getConfigs() { return iConfigs; }
154    
155    /**
156     * Add a configuration (of the offering {@link Reservation#getOffering()}) to this reservation
157     * @param config instructional offering configuration
158     */
159    public void addConfig(Config config) {
160        iConfigs.add(config);
161        clearLimitCapCache();
162    }
163    
164    /**
165     * One or more sections on which the reservation is set (optional).
166     * @return class restrictions
167     */
168    public Map<Subpart, Set<Section>> getSections() { return iSections; }
169    
170    /**
171     * One or more sections on which the reservation is set (optional).
172     * @param subpart scheduling subpart
173     * @return class restrictions for the given scheduling subpart
174     */
175    public Set<Section> getSections(Subpart subpart) {
176        return iSections.get(subpart);
177    }
178    
179    /**
180     * Add a section (of the offering {@link Reservation#getOffering()}) to this reservation.
181     * This will also add all parent sections and the appropriate configuration to the offering.
182     * @param section a class restriction
183     */
184    public void addSection(Section section) {
185        addConfig(section.getSubpart().getConfig());
186        while (section != null) {
187            Set<Section> sections = iSections.get(section.getSubpart());
188            if (sections == null) {
189                sections = new HashSet<Section>();
190                iSections.put(section.getSubpart(), sections);
191            }
192            sections.add(section);
193            section = section.getParent();
194        }
195        clearLimitCapCache();
196    }
197    
198    /**
199     * Return true if the given enrollment meets the reservation.
200     * @param enrollment given enrollment
201     * @return true if the given enrollment meets the reservation
202     */
203    public boolean isIncluded(Enrollment enrollment) {
204        // Free time request are never included
205        if (enrollment.getConfig() == null) return false;
206        
207        // Check the offering
208        if (!iOffering.equals(enrollment.getConfig().getOffering())) return false;
209        
210        // If there are configurations, check the configuration
211        if (!iConfigs.isEmpty() && !iConfigs.contains(enrollment.getConfig())) return false;
212        
213        // Check all the sections of the enrollment
214        for (Section section: enrollment.getSections()) {
215            Set<Section> sections = iSections.get(section.getSubpart());
216            if (sections != null && !sections.contains(section))
217                return false;
218        }
219        
220        return true;
221    }
222    
223    /**
224     * True if the enrollment can be done using this reservation
225     * @param assignment current assignment
226     * @param enrollment given enrollment
227     * @return true if the given enrollment can be assigned
228     */
229    public boolean canEnroll(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
230        // Check if student can use this reservation
231        if (!isApplicable(enrollment.getStudent())) return false;
232        
233        // Check if the enrollment meets the reservation
234        if (!isIncluded(enrollment)) return false;
235
236        // Check the limit
237        return getLimit() < 0 || getContext(assignment).getUsedSpace() + enrollment.getRequest().getWeight() <= getLimit();
238    }
239    
240    /**
241     * True if can go over the course / config / section limit. Only to be used in the online sectioning. 
242     * @return can assign over class / configuration / course limit
243      */
244    public boolean canAssignOverLimit() {
245        return iCanAssignOverLimit;
246    }
247    
248    /**
249     * True if the batch solver can assign the reservation over the course / config / section limit.
250     * @return {@link Reservation#canAssignOverLimit()} and {@link StudentSectioningModel#getReservationCanAssignOverTheLimit()}
251     */
252    public boolean canBatchAssignOverLimit() {
253        return canAssignOverLimit() && (iOffering.getModel() == null || ((StudentSectioningModel)iOffering.getModel()).getReservationCanAssignOverTheLimit());
254    }
255    
256    /**
257     * Set to true if a student meeting this reservation can go over the course / config / section limit.
258     * @param canAssignOverLimit can assign over class / configuration / course limit
259     */
260    public void setCanAssignOverLimit(boolean canAssignOverLimit) {
261        iCanAssignOverLimit = canAssignOverLimit;
262    }
263    
264    /**
265     * If true, student must use the reservation (if applicable). Expired reservations do not need to be used. 
266     * @return must this reservation be used
267     */
268    public boolean mustBeUsed() {
269        return iMustBeUsed && !isExpired();
270    }
271    
272    /**
273     * If true, student must use the reservation (if applicable). Expiration date is ignored. 
274     * @return must this reservation be used
275     */
276    public boolean mustBeUsedIgnoreExpiration() {
277        return iMustBeUsed;
278    }
279    
280    /**
281     * Set to true if the student must use the reservation (if applicable)
282     * @param mustBeUsed must this reservation be used
283     */
284    public void setMustBeUsed(boolean mustBeUsed) {
285        iMustBeUsed = mustBeUsed;
286    }
287    
288    /**
289     * Reservation restrictivity (estimated percentage of enrollments that include this reservation, 1.0 reservation on the whole offering)
290     * @return computed restrictivity
291     */
292    public double getRestrictivity() {
293        if (iCachedRestrictivity == null) {
294            if (getConfigs().isEmpty()) return 1.0;
295            int nrChoices = 0, nrMatchingChoices = 0;
296            for (Config config: getOffering().getConfigs()) {
297                int x[] = nrChoices(config, 0, new HashSet<Section>(), getConfigs().contains(config));
298                nrChoices += x[0];
299                nrMatchingChoices += x[1];
300            }
301            iCachedRestrictivity = ((double)nrMatchingChoices) / nrChoices;
302        }
303        return iCachedRestrictivity;
304    }
305    private Double iCachedRestrictivity = null;
306    
307    
308    /** Number of choices and number of chaing choices in the given sub enrollment */
309    private int[] nrChoices(Config config, int idx, HashSet<Section> sections, boolean matching) {
310        if (config.getSubparts().size() == idx) {
311            return new int[]{1, matching ? 1 : 0};
312        } else {
313            Subpart subpart = config.getSubparts().get(idx);
314            Set<Section> matchingSections = getSections(subpart);
315            int choicesThisSubpart = 0;
316            int matchingChoicesThisSubpart = 0;
317            for (Section section : subpart.getSections()) {
318                if (section.getParent() != null && !sections.contains(section.getParent()))
319                    continue;
320                if (section.isOverlapping(sections))
321                    continue;
322                sections.add(section);
323                boolean m = matching && (matchingSections == null || matchingSections.contains(section));
324                int[] x = nrChoices(config, 1 + idx, sections, m);
325                choicesThisSubpart += x[0];
326                matchingChoicesThisSubpart += x[1];
327                sections.remove(section);
328            }
329            return new int[] {choicesThisSubpart, matchingChoicesThisSubpart};
330        }
331    }
332    
333    /**
334     * Priority first, than restrictivity (more restrictive first), than availability (more available first), than id 
335     */
336    @Override
337    public int compareTo(Assignment<Request, Enrollment> assignment, Reservation r) {
338        if (getPriority() != r.getPriority()) {
339            return (getPriority() < r.getPriority() ? -1 : 1);
340        }
341        int cmp = Double.compare(getRestrictivity(), r.getRestrictivity());
342        if (cmp != 0) return cmp;
343        cmp = - Double.compare(getContext(assignment).getReservedAvailableSpace(assignment, null), r.getContext(assignment).getReservedAvailableSpace(assignment, null));
344        if (cmp != 0) return cmp;
345        return new Long(getId()).compareTo(r.getId());
346    }
347    
348    /**
349     * Priority first, than restrictivity (more restrictive first), than id 
350     */
351    @Override
352    public int compareTo(Reservation r) {
353        if (getPriority() != r.getPriority()) {
354            return (getPriority() < r.getPriority() ? -1 : 1);
355        }
356        int cmp = Double.compare(getRestrictivity(), r.getRestrictivity());
357        if (cmp != 0) return cmp;
358        return new Long(getId()).compareTo(r.getId());
359    }
360    
361    /**
362     * Return minimum of two limits where -1 counts as unlimited (any limit is smaller)
363     */
364    private static double min(double l1, double l2) {
365        return (l1 < 0 ? l2 : l2 < 0 ? l1 : Math.min(l1, l2));
366    }
367    
368    /**
369     * Add two limits where -1 counts as unlimited (unlimited plus anything is unlimited)
370     */
371    private static double add(double l1, double l2) {
372        return (l1 < 0 ? -1 : l2 < 0 ? -1 : l1 + l2);
373    }
374    
375
376    /** Limit cap cache */
377    private Double iLimitCap = null;
378
379    /**
380     * Compute limit cap (maximum number of students that can get into the offering using this reservation)
381     * @return reservation limit cap
382     */
383    public double getLimitCap() {
384        if (iLimitCap == null) iLimitCap = getLimitCapNoCache();
385        return iLimitCap;
386    }
387
388    /**
389     * Compute limit cap (maximum number of students that can get into the offering using this reservation)
390     */
391    private double getLimitCapNoCache() {
392        if (getConfigs().isEmpty()) return -1; // no config -> can be unlimited
393        
394        if (canAssignOverLimit()) return -1; // can assign over limit -> no cap
395        
396        double cap = 0;
397        // for each config
398        for (Config config: iConfigs) {
399            // config cap
400            double configCap = config.getLimit();
401        
402            for (Map.Entry<Subpart, Set<Section>> entry: getSections().entrySet()) {
403                if (!config.equals(entry.getKey().getConfig())) continue;
404                Set<Section> sections = entry.getValue();
405                
406                // subpart cap
407                double subpartCap = 0;
408                for (Section section: sections)
409                    subpartCap = add(subpartCap, section.getLimit());
410        
411                // minimize
412                configCap = min(configCap, subpartCap);
413            }
414            
415            // add config cap
416            cap = add(cap, configCap);
417        }
418        
419        return cap;
420    }
421    
422    /**
423     * Clear limit cap cache
424     */
425    private void clearLimitCapCache() {
426        iLimitCap = null;
427    }
428    
429    /**
430     * Reservation limit capped the limit cap (see {@link Reservation#getLimitCap()})
431     * @return reservation limit, -1 if unlimited
432     */
433    public double getLimit() {
434        return min(getLimitCap(), getReservationLimit());
435    }
436    
437    /**
438     * True if holding this reservation allows a student to have attend overlapping class. 
439     * @return does this reservation allow for overlaps
440     */
441    public boolean isAllowOverlap() {
442        return iAllowOverlap;
443    }
444    
445    /**
446     * Set to true if holding this reservation allows a student to have attend overlapping class.
447     * @param allowOverlap does this reservation allow for overlaps
448     */
449    public void setAllowOverlap(boolean allowOverlap) {
450        iAllowOverlap = allowOverlap;
451    }
452    
453    /**
454     * True if holding this reservation allows a student to attend a disabled class. 
455     * @return does this reservation allow for disabled sections
456     */
457    public boolean isAllowDisabled() {
458        return iAllowDisabled;
459    }
460    
461    /**
462     * Set to true if holding this reservation allows a student to attend a disabled class
463     * @param allowDisabled does this reservation allow for disabled sections
464     */
465    public void setAllowDisabled(boolean allowDisabled) {
466        iAllowDisabled = allowDisabled;
467    }
468    
469    /**
470     * Set reservation expiration. If a reservation is expired, it works as ordinary reservation
471     * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students
472     * of getting into the offering / config / section.  
473     * @param expired is this reservation expired
474     */
475    public void setExpired(boolean expired) {
476        iExpired = expired;
477    }
478    
479    /**
480     * True if the reservation is expired. If a reservation is expired, it works as ordinary reservation
481     * (especially the flags mutBeUsed and isAllowOverlap), except it does not block other students
482     * of getting into the offering / config / section.
483     * @return is this reservation expired
484     */
485    public boolean isExpired() {
486        return iExpired;
487    }
488    
489    @Override
490    public Model<Request, Enrollment> getModel() {
491        return getOffering().getModel();
492    }
493    
494    /**
495     * Available reserved space
496     * @param assignment current assignment
497     * @param excludeRequest excluding given request (if not null)
498     * @return available reserved space
499     **/
500    public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) {
501        return getContext(assignment).getReservedAvailableSpace(assignment, excludeRequest);
502    }
503    
504    /** Enrollments assigned using this reservation 
505     * @param assignment current assignment
506     * @return assigned enrollments of this reservation
507     **/
508    public Set<Enrollment> getEnrollments(Assignment<Request, Enrollment> assignment) {
509        return getContext(assignment).getEnrollments();
510    }
511
512    @Override
513    public ReservationContext createAssignmentContext(Assignment<Request, Enrollment> assignment) {
514        return new ReservationContext(assignment);
515    }
516    
517
518    @Override
519    public ReservationContext inheritAssignmentContext(Assignment<Request, Enrollment> assignment, ReservationContext parentContext) {
520        return new ReservationContext(parentContext);
521    }
522
523    
524    public class ReservationContext implements AssignmentConstraintContext<Request, Enrollment> {
525        /** Enrollments included in this reservation */
526        private Set<Enrollment> iEnrollments = new HashSet<Enrollment>();
527        
528        /** Used part of the limit */
529        private double iUsed = 0;
530        private boolean iReadOnly = false;
531
532        public ReservationContext(Assignment<Request, Enrollment> assignment) {
533            for (Course course: getOffering().getCourses())
534                for (CourseRequest request: course.getRequests()) {
535                    Enrollment enrollment = assignment.getValue(request);
536                    if (enrollment != null && Reservation.this.equals(enrollment.getReservation()))
537                        assigned(assignment, enrollment);
538                }
539        }
540        
541        public ReservationContext(ReservationContext parent) {
542            iUsed = parent.iUsed;
543            iEnrollments = parent.iEnrollments;
544            iReadOnly = true;
545        }
546
547        /** Notify reservation about an unassignment */
548        @Override
549        public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
550            if (iReadOnly) {
551                iEnrollments = new HashSet<Enrollment>(iEnrollments);
552                iReadOnly = false;
553            }
554            if (iEnrollments.add(enrollment))
555                iUsed += enrollment.getRequest().getWeight();
556        }
557
558        /** Notify reservation about an assignment */
559        @Override
560        public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
561            if (iReadOnly) {
562                iEnrollments = new HashSet<Enrollment>(iEnrollments);
563                iReadOnly = false;
564            }
565            if (iEnrollments.remove(enrollment))
566                iUsed -= enrollment.getRequest().getWeight();
567        }
568        
569        /** Enrollments assigned using this reservation 
570         * @return assigned enrollments of this reservation
571         **/
572        public Set<Enrollment> getEnrollments() {
573            return iEnrollments;
574        }
575        
576        /** Used space 
577         * @return spaced used of this reservation
578         **/
579        public double getUsedSpace() {
580            return iUsed;
581        }
582        
583        /**
584         * Available reserved space
585         * @param assignment current assignment
586         * @param excludeRequest excluding given request (if not null)
587         * @return available reserved space
588         **/
589        public double getReservedAvailableSpace(Assignment<Request, Enrollment> assignment, Request excludeRequest) {
590            // Unlimited
591            if (getLimit() < 0) return Double.MAX_VALUE;
592            
593            double reserved = getLimit() - getContext(assignment).getUsedSpace();
594            if (excludeRequest != null && assignment.getValue(excludeRequest) != null && iEnrollments.contains(assignment.getValue(excludeRequest)))
595                reserved += excludeRequest.getWeight();
596            
597            return reserved;
598        }
599    }
600}