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