001    package net.sf.cpsolver.studentsct.model;
002    
003    import java.text.DecimalFormat;
004    import java.util.ArrayList;
005    import java.util.HashMap;
006    import java.util.HashSet;
007    import java.util.List;
008    import java.util.Map;
009    import java.util.Set;
010    
011    import net.sf.cpsolver.coursett.model.Placement;
012    import net.sf.cpsolver.coursett.model.RoomLocation;
013    import net.sf.cpsolver.coursett.model.TimeLocation;
014    import net.sf.cpsolver.studentsct.reservation.Reservation;
015    
016    /**
017     * Representation of a class. Each section contains id, name, scheduling
018     * subpart, time/room placement, and a limit. Optionally, parent-child relation
019     * between sections can be defined. <br>
020     * <br>
021     * Each student requesting a course needs to be enrolled in a class of each
022     * subpart of a selected configuration. In the case of parent-child relation
023     * between classes, if a student is enrolled in a section that has a parent
024     * section defined, he/she has to be enrolled in the parent section as well. If
025     * there is a parent-child relation between two sections, the same relation is
026     * defined on their subparts as well, i.e., if section A is a parent section B,
027     * subpart of section A isa parent of subpart of section B. <br>
028     * <br>
029     * 
030     * @version StudentSct 1.2 (Student Sectioning)<br>
031     *          Copyright (C) 2007 - 2010 Tomas Muller<br>
032     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
033     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
034     * <br>
035     *          This library is free software; you can redistribute it and/or modify
036     *          it under the terms of the GNU Lesser General Public License as
037     *          published by the Free Software Foundation; either version 3 of the
038     *          License, or (at your option) any later version. <br>
039     * <br>
040     *          This library is distributed in the hope that it will be useful, but
041     *          WITHOUT ANY WARRANTY; without even the implied warranty of
042     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
043     *          Lesser General Public License for more details. <br>
044     * <br>
045     *          You should have received a copy of the GNU Lesser General Public
046     *          License along with this library; if not see
047     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
048     */
049    public class Section implements Assignment, Comparable<Section> {
050        private static DecimalFormat sDF = new DecimalFormat("0.000");
051        private long iId = -1;
052        private String iName = null;
053        private Map<Long, String> iNameByCourse = null;
054        private Subpart iSubpart = null;
055        private Section iParent = null;
056        private Placement iPlacement = null;
057        private int iLimit = 0;
058        private Set<Enrollment> iEnrollments = new HashSet<Enrollment>();
059        private Choice iChoice = null;
060        private double iPenalty = 0.0;
061        private double iEnrollmentWeight = 0.0;
062        private double iMaxEnrollmentWeight = 0.0;
063        private double iMinEnrollmentWeight = 0.0;
064        private double iSpaceExpected = 0.0;
065        private double iSpaceHeld = 0.0;
066        private String iNote = null;
067        private Set<Long> iIgnoreConflictsWith = null;
068    
069        /**
070         * Constructor
071         * 
072         * @param id
073         *            section unique id
074         * @param limit
075         *            section limit, i.e., the maximal number of students that can
076         *            be enrolled in this section at the same time
077         * @param name
078         *            section name
079         * @param subpart
080         *            subpart of this section
081         * @param placement
082         *            time/room placement
083         * @param instructorIds
084         *            instructor(s) id -- needed for {@link Section#getChoice()}
085         * @param instructorNames
086         *            instructor(s) name -- needed for {@link Section#getChoice()}
087         * @param parent
088         *            parent section -- if there is a parent section defined, a
089         *            student that is enrolled in this section has to be enrolled in
090         *            the parent section as well. Also, the same relation needs to
091         *            be defined between subpart of this section and the subpart of
092         *            the parent section
093         */
094        public Section(long id, int limit, String name, Subpart subpart, Placement placement, String instructorIds,
095                String instructorNames, Section parent) {
096            iId = id;
097            iLimit = limit;
098            iName = name;
099            iSubpart = subpart;
100            iSubpart.getSections().add(this);
101            iPlacement = placement;
102            iParent = parent;
103            iChoice = new Choice(getSubpart().getConfig().getOffering(), getSubpart().getInstructionalType(), getTime(),
104                    instructorIds, instructorNames);
105        }
106    
107        /** Section id */
108        @Override
109        public long getId() {
110            return iId;
111        }
112    
113        /**
114         * Section limit. This is defines the maximal number of students that can be
115         * enrolled into this section at the same time. It is -1 in the case of an
116         * unlimited section
117         */
118        public int getLimit() {
119            return iLimit;
120        }
121    
122        /** Set section limit */
123        public void setLimit(int limit) {
124            iLimit = limit;
125        }
126    
127        /** Section name */
128        public String getName() {
129            return iName;
130        }
131        
132        /** Set section name */
133        public void setName(String name) {
134            iName = name;
135        }
136    
137        /** Scheduling subpart to which this section belongs */
138        public Subpart getSubpart() {
139            return iSubpart;
140        }
141    
142        /**
143         * Parent section of this section (can be null). If there is a parent
144         * section defined, a student that is enrolled in this section has to be
145         * enrolled in the parent section as well. Also, the same relation needs to
146         * be defined between subpart of this section and the subpart of the parent
147         * section.
148         */
149        public Section getParent() {
150            return iParent;
151        }
152    
153        /**
154         * Time/room placement of the section. This can be null, for arranged
155         * sections.
156         */
157        public Placement getPlacement() {
158            return iPlacement;
159        }
160        
161        /**
162         * Set time/room placement of the section. This can be null, for arranged
163         * sections.
164         */
165        public void setPlacement(Placement placement) {
166            iPlacement = placement;
167        }
168    
169        /** Time placement of the section. */
170        @Override
171        public TimeLocation getTime() {
172            return (iPlacement == null ? null : iPlacement.getTimeLocation());
173        }
174    
175        /** Number of rooms in which the section meet. */
176        @Override
177        public int getNrRooms() {
178            return (iPlacement == null ? 0 : iPlacement.getNrRooms());
179        }
180    
181        /**
182         * Room placement -- list of
183         * {@link net.sf.cpsolver.coursett.model.RoomLocation}
184         */
185        @Override
186        public List<RoomLocation> getRooms() {
187            if (iPlacement == null)
188                return null;
189            if (iPlacement.getRoomLocations() == null && iPlacement.getRoomLocation() != null) {
190                List<RoomLocation> ret = new ArrayList<RoomLocation>(1);
191                ret.add(iPlacement.getRoomLocation());
192                return ret;
193            }
194            return iPlacement.getRoomLocations();
195        }
196    
197        /**
198         * True, if this section overlaps with the given assignment in time and
199         * space
200         */
201        @Override
202        public boolean isOverlapping(Assignment assignment) {
203            if (isAllowOverlap() || assignment.isAllowOverlap()) return false;
204            if (getTime() == null || assignment.getTime() == null) return false;
205            if (assignment instanceof Section && isToIgnoreStudentConflictsWith(assignment.getId())) return false;
206            return getTime().hasIntersection(assignment.getTime());
207        }
208    
209        /**
210         * True, if this section overlaps with one of the given set of assignments
211         * in time and space
212         */
213        @Override
214        public boolean isOverlapping(Set<? extends Assignment> assignments) {
215            if (isAllowOverlap()) return false;
216            if (getTime() == null || assignments == null)
217                return false;
218            for (Assignment assignment : assignments) {
219                if (assignment.isAllowOverlap())
220                    continue;
221                if (assignment.getTime() == null)
222                    continue;
223                if (assignment instanceof Section && isToIgnoreStudentConflictsWith(assignment.getId()))
224                    continue;
225                if (getTime().hasIntersection(assignment.getTime()))
226                    return true;
227            }
228            return false;
229        }
230    
231        /** Called when an enrollment with this section is assigned to a request */
232        @Override
233        public void assigned(Enrollment enrollment) {
234            if (iEnrollments.isEmpty()) {
235                iMinEnrollmentWeight = iMaxEnrollmentWeight = enrollment.getRequest().getWeight();
236            } else {
237                iMaxEnrollmentWeight = Math.max(iMaxEnrollmentWeight, enrollment.getRequest().getWeight());
238                iMinEnrollmentWeight = Math.min(iMinEnrollmentWeight, enrollment.getRequest().getWeight());
239            }
240            iEnrollments.add(enrollment);
241            iEnrollmentWeight += enrollment.getRequest().getWeight();
242        }
243    
244        /** Called when an enrollment with this section is unassigned from a request */
245        @Override
246        public void unassigned(Enrollment enrollment) {
247            iEnrollments.remove(enrollment);
248            iEnrollmentWeight -= enrollment.getRequest().getWeight();
249            if (iEnrollments.isEmpty()) {
250                iMinEnrollmentWeight = iMaxEnrollmentWeight = 0;
251            } else if (iMinEnrollmentWeight != iMaxEnrollmentWeight) {
252                if (iMinEnrollmentWeight == enrollment.getRequest().getWeight()) {
253                    double newMinEnrollmentWeight = Double.MAX_VALUE;
254                    for (Enrollment e : iEnrollments) {
255                        if (e.getRequest().getWeight() == iMinEnrollmentWeight) {
256                            newMinEnrollmentWeight = iMinEnrollmentWeight;
257                            break;
258                        } else {
259                            newMinEnrollmentWeight = Math.min(newMinEnrollmentWeight, e.getRequest().getWeight());
260                        }
261                    }
262                    iMinEnrollmentWeight = newMinEnrollmentWeight;
263                }
264                if (iMaxEnrollmentWeight == enrollment.getRequest().getWeight()) {
265                    double newMaxEnrollmentWeight = Double.MIN_VALUE;
266                    for (Enrollment e : iEnrollments) {
267                        if (e.getRequest().getWeight() == iMaxEnrollmentWeight) {
268                            newMaxEnrollmentWeight = iMaxEnrollmentWeight;
269                            break;
270                        } else {
271                            newMaxEnrollmentWeight = Math.max(newMaxEnrollmentWeight, e.getRequest().getWeight());
272                        }
273                    }
274                    iMaxEnrollmentWeight = newMaxEnrollmentWeight;
275                }
276            }
277        }
278    
279        /** Set of assigned enrollments */
280        @Override
281        public Set<Enrollment> getEnrollments() {
282            return iEnrollments;
283        }
284    
285        /**
286         * Enrollment weight -- weight of all requests which have an enrollment that
287         * contains this section, excluding the given one. See
288         * {@link Request#getWeight()}.
289         */
290        public double getEnrollmentWeight(Request excludeRequest) {
291            double weight = iEnrollmentWeight;
292            if (excludeRequest != null && excludeRequest.getAssignment() != null
293                    && iEnrollments.contains(excludeRequest.getAssignment()))
294                weight -= excludeRequest.getWeight();
295            return weight;
296        }
297    
298        /**
299         * Maximal weight of a single enrollment in the section
300         */
301        public double getMaxEnrollmentWeight() {
302            return iMaxEnrollmentWeight;
303        }
304    
305        /**
306         * Minimal weight of a single enrollment in the section
307         */
308        public double getMinEnrollmentWeight() {
309            return iMinEnrollmentWeight;
310        }
311    
312        /** Long name: subpart name + time long name + room names + instructor names */
313        public String getLongName() {
314            return getSubpart().getName() + " " + getName() + " " + (getTime() == null ? "" : " " + getTime().getLongName())
315                    + (getNrRooms() == 0 ? "" : " " + getPlacement().getRoomName(","))
316                    + (getChoice().getInstructorNames() == null ? "" : " " + getChoice().getInstructorNames());
317        }
318    
319        @Override
320        public String toString() {
321            return getSubpart().getConfig().getOffering().getName() + " " + getSubpart().getName() + " " + getName()
322                    + (getTime() == null ? "" : " " + getTime().getLongName())
323                    + (getNrRooms() == 0 ? "" : " " + getPlacement().getRoomName(","))
324                    + (getChoice().getInstructorNames() == null ? "" : " " + getChoice().getInstructorNames()) + " (L:"
325                    + (getLimit() < 0 ? "unlimited" : "" + getLimit())
326                    + (getPenalty() == 0.0 ? "" : ",P:" + sDF.format(getPenalty())) + ")";
327        }
328    
329        /** A (student) choice representing this section. */
330        public Choice getChoice() {
331            return iChoice;
332        }
333    
334        /**
335         * Return penalty which is added to an enrollment that contains this
336         * section.
337         */
338        public double getPenalty() {
339            return iPenalty;
340        }
341    
342        /** Set penalty which is added to an enrollment that contains this section. */
343        public void setPenalty(double penalty) {
344            iPenalty = penalty;
345        }
346    
347        /**
348         * Compare two sections, prefer sections with lower penalty and more open
349         * space
350         */
351        @Override
352        public int compareTo(Section s) {
353            int cmp = Double.compare(getPenalty(), s.getPenalty());
354            if (cmp != 0)
355                return cmp;
356            cmp = Double.compare(getLimit() - getEnrollmentWeight(null), s.getLimit() - s.getEnrollmentWeight(null));
357            if (cmp != 0)
358                return cmp;
359            return Double.compare(getId(), s.getId());
360        }
361    
362        /**
363         * Return the amount of space of this section that is held for incoming
364         * students. This attribute is computed during the batch sectioning (it is
365         * the overall weight of dummy students enrolled in this section) and it is
366         * being updated with each incomming student during the online sectioning.
367         */
368        public double getSpaceHeld() {
369            return iSpaceHeld;
370        }
371    
372        /**
373         * Set the amount of space of this section that is held for incoming
374         * students. See {@link Section#getSpaceHeld()} for more info.
375         */
376        public void setSpaceHeld(double spaceHeld) {
377            iSpaceHeld = spaceHeld;
378        }
379    
380        /**
381         * Return the amount of space of this section that is expected to be taken
382         * by incoming students. This attribute is computed during the batch
383         * sectioning (for each dummy student that can attend this section (without
384         * any conflict with other enrollments of that student), 1 / x where x is
385         * the number of such sections of this subpart is added to this value).
386         * Also, this value is being updated with each incomming student during the
387         * online sectioning.
388         */
389        public double getSpaceExpected() {
390            return iSpaceExpected;
391        }
392    
393        /**
394         * Set the amount of space of this section that is expected to be taken by
395         * incoming students. See {@link Section#getSpaceExpected()} for more info.
396         */
397        public void setSpaceExpected(double spaceExpected) {
398            iSpaceExpected = spaceExpected;
399        }
400    
401        /**
402         * Online sectioning penalty.
403         */
404        public double getOnlineSectioningPenalty() {
405            if (getLimit() <= 0)
406                return 0.0;
407    
408            double available = getLimit() - getEnrollmentWeight(null);
409    
410            double penalty = (getSpaceExpected() - available) / getLimit();
411    
412            return Math.max(-1.0, Math.min(1.0, penalty));
413        }
414    
415        /**
416         * Return true if overlaps are allowed, but the number of overlapping slots should be minimized.
417         * This can be changed on the subpart, using {@link Subpart#setAllowOverlap(boolean)}.
418         **/
419        @Override
420        public boolean isAllowOverlap() {
421            return iSubpart.isAllowOverlap();
422        }
423        
424        /** Sections first, then by {@link FreeTimeRequest#getId()} */
425        @Override
426        public int compareById(Assignment a) {
427            if (a instanceof Section) {
428                return new Long(getId()).compareTo(((Section)a).getId());
429            } else {
430                return -1;
431            }
432        }
433    
434        /**
435         * Available space in the section that is not reserved by any section reservation
436         * @param excludeRequest excluding given request (if not null)
437         **/
438        public double getUnreservedSpace(Request excludeRequest) {
439            // section is unlimited -> there is unreserved space unless there is an unlimited reservation too 
440            // (in which case there is no unreserved space)
441            if (getLimit() < 0) {
442                // exclude reservations that are not directly set on this section
443                for (Reservation r: getSectionReservations()) {
444                    // ignore expired reservations
445                    if (r.isExpired()) continue;
446                    // there is an unlimited reservation -> no unreserved space
447                    if (r.getLimit() < 0) return 0.0;
448                }
449                return Double.MAX_VALUE;
450            }
451            
452            double available = getLimit() - getEnrollmentWeight(excludeRequest);
453            // exclude reservations that are not directly set on this section
454            for (Reservation r: getSectionReservations()) {
455                // ignore expired reservations
456                if (r.isExpired()) continue;
457                // unlimited reservation -> all the space is reserved
458                if (r.getLimit() < 0.0) return 0.0;
459                // compute space that can be potentially taken by this reservation
460                double reserved = r.getReservedAvailableSpace(excludeRequest);
461                // deduct the space from available space
462                available -= Math.max(0.0, reserved);
463            }
464            
465            return available;
466        }
467        
468        /**
469         * Total space in the section that cannot be used by any section reservation
470         **/
471        public double getTotalUnreservedSpace() {
472            if (iTotalUnreservedSpace == null)
473                iTotalUnreservedSpace = getTotalUnreservedSpaceNoCache();
474            return iTotalUnreservedSpace;
475        }
476        private Double iTotalUnreservedSpace = null;
477        private double getTotalUnreservedSpaceNoCache() {
478            // section is unlimited -> there is unreserved space unless there is an unlimited reservation too 
479            // (in which case there is no unreserved space)
480            if (getLimit() < 0) {
481                // exclude reservations that are not directly set on this section
482                for (Reservation r: getSectionReservations()) {
483                    // ignore expired reservations
484                    if (r.isExpired()) continue;
485                    // there is an unlimited reservation -> no unreserved space
486                    if (r.getLimit() < 0) return 0.0;
487                }
488                return Double.MAX_VALUE;
489            }
490            
491            // we need to check all reservations linked with this section
492            double available = getLimit(), reserved = 0, exclusive = 0;
493            Set<Section> sections = new HashSet<Section>();
494            reservations: for (Reservation r: getSectionReservations()) {
495                // ignore expired reservations
496                if (r.isExpired()) continue;
497                // unlimited reservation -> no unreserved space
498                if (r.getLimit() < 0) return 0.0;
499                for (Section s: r.getSections(getSubpart())) {
500                    if (s.equals(this)) continue;
501                    if (s.getLimit() < 0) continue reservations;
502                    if (sections.add(s))
503                        available += s.getLimit();
504                }
505                reserved += r.getLimit();
506                if (r.getSections(getSubpart()).size() == 1)
507                    exclusive += r.getLimit();
508            }
509            
510            return Math.min(available - reserved, getLimit() - exclusive);
511        }
512        
513        
514        /**
515         * Get reservations for this section
516         */
517        public List<Reservation> getReservations() {
518            if (iReservations == null) {
519                iReservations = new ArrayList<Reservation>();
520                for (Reservation r: getSubpart().getConfig().getOffering().getReservations()) {
521                    if (r.getSections(getSubpart()) == null || r.getSections(getSubpart()).contains(this))
522                        iReservations.add(r);
523                }
524            }
525            return iReservations;
526        }
527        private List<Reservation> iReservations = null;
528        
529        /**
530         * Get reservations that require this section
531         */
532        public List<Reservation> getSectionReservations() {
533            if (iSectionReservations == null) {
534                iSectionReservations = new ArrayList<Reservation>();
535                for (Reservation r: getSubpart().getSectionReservations()) {
536                    if (r.getSections(getSubpart()).contains(this))
537                        iSectionReservations.add(r);
538                }
539            }
540            return iSectionReservations;
541        }
542        private List<Reservation> iSectionReservations = null;
543    
544        /**
545         * Clear reservation information that was cached on this section
546         */
547        public void clearReservationCache() {
548            iReservations = null;
549            iSectionReservations = null;
550            iTotalUnreservedSpace = null;
551        }
552        
553        /**
554         * Return course-dependent section name
555         */
556        public String getName(long courseId) {
557            if (iNameByCourse == null) return getName();
558            String name = iNameByCourse.get(courseId);
559            return (name == null ? getName() : name);
560        }
561        
562        /**
563         * Set course-dependent section name
564         */
565        public void setName(long courseId, String name) {
566            if (iNameByCourse == null) iNameByCourse = new HashMap<Long, String>();
567            iNameByCourse.put(courseId, name);
568        }
569    
570        /**
571         * Return course-dependent section names
572         */
573        public Map<Long, String> getNameByCourse() { return iNameByCourse; }
574        
575        @Override
576        public boolean equals(Object o) {
577            if (o == null || !(o instanceof Section)) return false;
578            return getId() == ((Section)o).getId();
579        }
580        
581        @Override
582        public int hashCode() {
583            return (int) (iId ^ (iId >>> 32));
584        }
585        
586        /**
587         * Section note
588         */
589        public String getNote() { return iNote; }
590        
591        /**
592         * Section note
593         */
594        public void setNote(String note) { iNote = note; }
595        
596        /**
597         * Add section id of a section that student conflicts are to be ignored with
598         */
599        public void addIgnoreConflictWith(long sectionId) {
600            if (iIgnoreConflictsWith == null) iIgnoreConflictsWith = new HashSet<Long>();
601            iIgnoreConflictsWith.add(sectionId);
602        }
603        
604        /**
605         * Returns true if student conflicts between this section and the given one are to be ignored
606         */
607        public boolean isToIgnoreStudentConflictsWith(long sectionId) {
608            return iIgnoreConflictsWith != null && iIgnoreConflictsWith.contains(sectionId);
609        }
610        
611        /**
612         * Returns a set of ids of sections that student conflicts are to be ignored with (between this section and the others)
613         */
614        public Set<Long> getIgnoreConflictWithSectionIds() {
615            return iIgnoreConflictsWith;
616        }
617    }