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().freeTimeConflicts(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            }
235            if (iMaxSectionsWithPenalty >= 0 && sectionsWithPenalty > iMaxSectionsWithPenalty)
236                return;
237            Suggestion s = new Suggestion(requests2resolve);
238            if (iSuggestions.size() >= iMaxSuggestions && iSuggestions.last().compareTo(s) <= 0)
239                return;
240            if (iMatched != 1) {
241                for (Iterator<Suggestion> i = iSuggestions.iterator(); i.hasNext();) {
242                    Suggestion x = i.next();
243                    if (x.sameSelectedSection()) {
244                        if (x.compareTo(s) <= 0) return;
245                        i.remove();
246                    }
247                }
248            }
249            s.init();
250            iSuggestions.add(s);
251            if (iSuggestions.size() > iMaxSuggestions)
252                iSuggestions.remove(iSuggestions.last());
253            for (FreeTimeRequest ft : okFreeTimes)
254                iAssignment.unassign(0, ft);
255            return;
256        }
257        if (!canContinue(requests2resolve, idx, depth))
258            return;
259        Request request = requests2resolve.get(idx);
260        for (Enrollment enrollment : values(request)) {
261            if (!canContinueEvaluation())
262                break;
263            if (!isAllowed(enrollment))
264                continue;
265            if (enrollment.equals(iAssignment.getValue(request)))
266                continue;
267            if (enrollment.getAssignments().isEmpty() && alt)
268                continue;
269            Set<Enrollment> conflicts = iModel.conflictValues(iAssignment, enrollment);
270            if (!checkBound(requests2resolve, idx, depth, enrollment, conflicts))
271                continue;
272            Enrollment current = iAssignment.getValue(request);
273            ArrayList<Request> newVariables2resolve = new ArrayList<Request>(requests2resolve);
274            for (Iterator<Enrollment> i = conflicts.iterator(); i.hasNext();) {
275                Enrollment conflict = i.next();
276                iAssignment.unassign(0, conflict.variable());
277                if (!newVariables2resolve.contains(conflict.variable()))
278                    newVariables2resolve.add(conflict.variable());
279            }
280            if (current != null)
281                iAssignment.unassign(0, current.variable());
282            iAssignment.assign(0, enrollment);
283            if (enrollment.getAssignments().isEmpty()) {
284                if (altRequests2resolve != null && !altRequests2resolve.isEmpty()) {
285                    Suggestion lastBefore = (iSuggestions.isEmpty() ? null : iSuggestions.last());
286                    int sizeBefore = iSuggestions.size();
287                    for (Request r : altRequests2resolve) {
288                        newVariables2resolve.add(r);
289                        backtrack(newVariables2resolve, null, idx + 1, depth, true);
290                        newVariables2resolve.remove(r);
291                    }
292                    Suggestion lastAfter = (iSuggestions.isEmpty() ? null : iSuggestions.last());
293                    int sizeAfter = iSuggestions.size();
294                    // did not succeeded with an alternative -> try without it
295                    if (sizeBefore == sizeAfter && (sizeAfter < iMaxSuggestions || sizeAfter == 0 || lastAfter.compareTo(lastBefore) == 0))
296                        backtrack(newVariables2resolve, altRequests2resolve, idx + 1, depth - 1, alt);
297                } else {
298                    backtrack(newVariables2resolve, altRequests2resolve, idx + 1, depth - 1, alt);
299                }
300            } else {
301                backtrack(newVariables2resolve, altRequests2resolve, idx + 1, depth - 1, alt);
302            }
303            if (current == null)
304                iAssignment.unassign(0, request);
305            else
306                iAssignment.assign(0, current);
307            for (Iterator<Enrollment> i = conflicts.iterator(); i.hasNext();) {
308                Enrollment conflict = i.next();
309                iAssignment.assign(0, conflict);
310            }
311        }
312    }
313
314    /**
315     * Domain of a request    
316     * @param request given request
317     * @return possible enrollments (meeting the filter etc)
318     */
319    protected List<Enrollment> values(final Request request) {
320        if (!request.getStudent().canAssign(iAssignment, request))
321            return new ArrayList<Enrollment>();
322        List<Enrollment> values = iValues.get(request);
323        if (values != null)
324            return values;
325        if (request instanceof CourseRequest) {
326            CourseRequest cr = (CourseRequest) request;
327            values = (cr.equals(iSelectedRequest) ? cr.getAvaiableEnrollments(iAssignment) : cr.getAvaiableEnrollmentsSkipSameTime(iAssignment));
328            Collections.sort(values, new Comparator<Enrollment>() {
329                @Override
330                public int compare(Enrollment e1, Enrollment e2) {
331                    return iComparator.compare(iAssignment, e1, e2);
332                }
333            });
334        } else {
335            values = new ArrayList<Enrollment>();
336            values.add(((FreeTimeRequest) request).createEnrollment());
337        }
338        if (canLeaveUnassigned(request)) {
339            Config config = null;
340            if (request instanceof CourseRequest)
341                config = ((CourseRequest) request).getCourses().get(0).getOffering().getConfigs().get(0);
342            values.add(new Enrollment(request, 0, config, new HashSet<Section>(), iAssignment));
343        }
344        iValues.put(request, values);
345        if (request.equals(iSelectedRequest) && iFilter != null && request instanceof CourseRequest) {
346            for (Iterator<Enrollment> i = values.iterator(); i.hasNext();) {
347                Enrollment enrollment = i.next();
348                if (enrollment.getAssignments() != null && !enrollment.getAssignments().isEmpty()) {
349                    boolean match = false;
350                    for (Iterator<Section> j = enrollment.getSections().iterator(); j.hasNext();) {
351                        Section section = j.next();
352                        if (iSelectedSection != null) {
353                            if (section.getSubpart().getId() == iSelectedSection.getSubpart().getId()) {
354                                if (iFilter.match(enrollment.getCourse(), section)) {
355                                    match = true;
356                                    break;
357                                }
358                            }
359                            if (section.getSubpart().getConfig().getId() != iSelectedSection.getSubpart().getConfig().getId() &&
360                                    section.getSubpart().getInstructionalType().equals(iSelectedSection.getSubpart().getInstructionalType())) {
361                                if (iFilter.match(enrollment.getCourse(), section)) {
362                                    match = true;
363                                    break;
364                                }
365                            }
366                        } else {
367                            if (iFilter.match(enrollment.getCourse(), section)) {
368                                match = true;
369                                break;
370                            }
371                        }
372                    }
373                    if (!match)
374                        i.remove();
375                }
376            }
377        }
378        if (request.equals(iSelectedRequest))
379            iMatched = values.size();
380        return values;
381    }
382
383    /**
384     * Termination criterion
385     * @param requests2resolve request to resolve
386     * @param idx current depth
387     * @param depth remaining depth
388     * @return true if the search can continue
389     */
390    protected boolean canContinue(ArrayList<Request> requests2resolve, int idx, int depth) {
391        if (depth <= 0)
392            return false;
393        if (iTimeoutReached)
394            return false;
395        return true;
396    }
397
398    /**
399     * Can continue evaluation of possible enrollments
400     * @return false if the timeout was reached
401     */
402    protected boolean canContinueEvaluation() {
403        return !iTimeoutReached;
404    }
405
406    /**
407     * Check bound
408     * @param requests2resolve requests to resolve
409     * @param idx current depth
410     * @param depth remaining depth
411     * @param value enrollment in question
412     * @param conflicts conflicting enrollments
413     * @return false if the branch can be cut
414     */
415    protected boolean checkBound(ArrayList<Request> requests2resolve, int idx, int depth, Enrollment value,
416            Set<Enrollment> conflicts) {
417        if (idx > 0 && !conflicts.isEmpty())
418            return false;
419        int nrUnassigned = requests2resolve.size() - idx;
420        if ((nrUnassigned + conflicts.size() > depth)) {
421            return false;
422        }
423        for (Enrollment conflict : conflicts) {
424            int confIdx = requests2resolve.indexOf(conflict.variable());
425            if (confIdx >= 0 && confIdx <= idx)
426                return false;
427        }
428        if (iMaxSectionsWithPenalty >= 0) {
429            double sectionsWithPenalty = 0;
430            for (Request r : iStudent.getRequests()) {
431                Enrollment e = iAssignment.getValue(r);
432                if (r.equals(value.variable())) {
433                    e = value;
434                } else if (conflicts.contains(e)) {
435                    e = null;
436                }
437                if (e != null && e.isCourseRequest()) {
438                    for (Section s : e.getSections())
439                        sectionsWithPenalty += iModel.getOverExpected(iAssignment, s, r);
440                }
441            }
442            if (sectionsWithPenalty > iMaxSectionsWithPenalty)
443                return false;
444        }
445        return true;
446    }
447
448    /**
449     * Check required sections
450     * @param enrollment given enrollment
451     * @return true if  the given enrollment allowed
452     */
453    public boolean isAllowed(Enrollment enrollment) {
454        if (iRequiredSections != null && enrollment.getRequest() instanceof CourseRequest) {
455            // Obey required sections
456            Set<Section> required = iRequiredSections.get(enrollment.getRequest());
457            if (required != null && !required.isEmpty()) {
458                if (enrollment.getAssignments() == null)
459                    return false;
460                for (Section r : required)
461                    if (!enrollment.getAssignments().contains(r))
462                        return false;
463            }
464        }
465        if (enrollment.getRequest().equals(iSelectedRequest)) {
466            // Selected request must be assigned
467            if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty())
468                return false;
469            // Selected section must be assigned differently
470            if (iSelectedSection != null && enrollment.getAssignments().contains(iSelectedSection))
471                return false;
472        }
473        return true;
474    }
475
476    /**
477     * Can this request be left unassigned
478     * @param request given request
479     * @return true if can be left unassigned (there is no requirement)
480     */
481    public boolean canLeaveUnassigned(Request request) {
482        if (request instanceof CourseRequest) {
483            if (iRequiredSections != null) {
484                // Request with required section must be assigned
485                Set<Section> required = iRequiredSections.get(request);
486                if (required != null && !required.isEmpty())
487                    return false;
488            }
489        } else {
490            // Free time is required
491            if (iRequiredFreeTimes.contains(request))
492                return false;
493        }
494        // Selected request must be assigned
495        if (request.equals(iSelectedRequest))
496            return false;
497        return true;
498    }
499
500    /**
501     * Compare two suggestions
502     * @param assignment current assignment
503     * @param s1 first suggestion
504     * @param s2 second suggestion
505     * @return true if s1 is better than s2
506     */
507    protected int compare(Assignment<Request, Enrollment> assignment, Suggestion s1, Suggestion s2) {
508        return Double.compare(s1.getValue(), s2.getValue());
509    }
510
511    /**
512     * Suggestion
513     */
514    public class Suggestion implements Comparable<Suggestion> {
515        private double iValue = 0.0;
516        private int iNrUnassigned = 0;
517        private int iUnassignedPriority = 0;
518        private int iNrChanges = 0;
519
520        private long iId = iLastSuggestionId++;
521        private Enrollment[] iEnrollments;
522        private Section iSelectedEnrollment = null;
523        private boolean iSelectedEnrollmentChangeTime = false;
524        private TreeSet<Section> iSelectedSections = new TreeSet<Section>(new EnrollmentSectionComparator());
525
526        /**
527         * Create suggestion
528         * @param resolvedRequests assigned requests
529         */
530        public Suggestion(ArrayList<Request> resolvedRequests) {
531            for (Request request : resolvedRequests) {
532                Enrollment enrollment = iAssignment.getValue(request);
533                if (enrollment.getAssignments().isEmpty()) {
534                    iNrUnassigned++;
535                    iUnassignedPriority += request.getPriority();
536                }
537                iValue += (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty() ? 0.0 : enrollment.toDouble(iAssignment));
538                if (request.getInitialAssignment() != null && enrollment.isCourseRequest()) {
539                    Enrollment original = request.getInitialAssignment();
540                    for (Iterator<Section> i = enrollment.getSections().iterator(); i.hasNext();) {
541                        Section section = i.next();
542                        Section originalSection = null;
543                        for (Iterator<Section> j = original.getSections().iterator(); j.hasNext();) {
544                            Section x = j.next();
545                            if (x.getSubpart().getId() == section.getSubpart().getId()) {
546                                originalSection = x;
547                                break;
548                            }
549                        }
550                        if (originalSection == null || !ToolBox.equals(section.getTime(), originalSection.getTime())
551                                || !ToolBox.equals(section.getRooms(), originalSection.getRooms()))
552                            iNrChanges++;
553                    }
554                }
555            }
556            if (iSelectedRequest != null && iSelectedSection != null) {
557                Enrollment enrollment = iAssignment.getValue(iSelectedRequest);
558                if (enrollment.getAssignments() != null && !enrollment.getAssignments().isEmpty()) {
559                    for (Iterator<Section> i = enrollment.getSections().iterator(); i.hasNext();) {
560                        Section section = i.next();
561                        if (section.getSubpart().getId() == iSelectedSection.getSubpart().getId()) {
562                            iSelectedEnrollment = section;
563                            break;
564                        }
565                        if (section.getSubpart().getConfig().getId() != iSelectedSection.getSubpart().getConfig()
566                                .getId()
567                                && section.getSubpart().getInstructionalType()
568                                        .equals(iSelectedSection.getSubpart().getInstructionalType())) {
569                            iSelectedEnrollment = section;
570                            break;
571                        }
572                    }
573                }
574            }
575            if (iSelectedEnrollment != null)
576                iSelectedEnrollmentChangeTime = !ToolBox.equals(iSelectedEnrollment.getTime(),
577                        iSelectedSection.getTime());
578            if (iSelectedRequest != null) {
579                Enrollment enrollment = iAssignment.getValue(iSelectedRequest);
580                if (enrollment.isCourseRequest() && enrollment.getAssignments() != null
581                        && !enrollment.getAssignments().isEmpty())
582                    iSelectedSections.addAll(enrollment.getSections());
583            }
584        }
585
586        /** initialization */
587        public void init() {
588            iEnrollments = new Enrollment[iStudent.getRequests().size()];
589            for (int i = 0; i < iStudent.getRequests().size(); i++) {
590                Request r = iStudent.getRequests().get(i);
591                iEnrollments[i] = iAssignment.getValue(r);
592                if (iEnrollments[i] == null) {
593                    Config c = null;
594                    if (r instanceof CourseRequest)
595                        c = ((CourseRequest) r).getCourses().get(0).getOffering().getConfigs().get(0);
596                    iEnrollments[i] = new Enrollment(r, 0, c, null, iAssignment);
597                }
598            }
599        }
600
601        /**
602         * Current assignment for the student
603         * @return schedule
604         */
605        public Enrollment[] getEnrollments() {
606            return iEnrollments;
607        }
608
609        /**
610         * Current value
611         * @return assignment value
612         */
613        public double getValue() {
614            return iValue;
615        }
616
617        /**
618         * Number of unassigned requests
619         * @return number of unassigned requests
620         */
621        public int getNrUnassigned() {
622            return iNrUnassigned;
623        }
624
625        /**
626         * Average unassigned priority
627         * @return average priority of unassinged requests
628         */
629        public double getAverageUnassignedPriority() {
630            return ((double) iUnassignedPriority) / iNrUnassigned;
631        }
632
633        /**
634         * Number of changes in this schedule (comparing to the original one)
635         * @return number of changes
636         */
637        public int getNrChanges() {
638            return iNrChanges;
639        }
640
641        /**
642         * Is the same section selected (as in the current assignment)
643         * @return true the same section is selected
644         */
645        public boolean sameSelectedSection() {
646            if (iSelectedRequest != null && iSelectedEnrollment != null) {
647                Enrollment enrollment = iAssignment.getValue(iSelectedRequest);
648                if (enrollment != null && enrollment.getAssignments().contains(iSelectedEnrollment))
649                    return true;
650                if (iSelectedEnrollmentChangeTime && iSelectedSection.getSubpart().getSections().size() > iMaxSuggestions) {
651                    Section selectedEnrollment = null;
652                    for (Iterator<Section> i = enrollment.getSections().iterator(); i.hasNext();) {
653                        Section section = i.next();
654                        if (section.getSubpart().getId() == iSelectedSection.getSubpart().getId()) {
655                            selectedEnrollment = section;
656                            break;
657                        }
658                        if (section.getSubpart().getConfig().getId() != iSelectedSection.getSubpart().getConfig().getId() &&
659                                section.getSubpart().getInstructionalType().equals(iSelectedSection.getSubpart().getInstructionalType())) {
660                            selectedEnrollment = section;
661                            break;
662                        }
663                    }
664                    if (selectedEnrollment != null && ToolBox.equals(selectedEnrollment.getTime(), iSelectedEnrollment.getTime()))
665                        return true;
666                }
667            }
668            return false;
669        }
670
671        @Override
672        public int compareTo(Suggestion suggestion) {
673            int cmp = Double.compare(getNrUnassigned(), suggestion.getNrUnassigned());
674            if (cmp != 0)
675                return cmp;
676            if (getNrUnassigned() > 0) {
677                cmp = Double.compare(suggestion.getAverageUnassignedPriority(), getAverageUnassignedPriority());
678                if (cmp != 0)
679                    return cmp;
680            }
681            cmp = Double.compare(getNrChanges(), suggestion.getNrChanges());
682            if (cmp != 0)
683                return cmp;
684
685            Iterator<Section> i1 = iSelectedSections.iterator();
686            Iterator<Section> i2 = suggestion.iSelectedSections.iterator();
687            SectionAssignmentComparator c = new SectionAssignmentComparator();
688            while (i1.hasNext() && i2.hasNext()) {
689                cmp = c.compare(i1.next(), i2.next());
690                if (cmp != 0)
691                    return cmp;
692            }
693
694            cmp = compare(iAssignment, this, suggestion);
695            if (cmp != 0)
696                return cmp;
697
698            return Double.compare(iId, suggestion.iId);
699        }
700    }
701
702    /**
703     * Enrollment comparator (used to sort enrollments in a domain).
704     * Selected sections go first.
705     */
706    public class EnrollmentSectionComparator implements Comparator<Section> {
707        /**
708         * Is section s1 parent of section s2 (or a parent of a parent...)
709         * @param s1 a section
710         * @param s2 a section
711         * @return if there is a parent-child relation between the two sections
712         */
713        public boolean isParent(Section s1, Section s2) {
714            Section p1 = s1.getParent();
715            if (p1 == null)
716                return false;
717            if (p1.equals(s2))
718                return true;
719            return isParent(p1, s2);
720        }
721
722        @Override
723        public int compare(Section a, Section b) {
724            if (iSelectedSection != null && iSelectedSection.getSubpart().getId() == a.getSubpart().getId())
725                return -1;
726            if (iSelectedSection != null && iSelectedSection.getSubpart().getId() == b.getSubpart().getId())
727                return 1;
728
729            if (isParent(a, b))
730                return 1;
731            if (isParent(b, a))
732                return -1;
733
734            int cmp = a.getSubpart().getInstructionalType().compareToIgnoreCase(b.getSubpart().getInstructionalType());
735            if (cmp != 0)
736                return cmp;
737
738            return Double.compare(a.getId(), b.getId());
739        }
740    }
741
742    /**
743     * Section comparator. Order section by time first, then by room.
744     */
745    public class SectionAssignmentComparator implements Comparator<Section> {
746        @Override
747        public int compare(Section a, Section b) {
748            TimeLocation t1 = (a == null ? null : a.getTime());
749            TimeLocation t2 = (b == null ? null : b.getTime());
750            if (t1 != null && t2 != null) {
751                for (int i = 0; i < Constants.DAY_CODES.length; i++) {
752                    if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) {
753                        if ((t2.getDayCode() & Constants.DAY_CODES[i]) == 0)
754                            return -1;
755                    } else if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) {
756                        return 1;
757                    }
758                }
759                int cmp = Double.compare(t1.getStartSlot(), t2.getStartSlot());
760                if (cmp != 0)
761                    return cmp;
762            }
763            String r1 = (a == null || a.getRooms() == null ? null : a.getRooms().toString());
764            String r2 = (b == null || b.getRooms() == null ? null : b.getRooms().toString());
765            if (r1 != null && r2 != null) {
766                int cmp = r1.compareToIgnoreCase(r2);
767                if (cmp != 0)
768                    return cmp;
769            }
770
771            return 0;
772        }
773    }
774
775    /** 
776     * Number of possible enrollments of the selected request
777     * @return number of possible enrollment of the selected request (meeting the given filter etc.)
778     */
779    public int getNrMatched() {
780        return iMatched;
781    }
782
783    /**
784     * Suggestion filter.
785     */
786    public static interface SuggestionFilter {
787        /**
788         * Match the given section 
789         * @param course given course
790         * @param section given section
791         * @return true if matching the filter (can be used)
792         */
793        public boolean match(Course course, Section section);
794    }
795
796}