001package org.cpsolver.studentsct.online.selection;
002
003import java.util.ArrayList;
004import java.util.Collections;
005import java.util.Comparator;
006import java.util.HashMap;
007import java.util.HashSet;
008import java.util.Hashtable;
009import java.util.Iterator;
010import java.util.List;
011import java.util.Map;
012import java.util.Set;
013import java.util.TreeSet;
014
015import org.cpsolver.coursett.Constants;
016import org.cpsolver.coursett.model.TimeLocation;
017import org.cpsolver.ifs.assignment.Assignment;
018import org.cpsolver.ifs.util.DataProperties;
019import org.cpsolver.ifs.util.ToolBox;
020import org.cpsolver.studentsct.model.Config;
021import org.cpsolver.studentsct.model.Course;
022import org.cpsolver.studentsct.model.CourseRequest;
023import org.cpsolver.studentsct.model.Enrollment;
024import org.cpsolver.studentsct.model.FreeTimeRequest;
025import org.cpsolver.studentsct.model.Request;
026import org.cpsolver.studentsct.model.Section;
027import org.cpsolver.studentsct.model.Student;
028import org.cpsolver.studentsct.online.OnlineSectioningModel;
029import org.cpsolver.studentsct.online.expectations.OverExpectedCriterion;
030import org.cpsolver.studentsct.online.selection.MultiCriteriaBranchAndBoundSelection.SelectionComparator;
031
032/**
033 * Computation of suggestions using a limited depth branch and bound.
034 * For a given schedule and a selected section, compute
035 * possible changes that will be displayed to the student as suggestions. The number
036 * of suggestions is limited by Suggestions.MaxSuggestions parameter (defaults to 20).
037 * Time is limited by Suggestions.Timeout (defaults to 5000 ms), search depth is limited
038 * by Suggestions.MaxDepth parameter (default to 4).
039 * 
040 * @version StudentSct 1.3 (Student Sectioning)<br>
041 *          Copyright (C) 2014 Tomas Muller<br>
042 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
043 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
044 * <br>
045 *          This library is free software; you can redistribute it and/or modify
046 *          it under the terms of the GNU Lesser General Public License as
047 *          published by the Free Software Foundation; either version 3 of the
048 *          License, or (at your option) any later version. <br>
049 * <br>
050 *          This library is distributed in the hope that it will be useful, but
051 *          WITHOUT ANY WARRANTY; without even the implied warranty of
052 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
053 *          Lesser General Public License for more details. <br>
054 * <br>
055 *          You should have received a copy of the GNU Lesser General Public
056 *          License along with this library; if not see <a
057 *          href='http://www.gnu.org/licenses'>http://www.gnu.org/licenses</a>.
058 * 
059 */
060public class SuggestionsBranchAndBound {
061    private Hashtable<CourseRequest, Set<Section>> iRequiredSections = null;
062    private Set<FreeTimeRequest> iRequiredFreeTimes = null;
063    private Hashtable<CourseRequest, Set<Section>> iPreferredSections = null;
064    private Request iSelectedRequest = null;
065    private Section iSelectedSection = null;
066    private Student iStudent = null;
067    private TreeSet<Suggestion> iSuggestions = new TreeSet<Suggestion>();
068    private int iMaxDepth = 4;
069    private long iTimeout = 5000;
070    private int iMaxSuggestions = 20;
071    private long iT0, iT1;
072    private boolean iTimeoutReached = false;
073    private int iNrSolutionsSeen = 0;
074    private OnlineSectioningModel iModel;
075    private Assignment<Request, Enrollment> iAssignment;
076    private Hashtable<Request, List<Enrollment>> iValues = new Hashtable<Request, List<Enrollment>>();
077    private long iLastSuggestionId = 0;
078    private SuggestionFilter iFilter = null;
079    protected SelectionComparator iComparator = null;
080    protected int iMatched = 0;
081    protected double iMaxSectionsWithPenalty = 0;
082
083    /**
084     * Constructor 
085     * @param properties configuration
086     * @param student given student
087     * @param assignment current assignment
088     * @param requiredSections required sections
089     * @param requiredFreeTimes required free times (free time requests that must be assigned)
090     * @param preferredSections preferred sections
091     * @param selectedRequest selected request
092     * @param selectedSection selected section
093     * @param filter section filter
094     * @param maxSectionsWithPenalty maximal number of sections that have a positive over-expectation penalty {@link OverExpectedCriterion#getOverExpected(Assignment, Section, Request)}
095     */
096    public SuggestionsBranchAndBound(DataProperties properties, Student student,
097            Assignment<Request, Enrollment> assignment, Hashtable<CourseRequest, Set<Section>> requiredSections,
098            Set<FreeTimeRequest> requiredFreeTimes, Hashtable<CourseRequest, Set<Section>> preferredSections,
099            Request selectedRequest, Section selectedSection, SuggestionFilter filter, double maxSectionsWithPenalty) {
100        iRequiredSections = requiredSections;
101        iRequiredFreeTimes = requiredFreeTimes;
102        iPreferredSections = preferredSections;
103        iSelectedRequest = selectedRequest;
104        iSelectedSection = selectedSection;
105        iStudent = student;
106        iModel = (OnlineSectioningModel) selectedRequest.getModel();
107        iAssignment = assignment;
108        iMaxDepth = properties.getPropertyInt("Suggestions.MaxDepth", iMaxDepth);
109        iTimeout = properties.getPropertyLong("Suggestions.Timeout", iTimeout);
110        iMaxSuggestions = properties.getPropertyInt("Suggestions.MaxSuggestions", iMaxSuggestions);
111        iMaxSectionsWithPenalty = maxSectionsWithPenalty;
112        iFilter = filter;
113        iComparator = new SelectionComparator() {
114            private HashMap<Enrollment, Double> iValues = new HashMap<Enrollment, Double>();
115
116            private Double value(Enrollment e) {
117                Double value = iValues.get(e);
118                if (value == null) {
119                    value = iModel.getStudentWeights().getWeight(iAssignment, e,
120                            (iModel.getDistanceConflict() == null ? null : iModel.getDistanceConflict().conflicts(e)),
121                            (iModel.getTimeOverlaps() == null ? null : iModel.getTimeOverlaps().conflicts(e)));
122                    iValues.put(e, value);
123                }
124                return value;
125            }
126
127            @Override
128            public int compare(Assignment<Request, Enrollment> a, Enrollment e1, Enrollment e2) {
129                return value(e2).compareTo(value(e1));
130            }
131        };
132    }
133
134    /**
135     * Return search time
136     * @return search time
137     */
138    public long getTime() {
139        return iT1 - iT0;
140    }
141
142    /**
143     * Was time limit reached
144     * @return true if reached
145     */
146    public boolean isTimeoutReached() {
147        return iTimeoutReached;
148    }
149
150    /**
151     * Number of possible suggestions visited
152     * @return a number of solutions seen
153     */
154    public int getNrSolutionsSeen() {
155        return iNrSolutionsSeen;
156    }
157
158    /**
159     * Perform the search
160     * @return an ordered set of possible suggestions
161     */
162    public TreeSet<Suggestion> computeSuggestions() {
163        iT0 = System.currentTimeMillis();
164        iTimeoutReached = false;
165        iNrSolutionsSeen = 0;
166        iSuggestions.clear();
167
168        ArrayList<Request> requests2resolve = new ArrayList<Request>();
169        requests2resolve.add(iSelectedRequest);
170        TreeSet<Request> altRequests2resolve = new TreeSet<Request>();
171
172        for (Map.Entry<CourseRequest, Set<Section>> entry : iPreferredSections.entrySet()) {
173            CourseRequest request = entry.getKey();
174            Set<Section> sections = entry.getValue();
175            if (!sections.isEmpty() && sections.size() == sections.iterator().next().getSubpart().getConfig().getSubparts().size())
176                iAssignment.assign(0, request.createEnrollment(iAssignment, sections));
177            else if (!request.equals(iSelectedRequest)) {
178                if (sections.isEmpty())
179                    altRequests2resolve.add(request);
180                else
181                    requests2resolve.add(request);
182            }
183        }
184
185        for (Request request : iStudent.getRequests()) {
186            if (iAssignment.getValue(request) == null && request instanceof FreeTimeRequest) {
187                FreeTimeRequest ft = (FreeTimeRequest) request;
188                Enrollment enrollment = ft.createEnrollment();
189                if (iModel.conflictValues(iAssignment, enrollment).isEmpty())
190                    iAssignment.assign(0, enrollment);
191            }
192        }
193
194        for (Request request : iStudent.getRequests()) {
195            request.setInitialAssignment(iAssignment.getValue(request));
196        }
197
198        backtrack(requests2resolve, altRequests2resolve, 0, iMaxDepth, false);
199
200        iT1 = System.currentTimeMillis();
201        return iSuggestions;
202    }
203
204    /**
205     * Main branch and bound rutine
206     * @param requests2resolve remaining requests to assign
207     * @param altRequests2resolve alternative requests to assign
208     * @param idx current depth
209     * @param depth remaining depth
210     * @param alt can leave a request unassigned
211     */
212    protected void backtrack(ArrayList<Request> requests2resolve, TreeSet<Request> altRequests2resolve, int idx,
213            int depth, boolean alt) {
214        if (!iTimeoutReached && iTimeout > 0 && System.currentTimeMillis() - iT0 > iTimeout)
215            iTimeoutReached = true;
216        int nrUnassigned = requests2resolve.size() - idx;
217        if (nrUnassigned == 0) {
218            List<FreeTimeRequest> okFreeTimes = new ArrayList<FreeTimeRequest>();
219            double sectionsWithPenalty = 0;
220            for (Request r : iStudent.getRequests()) {
221                Enrollment e = iAssignment.getValue(r);
222                if (iMaxSectionsWithPenalty >= 0 && e != null && r instanceof CourseRequest) {
223                    for (Section s : e.getSections())
224                        sectionsWithPenalty += iModel.getOverExpected(iAssignment, s, r);
225                }
226                if (e == null && r instanceof FreeTimeRequest) {
227                    FreeTimeRequest ft = (FreeTimeRequest) r;
228                    Enrollment enrollment = ft.createEnrollment();
229                    if (iModel.conflictValues(iAssignment, enrollment).isEmpty()) {
230                        iAssignment.assign(0, enrollment);
231                        okFreeTimes.add(ft);
232                    }
233                }
234                if (e != null && e.isCourseRequest() && e.getSections().isEmpty()) {
235                    Double minPenalty = null;
236                    for (Enrollment other : values(e.getRequest())) {
237                        if (!isAllowed(other)) continue;
238                        if (e.equals(other)) continue;
239                        double penalty = 0.0;
240                        for (Section s: other.getSections())
241                            penalty += iModel.getOverExpected(iAssignment, s, other.getRequest());
242                        if (minPenalty == null || minPenalty > penalty) minPenalty = penalty;
243                        if (minPenalty == 0.0) break;
244                    }
245                    if (minPenalty != null) sectionsWithPenalty += minPenalty;
246                }
247            }
248            if (iMaxSectionsWithPenalty >= 0 && sectionsWithPenalty > iMaxSectionsWithPenalty)
249                return;
250            Suggestion s = new Suggestion(requests2resolve);
251            if (iSuggestions.size() >= iMaxSuggestions && iSuggestions.last().compareTo(s) <= 0)
252                return;
253            if (iMatched != 1) {
254                for (Iterator<Suggestion> i = iSuggestions.iterator(); i.hasNext();) {
255                    Suggestion x = i.next();
256                    if (x.sameSelectedSection()) {
257                        if (x.compareTo(s) <= 0) return;
258                        i.remove();
259                    }
260                }
261            }
262            s.init();
263            iSuggestions.add(s);
264            if (iSuggestions.size() > iMaxSuggestions)
265                iSuggestions.remove(iSuggestions.last());
266            for (FreeTimeRequest ft : okFreeTimes)
267                iAssignment.unassign(0, ft);
268            return;
269        }
270        if (!canContinue(requests2resolve, idx, depth))
271            return;
272        Request request = requests2resolve.get(idx);
273        for (Enrollment enrollment : values(request)) {
274            if (!canContinueEvaluation())
275                break;
276            if (!isAllowed(enrollment))
277                continue;
278            if (enrollment.equals(iAssignment.getValue(request)))
279                continue;
280            if (enrollment.getAssignments().isEmpty() && alt)
281                continue;
282            Set<Enrollment> conflicts = iModel.conflictValues(iAssignment, enrollment);
283            if (!checkBound(requests2resolve, idx, depth, enrollment, conflicts))
284                continue;
285            Enrollment current = iAssignment.getValue(request);
286            ArrayList<Request> newVariables2resolve = new ArrayList<Request>(requests2resolve);
287            for (Iterator<Enrollment> i = conflicts.iterator(); i.hasNext();) {
288                Enrollment conflict = i.next();
289                iAssignment.unassign(0, conflict.variable());
290                if (!newVariables2resolve.contains(conflict.variable()))
291                    newVariables2resolve.add(conflict.variable());
292            }
293            if (current != null)
294                iAssignment.unassign(0, current.variable());
295            iAssignment.assign(0, enrollment);
296            if (enrollment.getAssignments().isEmpty()) {
297                if (altRequests2resolve != null && !altRequests2resolve.isEmpty()) {
298                    Suggestion lastBefore = (iSuggestions.isEmpty() ? null : iSuggestions.last());
299                    int sizeBefore = iSuggestions.size();
300                    for (Request r : altRequests2resolve) {
301                        newVariables2resolve.add(r);
302                        backtrack(newVariables2resolve, null, idx + 1, depth, true);
303                        newVariables2resolve.remove(r);
304                    }
305                    Suggestion lastAfter = (iSuggestions.isEmpty() ? null : iSuggestions.last());
306                    int sizeAfter = iSuggestions.size();
307                    // did not succeeded with an alternative -> try without it
308                    if (sizeBefore == sizeAfter && (sizeAfter < iMaxSuggestions || sizeAfter == 0 || lastAfter.compareTo(lastBefore) == 0))
309                        backtrack(newVariables2resolve, altRequests2resolve, idx + 1, depth - 1, alt);
310                } else {
311                    backtrack(newVariables2resolve, altRequests2resolve, idx + 1, depth - 1, alt);
312                }
313            } else {
314                backtrack(newVariables2resolve, altRequests2resolve, idx + 1, depth - 1, alt);
315            }
316            if (current == null)
317                iAssignment.unassign(0, request);
318            else
319                iAssignment.assign(0, current);
320            for (Iterator<Enrollment> i = conflicts.iterator(); i.hasNext();) {
321                Enrollment conflict = i.next();
322                iAssignment.assign(0, conflict);
323            }
324        }
325    }
326
327    /**
328     * Domain of a request    
329     * @param request given request
330     * @return possible enrollments (meeting the filter etc)
331     */
332    protected List<Enrollment> values(final Request request) {
333        if (!request.getStudent().canAssign(iAssignment, request))
334            return new ArrayList<Enrollment>();
335        List<Enrollment> values = iValues.get(request);
336        if (values != null)
337            return values;
338        if (request instanceof CourseRequest) {
339            CourseRequest cr = (CourseRequest) request;
340            values = (cr.equals(iSelectedRequest) ? cr.getAvaiableEnrollments(iAssignment) : cr.getAvaiableEnrollmentsSkipSameTime(iAssignment));
341            Collections.sort(values, new Comparator<Enrollment>() {
342                @Override
343                public int compare(Enrollment e1, Enrollment e2) {
344                    return iComparator.compare(iAssignment, e1, e2);
345                }
346            });
347        } else {
348            values = new ArrayList<Enrollment>();
349            values.add(((FreeTimeRequest) request).createEnrollment());
350        }
351        if (canLeaveUnassigned(request)) {
352            Config config = null;
353            if (request instanceof CourseRequest)
354                config = ((CourseRequest) request).getCourses().get(0).getOffering().getConfigs().get(0);
355            values.add(new Enrollment(request, 0, config, new HashSet<Section>(), iAssignment));
356        }
357        iValues.put(request, values);
358        if (request.equals(iSelectedRequest) && iFilter != null && request instanceof CourseRequest) {
359            for (Iterator<Enrollment> i = values.iterator(); i.hasNext();) {
360                Enrollment enrollment = i.next();
361                if (enrollment.getAssignments() != null && !enrollment.getAssignments().isEmpty()) {
362                    boolean match = false;
363                    for (Iterator<Section> j = enrollment.getSections().iterator(); j.hasNext();) {
364                        Section section = j.next();
365                        if (iSelectedSection != null) {
366                            if (section.getSubpart().getId() == iSelectedSection.getSubpart().getId()) {
367                                if (iFilter.match(enrollment.getCourse(), section)) {
368                                    match = true;
369                                    break;
370                                }
371                            }
372                            if (section.getSubpart().getConfig().getId() != iSelectedSection.getSubpart().getConfig().getId() &&
373                                    section.getSubpart().getInstructionalType().equals(iSelectedSection.getSubpart().getInstructionalType())) {
374                                if (iFilter.match(enrollment.getCourse(), section)) {
375                                    match = true;
376                                    break;
377                                }
378                            }
379                        } else {
380                            if (iFilter.match(enrollment.getCourse(), section)) {
381                                match = true;
382                                break;
383                            }
384                        }
385                    }
386                    if (!match)
387                        i.remove();
388                }
389            }
390        }
391        if (request.equals(iSelectedRequest))
392            iMatched = values.size();
393        return values;
394    }
395
396    /**
397     * Termination criterion
398     * @param requests2resolve request to resolve
399     * @param idx current depth
400     * @param depth remaining depth
401     * @return true if the search can continue
402     */
403    protected boolean canContinue(ArrayList<Request> requests2resolve, int idx, int depth) {
404        if (depth <= 0)
405            return false;
406        if (iTimeoutReached)
407            return false;
408        return true;
409    }
410
411    /**
412     * Can continue evaluation of possible enrollments
413     * @return false if the timeout was reached
414     */
415    protected boolean canContinueEvaluation() {
416        return !iTimeoutReached;
417    }
418
419    /**
420     * Check bound
421     * @param requests2resolve requests to resolve
422     * @param idx current depth
423     * @param depth remaining depth
424     * @param value enrollment in question
425     * @param conflicts conflicting enrollments
426     * @return false if the branch can be cut
427     */
428    protected boolean checkBound(ArrayList<Request> requests2resolve, int idx, int depth, Enrollment value,
429            Set<Enrollment> conflicts) {
430        if (iMaxSectionsWithPenalty < 0.0 && idx > 0 && !conflicts.isEmpty()) return false;
431        int nrUnassigned = requests2resolve.size() - idx;
432        if ((nrUnassigned + conflicts.size() > depth)) {
433            return false;
434        }
435        for (Enrollment conflict : conflicts) {
436            int confIdx = requests2resolve.indexOf(conflict.variable());
437            if (confIdx >= 0 && confIdx <= idx)
438                return false;
439        }
440        if (iMaxSectionsWithPenalty >= 0) {
441            double sectionsWithPenalty = 0;
442            for (Request r : iStudent.getRequests()) {
443                Enrollment e = iAssignment.getValue(r);
444                if (r.equals(value.variable())) {
445                    e = value;
446                } else if (conflicts.contains(e)) {
447                    e = null;
448                }
449                if (e != null && e.isCourseRequest()) {
450                    sectionsWithPenalty += iModel.getOverExpected(iAssignment, e, value, conflicts);
451                }
452            }
453            if (sectionsWithPenalty > iMaxSectionsWithPenalty)
454                return false;
455        }
456        return true;
457    }
458
459    /**
460     * Check required sections
461     * @param enrollment given enrollment
462     * @return true if  the given enrollment allowed
463     */
464    public boolean isAllowed(Enrollment enrollment) {
465        if (iRequiredSections != null && enrollment.getRequest() instanceof CourseRequest) {
466            // Obey required sections
467            Set<Section> required = iRequiredSections.get(enrollment.getRequest());
468            if (required != null && !required.isEmpty()) {
469                if (enrollment.getAssignments() == null)
470                    return false;
471                for (Section r : required)
472                    if (!enrollment.getAssignments().contains(r))
473                        return false;
474            }
475        }
476        if (enrollment.getRequest().equals(iSelectedRequest)) {
477            // Selected request must be assigned
478            if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty())
479                return false;
480            // Selected section must be assigned differently
481            if (iSelectedSection != null && enrollment.getAssignments().contains(iSelectedSection))
482                return false;
483        }
484        return true;
485    }
486
487    /**
488     * Can this request be left unassigned
489     * @param request given request
490     * @return true if can be left unassigned (there is no requirement)
491     */
492    public boolean canLeaveUnassigned(Request request) {
493        if (request instanceof CourseRequest) {
494            if (iRequiredSections != null) {
495                // Request with required section must be assigned
496                Set<Section> required = iRequiredSections.get(request);
497                if (required != null && !required.isEmpty())
498                    return false;
499            }
500        } else {
501            // Free time is required
502            if (iRequiredFreeTimes.contains(request))
503                return false;
504        }
505        // Selected request must be assigned
506        if (request.equals(iSelectedRequest))
507            return false;
508        return true;
509    }
510
511    /**
512     * Compare two suggestions
513     * @param assignment current assignment
514     * @param s1 first suggestion
515     * @param s2 second suggestion
516     * @return true if s1 is better than s2
517     */
518    protected int compare(Assignment<Request, Enrollment> assignment, Suggestion s1, Suggestion s2) {
519        return Double.compare(s1.getValue(), s2.getValue());
520    }
521
522    /**
523     * Suggestion
524     */
525    public class Suggestion implements Comparable<Suggestion> {
526        private double iValue = 0.0;
527        private int iNrUnassigned = 0;
528        private int iUnassignedPriority = 0;
529        private int iNrChanges = 0;
530
531        private long iId = iLastSuggestionId++;
532        private Enrollment[] iEnrollments;
533        private Section iSelectedEnrollment = null;
534        private boolean iSelectedEnrollmentChangeTime = false;
535        private TreeSet<Section> iSelectedSections = new TreeSet<Section>(new EnrollmentSectionComparator());
536
537        /**
538         * Create suggestion
539         * @param resolvedRequests assigned requests
540         */
541        public Suggestion(ArrayList<Request> resolvedRequests) {
542            for (Request request : resolvedRequests) {
543                Enrollment enrollment = iAssignment.getValue(request);
544                if (enrollment.getAssignments().isEmpty()) {
545                    iNrUnassigned++;
546                    iUnassignedPriority += request.getPriority();
547                }
548                iValue += (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty() ? 0.0 : enrollment.toDouble(iAssignment));
549                if (request.getInitialAssignment() != null && enrollment.isCourseRequest()) {
550                    Enrollment original = request.getInitialAssignment();
551                    for (Iterator<Section> i = enrollment.getSections().iterator(); i.hasNext();) {
552                        Section section = i.next();
553                        Section originalSection = null;
554                        for (Iterator<Section> j = original.getSections().iterator(); j.hasNext();) {
555                            Section x = j.next();
556                            if (x.getSubpart().getId() == section.getSubpart().getId()) {
557                                originalSection = x;
558                                break;
559                            }
560                        }
561                        if (originalSection == null || !ToolBox.equals(section.getTime(), originalSection.getTime())
562                                || !ToolBox.equals(section.getRooms(), originalSection.getRooms()))
563                            iNrChanges++;
564                    }
565                }
566            }
567            if (iSelectedRequest != null && iSelectedSection != null) {
568                Enrollment enrollment = iAssignment.getValue(iSelectedRequest);
569                if (enrollment.getAssignments() != null && !enrollment.getAssignments().isEmpty()) {
570                    for (Iterator<Section> i = enrollment.getSections().iterator(); i.hasNext();) {
571                        Section section = i.next();
572                        if (section.getSubpart().getId() == iSelectedSection.getSubpart().getId()) {
573                            iSelectedEnrollment = section;
574                            break;
575                        }
576                        if (section.getSubpart().getConfig().getId() != iSelectedSection.getSubpart().getConfig()
577                                .getId()
578                                && section.getSubpart().getInstructionalType()
579                                        .equals(iSelectedSection.getSubpart().getInstructionalType())) {
580                            iSelectedEnrollment = section;
581                            break;
582                        }
583                    }
584                }
585            }
586            if (iSelectedEnrollment != null)
587                iSelectedEnrollmentChangeTime = !ToolBox.equals(iSelectedEnrollment.getTime(),
588                        iSelectedSection.getTime());
589            if (iSelectedRequest != null) {
590                Enrollment enrollment = iAssignment.getValue(iSelectedRequest);
591                if (enrollment.isCourseRequest() && enrollment.getAssignments() != null
592                        && !enrollment.getAssignments().isEmpty())
593                    iSelectedSections.addAll(enrollment.getSections());
594            }
595        }
596
597        /** initialization */
598        public void init() {
599            iEnrollments = new Enrollment[iStudent.getRequests().size()];
600            for (int i = 0; i < iStudent.getRequests().size(); i++) {
601                Request r = iStudent.getRequests().get(i);
602                iEnrollments[i] = iAssignment.getValue(r);
603                if (iEnrollments[i] == null) {
604                    Config c = null;
605                    if (r instanceof CourseRequest)
606                        c = ((CourseRequest) r).getCourses().get(0).getOffering().getConfigs().get(0);
607                    iEnrollments[i] = new Enrollment(r, 0, c, null, iAssignment);
608                }
609            }
610        }
611
612        /**
613         * Current assignment for the student
614         * @return schedule
615         */
616        public Enrollment[] getEnrollments() {
617            return iEnrollments;
618        }
619
620        /**
621         * Current value
622         * @return assignment value
623         */
624        public double getValue() {
625            return iValue;
626        }
627
628        /**
629         * Number of unassigned requests
630         * @return number of unassigned requests
631         */
632        public int getNrUnassigned() {
633            return iNrUnassigned;
634        }
635
636        /**
637         * Average unassigned priority
638         * @return average priority of unassinged requests
639         */
640        public double getAverageUnassignedPriority() {
641            return ((double) iUnassignedPriority) / iNrUnassigned;
642        }
643
644        /**
645         * Number of changes in this schedule (comparing to the original one)
646         * @return number of changes
647         */
648        public int getNrChanges() {
649            return iNrChanges;
650        }
651
652        /**
653         * Is the same section selected (as in the current assignment)
654         * @return true the same section is selected
655         */
656        public boolean sameSelectedSection() {
657            if (iSelectedRequest != null && iSelectedEnrollment != null) {
658                Enrollment enrollment = iAssignment.getValue(iSelectedRequest);
659                if (enrollment != null && enrollment.getAssignments().contains(iSelectedEnrollment))
660                    return true;
661                if (iSelectedEnrollmentChangeTime && iSelectedSection.getSubpart().getSections().size() > iMaxSuggestions) {
662                    Section selectedEnrollment = null;
663                    for (Iterator<Section> i = enrollment.getSections().iterator(); i.hasNext();) {
664                        Section section = i.next();
665                        if (section.getSubpart().getId() == iSelectedSection.getSubpart().getId()) {
666                            selectedEnrollment = section;
667                            break;
668                        }
669                        if (section.getSubpart().getConfig().getId() != iSelectedSection.getSubpart().getConfig().getId() &&
670                                section.getSubpart().getInstructionalType().equals(iSelectedSection.getSubpart().getInstructionalType())) {
671                            selectedEnrollment = section;
672                            break;
673                        }
674                    }
675                    if (selectedEnrollment != null && ToolBox.equals(selectedEnrollment.getTime(), iSelectedEnrollment.getTime()))
676                        return true;
677                }
678            }
679            return false;
680        }
681
682        @Override
683        public int compareTo(Suggestion suggestion) {
684            int cmp = Double.compare(getNrUnassigned(), suggestion.getNrUnassigned());
685            if (cmp != 0)
686                return cmp;
687            if (getNrUnassigned() > 0) {
688                cmp = Double.compare(suggestion.getAverageUnassignedPriority(), getAverageUnassignedPriority());
689                if (cmp != 0)
690                    return cmp;
691            }
692            
693            if (iSelectedRequest != null && iSelectedRequest instanceof CourseRequest) {
694                int s1 = 0;
695                for (Section s: iSelectedSections)
696                    if (((CourseRequest)iSelectedRequest).isSelected(s)) s1++;
697                int s2 = 0;
698                for (Section s: suggestion.iSelectedSections)
699                    if (((CourseRequest)iSelectedRequest).isSelected(s)) s2++;
700                if (s1 != s2) return (s1 > s2 ? -1 : 1);
701            }
702
703            cmp = Double.compare(getNrChanges(), suggestion.getNrChanges());
704            if (cmp != 0)
705                return cmp;
706                        
707            Iterator<Section> i1 = iSelectedSections.iterator();
708            Iterator<Section> i2 = suggestion.iSelectedSections.iterator();
709            SectionAssignmentComparator c = new SectionAssignmentComparator();
710            while (i1.hasNext() && i2.hasNext()) {
711                cmp = c.compare(i1.next(), i2.next());
712                if (cmp != 0)
713                    return cmp;
714            }
715
716            cmp = compare(iAssignment, this, suggestion);
717            if (cmp != 0)
718                return cmp;
719
720            return Double.compare(iId, suggestion.iId);
721        }
722    }
723
724    /**
725     * Enrollment comparator (used to sort enrollments in a domain).
726     * Selected sections go first.
727     */
728    public class EnrollmentSectionComparator implements Comparator<Section> {
729        /**
730         * Is section s1 parent of section s2 (or a parent of a parent...)
731         * @param s1 a section
732         * @param s2 a section
733         * @return if there is a parent-child relation between the two sections
734         */
735        public boolean isParent(Section s1, Section s2) {
736            Section p1 = s1.getParent();
737            if (p1 == null)
738                return false;
739            if (p1.equals(s2))
740                return true;
741            return isParent(p1, s2);
742        }
743
744        @Override
745        public int compare(Section a, Section b) {
746            if (iSelectedSection != null && iSelectedSection.getSubpart().getId() == a.getSubpart().getId())
747                return -1;
748            if (iSelectedSection != null && iSelectedSection.getSubpart().getId() == b.getSubpart().getId())
749                return 1;
750
751            if (isParent(a, b))
752                return 1;
753            if (isParent(b, a))
754                return -1;
755
756            int cmp = a.getSubpart().getInstructionalType().compareToIgnoreCase(b.getSubpart().getInstructionalType());
757            if (cmp != 0)
758                return cmp;
759
760            return Double.compare(a.getId(), b.getId());
761        }
762    }
763
764    /**
765     * Section comparator. Order section by time first, then by room.
766     */
767    public class SectionAssignmentComparator implements Comparator<Section> {
768        @Override
769        public int compare(Section a, Section b) {
770            TimeLocation t1 = (a == null ? null : a.getTime());
771            TimeLocation t2 = (b == null ? null : b.getTime());
772            if (t1 != null && t2 != null) {
773                for (int i = 0; i < Constants.DAY_CODES.length; i++) {
774                    if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) {
775                        if ((t2.getDayCode() & Constants.DAY_CODES[i]) == 0)
776                            return -1;
777                    } else if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) {
778                        return 1;
779                    }
780                }
781                int cmp = Double.compare(t1.getStartSlot(), t2.getStartSlot());
782                if (cmp != 0)
783                    return cmp;
784            }
785            String r1 = (a == null || a.getRooms() == null ? null : a.getRooms().toString());
786            String r2 = (b == null || b.getRooms() == null ? null : b.getRooms().toString());
787            if (r1 != null && r2 != null) {
788                int cmp = r1.compareToIgnoreCase(r2);
789                if (cmp != 0)
790                    return cmp;
791            }
792
793            return 0;
794        }
795    }
796
797    /** 
798     * Number of possible enrollments of the selected request
799     * @return number of possible enrollment of the selected request (meeting the given filter etc.)
800     */
801    public int getNrMatched() {
802        return iMatched;
803    }
804
805    /**
806     * Suggestion filter.
807     */
808    public static interface SuggestionFilter {
809        /**
810         * Match the given section 
811         * @param course given course
812         * @param section given section
813         * @return true if matching the filter (can be used)
814         */
815        public boolean match(Course course, Section section);
816    }
817
818}