    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 Tomáš Müller<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                    if (iModel.getStudentQuality() != null)
    120                        value = iModel.getStudentWeights().getWeight(iAssignment, e, iModel.getStudentQuality().conflicts(e));
    121                    else
    122                        value = iModel.getStudentWeights().getWeight(iAssignment, e,
    123                                (iModel.getDistanceConflict() == null ? null : iModel.getDistanceConflict().conflicts(e)),
    124                                (iModel.getTimeOverlaps() == null ? null : iModel.getTimeOverlaps().conflicts(e)));
    125                    iValues.put(e, value);
    126                }
    127                return value;
    128            }
    129
    130            @Override
    131            public int compare(Assignment<Request, Enrollment> a, Enrollment e1, Enrollment e2) {
    132                return value(e2).compareTo(value(e1));
    133            }
    134        };
    135    }
    136
    137    /**
    138     * Return search time
    139     * @return search time
    140     */
    141    public long getTime() {
    142        return iT1 - iT0;
    143    }
    144
    145    /**
    146     * Was time limit reached
    147     * @return true if reached
    148     */
    149    public boolean isTimeoutReached() {
    150        return iTimeoutReached;
    151    }
    152
    153    /**
    154     * Number of possible suggestions visited
    155     * @return a number of solutions seen
    156     */
    157    public int getNrSolutionsSeen() {
    158        return iNrSolutionsSeen;
    159    }
    160
    161    /**
    162     * Perform the search
    163     * @return an ordered set of possible suggestions
    164     */
    165    public TreeSet<Suggestion> computeSuggestions() {
    166        iT0 = System.currentTimeMillis();
    167        iTimeoutReached = false;
    168        iNrSolutionsSeen = 0;
    169        iSuggestions.clear();
    170
    171        ArrayList<Request> requests2resolve = new ArrayList<Request>();
    172        requests2resolve.add(iSelectedRequest);
    173        TreeSet<Request> altRequests2resolve = new TreeSet<Request>();
    174
    175        for (Map.Entry<CourseRequest, Set<Section>> entry : iPreferredSections.entrySet()) {
    176            CourseRequest request = entry.getKey();
    177            Set<Section> sections = entry.getValue();
    178            if (!sections.isEmpty() && sections.size() == sections.iterator().next().getSubpart().getConfig().getSubparts().size())
    179                iAssignment.assign(0, request.createEnrollment(iAssignment, sections));
    180            else if (!request.equals(iSelectedRequest)) {
    181                if (sections.isEmpty())
    182                    altRequests2resolve.add(request);
    183                else
    184                    requests2resolve.add(request);
    185            }
    186        }
    187
    188        for (Request request : iStudent.getRequests()) {
    189            if (iAssignment.getValue(request) == null && request instanceof FreeTimeRequest) {
    190                FreeTimeRequest ft = (FreeTimeRequest) request;
    191                Enrollment enrollment = ft.createEnrollment();
    192                if (iModel.conflictValues(iAssignment, enrollment).isEmpty())
    193                    iAssignment.assign(0, enrollment);
    194            }
    195        }
    196
    197        for (Request request : iStudent.getRequests()) {
    198            request.setInitialAssignment(iAssignment.getValue(request));
    199        }
    200
    201        backtrack(requests2resolve, altRequests2resolve, 0, iMaxDepth, false);
    202
    203        iT1 = System.currentTimeMillis();
    204        return iSuggestions;
    205    }
    206
    207    /**
    208     * Main branch and bound rutine
    209     * @param requests2resolve remaining requests to assign
    210     * @param altRequests2resolve alternative requests to assign
    211     * @param idx current depth
    212     * @param depth remaining depth
    213     * @param alt can leave a request unassigned
    214     */
    215    protected void backtrack(ArrayList<Request> requests2resolve, TreeSet<Request> altRequests2resolve, int idx,
    216            int depth, boolean alt) {
    217        if (!iTimeoutReached && iTimeout > 0 && System.currentTimeMillis() - iT0 > iTimeout)
    218            iTimeoutReached = true;
    219        int nrUnassigned = requests2resolve.size() - idx;
    220        if (nrUnassigned == 0) {
    221            List<FreeTimeRequest> okFreeTimes = new ArrayList<FreeTimeRequest>();
    222            double sectionsWithPenalty = 0;
    223            for (Request r : iStudent.getRequests()) {
    224                Enrollment e = iAssignment.getValue(r);
    225                if (iMaxSectionsWithPenalty >= 0 && e != null && r instanceof CourseRequest) {
    226                    for (Section s : e.getSections())
    227                        sectionsWithPenalty += iModel.getOverExpected(iAssignment, s, r);
    228                }
    229                if (e == null && r instanceof FreeTimeRequest) {
    230                    FreeTimeRequest ft = (FreeTimeRequest) r;
    231                    Enrollment enrollment = ft.createEnrollment();
    232                    if (iModel.conflictValues(iAssignment, enrollment).isEmpty()) {
    233                        iAssignment.assign(0, enrollment);
    234                        okFreeTimes.add(ft);
    235                    }
    236                }
    237                if (e != null && e.isCourseRequest() && e.getSections().isEmpty()) {
    238                    Double minPenalty = null;
    239                    for (Enrollment other : values(e.getRequest())) {
    240                        if (!isAllowed(other)) continue;
    241                        if (e.equals(other)) continue;
    242                        double penalty = 0.0;
    243                        for (Section s: other.getSections())
    244                            penalty += iModel.getOverExpected(iAssignment, s, other.getRequest());
    245                        if (minPenalty == null || minPenalty > penalty) minPenalty = penalty;
    246                        if (minPenalty == 0.0) break;
    247                    }
    248                    if (minPenalty != null) sectionsWithPenalty += minPenalty;
    249                }
    250            }
    251            if (iMaxSectionsWithPenalty >= 0 && sectionsWithPenalty > iMaxSectionsWithPenalty)
    252                return;
    253            Suggestion s = new Suggestion(requests2resolve);
    254            if (iSuggestions.size() >= iMaxSuggestions && iSuggestions.last().compareTo(s) <= 0)
    255                return;
    256            if (iMatched != 1) {
    257                for (Iterator<Suggestion> i = iSuggestions.iterator(); i.hasNext();) {
    258                    Suggestion x = i.next();
    259                    if (x.sameSelectedSection()) {
    260                        if (x.compareTo(s) <= 0) return;
    261                        i.remove();
    262                    }
    263                }
    264            }
    265            s.init();
    266            iSuggestions.add(s);
    267            if (iSuggestions.size() > iMaxSuggestions)
    268                iSuggestions.remove(iSuggestions.last());
    269            for (FreeTimeRequest ft : okFreeTimes)
    270                iAssignment.unassign(0, ft);
    271            return;
    272        }
    273        if (!canContinue(requests2resolve, idx, depth))
    274            return;
    275        Request request = requests2resolve.get(idx);
    276        for (Enrollment enrollment : values(request)) {
    277            if (!canContinueEvaluation())
    278                break;
    279            if (!isAllowed(enrollment))
    280                continue;
    281            if (enrollment.equals(iAssignment.getValue(request)))
    282                continue;
    283            if (enrollment.getAssignments().isEmpty() && alt)
    284                continue;
    285            Set<Enrollment> conflicts = iModel.conflictValues(iAssignment, enrollment);
    286            if (!checkBound(requests2resolve, idx, depth, enrollment, conflicts))
    287                continue;
    288            Enrollment current = iAssignment.getValue(request);
    289            ArrayList<Request> newVariables2resolve = new ArrayList<Request>(requests2resolve);
    290            for (Iterator<Enrollment> i = conflicts.iterator(); i.hasNext();) {
    291                Enrollment conflict = i.next();
    292                iAssignment.unassign(0, conflict.variable());
    293                if (!newVariables2resolve.contains(conflict.variable()))
    294                    newVariables2resolve.add(conflict.variable());
    295            }
    296            if (current != null)
    297                iAssignment.unassign(0, current.variable());
    298            iAssignment.assign(0, enrollment);
    299            if (enrollment.getAssignments().isEmpty()) {
    300                if (altRequests2resolve != null && !altRequests2resolve.isEmpty()) {
    301                    Suggestion lastBefore = (iSuggestions.isEmpty() ? null : iSuggestions.last());
    302                    int sizeBefore = iSuggestions.size();
    303                    for (Request r : altRequests2resolve) {
    304                        newVariables2resolve.add(r);
    305                        backtrack(newVariables2resolve, null, idx + 1, depth, true);
    306                        newVariables2resolve.remove(r);
    307                    }
    308                    Suggestion lastAfter = (iSuggestions.isEmpty() ? null : iSuggestions.last());
    309                    int sizeAfter = iSuggestions.size();
    310                    // did not succeeded with an alternative -> try without it
    311                    if (sizeBefore == sizeAfter && (sizeAfter < iMaxSuggestions || sizeAfter == 0 || lastAfter.compareTo(lastBefore) == 0))
    312                        backtrack(newVariables2resolve, altRequests2resolve, idx + 1, depth - 1, alt);
    313                } else {
    314                    backtrack(newVariables2resolve, altRequests2resolve, idx + 1, depth - 1, alt);
    315                }
    316            } else {
    317                backtrack(newVariables2resolve, altRequests2resolve, idx + 1, depth - 1, alt);
    318            }
    319            if (current == null)
    320                iAssignment.unassign(0, request);
    321            else
    322                iAssignment.assign(0, current);
    323            for (Iterator<Enrollment> i = conflicts.iterator(); i.hasNext();) {
    324                Enrollment conflict = i.next();
    325                iAssignment.assign(0, conflict);
    326            }
    327        }
    328    }
    329
    330    /**
    331     * Domain of a request
    332     * @param request given request
    333     * @return possible enrollments (meeting the filter etc)
    334     */
    335    protected List<Enrollment> values(final Request request) {
    336        if (!request.equals(iSelectedRequest) && !request.getStudent().canAssign(iAssignment, request)) {
    337            if (canLeaveUnassigned(request)) {
    338                List<Enrollment> values = new ArrayList<Enrollment>();
    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                return values;
    344            }
    345            return new ArrayList<Enrollment>();
    346        }
    347        List<Enrollment> values = iValues.get(request);
    348        if (values != null)
    349            return values;
    350        if (request instanceof CourseRequest) {
    351            CourseRequest cr = (CourseRequest) request;
    352            values = (cr.equals(iSelectedRequest) ? cr.getAvaiableEnrollments(iAssignment) : cr.getAvaiableEnrollmentsSkipSameTime(iAssignment));
    353            if (cr.equals(iSelectedRequest)) {
    354                Collections.sort(values, new Comparator<Enrollment>() {
    355                    @Override
    356                    public int compare(Enrollment e1, Enrollment e2) {
    357                        int s1 = 0;
    358                        for (Section s: e1.getSections())
    359                            if (((CourseRequest)iSelectedRequest).isSelected(s)) s1++;
    360                        int s2 = 0;
    361                        for (Section s: e2.getSections())
    362                            if (((CourseRequest)iSelectedRequest).isSelected(s)) s2++;
    363                        if (s1 != s2) return (s1 > s2 ? -1 : 1);
    364
    365                        if (e1.getRequest().getInitialAssignment() != null) {
    366                            Enrollment original = e1.getRequest().getInitialAssignment();
    367                            int x1 = 0;
    368                            if (original.getCourse().equals(e1.getCourse())) x1 += 100;
    369                            if (original.getConfig().equals(e1.getConfig())) {
    370                                x1 += 10;
    371                                for (Section section: original.getSections()) {
    372                                    for (Section s: e1.getSections()) {
    373                                        if (s.getSubpart().getId() == section.getSubpart().getId()) {
    374                                            if (ToolBox.equals(section.getTime(), s.getTime()) && ToolBox.equals(section.getRooms(), s.getRooms()))
    375                                                x1 ++;
    376                                            break;
    377                                        }
    378                                    }
    379                                }
    380                            }
    381                            int x2 = 0;
    382                            if (original.getCourse().equals(e2.getCourse())) x2 += 100;
    383                            if (original.getConfig().equals(e2.getConfig())) {
    384                                x2 += 10;
    385                                for (Section section: original.getSections()) {
    386                                    for (Section s: e2.getSections()) {
    387                                        if (s.getSubpart().getId() == section.getSubpart().getId()) {
    388                                            if (ToolBox.equals(section.getTime(), s.getTime()) && ToolBox.equals(section.getRooms(), s.getRooms()))
    389                                                x2 ++;
    390                                            break;
    391                                        }
    392                                    }
    393                                }
    394                            }
    395                            if (x1 != x2) {
    396                                return (x1 > x2 ? -1 : 1);
    397                            }
    398                        }
    399
    400                        return iComparator.compare(iAssignment, e1, e2);
    401                    }
    402                });
    403            } else {
    404                Collections.sort(values, new Comparator<Enrollment>() {
    405                    @Override
    406                    public int compare(Enrollment e1, Enrollment e2) {
    407                        return iComparator.compare(iAssignment, e1, e2);
    408                    }
    409                });
    410            }
    411        } else {
    412            values = new ArrayList<Enrollment>();
    413            values.add(((FreeTimeRequest) request).createEnrollment());
    414        }
    415        if (canLeaveUnassigned(request)) {
    416            Config config = null;
    417            if (request instanceof CourseRequest)
    418                config = ((CourseRequest) request).getCourses().get(0).getOffering().getConfigs().get(0);
    419            values.add(new Enrollment(request, 0, config, new HashSet<Section>(), iAssignment));
    420        }
    421        iValues.put(request, values);
    422        if (request.equals(iSelectedRequest) && iFilter != null && request instanceof CourseRequest) {
    423            for (Iterator<Enrollment> i = values.iterator(); i.hasNext();) {
    424                Enrollment enrollment = i.next();
    425                if (enrollment.getAssignments() != null && !enrollment.getAssignments().isEmpty()) {
    426                    boolean match = false;
    427                    for (Iterator<Section> j = enrollment.getSections().iterator(); j.hasNext();) {
    428                        Section section = j.next();
    429                        if (iSelectedSection != null) {
    430                            if (section.getSubpart().getId() == iSelectedSection.getSubpart().getId()) {
    431                                if (iFilter.match(enrollment.getCourse(), section)) {
    432                                    match = true;
    433                                    break;
    434                                }
    435                            }
    436                            if (section.getSubpart().getConfig().getId() != iSelectedSection.getSubpart().getConfig().getId() &&
    437                                    section.getSubpart().getInstructionalType().equals(iSelectedSection.getSubpart().getInstructionalType())) {
    438                                if (iFilter.match(enrollment.getCourse(), section)) {
    439                                    match = true;
    440                                    break;
    441                                }
    442                            }
    443                        } else {
    444                            if (iFilter.match(enrollment.getCourse(), section)) {
    445                                match = true;
    446                                break;
    447                            }
    448                        }
    449                    }
    450                    if (!match)
    451                        i.remove();
    452                }
    453            }
    454        }
    455        if (request.equals(iSelectedRequest))
    456            iMatched = values.size();
    457        return values;
    458    }
    459
    460    /**
    461     * Termination criterion
    462     * @param requests2resolve request to resolve
    463     * @param idx current depth
    464     * @param depth remaining depth
    465     * @return true if the search can continue
    466     */
    467    protected boolean canContinue(ArrayList<Request> requests2resolve, int idx, int depth) {
    468        if (depth <= 0)
    469            return false;
    470        if (iTimeoutReached)
    471            return false;
    472        return true;
    473    }
    474
    475    /**
    476     * Can continue evaluation of possible enrollments
    477     * @return false if the timeout was reached
    478     */
    479    protected boolean canContinueEvaluation() {
    480        return !iTimeoutReached;
    481    }
    482
    483    /**
    484     * Check bound
    485     * @param requests2resolve requests to resolve
    486     * @param idx current depth
    487     * @param depth remaining depth
    488     * @param value enrollment in question
    489     * @param conflicts conflicting enrollments
    490     * @return false if the branch can be cut
    491     */
    492    protected boolean checkBound(ArrayList<Request> requests2resolve, int idx, int depth, Enrollment value,
    493            Set<Enrollment> conflicts) {
    494        if (iMaxSectionsWithPenalty < 0.0 && idx > 0 && !conflicts.isEmpty()) return false;
    495        int nrUnassigned = requests2resolve.size() - idx;
    496        if ((nrUnassigned + conflicts.size() > depth)) {
    497            return false;
    498        }
    499        for (Enrollment conflict : conflicts) {
    500            int confIdx = requests2resolve.indexOf(conflict.variable());
    501            if (confIdx >= 0 && confIdx <= idx)
    502                return false;
    503        }
    504        if (iMaxSectionsWithPenalty >= 0) {
    505            double sectionsWithPenalty = 0;
    506            for (Request r : iStudent.getRequests()) {
    507                Enrollment e = iAssignment.getValue(r);
    508                if (r.equals(value.variable())) {
    509                    e = value;
    510                } else if (conflicts.contains(e)) {
    511                    e = null;
    512                }
    513                if (e != null && e.isCourseRequest()) {
    514                    sectionsWithPenalty += iModel.getOverExpected(iAssignment, e, value, conflicts);
    515                }
    516            }
    517            if (sectionsWithPenalty > iMaxSectionsWithPenalty)
    518                return false;
    519        }
    520        return true;
    521    }
    522
    523    /**
    524     * Check required sections
    525     * @param enrollment given enrollment
    526     * @return true if  the given enrollment allowed
    527     */
    528    public boolean isAllowed(Enrollment enrollment) {
    529        if (iRequiredSections != null && enrollment.getRequest() instanceof CourseRequest) {
    530            // Obey required sections
    531            Set<Section> required = iRequiredSections.get(enrollment.getRequest());
    532            if (required != null && !required.isEmpty()) {
    533                if (enrollment.getAssignments() == null)
    534                    return false;
    535                for (Section r : required)
    536                    if (!enrollment.getAssignments().contains(r))
    537                        return false;
    538            }
    539        }
    540        if (enrollment.getRequest().equals(iSelectedRequest)) {
    541            // Selected request must be assigned
    542            if (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty())
    543                return false;
    544            // Selected section must be assigned differently
    545            if (iSelectedSection != null && enrollment.getAssignments().contains(iSelectedSection))
    546                return false;
    547        }
    548        return true;
    549    }
    550
    551    /**
    552     * Can this request be left unassigned
    553     * @param request given request
    554     * @return true if can be left unassigned (there is no requirement)
    555     */
    556    public boolean canLeaveUnassigned(Request request) {
    557        if (request instanceof CourseRequest) {
    558            if (iRequiredSections != null) {
    559                // Request with required section must be assigned
    560                Set<Section> required = iRequiredSections.get(request);
    561                if (required != null && !required.isEmpty())
    562                    return false;
    563            }
    564        } else {
    565            // Free time is required
    566            if (iRequiredFreeTimes.contains(request))
    567                return false;
    568        }
    569        // Selected request must be assigned
    570        if (request.equals(iSelectedRequest))
    571            return false;
    572        return true;
    573    }
    574
    575    /**
    576     * Compare two suggestions
    577     * @param assignment current assignment
    578     * @param s1 first suggestion
    579     * @param s2 second suggestion
    580     * @return true if s1 is better than s2
    581     */
    582    protected int compare(Assignment<Request, Enrollment> assignment, Suggestion s1, Suggestion s2) {
    583        return Double.compare(s1.getValue(), s2.getValue());
    584    }
    585
    586    /**
    587     * Suggestion
    588     */
    589    public class Suggestion implements Comparable<Suggestion> {
    590        private double iValue = 0.0;
    591        private int iNrUnassigned = 0;
    592        private int iUnassignedPriority = 0;
    593        private int iNrChanges = 0;
    594
    595        private long iId = iLastSuggestionId++;
    596        private Enrollment[] iEnrollments;
    597        private Section iSelectedEnrollment = null;
    598        private boolean iSelectedEnrollmentChangeTime = false;
    599        private TreeSet<Section> iSelectedSections = new TreeSet<Section>(new EnrollmentSectionComparator());
    600        private int iSelectedChoice = 0;
    601
    602        /**
    603         * Create suggestion
    604         * @param resolvedRequests assigned requests
    605         */
    606        public Suggestion(ArrayList<Request> resolvedRequests) {
    607            for (Request request : resolvedRequests) {
    608                Enrollment enrollment = iAssignment.getValue(request);
    609                if (enrollment.getAssignments().isEmpty()) {
    610                    iNrUnassigned++;
    611                    iUnassignedPriority += request.getPriority();
    612                }
    613                iValue += (enrollment.getAssignments() == null || enrollment.getAssignments().isEmpty() ? 0.0 : enrollment.toDouble(iAssignment, false));
    614                if (request.getInitialAssignment() != null && enrollment.isCourseRequest()) {
    615                    Enrollment original = request.getInitialAssignment();
    616                    for (Iterator<Section> i = enrollment.getSections().iterator(); i.hasNext();) {
    617                        Section section = i.next();
    618                        Section originalSection = null;
    619                        for (Iterator<Section> j = original.getSections().iterator(); j.hasNext();) {
    620                            Section x = j.next();
    621                            if (x.getSubpart().getId() == section.getSubpart().getId()) {
    622                                originalSection = x;
    623                                break;
    624                            }
    625                        }
    626                        if (originalSection == null || !ToolBox.equals(section.getTime(), originalSection.getTime())
    627                                || !ToolBox.equals(section.getRooms(), originalSection.getRooms()))
    628                            iNrChanges++;
    629                    }
    630                    if (!enrollment.getCourse().equals(request.getInitialAssignment().getCourse()))
    631                        iNrChanges += 100 * (1 + enrollment.getTruePriority());
    632                    if (!enrollment.getConfig().equals(request.getInitialAssignment().getConfig()))
    633                        iNrChanges += 10;
    634                }
    635            }
    636            if (iSelectedRequest != null && iSelectedSection != null) {
    637                Enrollment enrollment = iAssignment.getValue(iSelectedRequest);
    638                if (enrollment.getAssignments() != null && !enrollment.getAssignments().isEmpty()) {
    639                    for (Iterator<Section> i = enrollment.getSections().iterator(); i.hasNext();) {
    640                        Section section = i.next();
    641                        if (section.getSubpart().getId() == iSelectedSection.getSubpart().getId()) {
    642                            iSelectedEnrollment = section;
    643                            break;
    644                        }
    645                        if (section.getSubpart().getConfig().getId() != iSelectedSection.getSubpart().getConfig()
    646                                .getId()
    647                                && section.getSubpart().getInstructionalType()
    648                                        .equals(iSelectedSection.getSubpart().getInstructionalType())) {
    649                            iSelectedEnrollment = section;
    650                            break;
    651                        }
    652                    }
    653                }
    654            }
    655            if (iSelectedEnrollment != null)
    656                iSelectedEnrollmentChangeTime = !ToolBox.equals(iSelectedEnrollment.getTime(),
    657                        iSelectedSection.getTime());
    658            if (iSelectedRequest != null) {
    659                Enrollment enrollment = iAssignment.getValue(iSelectedRequest);
    660                if (enrollment.isCourseRequest() && enrollment.getAssignments() != null
    661                        && !enrollment.getAssignments().isEmpty()) {
    662                    iSelectedSections.addAll(enrollment.getSections());
    663                    iSelectedChoice = ((CourseRequest)iSelectedRequest).getCourses().indexOf(enrollment.getCourse());
    664                }
    665            }
    666        }
    667
    668        /** initialization */
    669        public void init() {
    670            iEnrollments = new Enrollment[iStudent.getRequests().size()];
    671            for (int i = 0; i < iStudent.getRequests().size(); i++) {
    672                Request r = iStudent.getRequests().get(i);
    673                iEnrollments[i] = iAssignment.getValue(r);
    674                if (iEnrollments[i] == null) {
    675                    Config c = null;
    676                    if (r instanceof CourseRequest)
    677                        c = ((CourseRequest) r).getCourses().get(0).getOffering().getConfigs().get(0);
    678                    iEnrollments[i] = new Enrollment(r, 0, c, null, iAssignment);
    679                }
    680            }
    681        }
    682
    683        /**
    684         * Current assignment for the student
    685         * @return schedule
    686         */
    687        public Enrollment[] getEnrollments() {
    688            return iEnrollments;
    689        }
    690
    691        /**
    692         * Current value
    693         * @return assignment value
    694         */
    695        public double getValue() {
    696            return iValue;
    697        }
    698
    699        /**
    700         * Number of unassigned requests
    701         * @return number of unassigned requests
    702         */
    703        public int getNrUnassigned() {
    704            return iNrUnassigned;
    705        }
    706
    707        /**
    708         * Average unassigned priority
    709         * @return average priority of unassinged requests
    710         */
    711        public double getAverageUnassignedPriority() {
    712            return ((double) iUnassignedPriority) / iNrUnassigned;
    713        }
    714
    715        /**
    716         * Number of changes in this schedule (comparing to the original one)
    717         * @return number of changes
    718         */
    719        public int getNrChanges() {
    720            return iNrChanges;
    721        }
    722
    723        /**
    724         * Is the same section selected (as in the current assignment)
    725         * @return true the same section is selected
    726         */
    727        public boolean sameSelectedSection() {
    728            if (iSelectedRequest != null && iSelectedEnrollment != null) {
    729                Enrollment enrollment = iAssignment.getValue(iSelectedRequest);
    730                if (enrollment != null && enrollment.getAssignments().contains(iSelectedEnrollment))
    731                    return true;
    732                if (iSelectedEnrollmentChangeTime && iSelectedSection.getSubpart().getSections().size() > iMaxSuggestions) {
    733                    Section selectedEnrollment = null;
    734                    for (Iterator<Section> i = enrollment.getSections().iterator(); i.hasNext();) {
    735                        Section section = i.next();
    736                        if (section.getSubpart().getId() == iSelectedSection.getSubpart().getId()) {
    737                            selectedEnrollment = section;
    738                            break;
    739                        }
    740                        if (section.getSubpart().getConfig().getId() != iSelectedSection.getSubpart().getConfig().getId() &&
    741                                section.getSubpart().getInstructionalType().equals(iSelectedSection.getSubpart().getInstructionalType())) {
    742                            selectedEnrollment = section;
    743                            break;
    744                        }
    745                    }
    746                    if (selectedEnrollment != null && ToolBox.equals(selectedEnrollment.getTime(), iSelectedEnrollment.getTime()))
    747                        return true;
    748                }
    749            }
    750            return false;
    751        }
    752
    753        @Override
    754        public int compareTo(Suggestion suggestion) {
    755            int cmp = Double.compare(getNrUnassigned(), suggestion.getNrUnassigned());
    756            if (cmp != 0)
    757                return cmp;
    758            if (getNrUnassigned() > 0) {
    759                cmp = Double.compare(suggestion.getAverageUnassignedPriority(), getAverageUnassignedPriority());
    760                if (cmp != 0)
    761                    return cmp;
    762            }
    763
    764            if (iSelectedRequest != null && iSelectedRequest instanceof CourseRequest) {
    765                int s1 = 0;
    766                for (Section s: iSelectedSections)
    767                    if (((CourseRequest)iSelectedRequest).isSelected(s)) s1++;
    768                int s2 = 0;
    769                for (Section s: suggestion.iSelectedSections)
    770                    if (((CourseRequest)iSelectedRequest).isSelected(s)) s2++;
    771                if (s1 != s2) {
    772                    return (s1 > s2 ? -1 : 1);
    773                }
    774            }
    775
    776            cmp = Double.compare(getNrChanges(), suggestion.getNrChanges());
    777            if (cmp != 0)
    778                return cmp;
    779
    780            cmp = Double.compare(iSelectedChoice, suggestion.iSelectedChoice);
    781            if (cmp != 0)
    782                return cmp;
    783
    784            Iterator<Section> i1 = iSelectedSections.iterator();
    785            Iterator<Section> i2 = suggestion.iSelectedSections.iterator();
    786            SectionAssignmentComparator c = new SectionAssignmentComparator();
    787            while (i1.hasNext() && i2.hasNext()) {
    788                cmp = c.compare(i1.next(), i2.next());
    789                if (cmp != 0)
    790                    return cmp;
    791            }
    792
    793            cmp = compare(iAssignment, this, suggestion);
    794            if (cmp != 0)
    795                return cmp;
    796
    797            return Double.compare(iId, suggestion.iId);
    798        }
    799    }
    800
    801    /**
    802     * Enrollment comparator (used to sort enrollments in a domain).
    803     * Selected sections go first.
    804     */
    805    public class EnrollmentSectionComparator implements Comparator<Section> {
    806        /**
    807         * Is section s1 parent of section s2 (or a parent of a parent...)
    808         * @param s1 a section
    809         * @param s2 a section
    810         * @return if there is a parent-child relation between the two sections
    811         */
    812        public boolean isParent(Section s1, Section s2) {
    813            Section p1 = s1.getParent();
    814            if (p1 == null)
    815                return false;
    816            if (p1.equals(s2))
    817                return true;
    818            return isParent(p1, s2);
    819        }
    820
    821        @Override
    822        public int compare(Section a, Section b) {
    823            if (iSelectedSection != null && iSelectedSection.getSubpart().getId() == a.getSubpart().getId())
    824                return -1;
    825            if (iSelectedSection != null && iSelectedSection.getSubpart().getId() == b.getSubpart().getId())
    826                return 1;
    827
    828            if (isParent(a, b))
    829                return 1;
    830            if (isParent(b, a))
    831                return -1;
    832
    833            int cmp = a.getSubpart().getInstructionalType().compareToIgnoreCase(b.getSubpart().getInstructionalType());
    834            if (cmp != 0)
    835                return cmp;
    836
    837            return Double.compare(a.getId(), b.getId());
    838        }
    839    }
    840
    841    /**
    842     * Section comparator. Order section by time first, then by room.
    843     */
    844    public class SectionAssignmentComparator implements Comparator<Section> {
    845        @Override
    846        public int compare(Section a, Section b) {
    847            TimeLocation t1 = (a == null ? null : a.getTime());
    848            TimeLocation t2 = (b == null ? null : b.getTime());
    849            if (t1 != null && t2 != null) {
    850                for (int i = 0; i < Constants.DAY_CODES.length; i++) {
    851                    if ((t1.getDayCode() & Constants.DAY_CODES[i]) != 0) {
    852                        if ((t2.getDayCode() & Constants.DAY_CODES[i]) == 0)
    853                            return -1;
    854                    } else if ((t2.getDayCode() & Constants.DAY_CODES[i]) != 0) {
    855                        return 1;
    856                    }
    857                }
    858                int cmp = Double.compare(t1.getStartSlot(), t2.getStartSlot());
    859                if (cmp != 0)
    860                    return cmp;
    861            }
    862            String r1 = (a == null || a.getRooms() == null ? null : a.getRooms().toString());
    863            String r2 = (b == null || b.getRooms() == null ? null : b.getRooms().toString());
    864            if (r1 != null && r2 != null) {
    865                int cmp = r1.compareToIgnoreCase(r2);
    866                if (cmp != 0)
    867                    return cmp;
    868            }
    869
    870            return 0;
    871        }
    872    }
    873
    874    /**
    875     * Number of possible enrollments of the selected request
    876     * @return number of possible enrollment of the selected request (meeting the given filter etc.)
    877     */
    878    public int getNrMatched() {
    879        return iMatched;
    880    }
    881
    882    /**
    883     * Suggestion filter.
    884     */
    885    public static interface SuggestionFilter {
    886        /**
    887         * Match the given section
    888         * @param course given course
    889         * @param section given section
    890         * @return true if matching the filter (can be used)
    891         */
    892        public boolean match(Course course, Section section);
    893    }
    894
    895}