001    package net.sf.cpsolver.studentsct.constraint;
002    
003    import java.util.ArrayList;
004    import java.util.List;
005    import java.util.Set;
006    
007    import net.sf.cpsolver.ifs.model.GlobalConstraint;
008    import net.sf.cpsolver.ifs.util.DataProperties;
009    import net.sf.cpsolver.ifs.util.ToolBox;
010    import net.sf.cpsolver.studentsct.StudentSectioningModel;
011    import net.sf.cpsolver.studentsct.model.Course;
012    import net.sf.cpsolver.studentsct.model.Enrollment;
013    import net.sf.cpsolver.studentsct.model.Request;
014    
015    /**
016     * Course limit constraint. This global constraint ensures that a limit of each
017     * course is not exceeded. This means that the total sum of weights of course
018     * requests (see {@link Request#getWeight()}) enrolled into a course is below
019     * the course's limit (see {@link Course#getLimit()}).
020     * 
021     * <br>
022     * <br>
023     * Sections with negative limit are considered unlimited, and therefore
024     * completely ignored by this constraint.
025     * 
026     * <br>
027     * <br>
028     * Parameters:
029     * <table border='1'>
030     * <tr>
031     * <th>Parameter</th>
032     * <th>Type</th>
033     * <th>Comment</th>
034     * </tr>
035     * <tr>
036     * <td>CourseLimit.PreferDummyStudents</td>
037     * <td>{@link Boolean}</td>
038     * <td>If true, requests of dummy (last-like) students are preferred to be
039     * selected as conflicting.</td>
040     * </tr>
041     * </table>
042     * <br>
043     * <br>
044     * 
045     * @version StudentSct 1.2 (Student Sectioning)<br>
046     *          Copyright (C) 2007 - 2010 Tomas Muller<br>
047     *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
048     *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
049     * <br>
050     *          This library is free software; you can redistribute it and/or modify
051     *          it under the terms of the GNU Lesser General Public License as
052     *          published by the Free Software Foundation; either version 3 of the
053     *          License, or (at your option) any later version. <br>
054     * <br>
055     *          This library is distributed in the hope that it will be useful, but
056     *          WITHOUT ANY WARRANTY; without even the implied warranty of
057     *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
058     *          Lesser General Public License for more details. <br>
059     * <br>
060     *          You should have received a copy of the GNU Lesser General Public
061     *          License along with this library; if not see
062     *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
063     */
064    public class CourseLimit extends GlobalConstraint<Request, Enrollment> {
065        private boolean iPreferDummyStudents = false;
066    
067        /**
068         * Constructor
069         * 
070         * @param cfg
071         *            solver configuration
072         */
073        public CourseLimit(DataProperties cfg) {
074            super();
075            iPreferDummyStudents = cfg.getPropertyBoolean("CourseLimit.PreferDummyStudents", false);
076        }
077    
078    
079        /**
080         * Enrollment weight of a course if the given request is assigned.
081         * 
082         * @param course
083         *            a course that is of concern
084         * @param request
085         *            a request of a student to be assigned containing the given
086         *            section
087         * @return section's new weight
088         */
089        public static double getEnrollmentWeight(Course course, Request request) {
090            return course.getEnrollmentWeight(request) + request.getWeight();
091        }
092    
093        /**
094         * A given enrollment is conflicting, if the course's enrollment
095         * (computed by {@link CourseLimit#getEnrollmentWeight(Course, Request)})
096         * exceeds the limit. <br>
097         * If the limit is breached, one or more existing enrollments are
098         * (randomly) selected as conflicting until the overall weight is under the
099         * limit.
100         * 
101         * @param enrollment
102         *            {@link Enrollment} that is being considered
103         * @param conflicts
104         *            all computed conflicting requests are added into this set
105         */
106        @Override
107        public void computeConflicts(Enrollment enrollment, Set<Enrollment> conflicts) {
108            // check reservation can assign over the limit
109            if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
110                enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
111                return;
112    
113            // enrollment's course
114            Course course = enrollment.getCourse();
115    
116            // exclude free time requests
117            if (course == null)
118                return;
119    
120            // unlimited course
121            if (course.getLimit() < 0)
122                return;
123            
124            // new enrollment weight
125            double enrlWeight = getEnrollmentWeight(course, enrollment.getRequest());
126    
127            // below limit -> ok
128            if (enrlWeight <= course.getLimit())
129                return;
130    
131            // above limit -> compute adepts (current assignments that are not
132            // yet conflicting)
133            // exclude all conflicts as well
134            List<Enrollment> adepts = new ArrayList<Enrollment>(course.getEnrollments().size());
135            for (Enrollment e : course.getEnrollments()) {
136                if (e.getRequest().equals(enrollment.getRequest()))
137                    continue;
138                if (conflicts.contains(e))
139                    enrlWeight -= e.getRequest().getWeight();
140                else
141                    adepts.add(e);
142            }
143    
144            // while above limit -> pick an adept and make it conflicting
145            while (enrlWeight > course.getLimit()) {
146                if (adepts.isEmpty()) {
147                    // no adepts -> enrollment cannot be assigned
148                    conflicts.add(enrollment);
149                    break;
150                }
151                
152                // pick adept (prefer dummy students), decrease unreserved space,
153                // make conflict
154                List<Enrollment> best = new ArrayList<Enrollment>();
155                boolean bestDummy = false;
156                double bestValue = 0;
157                for (Enrollment adept: adepts) {
158                    boolean dummy = adept.getStudent().isDummy();
159                    double value = adept.toDouble(false);
160                    
161                    if (iPreferDummyStudents && dummy != bestDummy) {
162                        if (dummy) {
163                            best.clear();
164                            best.add(adept);
165                            bestDummy = dummy;
166                            bestValue = value;
167                        }
168                        continue;
169                    }
170                    
171                    if (best.isEmpty() || value > bestValue) {
172                        if (best.isEmpty()) best.clear();
173                        best.add(adept);
174                        bestDummy = dummy;
175                        bestValue = value;
176                    } else if (bestValue == value) {
177                        best.add(adept);
178                    }
179                }
180                
181                Enrollment conflict = ToolBox.random(best);
182                adepts.remove(conflict);
183                enrlWeight -= conflict.getRequest().getWeight();
184                conflicts.add(conflict);
185            }
186        }
187    
188        /**
189         * A given enrollment is conflicting, if the course's enrollment (computed by
190         * {@link CourseLimit#getEnrollmentWeight(Course, Request)}) exceeds the
191         * limit.
192         * 
193         * @param enrollment
194         *            {@link Enrollment} that is being considered
195         * @return true, if the enrollment cannot be assigned without exceeding the limit
196         */
197        @Override
198        public boolean inConflict(Enrollment enrollment) {
199            // check reservation can assign over the limit
200            if (((StudentSectioningModel)getModel()).getReservationCanAssignOverTheLimit() &&
201                enrollment.getReservation() != null && enrollment.getReservation().canAssignOverLimit())
202                return false;
203    
204            // enrollment's course
205            Course course = enrollment.getCourse();
206    
207            // exclude free time requests
208            if (course == null)
209                return false;
210    
211            // unlimited course
212            if (course.getLimit() < 0)
213                return false;
214    
215    
216            // new enrollment weight
217            double enrlWeight = getEnrollmentWeight(course, enrollment.getRequest());
218            
219            // above limit -> conflict
220            return (enrlWeight > course.getLimit());
221        }
222        
223        @Override
224        public String toString() {
225            return "CourseLimit";
226        }
227    
228    }