001package org.cpsolver.studentsct;
002
003import java.text.DecimalFormat;
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.Comparator;
007import java.util.HashSet;
008import java.util.List;
009import java.util.Map;
010import java.util.Set;
011import java.util.TreeSet;
012
013
014import org.apache.log4j.Logger;
015import org.cpsolver.ifs.assignment.Assignment;
016import org.cpsolver.ifs.assignment.context.AssignmentConstraintContext;
017import org.cpsolver.ifs.assignment.context.ModelWithContext;
018import org.cpsolver.ifs.model.Constraint;
019import org.cpsolver.ifs.model.ConstraintListener;
020import org.cpsolver.ifs.model.InfoProvider;
021import org.cpsolver.ifs.model.Model;
022import org.cpsolver.ifs.util.DataProperties;
023import org.cpsolver.studentsct.constraint.ConfigLimit;
024import org.cpsolver.studentsct.constraint.CourseLimit;
025import org.cpsolver.studentsct.constraint.LinkedSections;
026import org.cpsolver.studentsct.constraint.RequiredReservation;
027import org.cpsolver.studentsct.constraint.ReservationLimit;
028import org.cpsolver.studentsct.constraint.SectionLimit;
029import org.cpsolver.studentsct.constraint.StudentConflict;
030import org.cpsolver.studentsct.extension.DistanceConflict;
031import org.cpsolver.studentsct.extension.TimeOverlapsCounter;
032import org.cpsolver.studentsct.model.Config;
033import org.cpsolver.studentsct.model.Course;
034import org.cpsolver.studentsct.model.CourseRequest;
035import org.cpsolver.studentsct.model.Enrollment;
036import org.cpsolver.studentsct.model.Offering;
037import org.cpsolver.studentsct.model.Request;
038import org.cpsolver.studentsct.model.Section;
039import org.cpsolver.studentsct.model.Student;
040import org.cpsolver.studentsct.model.Subpart;
041import org.cpsolver.studentsct.reservation.Reservation;
042import org.cpsolver.studentsct.weights.PriorityStudentWeights;
043import org.cpsolver.studentsct.weights.StudentWeights;
044
045/**
046 * Student sectioning model.
047 * 
048 * <br>
049 * <br>
050 * 
051 * @version StudentSct 1.3 (Student Sectioning)<br>
052 *          Copyright (C) 2007 - 2014 Tomas Muller<br>
053 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
054 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
055 * <br>
056 *          This library is free software; you can redistribute it and/or modify
057 *          it under the terms of the GNU Lesser General Public License as
058 *          published by the Free Software Foundation; either version 3 of the
059 *          License, or (at your option) any later version. <br>
060 * <br>
061 *          This library is distributed in the hope that it will be useful, but
062 *          WITHOUT ANY WARRANTY; without even the implied warranty of
063 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
064 *          Lesser General Public License for more details. <br>
065 * <br>
066 *          You should have received a copy of the GNU Lesser General Public
067 *          License along with this library; if not see
068 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
069 */
070public class StudentSectioningModel extends ModelWithContext<Request, Enrollment, StudentSectioningModel.StudentSectioningModelContext> {
071    private static Logger sLog = Logger.getLogger(StudentSectioningModel.class);
072    protected static DecimalFormat sDecimalFormat = new DecimalFormat("0.000");
073    private List<Student> iStudents = new ArrayList<Student>();
074    private List<Offering> iOfferings = new ArrayList<Offering>();
075    private List<LinkedSections> iLinkedSections = new ArrayList<LinkedSections>();
076    private DataProperties iProperties;
077    private DistanceConflict iDistanceConflict = null;
078    private TimeOverlapsCounter iTimeOverlaps = null;
079    private int iNrDummyStudents = 0, iNrDummyRequests = 0;
080    private double iTotalDummyWeight = 0.0;
081    private double iTotalCRWeight = 0.0, iTotalDummyCRWeight = 0.0;
082    private double iTotalReservedSpace = 0.0;
083    private StudentWeights iStudentWeights = null;
084    private boolean iReservationCanAssignOverTheLimit;
085    protected double iProjectedStudentWeight = 0.0100;
086    private int iMaxDomainSize = -1; 
087
088
089    /**
090     * Constructor
091     * 
092     * @param properties
093     *            configuration
094     */
095    @SuppressWarnings("unchecked")
096    public StudentSectioningModel(DataProperties properties) {
097        super();
098        iReservationCanAssignOverTheLimit =  properties.getPropertyBoolean("Reservation.CanAssignOverTheLimit", false);
099        iStudentWeights = new PriorityStudentWeights(properties);
100        iMaxDomainSize = properties.getPropertyInt("Sectioning.MaxDomainSize", iMaxDomainSize);
101        if (properties.getPropertyBoolean("Sectioning.SectionLimit", true)) {
102            SectionLimit sectionLimit = new SectionLimit(properties);
103            addGlobalConstraint(sectionLimit);
104            if (properties.getPropertyBoolean("Sectioning.SectionLimit.Debug", false)) {
105                sectionLimit.addConstraintListener(new ConstraintListener<Request, Enrollment>() {
106                    @Override
107                    public void constraintBeforeAssigned(Assignment<Request, Enrollment> assignment, long iteration, Constraint<Request, Enrollment> constraint, Enrollment enrollment, Set<Enrollment> unassigned) {
108                        if (enrollment.getStudent().isDummy())
109                            for (Enrollment conflict : unassigned) {
110                                if (!conflict.getStudent().isDummy()) {
111                                    sLog.warn("Enrolment of a real student " + conflict.getStudent() + " is unassigned "
112                                            + "\n  -- " + conflict + "\ndue to an enrollment of a dummy student "
113                                            + enrollment.getStudent() + " " + "\n  -- " + enrollment);
114                                }
115                            }
116                    }
117
118                    @Override
119                    public void constraintAfterAssigned(Assignment<Request, Enrollment> assignment, long iteration, Constraint<Request, Enrollment> constraint, Enrollment assigned, Set<Enrollment> unassigned) {
120                    }
121                });
122            }
123        }
124        if (properties.getPropertyBoolean("Sectioning.ConfigLimit", true)) {
125            ConfigLimit configLimit = new ConfigLimit(properties);
126            addGlobalConstraint(configLimit);
127        }
128        if (properties.getPropertyBoolean("Sectioning.CourseLimit", true)) {
129            CourseLimit courseLimit = new CourseLimit(properties);
130            addGlobalConstraint(courseLimit);
131        }
132        if (properties.getPropertyBoolean("Sectioning.ReservationLimit", true)) {
133            ReservationLimit reservationLimit = new ReservationLimit(properties);
134            addGlobalConstraint(reservationLimit);
135        }
136        if (properties.getPropertyBoolean("Sectioning.RequiredReservations", true)) {
137            RequiredReservation requiredReservation = new RequiredReservation();
138            addGlobalConstraint(requiredReservation);
139        }
140        try {
141            Class<StudentWeights> studentWeightsClass = (Class<StudentWeights>)Class.forName(properties.getProperty("StudentWeights.Class", PriorityStudentWeights.class.getName()));
142            iStudentWeights = studentWeightsClass.getConstructor(DataProperties.class).newInstance(properties);
143        } catch (Exception e) {
144            sLog.error("Unable to create custom student weighting model (" + e.getMessage() + "), using default.", e);
145            iStudentWeights = new PriorityStudentWeights(properties);
146        }
147        iProjectedStudentWeight = properties.getPropertyDouble("StudentWeights.ProjectedStudentWeight", iProjectedStudentWeight);
148        iProperties = properties;
149    }
150    
151    /**
152     * Return true if reservation that has {@link Reservation#canAssignOverLimit()} can assign enrollments over the limit
153     * @return true if reservation that has {@link Reservation#canAssignOverLimit()} can assign enrollments over the limit
154     */
155    public boolean getReservationCanAssignOverTheLimit() {
156        return iReservationCanAssignOverTheLimit;
157    }
158    
159    /**
160     * Return student weighting model
161     * @return student weighting model
162     */
163    public StudentWeights getStudentWeights() {
164        return iStudentWeights;
165    }
166
167    /**
168     * Set student weighting model
169     * @param weights student weighting model
170     */
171    public void setStudentWeights(StudentWeights weights) {
172        iStudentWeights = weights;
173    }
174
175    /**
176     * Students
177     * @return all students in the problem
178     */
179    public List<Student> getStudents() {
180        return iStudents;
181    }
182
183    /**
184     * Add a student into the model
185     * @param student a student to be added into the problem
186     */
187    public void addStudent(Student student) {
188        iStudents.add(student);
189        if (student.isDummy())
190            iNrDummyStudents++;
191        for (Request request : student.getRequests())
192            addVariable(request);
193        if (getProperties().getPropertyBoolean("Sectioning.StudentConflict", true)) {
194            addConstraint(new StudentConflict(student));
195        }
196    }
197    
198    @Override
199    public void addVariable(Request request) {
200        super.addVariable(request);
201        if (request instanceof CourseRequest)
202            iTotalCRWeight += request.getWeight();
203        if (request.getStudent().isDummy()) {
204            iNrDummyRequests++;
205            iTotalDummyWeight += request.getWeight();
206            if (request instanceof CourseRequest)
207                iTotalDummyCRWeight += request.getWeight();
208        }
209    }
210    
211    /** 
212     * Recompute cached request weights
213     * @param assignment current assignment
214     */
215    public void requestWeightsChanged(Assignment<Request, Enrollment> assignment) {
216        getContext(assignment).requestWeightsChanged(assignment);
217    }
218
219    /**
220     * Remove a student from the model
221     * @param student a student to be removed from the problem
222     */
223    public void removeStudent(Student student) {
224        iStudents.remove(student);
225        if (student.isDummy())
226            iNrDummyStudents--;
227        StudentConflict conflict = null;
228        for (Request request : student.getRequests()) {
229            for (Constraint<Request, Enrollment> c : request.constraints()) {
230                if (c instanceof StudentConflict) {
231                    conflict = (StudentConflict) c;
232                    break;
233                }
234            }
235            if (conflict != null) 
236                conflict.removeVariable(request);
237            removeVariable(request);
238        }
239        if (conflict != null) 
240            removeConstraint(conflict);
241    }
242    
243    @Override
244    public void removeVariable(Request request) {
245        super.removeVariable(request);
246        if (request instanceof CourseRequest) {
247            CourseRequest cr = (CourseRequest)request;
248            for (Course course: cr.getCourses())
249                course.getRequests().remove(request);
250        }
251        if (request.getStudent().isDummy()) {
252            iNrDummyRequests--;
253            iTotalDummyWeight -= request.getWeight();
254            if (request instanceof CourseRequest)
255                iTotalDummyCRWeight -= request.getWeight();
256        }
257        if (request instanceof CourseRequest)
258            iTotalCRWeight -= request.getWeight();
259    }
260
261
262    /**
263     * List of offerings
264     * @return all instructional offerings of the problem
265     */
266    public List<Offering> getOfferings() {
267        return iOfferings;
268    }
269
270    /**
271     * Add an offering into the model
272     * @param offering an instructional offering to be added into the problem
273     */
274    public void addOffering(Offering offering) {
275        iOfferings.add(offering);
276        offering.setModel(this);
277    }
278    
279    /**
280     * Link sections using {@link LinkedSections}
281     * @param sections a linked section constraint to be added into the problem
282     */
283    public void addLinkedSections(Section... sections) {
284        LinkedSections constraint = new LinkedSections(sections);
285        iLinkedSections.add(constraint);
286        constraint.createConstraints();
287    }
288
289    /**
290     * Link sections using {@link LinkedSections}
291     * @param sections a linked section constraint to be added into the problem
292     */
293    public void addLinkedSections(Collection<Section> sections) {
294        LinkedSections constraint = new LinkedSections(sections);
295        iLinkedSections.add(constraint);
296        constraint.createConstraints();
297    }
298
299    /**
300     * List of linked sections
301     * @return all linked section constraints of the problem
302     */
303    public List<LinkedSections> getLinkedSections() {
304        return iLinkedSections;
305    }
306
307    /**
308     * Model info
309     */
310    @Override
311    public Map<String, String> getInfo(Assignment<Request, Enrollment> assignment) {
312        Map<String, String> info = super.getInfo(assignment);
313        StudentSectioningModelContext context = getContext(assignment);
314        if (!getStudents().isEmpty())
315            info.put("Students with complete schedule", sDoubleFormat.format(100.0 * context.nrComplete() / getStudents().size()) + "% (" + context.nrComplete() + "/" + getStudents().size() + ")");
316        if (getDistanceConflict() != null && getDistanceConflict().getTotalNrConflicts(assignment) != 0)
317            info.put("Student distance conflicts", String.valueOf(getDistanceConflict().getTotalNrConflicts(assignment)));
318        if (getTimeOverlaps() != null && getTimeOverlaps().getTotalNrConflicts(assignment) != 0)
319            info.put("Time overlapping conflicts", String.valueOf(getTimeOverlaps().getTotalNrConflicts(assignment)));
320        int nrLastLikeStudents = getNrLastLikeStudents(false);
321        if (nrLastLikeStudents != 0 && nrLastLikeStudents != getStudents().size()) {
322            int nrRealStudents = getStudents().size() - nrLastLikeStudents;
323            int nrLastLikeCompleteStudents = getNrCompleteLastLikeStudents(assignment, false);
324            int nrRealCompleteStudents = context.nrComplete() - nrLastLikeCompleteStudents;
325            if (nrLastLikeStudents > 0)
326                info.put("Projected students with complete schedule", sDecimalFormat.format(100.0
327                        * nrLastLikeCompleteStudents / nrLastLikeStudents)
328                        + "% (" + nrLastLikeCompleteStudents + "/" + nrLastLikeStudents + ")");
329            if (nrRealStudents > 0)
330                info.put("Real students with complete schedule", sDecimalFormat.format(100.0 * nrRealCompleteStudents
331                        / nrRealStudents)
332                        + "% (" + nrRealCompleteStudents + "/" + nrRealStudents + ")");
333            int nrLastLikeRequests = getNrLastLikeRequests(false);
334            int nrRealRequests = variables().size() - nrLastLikeRequests;
335            int nrLastLikeAssignedRequests = context.getNrAssignedLastLikeRequests();
336            int nrRealAssignedRequests = assignment.nrAssignedVariables() - nrLastLikeAssignedRequests;
337            if (nrLastLikeRequests > 0)
338                info.put("Projected assigned requests", sDecimalFormat.format(100.0 * nrLastLikeAssignedRequests / nrLastLikeRequests)
339                        + "% (" + nrLastLikeAssignedRequests + "/" + nrLastLikeRequests + ")");
340            if (nrRealRequests > 0)
341                info.put("Real assigned requests", sDecimalFormat.format(100.0 * nrRealAssignedRequests / nrRealRequests)
342                        + "% (" + nrRealAssignedRequests + "/" + nrRealRequests + ")");
343            if (getDistanceConflict() != null && getDistanceConflict().getTotalNrConflicts(assignment) > 0)
344                info.put("Student distance conflicts", String.valueOf(getDistanceConflict().getTotalNrConflicts(assignment)));
345            if (getTimeOverlaps() != null && getTimeOverlaps().getTotalNrConflicts(assignment) > 0)
346                info.put("Time overlapping conflicts", String.valueOf(getTimeOverlaps().getTotalNrConflicts(assignment)));
347        }
348        context.getInfo(assignment, info);
349
350        return info;
351    }
352
353    /**
354     * Overall solution value
355     * @param assignment current assignment
356     * @param precise true if should be computed
357     * @return solution value
358     */
359    public double getTotalValue(Assignment<Request, Enrollment> assignment, boolean precise) {
360        if (precise) {
361            double total = 0;
362            for (Request r: assignment.assignedVariables())
363                total += r.getWeight() * iStudentWeights.getWeight(assignment, assignment.getValue(r));
364            if (iDistanceConflict != null)
365                for (DistanceConflict.Conflict c: iDistanceConflict.computeAllConflicts(assignment))
366                    total -= avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(assignment, c);
367            if (iTimeOverlaps != null)
368                for (TimeOverlapsCounter.Conflict c: iTimeOverlaps.getContext(assignment).computeAllConflicts(assignment)) {
369                    total -= c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE1(), c);
370                    total -= c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE2(), c);
371                }
372            return -total;
373        }
374        return getContext(assignment).getTotalValue();
375    }
376    
377    /**
378     * Overall solution value
379     */
380    @Override
381    public double getTotalValue(Assignment<Request, Enrollment> assignment) {
382        return getContext(assignment).getTotalValue();
383    }
384
385    /**
386     * Configuration
387     * @return solver configuration
388     */
389    public DataProperties getProperties() {
390        return iProperties;
391    }
392
393    /**
394     * Empty online student sectioning infos for all sections (see
395     * {@link Section#getSpaceExpected()} and {@link Section#getSpaceHeld()}).
396     */
397    public void clearOnlineSectioningInfos() {
398        for (Offering offering : iOfferings) {
399            for (Config config : offering.getConfigs()) {
400                for (Subpart subpart : config.getSubparts()) {
401                    for (Section section : subpart.getSections()) {
402                        section.setSpaceExpected(0);
403                        section.setSpaceHeld(0);
404                    }
405                }
406            }
407        }
408    }
409
410    /**
411     * Compute online student sectioning infos for all sections (see
412     * {@link Section#getSpaceExpected()} and {@link Section#getSpaceHeld()}).
413     * @param assignment current assignment
414     */
415    public void computeOnlineSectioningInfos(Assignment<Request, Enrollment> assignment) {
416        clearOnlineSectioningInfos();
417        for (Student student : getStudents()) {
418            if (!student.isDummy())
419                continue;
420            for (Request request : student.getRequests()) {
421                if (!(request instanceof CourseRequest))
422                    continue;
423                CourseRequest courseRequest = (CourseRequest) request;
424                Enrollment enrollment = assignment.getValue(courseRequest);
425                if (enrollment != null) {
426                    for (Section section : enrollment.getSections()) {
427                        section.setSpaceHeld(courseRequest.getWeight() + section.getSpaceHeld());
428                    }
429                }
430                List<Enrollment> feasibleEnrollments = new ArrayList<Enrollment>();
431                int totalLimit = 0;
432                for (Enrollment enrl : courseRequest.values(assignment)) {
433                    boolean overlaps = false;
434                    for (Request otherRequest : student.getRequests()) {
435                        if (otherRequest.equals(courseRequest) || !(otherRequest instanceof CourseRequest))
436                            continue;
437                        Enrollment otherErollment = assignment.getValue(otherRequest);
438                        if (otherErollment == null)
439                            continue;
440                        if (enrl.isOverlapping(otherErollment)) {
441                            overlaps = true;
442                            break;
443                        }
444                    }
445                    if (!overlaps) {
446                        feasibleEnrollments.add(enrl);
447                        if (totalLimit >= 0) {
448                            int limit = enrl.getLimit();
449                            if (limit < 0) totalLimit = -1;
450                            else totalLimit += limit;
451                        }
452                    }
453                }
454                double increment = courseRequest.getWeight() / (totalLimit > 0 ? totalLimit : feasibleEnrollments.size());
455                for (Enrollment feasibleEnrollment : feasibleEnrollments) {
456                    for (Section section : feasibleEnrollment.getSections()) {
457                        if (totalLimit > 0) {
458                            section.setSpaceExpected(section.getSpaceExpected() + increment * feasibleEnrollment.getLimit());
459                        } else {
460                            section.setSpaceExpected(section.getSpaceExpected() + increment);
461                        }
462                    }
463                }
464            }
465        }
466    }
467
468    /**
469     * Sum of weights of all requests that are not assigned (see
470     * {@link Request#getWeight()}).
471     * @param assignment current assignment
472     * @return unassigned request weight
473     */
474    public double getUnassignedRequestWeight(Assignment<Request, Enrollment> assignment) {
475        double weight = 0.0;
476        for (Request request : assignment.unassignedVariables(this)) {
477            weight += request.getWeight();
478        }
479        return weight;
480    }
481
482    /**
483     * Sum of weights of all requests (see {@link Request#getWeight()}).
484     * @return total request weight
485     */
486    public double getTotalRequestWeight() {
487        double weight = 0.0;
488        for (Request request : variables()) {
489            weight += request.getWeight();
490        }
491        return weight;
492    }
493
494    /**
495     * Set distance conflict extension
496     * @param dc distance conflicts extension
497     */
498    public void setDistanceConflict(DistanceConflict dc) {
499        iDistanceConflict = dc;
500    }
501
502    /**
503     * Return distance conflict extension
504     * @return distance conflicts extension
505     */
506    public DistanceConflict getDistanceConflict() {
507        return iDistanceConflict;
508    }
509
510    /**
511     * Set time overlaps extension
512     * @param toc time overlapping conflicts extension
513     */
514    public void setTimeOverlaps(TimeOverlapsCounter toc) {
515        iTimeOverlaps = toc;
516    }
517
518    /**
519     * Return time overlaps extension
520     * @return time overlapping conflicts extension
521     */
522    public TimeOverlapsCounter getTimeOverlaps() {
523        return iTimeOverlaps;
524    }
525
526    /**
527     * Average priority of unassigned requests (see
528     * {@link Request#getPriority()})
529     * @param assignment current assignment
530     * @return average priority of unassigned requests
531     */
532    public double avgUnassignPriority(Assignment<Request, Enrollment> assignment) {
533        double totalPriority = 0.0;
534        for (Request request : assignment.unassignedVariables(this)) {
535            if (request.isAlternative())
536                continue;
537            totalPriority += request.getPriority();
538        }
539        return 1.0 + totalPriority / assignment.nrUnassignedVariables(this);
540    }
541
542    /**
543     * Average number of requests per student (see {@link Student#getRequests()}
544     * )
545     * @return average number of requests per student
546     */
547    public double avgNrRequests() {
548        double totalRequests = 0.0;
549        int totalStudents = 0;
550        for (Student student : getStudents()) {
551            if (student.nrRequests() == 0)
552                continue;
553            totalRequests += student.nrRequests();
554            totalStudents++;
555        }
556        return totalRequests / totalStudents;
557    }
558
559    /** Number of last like ({@link Student#isDummy()} equals true) students. 
560     * @param precise true if to be computed
561     * @return number of last like (projected) students
562     **/
563    public int getNrLastLikeStudents(boolean precise) {
564        if (!precise)
565            return iNrDummyStudents;
566        int nrLastLikeStudents = 0;
567        for (Student student : getStudents()) {
568            if (student.isDummy())
569                nrLastLikeStudents++;
570        }
571        return nrLastLikeStudents;
572    }
573
574    /** Number of real ({@link Student#isDummy()} equals false) students. 
575     * @param precise true if to be computed
576     * @return number of real students
577     **/
578    public int getNrRealStudents(boolean precise) {
579        if (!precise)
580            return getStudents().size() - iNrDummyStudents;
581        int nrRealStudents = 0;
582        for (Student student : getStudents()) {
583            if (!student.isDummy())
584                nrRealStudents++;
585        }
586        return nrRealStudents;
587    }
588
589    /**
590     * Number of last like ({@link Student#isDummy()} equals true) students with
591     * a complete schedule ({@link Student#isComplete(Assignment)} equals true).
592     * @param assignment current assignment
593     * @param precise true if to be computed
594     * @return number of last like (projected) students with a complete schedule
595     */
596    public int getNrCompleteLastLikeStudents(Assignment<Request, Enrollment> assignment, boolean precise) {
597        if (!precise)
598            return getContext(assignment).getNrCompleteLastLikeStudents();
599        int nrLastLikeStudents = 0;
600        for (Student student : getStudents()) {
601            if (student.isComplete(assignment) && student.isDummy())
602                nrLastLikeStudents++;
603        }
604        return nrLastLikeStudents;
605    }
606
607    /**
608     * Number of real ({@link Student#isDummy()} equals false) students with a
609     * complete schedule ({@link Student#isComplete(Assignment)} equals true).
610     * @param assignment current assignment
611     * @param precise true if to be computed
612     * @return number of real students with a complete schedule
613     */
614    public int getNrCompleteRealStudents(Assignment<Request, Enrollment> assignment, boolean precise) {
615        if (!precise)
616            return getContext(assignment).nrComplete() - getContext(assignment).getNrCompleteLastLikeStudents();
617        int nrRealStudents = 0;
618        for (Student student : getStudents()) {
619            if (student.isComplete(assignment) && !student.isDummy())
620                nrRealStudents++;
621        }
622        return nrRealStudents;
623    }
624
625    /**
626     * Number of requests from projected ({@link Student#isDummy()} equals true)
627     * students.
628     * @param precise true if to be computed
629     * @return number of requests from projected students 
630     */
631    public int getNrLastLikeRequests(boolean precise) {
632        if (!precise)
633            return iNrDummyRequests;
634        int nrLastLikeRequests = 0;
635        for (Request request : variables()) {
636            if (request.getStudent().isDummy())
637                nrLastLikeRequests++;
638        }
639        return nrLastLikeRequests;
640    }
641
642    /**
643     * Number of requests from real ({@link Student#isDummy()} equals false)
644     * students.
645     * @param precise true if to be computed
646     * @return number of requests from real students 
647     */
648    public int getNrRealRequests(boolean precise) {
649        if (!precise)
650            return variables().size() - iNrDummyRequests;
651        int nrRealRequests = 0;
652        for (Request request : variables()) {
653            if (!request.getStudent().isDummy())
654                nrRealRequests++;
655        }
656        return nrRealRequests;
657    }
658
659    /**
660     * Number of requests from projected ({@link Student#isDummy()} equals true)
661     * students that are assigned.
662     * @param assignment current assignment
663     * @param precise true if to be computed
664     * @return number of requests from projected students that are assigned
665     */
666    public int getNrAssignedLastLikeRequests(Assignment<Request, Enrollment> assignment, boolean precise) {
667        if (!precise)
668            return getContext(assignment).getNrAssignedLastLikeRequests();
669        int nrLastLikeRequests = 0;
670        for (Request request : assignment.assignedVariables()) {
671            if (request.getStudent().isDummy())
672                nrLastLikeRequests++;
673        }
674        return nrLastLikeRequests;
675    }
676
677    /**
678     * Number of requests from real ({@link Student#isDummy()} equals false)
679     * students that are assigned.
680     * @param assignment current assignment
681     * @param precise true if to be computed
682     * @return number of requests from real students that are assigned
683     */
684    public int getNrAssignedRealRequests(Assignment<Request, Enrollment> assignment, boolean precise) {
685        if (!precise)
686            return assignment.nrAssignedVariables() - getContext(assignment).getNrAssignedLastLikeRequests();
687        int nrRealRequests = 0;
688        for (Request request : assignment.assignedVariables()) {
689            if (!request.getStudent().isDummy())
690                nrRealRequests++;
691        }
692        return nrRealRequests;
693    }
694
695    /**
696     * Model extended info. Some more information (that is more expensive to
697     * compute) is added to an ordinary {@link Model#getInfo(Assignment)}.
698     */
699    @Override
700    public Map<String, String> getExtendedInfo(Assignment<Request, Enrollment> assignment) {
701        Map<String, String> info = getInfo(assignment);
702        /*
703        int nrLastLikeStudents = getNrLastLikeStudents(true);
704        if (nrLastLikeStudents != 0 && nrLastLikeStudents != getStudents().size()) {
705            int nrRealStudents = getStudents().size() - nrLastLikeStudents;
706            int nrLastLikeCompleteStudents = getNrCompleteLastLikeStudents(true);
707            int nrRealCompleteStudents = getCompleteStudents().size() - nrLastLikeCompleteStudents;
708            info.put("Projected students with complete schedule", sDecimalFormat.format(100.0
709                    * nrLastLikeCompleteStudents / nrLastLikeStudents)
710                    + "% (" + nrLastLikeCompleteStudents + "/" + nrLastLikeStudents + ")");
711            info.put("Real students with complete schedule", sDecimalFormat.format(100.0 * nrRealCompleteStudents
712                    / nrRealStudents)
713                    + "% (" + nrRealCompleteStudents + "/" + nrRealStudents + ")");
714            int nrLastLikeRequests = getNrLastLikeRequests(true);
715            int nrRealRequests = variables().size() - nrLastLikeRequests;
716            int nrLastLikeAssignedRequests = getNrAssignedLastLikeRequests(true);
717            int nrRealAssignedRequests = assignedVariables().size() - nrLastLikeAssignedRequests;
718            info.put("Projected assigned requests", sDecimalFormat.format(100.0 * nrLastLikeAssignedRequests
719                    / nrLastLikeRequests)
720                    + "% (" + nrLastLikeAssignedRequests + "/" + nrLastLikeRequests + ")");
721            info.put("Real assigned requests", sDecimalFormat.format(100.0 * nrRealAssignedRequests / nrRealRequests)
722                    + "% (" + nrRealAssignedRequests + "/" + nrRealRequests + ")");
723        }
724        */
725        // info.put("Average unassigned priority", sDecimalFormat.format(avgUnassignPriority()));
726        // info.put("Average number of requests", sDecimalFormat.format(avgNrRequests()));
727        
728        /*
729        double total = 0;
730        for (Request r: variables())
731            if (r.getAssignment() != null)
732                total += r.getWeight() * iStudentWeights.getWeight(r.getAssignment());
733        */
734        double dc = 0;
735        if (getDistanceConflict() != null && getDistanceConflict().getTotalNrConflicts(assignment) != 0) {
736            Set<DistanceConflict.Conflict> conf = getDistanceConflict().getAllConflicts(assignment);
737            for (DistanceConflict.Conflict c: conf)
738                dc += avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(assignment, c);
739            if (!conf.isEmpty())
740                info.put("Student distance conflicts", conf.size() + " (weighted: " + sDecimalFormat.format(dc) + ")");
741        }
742        double toc = 0;
743        if (getTimeOverlaps() != null && getTimeOverlaps().getTotalNrConflicts(assignment) != 0) {
744            Set<TimeOverlapsCounter.Conflict> conf = getTimeOverlaps().getAllConflicts(assignment);
745            int share = 0;
746            for (TimeOverlapsCounter.Conflict c: conf) {
747                toc += c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE1(), c);
748                toc += c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE2(), c);
749                share += c.getShare();
750            }
751            if (toc != 0.0)
752                info.put("Time overlapping conflicts", share + " (average: " + sDecimalFormat.format(5.0 * share / getStudents().size()) + " min, weighted: " + sDoubleFormat.format(toc) + ")");
753        }
754        /*
755        info.put("Overall solution value", sDecimalFormat.format(total - dc - toc) + (dc == 0.0 && toc == 0.0 ? "" :
756            " (" + (dc != 0.0 ? "distance: " + sDecimalFormat.format(dc): "") + (dc != 0.0 && toc != 0.0 ? ", " : "") + 
757            (toc != 0.0 ? "overlap: " + sDecimalFormat.format(toc) : "") + ")")
758            );
759        */
760        
761        double disbWeight = 0;
762        int disbSections = 0;
763        int disb10Sections = 0;
764        int disb10Limit = getProperties().getPropertyInt("Info.ListDisbalancedSections", 0);
765        Set<String> disb10SectionList = (disb10Limit == 0 ? null : new TreeSet<String>()); 
766        for (Offering offering: getOfferings()) {
767            for (Config config: offering.getConfigs()) {
768                double enrl = config.getEnrollmentWeight(assignment, null);
769                for (Subpart subpart: config.getSubparts()) {
770                    if (subpart.getSections().size() <= 1) continue;
771                    if (subpart.getLimit() > 0) {
772                        // sections have limits -> desired size is section limit x (total enrollment / total limit)
773                        double ratio = enrl / subpart.getLimit();
774                        for (Section section: subpart.getSections()) {
775                            double desired = ratio * section.getLimit();
776                            disbWeight += Math.abs(section.getEnrollmentWeight(assignment, null) - desired);
777                            disbSections ++;
778                            if (Math.abs(desired - section.getEnrollmentWeight(assignment, null)) >= Math.max(1.0, 0.1 * section.getLimit())) {
779                                disb10Sections++;
780                                if (disb10SectionList != null)
781                                        disb10SectionList.add(section.getSubpart().getConfig().getOffering().getName() + " " + section.getSubpart().getName() + " " + section.getName()); 
782                            }
783                        }
784                    } else {
785                        // unlimited sections -> desired size is total enrollment / number of sections
786                        for (Section section: subpart.getSections()) {
787                            double desired = enrl / subpart.getSections().size();
788                            disbWeight += Math.abs(section.getEnrollmentWeight(assignment, null) - desired);
789                            disbSections ++;
790                            if (Math.abs(desired - section.getEnrollmentWeight(assignment, null)) >= Math.max(1.0, 0.1 * desired)) {
791                                disb10Sections++;
792                                if (disb10SectionList != null)
793                                        disb10SectionList.add(section.getSubpart().getConfig().getOffering().getName() + " " + section.getSubpart().getName() + " " + section.getName());
794                            }
795                        }
796                    }
797                }
798            }
799        }
800        if (disbSections != 0) {
801            double assignedCRWeight = getContext(assignment).getAssignedCourseRequestWeight();
802            info.put("Average disbalance", sDecimalFormat.format(disbWeight / disbSections) + " (" + sDecimalFormat.format(assignedCRWeight == 0 ? 0.0 : 100.0 * disbWeight / assignedCRWeight) + "%)");
803            String list = "";
804            if (disb10SectionList != null) {
805                int i = 0;
806                for (String section: disb10SectionList) {
807                    if (i == disb10Limit) {
808                        list += "<br>...";
809                        break;
810                    }
811                    list += "<br>" + section;
812                    i++;
813                }
814            }
815            info.put("Sections disbalanced by 10% or more", disb10Sections + " (" + sDecimalFormat.format(disbSections == 0 ? 0.0 : 100.0 * disb10Sections / disbSections) + "%)" + list);
816        }
817        return info;
818    }
819    
820    @Override
821    public void restoreBest(Assignment<Request, Enrollment> assignment) {
822        restoreBest(assignment, new Comparator<Request>() {
823            @Override
824            public int compare(Request r1, Request r2) {
825                Enrollment e1 = r1.getBestAssignment();
826                Enrollment e2 = r2.getBestAssignment();
827                // Reservations first
828                if (e1.getReservation() != null && e2.getReservation() == null) return -1;
829                if (e1.getReservation() == null && e2.getReservation() != null) return 1;
830                // Then assignment iteration (i.e., order in which assignments were made)
831                if (r1.getBestAssignmentIteration() != r2.getBestAssignmentIteration())
832                    return (r1.getBestAssignmentIteration() < r2.getBestAssignmentIteration() ? -1 : 1);
833                // Then student and priority
834                return r1.compareTo(r2);
835            }
836        });
837    }
838        
839    @Override
840    public String toString(Assignment<Request, Enrollment> assignment) {
841        return   (getNrRealStudents(false) > 0 ? "RRq:" + getNrAssignedRealRequests(assignment, false) + "/" + getNrRealRequests(false) + ", " : "")
842                + (getNrLastLikeStudents(false) > 0 ? "DRq:" + getNrAssignedLastLikeRequests(assignment, false) + "/" + getNrLastLikeRequests(false) + ", " : "")
843                + (getNrRealStudents(false) > 0 ? "RS:" + getNrCompleteRealStudents(assignment, false) + "/" + getNrRealStudents(false) + ", " : "")
844                + (getNrLastLikeStudents(false) > 0 ? "DS:" + getNrCompleteLastLikeStudents(assignment, false) + "/" + getNrLastLikeStudents(false) + ", " : "")
845                + "V:"
846                + sDecimalFormat.format(-getTotalValue(assignment))
847                + (getDistanceConflict() == null ? "" : ", DC:" + getDistanceConflict().getTotalNrConflicts(assignment))
848                + (getTimeOverlaps() == null ? "" : ", TOC:" + getTimeOverlaps().getTotalNrConflicts(assignment))
849                + ", %:" + sDecimalFormat.format(-100.0 * getTotalValue(assignment) / (getStudents().size() - iNrDummyStudents + 
850                        (iProjectedStudentWeight < 0.0 ? iNrDummyStudents * (iTotalDummyWeight / iNrDummyRequests) :iProjectedStudentWeight * iTotalDummyWeight)));
851
852    }
853    
854    /**
855     * Quadratic average of two weights.
856     * @param w1 first weight
857     * @param w2 second weight
858     * @return average of the two weights
859     */
860    public double avg(double w1, double w2) {
861        return Math.sqrt(w1 * w2);
862    }
863
864    /**
865     * Maximal domain size (i.e., number of enrollments of a course request), -1 if there is no limit.
866     * @return maximal domain size, -1 if unlimited
867     */
868    public int getMaxDomainSize() { return iMaxDomainSize; }
869
870    /**
871     * Maximal domain size (i.e., number of enrollments of a course request), -1 if there is no limit.
872     * @param maxDomainSize maximal domain size, -1 if unlimited
873     */
874    public void setMaxDomainSize(int maxDomainSize) { iMaxDomainSize = maxDomainSize; }
875    
876
877    @Override
878    public StudentSectioningModelContext createAssignmentContext(Assignment<Request, Enrollment> assignment) {
879        return new StudentSectioningModelContext(assignment);
880    }
881    
882    public class StudentSectioningModelContext implements AssignmentConstraintContext<Request, Enrollment>, InfoProvider<Request, Enrollment>{
883        private Set<Student> iCompleteStudents = new HashSet<Student>();
884        private double iTotalValue = 0.0;
885        private int iNrAssignedDummyRequests = 0, iNrCompleteDummyStudents = 0;
886        private double iAssignedCRWeight = 0.0, iAssignedDummyCRWeight = 0.0;
887        private double iReservedSpace = 0.0;
888
889        public StudentSectioningModelContext(Assignment<Request, Enrollment> assignment) {
890            for (Request request: variables()) {
891                Enrollment enrollment = assignment.getValue(request);
892                if (enrollment != null)
893                    assigned(assignment, enrollment);
894            }
895        }
896
897        /**
898         * Called after an enrollment was assigned to a request. The list of
899         * complete students and the overall solution value are updated.
900         */
901        @Override
902        public void assigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
903            Student student = enrollment.getStudent();
904            if (student.isComplete(assignment))
905                iCompleteStudents.add(student);
906            double value = enrollment.getRequest().getWeight() * iStudentWeights.getWeight(assignment, enrollment);
907            iTotalValue -= value;
908            enrollment.variable().getContext(assignment).setLastWeight(value);
909            if (enrollment.isCourseRequest())
910                iAssignedCRWeight += enrollment.getRequest().getWeight();
911            if (enrollment.getReservation() != null)
912                iReservedSpace += enrollment.getRequest().getWeight();
913            if (enrollment.isCourseRequest() && ((CourseRequest)enrollment.getRequest()).hasReservations())
914                iTotalReservedSpace += enrollment.getRequest().getWeight();
915            if (student.isDummy()) {
916                iNrAssignedDummyRequests++;
917                if (enrollment.isCourseRequest())
918                    iAssignedDummyCRWeight += enrollment.getRequest().getWeight();
919                if (student.isComplete(assignment))
920                    iNrCompleteDummyStudents++;
921            }
922        }
923
924        /**
925         * Called before an enrollment was unassigned from a request. The list of
926         * complete students and the overall solution value are updated.
927         */
928        @Override
929        public void unassigned(Assignment<Request, Enrollment> assignment, Enrollment enrollment) {
930            Student student = enrollment.getStudent();
931            if (iCompleteStudents.contains(student) && !student.isComplete(assignment)) {
932                iCompleteStudents.remove(student);
933                if (student.isDummy())
934                    iNrCompleteDummyStudents--;
935            }
936            Request.RequestContext cx = enrollment.variable().getContext(assignment);
937            Double value = cx.getLastWeight();
938            if (value == null)
939                value = enrollment.getRequest().getWeight() * iStudentWeights.getWeight(assignment, enrollment);
940            iTotalValue += value;
941            cx.setLastWeight(null);
942            if (enrollment.isCourseRequest())
943                iAssignedCRWeight -= enrollment.getRequest().getWeight();
944            if (enrollment.getReservation() != null)
945                iReservedSpace -= enrollment.getRequest().getWeight();
946            if (enrollment.isCourseRequest() && ((CourseRequest)enrollment.getRequest()).hasReservations())
947                iTotalReservedSpace -= enrollment.getRequest().getWeight();
948            if (student.isDummy()) {
949                iNrAssignedDummyRequests--;
950                if (enrollment.isCourseRequest())
951                    iAssignedDummyCRWeight -= enrollment.getRequest().getWeight();
952            }
953        }
954        
955        public void add(Assignment<Request, Enrollment> assignment, DistanceConflict.Conflict c) {
956            iTotalValue += avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(assignment, c);
957        }
958
959        public void remove(Assignment<Request, Enrollment> assignment, DistanceConflict.Conflict c) {
960            iTotalValue -= avg(c.getR1().getWeight(), c.getR2().getWeight()) * iStudentWeights.getDistanceConflictWeight(assignment, c);
961        }
962        
963        public void add(Assignment<Request, Enrollment> assignment, TimeOverlapsCounter.Conflict c) {
964            iTotalValue += c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE1(), c);
965            iTotalValue += c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE2(), c);
966        }
967
968        public void remove(Assignment<Request, Enrollment> assignment, TimeOverlapsCounter.Conflict c) {
969            iTotalValue -= c.getR1().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE1(), c);
970            iTotalValue -= c.getR2().getWeight() * iStudentWeights.getTimeOverlapConflictWeight(assignment, c.getE2(), c);
971        }
972        
973        /**
974         * Students with complete schedules (see {@link Student#isComplete(Assignment)})
975         * @return students with complete schedule
976         */
977        public Set<Student> getCompleteStudents() {
978            return iCompleteStudents;
979        }
980        
981        /**
982         * Number of students with complete schedule
983         * @return number of students with complete schedule
984         */
985        public int nrComplete() {
986            return getCompleteStudents().size();
987        }
988        
989        /** 
990         * Recompute cached request weights
991         * @param assignment curent assignment
992         */
993        public void requestWeightsChanged(Assignment<Request, Enrollment> assignment) {
994            iTotalCRWeight = 0.0;
995            iTotalDummyWeight = 0.0; iTotalDummyCRWeight = 0.0;
996            iAssignedCRWeight = 0.0;
997            iAssignedDummyCRWeight = 0.0;
998            iNrDummyRequests = 0; iNrAssignedDummyRequests = 0;
999            iTotalReservedSpace = 0.0; iReservedSpace = 0.0;
1000            for (Request request: variables()) {
1001                boolean cr = (request instanceof CourseRequest);
1002                if (cr)
1003                    iTotalCRWeight += request.getWeight();
1004                if (request.getStudent().isDummy()) {
1005                    iTotalDummyWeight += request.getWeight();
1006                    iNrDummyRequests ++;
1007                    if (cr)
1008                        iTotalDummyCRWeight += request.getWeight();
1009                }
1010                if (assignment.getValue(request) != null) {
1011                    if (cr)
1012                        iAssignedCRWeight += request.getWeight();
1013                    if (assignment.getValue(request).getReservation() != null)
1014                        iReservedSpace += request.getWeight();
1015                    if (cr && ((CourseRequest)request).hasReservations())
1016                        iTotalReservedSpace += request.getWeight();
1017                    if (request.getStudent().isDummy()) {
1018                        iNrAssignedDummyRequests ++;
1019                        if (cr)
1020                            iAssignedDummyCRWeight += request.getWeight();
1021                    }
1022                }
1023            }
1024        }
1025        
1026        /**
1027         * Overall solution value
1028         * @return solution value
1029         */
1030        public double getTotalValue() {
1031            return iTotalValue;
1032        }
1033        
1034        /**
1035         * Number of last like ({@link Student#isDummy()} equals true) students with
1036         * a complete schedule ({@link Student#isComplete(Assignment)} equals true).
1037         * @return number of last like (projected) students with a complete schedule
1038         */
1039        public int getNrCompleteLastLikeStudents() {
1040            return iNrCompleteDummyStudents;
1041        }
1042        
1043        /**
1044         * Number of requests from projected ({@link Student#isDummy()} equals true)
1045         * students that are assigned.
1046         * @return number of real students with a complete schedule
1047         */
1048        public int getNrAssignedLastLikeRequests() {
1049            return iNrAssignedDummyRequests;
1050        }
1051
1052        @Override
1053        public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info) {
1054            if (iTotalCRWeight > 0.0) {
1055                info.put("Assigned course requests", sDecimalFormat.format(100.0 * iAssignedCRWeight / iTotalCRWeight) + "% (" + (int)Math.round(iAssignedCRWeight) + "/" + (int)Math.round(iTotalCRWeight) + ")");
1056                if (getNrLastLikeStudents(false) != getStudents().size() && iTotalCRWeight != iTotalDummyCRWeight) {
1057                    if (iTotalDummyCRWeight > 0.0)
1058                        info.put("Projected assigned course requests", sDecimalFormat.format(100.0 * iAssignedDummyCRWeight / iTotalDummyCRWeight) + "% (" + (int)Math.round(iAssignedDummyCRWeight) + "/" + (int)Math.round(iTotalDummyCRWeight) + ")");
1059                    info.put("Real assigned course requests", sDecimalFormat.format(100.0 * (iAssignedCRWeight - iAssignedDummyCRWeight) / (iTotalCRWeight - iTotalDummyCRWeight)) +
1060                            "% (" + (int)Math.round(iAssignedCRWeight - iAssignedDummyCRWeight) + "/" + (int)Math.round(iTotalCRWeight - iTotalDummyCRWeight) + ")");
1061                }
1062            }
1063            if (iTotalReservedSpace > 0.0)
1064                info.put("Reservations", sDoubleFormat.format(100.0 * iReservedSpace / iTotalReservedSpace) + "% (" + Math.round(iReservedSpace) + "/" + Math.round(iTotalReservedSpace) + ")"); 
1065        }
1066
1067        @Override
1068        public void getInfo(Assignment<Request, Enrollment> assignment, Map<String, String> info, Collection<Request> variables) {
1069        }
1070        
1071        public double getAssignedCourseRequestWeight() {
1072            return iAssignedCRWeight;
1073        }
1074    }
1075}