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