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