001    package net.sf.cpsolver.studentsct.reservation;
002    
003    import java.util.HashMap;
004    import java.util.HashSet;
005    import java.util.Map;
006    import java.util.Set;
007    
008    import net.sf.cpsolver.studentsct.model.Config;
009    import net.sf.cpsolver.studentsct.model.Enrollment;
010    import net.sf.cpsolver.studentsct.model.Offering;
011    import net.sf.cpsolver.studentsct.model.Request;
012    import net.sf.cpsolver.studentsct.model.Section;
013    import net.sf.cpsolver.studentsct.model.Student;
014    import 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 Tomas Muller<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     */
046    public 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    }